Движение объекта по прямой траектории

[8Observer8]

Сообщение от OmegaBerkut

или знакомый волновой алгоритм

Посмотрите ещё в сторону алгоритма A* (А стар) Ваша задача напоминает компьютерную игру, а алгоритм А* чаще всех используется для поиска пути в компьютерных играх. Наверное, не случайно. Возможно алгортм А* более эффективный раз его применяют чаще всех. Особенно, если объектов, которым нужно расчитать путь, несколько десятков или сотен.

[OmegaBerkut]

Сообщение от 8Observer8

Посмотрите ещё в сторону алгоритма A*

Посмотрел ... Из того, что я понял, я могу из точки {x0;y0} брать соседние, и смотреть в какой точке будет наименьшая разница координат с точкой {x;y}. И так до тех пор, пока не доберусь до пункта назначения. С такой реализацией можно обойтись без общей матрицы координат. Получается эдакий вариант жадного алгоритма.
И в принципе, для моей задачи такой метод тоже подходит. Он даже возможно будет проще уравнения прямой.

Но я немного отойду от темы, и пройдусь по некоторым моментам ...
1. Подобная реализация пришла мне в голову исходя из анимации на странице статьи в википедии.
2. Я так и не понял, как оценивать расстояние с учётом препятствий (в мою задачу это не входит), я не зря упомянул жадный алгоритм.

[OmegaBerkut]

Сообщение от Black Fregat

предварительное вычисление приращений может увести довольно далеко

Действительно ...

Сообщение от kvitaliy

рассчитываются приращения к координатам

Сообщение от kvitaliy

Пока X1 и Y1 не равны X и Y выполнять в таймере:
X1 = Xo + Xd:
Y1 = Yo + Yd:

С каким нибудь float/double при целочисленных координатах картинка может уйти налево, ну или направо, как повезёт. Я только вот дошёл до написания кода маршрута картинки, и сейчас походу буду заниматься вот этим:

Сообщение от OmegaBerkut

я могу из точки {x0;y0} брать соседние, и смотреть в какой точке будет наименьшая разница координат с точкой {x;y}

[OmegaBerkut]

Чёто я сейчас прозрел ... У меня из этого получился волновой алгоритм без учёта препятствий. Картинка выравнивается по оси Y, двигаясь по кратчайшему пути к оси X по диагонали (45 градусов), а оставшийся маршрут держит прямой путь по оси X.
Вот код:

private Point NextPoint()
{
	int i=0,pCount=8;
	Point[] beside=new Point[pCount];
	beside[0]=new Point(location.X-1,location.Y-1);
	beside[1]=new Point(location.X-1,location.Y);
	beside[2]=new Point(location.X-1,location.Y+1);
	beside[3]=new Point(location.X,location.Y-1);
	beside[4]=new Point(location.X,location.Y+1);
	beside[5]=new Point(location.X+1,location.Y-1);
	beside[6]=new Point(location.X+1,location.Y);
	beside[7]=new Point(location.X+1,location.Y+1);
	double difference,min=Double.MaxValue;
	Point result=new Point();
	for (;i<pCount;i++)
	{
		difference=Math.Sqrt(
			Math.Pow(Math.Abs(beside[i].X-destination.X),2)+
			Math.Pow(Math.Abs(beside[i].Y-destination.Y),2));
		if (difference<min)
		{
			result.X=beside[i].X;
			result.Y=beside[i].Y;
			min=difference;
		} else {}
	}
	return result;
}

location - текущая позиция перед вызовом функции.
После вызова этой функции результат выбрасывается в location и в позицию контрола.
Все данные варятся в глобалке класса.
Что тут нужно поправить ?

[kvitaliy]

Сообщение от OmegaBerkut

С каким нибудь float/double при целочисленных координатах картинка может уйти налево, ну или направо, как повезёт.

Ни куда не уходит. В коде используется double.
Видео в архиве

[OmegaBerkut]

Сообщение от kvitaliy

Ни куда не уходит. В коде используется double.

Хорошо ... А если я вдруг захочу, что бы моя переменная destination стала вдруг меняться ?
Перед каждым приращением пересчитывать приращение норм будет ?

[kvitaliy]

Сообщение от OmegaBerkut

переменная destination стала вдруг меняться

На видео видно, как я меняю конечную точку (кликом мышки по экрану) и объект сразу же меняет направление движения к новой цели по кратчайшему пути.
Естественно, после каждой смены цели движения новый пересчет.

[kvitaliy]

А вообще, если надо искать кратчайший путь, то есть специальные алгоритмы.
Вот волновой, как раз для C# есть код

[OmegaBerkut]

Но всё же, я хочу разобраться, почему эта функция в итоге даёт не прямую, а сначала выравнивает по ближайшей оси ...

private Point NextPoint()
{
	int i=0,pCount=8;
	Point[] beside=new Point[pCount];
	beside[0]=new Point(location.X-1,location.Y-1);
	beside[1]=new Point(location.X-1,location.Y);
	beside[2]=new Point(location.X-1,location.Y+1);
	beside[3]=new Point(location.X,location.Y-1);
	beside[4]=new Point(location.X,location.Y+1);
	beside[5]=new Point(location.X+1,location.Y-1);
	beside[6]=new Point(location.X+1,location.Y);
	beside[7]=new Point(location.X+1,location.Y+1);
	double sideA,sideB,difference,min=Double.MaxValue;
	Point result=new Point();
	for (;i<pCount;i++)
	{
		sideA=Math.Abs(beside[i].X-destination.X);
		sideB=Math.Abs(beside[i].Y-destination.Y);
		difference=Math.Sqrt(sideA*sideA+sideB*sideB);
		if (difference<min)
		{
			result.X=beside[i].X;
			result.Y=beside[i].Y;
			min=difference;
		} else {}
	}
	return result;
}

Ведь по сути, я для каждого соседа смотрю, кто ближе всего к цели, причём по длинам гипотенуз (на каждом шаге новый треугольник).
Передавая привет Валерию:

Сообщение от waleri

вам надо двигаться по гипотенузе

А вообще, я вижу в этом движение по гипотенузе, упрощённую реализацию A* (наименьшая стоимость, оценивается расстоянием), а так же частный случай волнового алгоритма (там тоже соседей опрашивают).
Вот мне интересно: почему это не работает как предполагается ?

Оффтопп: программист предполагает, а компьютер располагает.

[evg_m]

Но всё же, я хочу разобраться, почему эта функция в итоге даёт не прямую, а сначала выравнивает по ближайшей оси ...

потому что вы сразу же забываете об исходной точке(откуда НАЧАТО движение). Всегда используете "текущее" положение.
а так все верно. САМАЯ ближайшая (первая) точка ВСЕГДА будет лежать на ближайшей оси (кроме случая РАВНОудаленных осей, т.е. диагонали )
и только следующая итерация(накопление НЕЦЕЛОГО <0.5 ) смещения может привести к НЕНУЛЕВОМУ смещению по "дальней" оси.
позицию надо рассчитывать ВСЕГДА от начальной точки (точки смены направления движения).
00.PNG
вторая точка окажется лучшей для движения по прямой соединяющей текущую(ее САМУ) и конечную, но ... это совсем ДРУГАЯ прямая.
и только когда прямая соединяющая ТЕКУЩУЮ и конечную точки "доcтигнет" диагонали начнется движение СТРОГО по ней.