Поиск путей (A*, волновой алгоритм)

← →
flaxe © (2006-08-03 22:33) [0]

Проблема собственно такая: имеется лабиринт - [img]http://smartphones.net.ru/map.jpg[/img]

Карта закладывается двухмерным массивом map[x][y]
допустим если есть стенка сверху, а других нету, то map[x][y]:="up1down0left0righ0";
Нужно найти кратчайший путь от одной точки лабиринта, до другой... нашел много готовых примеров поиска кратчайших путей, но вот в чем проблема: в моем лабиринте клетка может быть закрыта полностью для прохода, а может и не полностью, т.е. если допустим из 1*1 нельзя пройти в 1*2, то это не значит что в 1*2 нельзя попать вообще(т.е. можно пройти допустим 1*1 -> 2*1 -> 2*2 ->1*2). Каким образом в данном случае можно произвести поиск пути?

← →
flaxe © (2006-08-03 22:34) [1]

http://smartphones.net.ru/map.jpg

← →
TUser © (2006-08-03 22:39) [2]

Ну построй ориентированный граф, вершины - это клетки, ребро - это если можно пройти. Дальше воспользуйся готовыми алгоритмами, типа Дейкстры.

← →
flaxe © (2006-08-03 22:48) [3]

хм.. так так так.. видно е не совсем верно понимал что значит "ребро", ориентированный граф... что он из себя представляет?

← →
Cardinal © (2006-08-03 23:45) [4]

проверенный способ идти вдоль одной стенки :)

← →
o_serg (2006-08-03 23:55) [5]

flaxe, это если в одну сторону можно пройти, а в другую нет, вот он и ориентированный

> проверенный способ идти вдоль одной стенки :)

Это ты с поиском выхода перепутал.

> flaxe © (03.08.06 22:33)

Ты не те вещи клетками считаешь.
Если у тебя стены нулевой толщины, то тебя интересует только доступность непосредственых соседей каждой клетки.
Если стены ненулевой толщины, то лабиринт надо бить на другие клетки, более мелкие, такие, чтоб каждая клетка была либо полностью занята стеной, либо была полностью свободна. Т.е. приводить к первому случаю.

Поиск путей (A*, волновой алгоритм) Найти похожие ветки