Разработка бота прохождения лабиринта.

[irvin12345]

Дано:
автогенерируемый лабиринт. (пример во вложении) У него 1 вход( всегда в левой части лабиринта) и 1 выход из 2-6 возможных. У каждого выхода есть свой номер (нумеруются по часовой стрелке от входа).

Нужно: написать скрипт, который возьмет картинку и скажет номер выхода.

Раньше подобным не занимался, поэтому не знаю "адекватных" аглоритмов.
Пока есть только 1 идея:
преобразовать картинку в массив соответствующего размера,
закрашивать рекурсивно от входа весь белый в другой цвет попиксельно(поячеечно). Где выйдет за пределы - там выход.

Насколько она адекватна по ресурсоемкости? Есть ли более простые варианты?

 

[Fever]

http://autoit-script.ru/index.php/topic,4375.msg31566.html#msg31566

это должно оказаться полезным в Ваших поисках.

 

[irvin12345]

Решено.
Описание алгоритма, если кому понадобится:
1. на вход функции передается двумерный массив, в котором 1=стена,0=дорога. По желанию можно добавить 2=старт, 3=финиш и их обработку, для моей задачи они были фиксированы, потому обошелся без них.
2. Использовался "поиск в глубину" + переделка рекурсии на FILO стек (в данном случае при больших картах можно уйти далеко в степь, поэтому для определения именно "пути" придется переделать на поиск в ширину + FIFO стек)
2а. Каждая проходимая клетка рядом с текущей кладется в стек
2б. Для каждой ячейки проверяется условие выхода и ячейка помечается пройденной (в данном коде стеной, тк нет смысла хранить ее состояние.)

Func _SolveLabirint($Matrix)
   $W = 50;размерность лабиринта. можно вынести в глобальные, если не меняется
   $H = 50
   
   $iSPos=1;указатель вершины стека. 
   Dim $Stack[$W*$H][2];стек с перемещениями
   $Stack[0][0]=1;стартовая позиция
   $Stack[0][1]=1;стартовая позиция
   While $iSPos>0; пока не закончим стек
	  $iSPos -=1
	  $iX = $Stack[$iSPos][0]
	  $iY = $Stack[$iSPos][1]
	  $Matrix[$iX][$iY]=1
	  
	  If ... Then       ;условия выхода
	  	Return "1"
	  ElseIf ... Then
		Return "2"
	  EndIf
	  
	  For $iDirection = 0 to 3 ; перебор соседних клеток
		 $iNewX = $iX
		 $iNewY = $iY
		 Switch $iDirection
		 Case 0
			$iNewY += 1
		 Case 1
			$iNewY -= 1
		 Case 2
			$iNewX += 1
		 Case 3
			$iNewX -= 1
		 EndSwitch
		 
		 If $Matrix[$iNewX][$iNewY]=0 Then
			$Stack[$iSPos][0] = $iNewX
			$Stack[$iSPos][1] = $iNewY
			$iSPos += 1
		 EndIf
	  Next
   WEnd
   Return 0; выход не найден
EndFunc