Алгоpитмы поиска пyти

From

Roman Ilyin ()

To

Dmitriy Gerasimenko

Date

2002-07-25T12:18:27Z

Area

RU.ALGORITHMS

From: "Roman Ilyin" <grisper@voronezh.net>

Area: fido7.ru.algorithms.
Доброе время суток, Dmitriy!
Вы писали в эхоконференции fido7.ru.algorithms --> Peter Pike's [25 июля
2002]:

 DG> да собственно хочется исходники чужие по этой теме поглядеть,
 DG> пощупать...
Мы делали для перемещающейся цели.
(поиск монстром игрока при обходе лабиринта)

Правило правой/левой руки тут не поможет.
У нас ещё монстр видел только перед собой (угол обзора 90 градусов).
~полмега в архиве. Игра типа сокобана с генерацией уровней
(только расстановка стен, дверей и монстры, а также ключей и аптечек),
в самом "движке" было предусмотренно куда больше...

Вопросы задавай. Конкретные.
Для цели с известными координатами можно использовать векторный
алгоритм деления пополам. Находит не оптимальный путь, но быстрее.
Вообще там много есть способов.

 DG> а вообще говоря, не зная координаты цели (или направление),
 DG> в худшем случае (цель в самом дальнем углу матрицы)
 DG> цель найдётся в самый последний момент...
Не обязательно.
При волновом алгоритме кол-во итераций будет О(n*n)
_от длины кратчайшего пути_. Для векторного (рассчитан на обход
крупных препятствий) чуть меньше.

-==================================================-
With best regards, Roman Ilyin.  E-mail: grisper@voronezh.net


--- ifmail v.2.15dev5
 * Origin: Информсвязь-Черноземье (2:5020/400)