Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

поиск пути [Delphi]

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

XProger (2005-07-29 15:15:00) [1]
А зачем GLScene в отдельный поток выносить? Выноси расчёты!

ПЛОВ (2005-07-29 10:21:00) [2]

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

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

ViK (2005-07-28 19:10:00) [3]
Можно попробовать в самом начале разделить весь лабиринт на несколько путей, создать список в котором будет указываться какой путь с каким соединяются, а потом уже во время игры проверять принадлежность машинок к путям (это будут конечные пути), искать промежуточные пути, т.о. ты получишь маршрут из небольшого кол-ва путей и для каждого надо будет всего лишь определить направление движения.
Только наверно потребуется специальный алгоритм формирования лабиринта.

ПЛОВ (2005-07-28 19:05:00) [4]

> java73 ©

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

java73 (2005-07-28 18:47:00) [5]
А что если вынести посик пути в отдельный процесс и время от времени обновлять? GLScene нормально работает с процессами? DelphiX глючит как маленькая девочка.

JaVa73 (2005-07-28 18:46:00) [6]
В том-то и дело, что линейное расстояние может быть маленкьим, а путь в лабиринте между этими точками - километровым, или наоборот, будут они на одной прямой но в разных углах, а алгоритм будет перебирать лишних 99%

ПЛОВ (2005-07-28 16:03:00) [7]
Ну тогда, как посоветовал XProger, измени интервалы, через которые будет происходить поиск нового пути.

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

java73 (2005-07-28 15:24:00) [8]
Я тоже так думал, но сложность лабиринта (запутанность что ли), не позволяет определить на маленьком отрезке (как и сам размер "маленькости" отрезка), достаточного для определения пути

ПЛОВ (2005-07-28 14:51:00) [9]
Не ищи весь путь сразу!!! Зачем, машинка то едет постоянно. Ищи только "маленький кусочек" пути, которого хватит, чтоб задать параметры движения для другой машинки. Ускорение, думаю, будет огромное.

XProger (2005-07-28 14:46:00) [10]
Прямые руки и тормозить не будет!
Пересчитывать путь можно через некоторый интервал времени.

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »