поиск пути

← →
java73 © (2005-07-28 13:46) [0]

Привет всем,
кто-нибудь помнит игру для спектрума carwars?
Там в гиганстком лабиринте две машинки друг за другом гоняются. Я начал делать подобное на дельфи и столкнулся с тем, что все алгоритмы поиска пути (самый быстрый А*) в таком лабиринте жутко тормозят. Но в той игре машинка гонялась беспрестанно за машинкой пользователя.
Так вот, кто-нибудь может поделиться материалами по поводу того, как организовывать постоянный поиск нового пути в лабиринтах такого типа (сложных, запутанных).

← →
XProger © (2005-07-28 14:46) [1]

Прямые руки и тормозить не будет!
Пересчитывать путь можно через некоторый интервал времени.

← →
ПЛОВ © (2005-07-28 14:51) [2]

Не ищи весь путь сразу!!! Зачем, машинка то едет постоянно. Ищи только "маленький кусочек" пути, которого хватит, чтоб задать параметры движения для другой машинки. Ускорение, думаю, будет огромное.

← →
java73 © (2005-07-28 15:24) [3]

Я тоже так думал, но сложность лабиринта (запутанность что ли), не позволяет определить на маленьком отрезке (как и сам размер "маленькости" отрезка), достаточного для определения пути

← →
ПЛОВ © (2005-07-28 16:03) [4]

Ну тогда, как посоветовал XProger, измени интервалы, через которые будет происходить поиск нового пути.

Можно попробовать как-то оптимизировать поиск пути. Попробуй динамически изменять "маленькость" отрезка в зависимости от расстояния (линейного) между машинками. Расстояние большое (и как следствие - долгий поиск) - "поисковый отрезок" укорачиваеться, расстояние маленькое - поиск быстрее, и до достижения цели.

← →
JaVa73 © (2005-07-28 18:46) [5]

В том-то и дело, что линейное расстояние может быть маленкьим, а путь в лабиринте между этими точками - километровым, или наоборот, будут они на одной прямой но в разных углах, а алгоритм будет перебирать лишних 99%

← →
java73 © (2005-07-28 18:47) [6]

А что если вынести посик пути в отдельный процесс и время от времени обновлять? GLScene нормально работает с процессами? DelphiX глючит как маленькая девочка.

← →
ПЛОВ © (2005-07-28 19:05) [7]

> java73 ©

Истина где-то рядом :) Используй сразу оба пути оптимизации примерно так:
Делаем период вычисления пути большим. Считаем какой-то кусок - цель не найдена - увеличиваем кусок, интервал тот же. Цель найдена, движимся туды и потихоньку ускоряемся... Поекспериментировать тут нужно :)

Можно попробовать в самом начале разделить весь лабиринт на несколько путей, создать список в котором будет указываться какой путь с каким соединяются, а потом уже во время игры проверять принадлежность машинок к путям (это будут конечные пути), искать промежуточные пути, т.о. ты получишь маршрут из небольшого кол-ва путей и для каждого надо будет всего лишь определить направление движения.
Только наверно потребуется специальный алгоритм формирования лабиринта.

> GLScene нормально работает с процессами? DelphiX глючит
> как маленькая девочка.

Если честно, я вообще не пользуюсь ни тем, ни другим! Это все глюкавый оцтой ИМХО. Чистый АПИ и OpenGL - вот что нужно!

А зачем GLScene в отдельный поток выносить? Выноси расчёты!

поиск пути Найти похожие ветки