Лабиринт, Нахождение выхода Опции

[Илюха]

Доброго времени суток! Вот такой вопросик:

У меня создан правильный лабиринт (из каждой точки в каждую можно попасть т.е. нет замкнутых комнат, и из каждой точки в каждую существует только 1 путь).

Вообщем это матрица:

Код

type
 TPoint = record
   visited:boolean;
   Bottomwall:boolean;
   RightWall:boolean;
 end;
TGrid = array [1..50,1..50] of Tpoint;

Как найти путь из верхнего левого угла в нижний правый?

Лабиринт выглядит примерно так http://www.sulaco.co.za/images/maze.gif

Сообщение отредактировано: Oleg_Z - 16.05.2004 12:44

[BlackShadow]

Самое простое решение - метод правой руки.
Это когда ты представляншь, что идёшь по лабиринту не отрывая правой руки от стенки. При обходе "правильного" лабиринта даёт 100%-ный результат. Проблема только в том, что найденный путь с большой вероятностью будет содержать прогулки туда и обратно. В таком случае их можно просто выкинуть из общего пути.

[Dark]

почитай пока здесь -
http://codenet.ru/progr/alg/ai/htm/gl4_3.php
правда... здесь на прологе =)

я потом скину из своево архива доков - где то были интересные проги...

[trminator]

По идее, можно просто построить граф, затем найти в нем кратчайший путь (методом Дейкстра). Так как лабиринт не очень большой, это вполне пройдет.

А вообще для таких лабиринтов существует своя схема поиска пути. Только я ее внятно не объясню сейчас =/

[BlackShadow]

Нп programme.ru вроде были ОЧЕНЬ неплохие статьи на эту тему...