|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Roman Ilyin 2:5020/400 25 Jul 2002 12:18:27
To : Dmitriy Gerasimenko
Subject : Алгоpитмы поиска пyти
--------------------------------------------------------------------------------
Area: fido7.ru.algorithms.
Доброе время суток, Dmitriy!
Вы писали в эхоконференции fido7.ru.algorithms --> Peter Pike's [25 июля
2002]:
DG> да собственно хочется исходники чужие по этой теме поглядеть,
DG> пощупать...
Мы делали для перемещающейся цели.
(поиск монстром игрока при обходе лабиринта)
Правило правой/левой руки тут не поможет.
У нас ещё монстр видел только перед собой (угол обзора 90 градусов).
~полмега в архиве. Игра типа сокобана с генерацией уровней
(только расстановка стен, дверей и монстры, а также ключей и аптечек),
в самом "движке" было предусмотренно куда больше...
Вопросы задавай. Конкретные.
Для цели с известными координатами можно использовать векторный
алгоритм деления пополам. Hаходит не оптимальный путь, но быстрее.
Вообще там много есть способов.
DG> а вообще говоря, не зная координаты цели (или направление),
DG> в худшем случае (цель в самом дальнем углу матрицы)
DG> цель найдётся в самый последний момент...
Hе обязательно.
При волновом алгоритме кол-во итераций будет О(n*n)
_от длины кратчайшего пути_. Для векторного (рассчитан на обход
крупных препятствий) чуть меньше.
-==================================================-
With best regards, Roman Ilyin. E-mail: grisper@voronezh.net
--- ifmail v.2.15dev5
* Origin: Информсвязь-Черноземье (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
