Главная страница
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.029 c
3-1149777720
Василий
2006-06-08 18:42
2006.09.17
Формирование расп. занят. в ВУЗе, способом эксп-та из БД в Excel


6-1146644798
Chaser
2006-05-03 12:26
2006.09.17
Зависание при "IdTCPClient.ReadInteger(true)"


2-1156579096
Std
2006-08-26 11:58
2006.09.17
html+форма


3-1152875840
drashka
2006-07-14 15:17
2006.09.17
Как лучше реализовать поиск?


15-1156408984
ZMRaven
2006-08-24 12:43
2006.09.17
а куда девать излишки энергии ?