A simple pathfinder (nothing fancy)

Monkey Forums/Monkey Code/A simple pathfinder (nothing fancy)

Supertino

(Posted 2014) [#1]

I finally got around to creating an all in one Class for 2D pathfinding, it's nothing fancy and it's not a slick as A* or indeed anything more advanced. This will always find the shortest route but it wont always be the nicest.

I don't know what the technique is called but basically it spirals out for the Start location until it finds the Goal location which does result in a lot of squares being checked that don't need to be, it should not have much of an impact on performance unless you're going with large arrays with dimensions in the several hundreds.

You can play a test app here http://moarlasers.com/path/MonkeyGame.html [HTML5] and grab the source from here https://drive.google.com/folderview?id=0B1jBbicq8v_dbUtHWlNfZFh2Qm8&usp=drive_web

It's requires you use an Array in the array:Int[a][b] format.

The Methods

Prepare:Void(arr:Int[][], unpassable_vals:Int[], start_x:Int, start_y:Int, finish_x:Int, finish_y:Int) ' Call before you search
Search:Bool() ' Start the search, return True or False if path can be found
GetString:String() ' Get the Path as single string of U,D,L,R
Get:String[] () ' Get the Path as an Array containing U,D,L,R

The Prepare method needs a little explaining, lets assume this is being used for PacMan;
- The first argumant is requesting you feed in an array, this will typical be your level containing the walls, floors all represended with a value, walls are '1' floors as '2' for example, the Class will take a take a copy of this for it's needs and wont change the original.

- The second argument is where you can feed in values that you want the Class to treat as unpassable, such as walls

- The 3rd\4th is the array x&y of the where you want to start your search from

- The 5th and 6th us the array x&y where you want to end the search

The idea is you call Prepare then Search and get your Path info by calling Get or GetString

The Class

Class PathingClass
	Private
	Const PASSABLE:Int = 0, UNPASSABLE:Int = -1
	Field unpassable:Int[]
	Field arrData:Int[][]
	Field arrWidth:Int
	Field arrHeight:Int
	Field start:Int[2]
	Field finish:Int[2]
	Field arrCheckList:Int[][]
	Field path:String[]
	
	'Summary: Reset values and arrays (is not normally required to be called at any time)
	Method Reset:Void()
		For Local x:Int = 0 Until arrWidth
			For Local y:Int = 0 Until arrHeight
				arrData[x][y] = PASSABLE
				arrCheckList[x][y] = 0
			Next y
		Next x
		path = path.Resize(0)
	End Method
	
	'Summary: Return true if the value is an Unpassable value
	Method IsUnPassable:Bool(value:Int)
		For Local i:Int = 0 Until unpassable.Length
			If value = unpassable[i] Then Return True
		Next
	End Method
	
	'Summary: Trace back and complie the path
	Method TracePath:Void()
		Local Score:Int = arrData[finish[0]][finish[1]]
		Local x:Int = finish[0]
		Local y:Int = finish[1]
		'Store the directions
		path = path.Resize(Score)
		'Start from finish and work back to Start using Score
		Repeat
			Score = Score - 1
			If Score = 0 Then Exit ' Found Start so exit here
			If y - 1 >= 0
				If arrData[x][y - 1] = Score Then path[Score - 1] = "D"; y = y - 1; Continue
			EndIf
			If x + 1 < arrWidth
				If arrData[x + 1][y] = Score Then path[Score - 1] = "L"; x = x + 1; Continue
			EndIf
			If y + 1 < arrHeight
				If arrData[x][y + 1] = Score Then path[Score - 1] = "U"; y = y + 1; Continue
			EndIf
			If x - 1 >= 0
				If arrData[x - 1][y] = Score Then path[Score - 1] = "R"; x = x - 1; Continue
			EndIf
		Forever
	End Method
	
		'Summary:
	Method CheckNeighbours:Void(x:Int, y:Int, value:Int)
		'above
		If y - 1 >= 0
			If arrData[x][y - 1] = PASSABLE
				arrData[x][y - 1] = value
			EndIf
		End If
		'right
		If x + 1 < arrWidth
			If arrData[x + 1][y] = PASSABLE
				arrData[x + 1][y] = value
			EndIf	
		End If
		'below
		If y + 1 < arrHeight
			If arrData[x][y + 1] = PASSABLE
				arrData[x][y + 1] = value
			EndIf
		End If
		'left
		If x - 1 >= 0
			If arrData[x - 1][y] = PASSABLE
				arrData[x - 1][y] = value
			EndIf
		End If
	End Method
	
	'Summary: Create a return a 2 Dim array [x][y]
	Function AllocateArrayInt:Int[][] (i:Int, j:Int)
	    Local arr:Int[][] = New Int[i][]
	    For Local ind = 0 Until i
	        arr[ind] = New Int[j]
	    Next
    	Return arr
	End Function
	
	Public
	
	'Summary: Return the path as a String [Array] U,D,R,L
	Method Get:String[] ()
		Return path
	End Method
	
	'Summary: Return the Path U,D,R,L as a single String
	Method GetString:String()
		Local t:String
		For Local a:Int = 0 Until path.Length - 1
			t = t + path[a]
		Next
		Return t
	End Method
	
	'Summary: The main method that makes it all go
	Method Search:Bool()
		Const NEEDS_CHECKING:Int = 1, BEEN_CHECKED:Int = 2
		Local Score:Int
		Local NothingToCheck:Bool
		Local FinishFound:Bool
		
		Repeat
			' Increase Score
			Score = Score + 1
			' Ready this
			NothingToCheck = True
			' Update what positions to check
			For Local x:Int = 0 Until arrWidth
				For Local y:Int = 0 Until arrHeight
				 	If arrData[x][y] = Score Then arrCheckList[x][y] = NEEDS_CHECKING; NothingToCheck = False
				Next y
			Next x
			' All searchable sqaures have been checked so exit here
			If NothingToCheck = True Then FinishFound = False; Exit
			' The Finish has been found so lets stop the search here
			If arrCheckList[finish[0]][finish[1]] = NEEDS_CHECKING Then FinishFound = True; Exit
			' Check neighbouring squares
			For Local x:Int = 0 Until arrWidth
				For Local y:Int = 0 Until arrHeight
				 	If arrCheckList[x][y] = NEEDS_CHECKING Then CheckNeighbours(x, y, Score + 1); arrCheckList[x][y] = BEEN_CHECKED
				Next y
			Next x
		Forever	
		' Results
		If FinishFound = False
			Reset()
			Return False
		Else
			TracePath()
			Return True
		End If
		
	End Method
	
	'Summary: Call before you Search, sets up the all the data the Path Class requires
	Method Prepare:Void(arr:Int[][], unpassable_vals:Int[], start_x:Int, start_y:Int, finish_x:Int, finish_y:Int)
		' Get list of unpassable values
		unpassable = unpassable_vals
		' Set start & finish locations
		start =[start_x, start_y]
		finish =[finish_x, finish_y]
		' Config the array
		arrWidth = arr.Length
		arrHeight = arr[1].Length
		arrData = AllocateArrayInt(arrWidth, arrHeight)
		arrCheckList = AllocateArrayInt(arrWidth, arrHeight)
		' Copy array values and set as PASSABLE\UNPASSBLE
		For Local x:Int = 0 Until arrWidth
			For Local y:Int = 0 Until arrHeight
				arrData[x][y] = arr[x][y]
				If IsUnPassable(arrData[x][y]) Then arrData[x][y] = UNPASSABLE Else arrData[x][y] = PASSABLE
			Next y
		Next x
		' Set start position as score '1' (start)
		arrData[start[0]][start[1]] = 1
	End Method
		
End Class

Snader

(Posted 2014) [#2]

Great work!