поиск пути не по клеткам...

← →
Ландграф Павел © (2004-08-04 12:07) [0]

Дык вот, у меня в игре непроходимые участки выглядят как массив TRect, есть ли у кого совет, или ссылочка на подобный алгоритм поиска пути не по клеткам...

← →
Белый Крыс © (2004-08-04 12:35) [1]

Если статика, то можно перевести в клетки :), и искать по клеткам.
Вообще я считаю, что по клеткам легче и удобнее всего, а привести к клеткам можно ВСЕ.

← →
cyborg © (2004-08-04 13:01) [2]

> [1] Белый Крыс © (04.08.04 12:35)

Поддерживаю!

← →
Ландграф Павел © (2004-08-04 13:55) [3]

Белый Крыс>ага, в каждую клетку вносить TRect координаты, потом поиск пути будет относительно этих координат... не слижком уж тупо? для чего разводить массивы, если один одномерный с TRect уже есть...

← →
VolanD (2004-08-04 13:55) [4]

Замути маску карты (в виде картинки) и проверяй на столкновение.

← →
Белый Крыс © (2004-08-04 14:03) [5]

Ты не понял. Зачем TRect вносить в клетку.
1) С TRect массив после перевода в клетки уже не нужен.
2) Какая ситуация? ректы занесены еще при создании карты? Тогда еще проще, сразу переводишь в клетки и используешь в игре.
3) Клетки могут быть и маленьких размеров (8*8, 4*4 и т.п.)

1) Маску лично я не делал. Может и можно, но прийдется хранить маску именно в файле.
2D еще ладно, а вот 3D думаю точно по клеткам.

← →
Ландграф Павел © (2004-08-04 14:39) [6]

Я ж спросил про TRect, нихочу я никакие клетки... ни форум, а общество принуждения какое-то...

← →
Digitman © (2004-08-04 14:49) [7]

> Ландграф Павел © (04.08.04 14:39) [6]

http://www.codenet.ru/progr/alg/way.php
http://emanual.ru/download/716.html
http://andrey.nnov.ru/articles.php?a=10
http://www.firststeps.ru/theory/karta.html

← →
Белый Крыс © (2004-08-04 15:52) [8]

На самом деле TRect НИЧЕМ НЕ отличается от клеток в смысле алгоритма нахождения пути. Более того во второй ссылке вопрос "Как постоить кратчайший маршрут между двумя точками, если пространство задано в виде обычной растровой карты?" по сути - твой. А волновой алгоритм во всех четырех ссылках упоминается.
Я ж спросил про TRect, нихочу я никакие клетки...
Надо Паша, НАДО! :)

← →
Ландграф Павел © (2004-08-05 13:44) [9]

читаю, разбираюсь, пасибо Digitman, Белый Крыс=))

← →
Micah'GF © (2004-08-05 14:13) [10]

у меня есть прога "Path search demo" от Браина Стоута (Bryan Stout) - она в графическом виде демонстрирует работу нескольких алгоритмов поиска (больше 10), с ней идут описания трех из них. Еще есть несколько описаный отдельно. Где все это качал уже не скажу, а выслать могу если кому надо. Весит все это не больше 700кб.

← →
Megabyte-CeerCop © (2004-08-05 14:29) [11]

Micah`GF
Спрашиваешь ещё!
Это нужно всем!!! Только я первый в очереди!!!

← →
Белый Крыс © (2004-08-05 14:48) [12]

2 Micah"GF
Лучше ссылку выложи. Т.е. закачай на сайт какой-нибудь.

Micah"GF>кинь на freeart@kemtel.ru плиз... я пока пробую с алгоритмом A*, довольно-таки быстрый, волновой мне не к чему... у меня же не супер-лабиринты=)

можно скачать отсюда http://200mb.org/files/temp/pathfind.rar

блин, путь нашел, получил 2-у мерную матрицу (ячейка 16х16) с waypoint`ами... перенес эти точки в одномерный массив героя, как теперь эту скотину заставить идти по этим точкам... я думаю надо так: найти угол между моим положением и следующей точкой и шагать... я тут формулу нашел, но что-то он туда не идет...
Angle:=((Trunc(RadToDeg(ArcTan2(NextY*16-Y,NextX*16-X))+202.5) div 45)*45)-180;
X:=X+Speed*Cos(DegToRad(Angle));
Y:=Y+Speed*Sin(DegToRad(Angle));
Если пришли удалять эту точку из локального массива точек...
С математикой к меня туго со школы, так что сильно не опускайте, напишите у кого с ней нету проблем...
в школе была 3-ка все жисть... и то из жалости))

← →
Zer0_forgot_password (2004-08-06 17:33) [16]

можно сделать по тупому:

dx:=nextx*16-x; dy:=nexty*16-y; d:=sqrt(dx*dx+dy*dy);
if (d<=speed)
пришли, обрабатываем слелующую точку
else
begin
x:=x+dx/d*speed;
y:=y+dy/d*speed;
end;

определяем вектор направления движения, если до точки еще не дошли то нормализуем его (1-ная длинна) и умножаем на скорость.

если хочется чтобы перс гулял толко по углам кратным 45 градусам можно сделать следующее
dx:=sign(nextx*16-x); dy:=sign(nexty*16-y);

зы код не проверял но работать должен 99.8%

Zer0_forgot_password>да, спасибо, работает!

поиск пути не по клеткам... Найти похожие ветки