Проблемы с поиском пути (A*), Долго обрабатывает. Помогите пожалуйста..

[darkthor]

На днях я взял класс А* на AS и переделал под пхп. (готовый пхп скрипт найти не смог).
Скрипт взял отсюда: алгоритм поиска пути на AS
Там же все подробно разжевано.

Сначала все работало быстро и хорошо пока не начал добавлять преграды. Сделал сетку 10 на 10 и поставил посередине непроходимую стену чтобы протестить обходной путь. Теперь у меня скрипт выполняется 15 секунд, но путь находит. Посчитал количество проверенных клеток - выдал 5272.

Кому не сложно или кто уже делал что-то подобное посмотрите пожалуйста. Я уже даже не знаю как найти ошибку.

Мой класс: AStar.zip

 

[AmdY]

попробуй воспользоваться профайлингом, xdebug и (или) добавить вывод отладочной информации, чтобы знать что и где много раз отрабатывает, возможно где-то лишние циклы гоняются или логическая бомба. Но и php не очень хорош в таких задачах

 

[darkthor]

вот я это и делал ) все равно не могу найти логическую ошибку ) поэтому прошу помочь )

 

[jahson]

Опиши, как ты всё это счастье вызываешь.

 

[darkthor]

$closed = array(
	array('x'=>1, 'y'=>5),
	array('x'=>2, 'y'=>5),
	array('x'=>3, 'y'=>5),
	array('x'=>4, 'y'=>5),
	array('x'=>5, 'y'=>5),
	array('x'=>6, 'y'=>5),
	array('x'=>7, 'y'=>5),
	array('x'=>8, 'y'=>5),
);

$result = Service_AStar::findPath(array(10, 10), array(0, 0), array(7, 9), $closed);
var_dump($result);

echo '<br><br>';

print_r(Service_AStar::$path);

вот так я делаю

 

[tz-lom]

на поле 10 на 10 php справится,тем более что 5272 на порядок больше чем количество клеток (лол и вывод что алгоритм перенесён криво)

 

[jahson]

Там проблема где-то в области работы со списком посещённых нод. Сейчас поковыряю.

 

[darkthor]

Там проблема где-то в области работы со списком посещённых нод. Сейчас поковыряю.

да. потому что пока не упирается в преграду - он выполняется быстро.. а потом начинается жара.. спасибо за помощь

на поле 10 на 10 php справится,тем более что 5272 на порядок больше чем количество клеток (лол и вывод что алгоритм перенесён криво)

вот и не могу найти где неправильно перенес. поэтому суда и обратился. согласен с тем что 5272 это ненормально. я думаю когда этот скрипт будет нормально работать - будет многим людям полезен. лично я в инете на пхп готового решения не нашел, только описания алгоритма.

 

[jahson]

					if ((!self::isOpen($test) && !self::isClosed($test)) || $test['f'] <= $f) {

Убрать всё, что связано с ||.

 

[darkthor]

не понял. убрать это условие вообще? но тогда логика скрипта сразу теряется и он никогда не найдет путь.

 

[darkthor]

а понял.. убрать $test['f'] <= $f.
работает ))

только странно:
все оставил как есть, те же начало и конец, ту же непроходимую стенку.
он идет от 0х0 к 0х5 через 1х3. Это странно, так как цена перехода по диагонали больше чем по горизонтали. по идее он должен был сразу пойти направо до нода 0х5.

 

[darkthor]

 

[darkthor]

походу там вот так должно быть:

if ((!self::isOpen($test) && !self::isClosed($test)) || $f <= $node['f']) {
	self::$open[] = $test;
}

 

[darkthor]

и вот так вот закомментить:

if (($test['x'] == $node['x'] && $test['y'] == $node['y']) ||
	!$test['walkable'] /*||
	!self::$nodes[$node['x']][$test['y']]['walkable'] ||
	!self::$nodes[$test['x']][$node['y']]['walkable']*/)
{
	continue;
}