Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2006.09.17;
Скачать: CL | DM;

Вниз

Поиск путей (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, это если в одну сторону можно пройти, а в другую нет, вот он и ориентированный


 
DiamondShark ©   (2006-08-04 00:03) [6]


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

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


> flaxe ©   (03.08.06 22:33)  

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



Страницы: 1 вся ветка

Текущий архив: 2006.09.17;
Скачать: CL | DM;

Наверх




Память: 0.48 MB
Время: 0.058 c
15-1156998605
cyborg
2006-08-31 08:30
2006.09.17
Кто тут монитор хотел?


15-1155678234
Караед
2006-08-16 01:43
2006.09.17
Домофон!


2-1156832949
Pok
2006-08-29 10:29
2006.09.17
Определение пути к моему безоконному приложению


2-1156754056
XTD
2006-08-28 12:34
2006.09.17
Почему в процедуре FormCreate; не работает Form1.Visible:=False;?


2-1157020656
валет
2006-08-31 14:37
2006.09.17
ip адреса