Лабиринты

From

Roman Ilyin ()

To

Andrew Starsh

Date

2002-11-21T13:10:43Z

Area

RU.ALGORITHMS

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

Доброе время суток, Andrew!
Вы писали в эхоконференции fido7.ru.algorithms --> Roman Ilyin [21 ноября
2002 08:41]:

AS>>> Вообще-то для pеальных двумеpных лабиpинтов совет дают один -
AS>>> всегда повоpачивать _только_ влево. Или _только_ впpаво. Это
AS>>> всего-навсего только отсекает повтоpный заход в тупики.
RI>> Слева от тебя столб, справа ещё один столб. Всё это посреди комнаты с
RI>> 4 выходами по углам. Ты - в центре... ;)
RI>> Смена руки при возвращении в ту же точку не поможет.
RI>> Так что фигня это.
AS> Ну да, можно попасться на такой...
Бывает и хуже. =)
Ширина коридора 4 клетки, например.

RI>> Можно ставить "следы" (второй раз наступил на клетку - два "следа"),
RI>> и идти туда где меньше следов. Довольно медлено, но работает.
AS> Все-таки "заполнение" двумя взаимопpоникающими "газами" до пеpвого
AS> контакта куда pулезнее. И путь будет сpазу оптимальный.
Только если весь лабиринт сразу известен. Т.е. если ты знаешь координаты
выхода и ищешь к нему путь.
У нас было сложнее - надо было монстром найти двигающегося по
лабиринту игрока, при этом монстр "видел" только то, что трассировкой лучей
попадало в область видимости.

Неплохая статья на "Программирование магических игр" была по поиску пути.

Удачи!
Roman Ilyin.  E-mail: grisper@voronezh.net


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