Про вариант с рандомом, похоже вы просто не поняли.
Код:
dx:=0;if cx>x then dx:=1;if cx<x then dx:=-1;
dy:=0;if cy>y then dy:=1;if cy<y then dy:=-1;
Этот простейший метод дает некрасивую диагональ в начале пути.
Диагональ возникает когда одна из величин delta_X или delta_Y много больше другой. Если при этом сделать вероятность изменения меньшей величины менее 100%, то наша диагональ начнет вытягиваться, приближаясь к "правильной" прямой.