Поиск в глубину

[lammeR]

Всё привет!
Мне нужно реализовать поле(двумерный массив), в котором есть 4 объекта: 1)свободный путь(это 0) 2)стена(это 1) 3)охотник("S") 4)жертва("G"), то есть охотник должен перед тем как дойти до цели, узнать, где находится жертва, а потом к ней дойти, обходя стены.
Я поспрашивал в инете на форумах и мне подсказали, что для поиска пути в массиве используется "поиски в глубину " и тд, полазив в гугле я нашёл с++ исходник и сразу же переписал его в javascript. Вроде как поиск работает, но охотник не доходит к жертве пару шагов и как мне потом сделать движение по найденному пути , само движение я умею делать, я просто не могу понять как задать найденную траекторию в движении. Очень буду благодарен за вашу помощь.
Исходники с++ и javascript:

[Kolyaj]

мне подсказали, что для поиска пути в массиве используется "поиски в глубину "

Поиск не в массиве, а в лабиринте (в графе, если более формально), не важно, как вы его храните в памяти. А алгоритм называется волновой.

[lammeR]

Kolyaj,
угу, волновой, в исходнике с++ вроде как реализован волновой алгоритм, а переделанный мною не совсем. В чем загвоздка ?

[PeaceCoder]

Краткая суть метода волнового алгоритма:
1. Начинаем строить волну из точки назначения или исходящей.
2. создаем массив X x Y где X и Y - размерности (ширина и высота) вышего лабиринта в клетках передвижения.
3. В этом массиве в стартовой точке ставим 0.
4. Вокруг каждого текущего уровня ставим цифры выше уровнем + 1
5. Проверяем попали ли мы в конечную точку или нет. Да - шаг 6. Нет - шаг 4.
6. Найкратчайший путь - от максимальной цифры с поиском уменьшения уровня вокруг и так пока не достигнем 0.

[lammeR]

PeaceCoder,
Так вроде как, в моём исходнике так и сделано.

[PeaceCoder]

Именно и не так. Вы пытаетесь искать путь не найдя конечной точки и там же уже отмечаете +. + должен проставляться аж после нахождения конечной точки (цикл 6).
Кратко ваш алгоритм выдает следующее: есть проход на юг? ставим +. есть проход на юг? ставим + ....... нет прохода ? ставим х и пытаемся искать путь восток/запад/северю
Точ то вы реализовали называется "в обход"
Почитайте вот тут: http://pmg.org.ru/ai/stout.htm

[lammeR]

PeaceCoder, спасибо, понял, попытаюсь сделать, покажу потом, что получилось.

[lammeR]

Вот получилось, но из-за какой-то ошибки не работает:

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]

maze[i-1][j]==-2

При первой итерации у вас будет отрицательный индекс массива.

[lammeR]

exec, да, я понял это, но что же делать индекс обязан отниматься, иначе не выйдет распространение волны во все стороны, что просто сделать условие если i<0, то i=0 ???