Поиск в глубину
Вложений: 1
Всё привет!
Мне нужно реализовать поле(двумерный массив), в котором есть 4 объекта: 1)свободный путь(это 0) 2)стена(это 1) 3)охотник("S") 4)жертва("G"), то есть охотник должен перед тем как дойти до цели, узнать, где находится жертва, а потом к ней дойти, обходя стены. Я поспрашивал в инете на форумах и мне подсказали, что для поиска пути в массиве используется "поиски в глубину " и тд, полазив в гугле я нашёл с++ исходник и сразу же переписал его в javascript. Вроде как поиск работает, но охотник не доходит к жертве пару шагов и как мне потом сделать движение по найденному пути , само движение я умею делать, я просто не могу понять как задать найденную траекторию в движении. Очень буду благодарен за вашу помощь. Исходники с++ и javascript: |
Цитата:
|
Kolyaj,
угу, волновой, в исходнике с++ вроде как реализован волновой алгоритм, а переделанный мною не совсем. В чем загвоздка ? |
Краткая суть метода волнового алгоритма:
1. Начинаем строить волну из точки назначения или исходящей. 2. создаем массив X x Y где X и Y - размерности (ширина и высота) вышего лабиринта в клетках передвижения. 3. В этом массиве в стартовой точке ставим 0. 4. Вокруг каждого текущего уровня ставим цифры выше уровнем + 1 5. Проверяем попали ли мы в конечную точку или нет. Да - шаг 6. Нет - шаг 4. 6. Найкратчайший путь - от максимальной цифры с поиском уменьшения уровня вокруг и так пока не достигнем 0. |
PeaceCoder,
Так вроде как, в моём исходнике так и сделано. |
Именно и не так. Вы пытаетесь искать путь не найдя конечной точки и там же уже отмечаете +. + должен проставляться аж после нахождения конечной точки (цикл 6).
Кратко ваш алгоритм выдает следующее: есть проход на юг? ставим +. есть проход на юг? ставим + ....... нет прохода ? ставим х и пытаемся искать путь восток/запад/северю Точ то вы реализовали называется "в обход" Почитайте вот тут: http://pmg.org.ru/ai/stout.htm |
PeaceCoder, спасибо, понял, попытаюсь сделать, покажу потом, что получилось.
|
Вот получилось, но из-за какой-то ошибки не работает:
var size_row=10; var size_col=10; var Ni=0; //номер итерации var Nk=300; //max кол-во итераций var y=-1; //точка проходимости var n=-2; //точка непроходимости var s=0; //точка старта var e=254; //точка финиша var i,j; var maze=new Array( new Array(s,y,y,y,y,y,y,y,n,n), new Array(n,y,n,n,n,y,y,y,n,n), new Array(y,y,n,n,n,y,n,y,n,n), new Array(y,n,n,y,y,y,n,y,n,n), new Array(y,y,y,n,n,n,n,y,n,n), new Array(n,n,n,n,n,n,n,y,n,n), new Array(n,n,n,n,n,n,n,y,n,n), new Array(n,n,n,n,n,n,n,y,n,n), new Array(n,n,n,n,n,n,n,y,n,n), new Array(n,n,n,n,n,n,n,y,y,e) ); function waveSearch() { /*волновой алгоритм*/ while (Ni < Nk) { for (i=0; i < size_row; i++) { for (j=0; j < size_col; j++) /*запуск волны*/ if (maze[i][j]==Ni) { if (maze[i][j+1]==-1)maze[i][j+1]=Ni+1; if (maze[i][j-1]==-1)maze[i][j-1]=Ni+1; if (maze[i+1][j]==-1)maze[i+1][j]=Ni+1; if (maze[i-1][j]==-1)maze[i-1][j]=Ni+1; if ((maze[i+1][j]==-2) || (maze[i-1][j]==-2) || (maze[i][j+1]==-2) || (maze[i][j-1]==-2)) { // return 0; break; } } } Ni++; } //вывод массива на экран for(var i=0;i<size_row;i++) { for(var j=0;j<size_col;j++) { document.write("<span style='width:20px; float:left;'>"+ maze[i][j] +" </span>"); } document.write("<br/>"); } } waveSearch(); |
Цитата:
|
exec, да, я понял это, но что же делать индекс обязан отниматься, иначе не выйдет распространение волны во все стороны, что просто сделать условие если i<0, то i=0 ???
|
Часовой пояс GMT +3, время: 13:09. |