Как найти точку в лабиринте, самую отдалённую от данной?

[Parez]

Недавно создавал тему по генерации лабиринта. С этим вроде разобрался. Теперь волнует вопрос нахождения самой отдалённой точки от данной. Пусть данная точка будет стартом, а самая отдалённая от неё будет финишем. Вопрос как найти эту самую удалённую точку?
В лабиринте есть только один главный проход, все остальные являются тупиковыми. Зацикливаний в лабиринте нет. Лабиринт генерируется алгоритмом depth-first search.

[Jewelz]

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

[Rzer]

Волной от данной точки по проходимым. Все клетки, которые накроет последняя волна находятся на самом большом удалении.

[Parez]

Jewelz, в том то и дело, что лабиринт замкнутый и не имеет ни входа, ни выхода. Это как прямоугольник, изрытый проходами. Причём, как я уже сказал, существует только один главный проход, остальные ветвятся от него и являются тупиковыми.
Вот иллюстрация того, как у меня генерируется лабиринт: http://en.wikipedia.org/wiki/File:MAZE_30x20_DFS.ogv


Rzer, можно поподробней? Что за волна? Может где-то про это можно почитать?

[-De-]

Вода, заливаемая в начало лабиринта равномерно растекается - такая идея.
http://ru.wikipedia.org/wiki/%D0%92%...B8%D1%82%D0%BC

[Parez]

Попробовал организовать волновой алгоритм, но получилось что-то странное. В большинстве случаях "самая дальняя" точка находится в одной-двух клетках от данной.
Вот код:

function waveSearch(xs:int,ys:int):void
{
	trace(xs+" "+ys);
	passed++;
	waveObjMatrix[ys][xs].passed = true;
	if(passed < total-1)
	{
		if(ys+1 < waveObjMatrix.length)
		{
			if(!waveObjMatrix[ys+1][xs].passed && !waveObjMatrix[ys+1][xs].wall)
			{
				waveSearch(xs, ys+1);
			}
		}
		if(ys-1 >= 0)
		{
			if(!waveObjMatrix[ys-1][xs].passed && !waveObjMatrix[ys-1][xs].wall)
			{
				waveSearch(xs, ys-1);
			}
		}
		if(xs+1 < waveObjMatrix[0].length)
		{
			if(!waveObjMatrix[ys][xs+1].passed && !waveObjMatrix[ys][xs+1].wall)
			{
				waveSearch(xs+1, ys);
			}
		}
		if(xs-1 >= 0)
		{
			if(!waveObjMatrix[ys][xs-1].passed && !waveObjMatrix[ys][xs-1].wall)
			{
				waveSearch(xs-1, ys);
			}
		}
	}
	else
	{
		trace("xs = "+xs+" , "+"ys = "+ys);
	}
}

Суть алгоритма: в начале xs и ys - координаты старта. Дальше рекурсивно точки "растекаются" по всем направлениям (если в клетке по данному направлению нет стены, и она ранее не была посещена). Соответственно, по моей задумке, когда алгоритм закончит работу (когда будут пройдены все пустые клетки), переменные xs и ys будут равны координатам самой удалённой клетки от стартовой...
Что здесь может быть неправильно?

[-De-]

Это не волновой алгоритм. У вас поиск в глубину, а не в ширину. Неравномерно вода течет.

[Parez]

Разве? По-моему, она как-раз течёт, равномерно заполняя собой все проходы... Я старался следовать алгоритму Ли: http://ru.wikipedia.org/wiki/%D0%90%...C_%D0%9B%D0%B8.
Не можете указать в чём ошибка, или поподробнее объяснить, что следует делать?

[-De-]

Точно. Это совершенно не волна. Сделать волну. Полно описаний в инете и алгоритма Ли (да, лучше его ковырять, волна более общий алгоритм) и волны. Но код выше на них не похож. Можно вместо трейса загонять в массив пройденные клетки и выводить их потом по одной за кадр - увидите, как у вас вода течёт. Даже не из источника, а к источнику скорее)

[ChuwY]

В приложении моя старая реализация.
Во многом плоха, но работает.

p.s. Оказалось, что не так уж и плоха. Обновил, стала еще побыстрее.