A* pathfinder (bmx)

Community Forums/Showcase/A* pathfinder (bmx)

Andres

(Posted 2008) [#1]

It's actually "Breadth-first pathfinder"

Here's an easy to use pathfinder, made it as portable as possible. Uses only 4 functions. Supports 2D and 3D maps (map's depth).
The pathmap is filled with flags like:
PATH_TOP, PATH_BOTTOM, PATH_LEFT, PATH_RIGHT, PATH_CEIL, PATH_FLOOR, PATH_ALL

As you can see it doesn't support just 1/0 maps, but also can handle walls (hope you understand what i mean :)

The path returned by FindPath() is a string (something like "11444422222222223331123") where 1 - north, 2 - south, 3 - west, 4 - east, 5 - up, 6 - down.

Win32 executable

Function list:

CreatePathmap:TPathmap(width:Long, height:Long, depth:Long = 1)
PathmapSlot(this:TPathmap, flags:Int, x:Long, y:Long, z:Long = 0) ' Used to fill pathmap with information
FindPath:String(this:TPathmap, x1:Long, y1:Long, z1:Long, x2:Long, y2:Long, z2:Long) ' finds the path in a pathmap from position x1, y1, z1 to x2, y2, z2
FreePathmap(this:TPathmap)

Example:

SuperStrict

Graphics(800, 600)
SeedRnd(MilliSecs())

Global map_width:Int = 80
Global map_height:Int = 60

Include "pathfind.bmx"

' Create level
Global map:Int[map_width, map_height]
For Local y:Int = 0 To map_height -1
	For Local x:Int = 0 To map_width - 1
		If Rand(0, 5) < 2 Then map[x, y] = PATH_ALL
	Next
Next

' Create pathmap
Global pathmap:TPathmap = CreatePathmap:TPathmap(map_width, map_height)
Global path:String = ""

' Copy level to pathmap
For Local y:Long = 0 To map_height -1
	For Local x:Long = 0 To map_width - 1
		PathmapSlot(pathmap, map[x, y], x, y)
	Next
Next

While Not KeyHit(KEY_ESCAPE)
	Cls()
	
	' Draw level
	For Local y:Int = 0 To map_height -1
		For Local x:Int = 0 To map_width - 1
			If CheckFlag(map[x, y], PATH_ALL)
				SetColor(255, 0, 0)
			Else
				SetColor(255, 255, 255)
			EndIf
			DrawRect(x * 10, y * 10, 10, 10)
		Next
	Next
	
	' 1 - north, 2 - south, 3 - west, 4 - east, 5 - up, 6 - down
	path = FindPath(pathmap, map_width / 2, map_height / 2, 0, MouseX() / 10.0, MouseY() / 10.0, 0)
	
	' Draw the PATH
	If Len(path) > 0
		SetColor(0, 0, 255)
		Local x:Long = map_width / 2, y:Long = map_height / 2
		For Local i:Int = 1 To Len(path)
			Select Mid(path, i, 1)
				Case "1"
					y :- 1
				Case "2"
					y :+ 1
				Case "3"
					x :- 1
				Case "4"
					x :+ 1
			End Select
			DrawOval(x * 10, y * 10, 10, 10)
		Next
	EndIf
	
	Flip()
Wend

FreePathmap(pathmap)

Engine ("pathfind.bmx"):

Const FLAG1:Int = $01
Const FLAG2:Int = $02
Const FLAG4:Int = $04
Const FLAG8:Int = $08
Const FLAG16:Int = $10
Const FLAG32:Int = $20
Const FLAG64:Int = $40
Const FLAG128:Int = $80

Function CheckFlag:Int(flags:Int, flag:Int)
	If flags & flag Then Return True Else Return False
End Function

Const PATH_TOP:Int = FLAG1
Const PATH_BOTTOM:Int = FLAG2
Const PATH_LEFT:Int = FLAG4
Const PATH_RIGHT:Int = FLAG8
Const PATH_CEIL:Int = FLAG16
Const PATH_FLOOR:Int = FLAG32
Const PATH_ALL:Int = FLAG64

' List used for path find
Global pathmap_path_list:TList = CreateList()

' Pathmap type
Type TPathmap
	Field width:Long, height:Long, depth:Long
	
	Field map:TBank
End Type

Type TPath
	Field x:Long, y:Long, z:Long
	Field path:String
End Type

' Create a new pathmap
Function CreatePathmap:TPathmap(width:Long, height:Long, depth:Long = 1)
	Local this:TPathmap = New TPathmap
		this.width = width
		this.height = height
		this.depth = depth
		
		this.map = CreateBank(this.width * this.height * this.depth)
		
	Return this
End Function

' Insert flags to pathmap slot
Function PathmapSlot(this:TPathmap, flags:Int, x:Long, y:Long, z:Long = 0)
	Local offset:Long = (z * this.width * this.height) + (y * this.width) + x
	PokeByte(this.map, offset, flags)
End Function

' Search for a path within pathmap; 1 - north, 2 - south, 3 - west, 4 - east, 5 - up, 6 - down
Function FindPath:String(this:TPathmap, x1:Long, y1:Long, z1:Long, x2:Long, y2:Long, z2:Long)
	Local offset:Long, offset_top:Long, offset_bottom:Long, offset_left:Long, offset_right:Long, offset_ceil:Long, offset_floor:Long
	
	Local temp_bank:TBank = CreateBank(BankSize(this.map))
	CopyBank(this.map, 0, temp_bank, 0, BankSize(this.map))
	
	ClearList(pathmap_path_list)
	Local that:TPath = New TPath
		that.x = x1
		that.y = y1
		that.z = z1
		that.path = ""
		ListAddFirst(pathmap_path_list, that)
		ListAddFirst(pathmap_path_list, that)
	
	For that:TPath = EachIn pathmap_path_list
		offset = (that.z * this.width * this.height) + (that.y * this.width) + that.x
		
		' TOP
		If that.y > 0
			offset_top = (that.z * this.width * this.height) + ((that.y - 1) * this.width) + that.x
			If Not CheckFlag(PeekByte(temp_bank, offset), PATH_TOP) And Not CheckFlag(PeekByte(temp_bank, offset_top), PATH_BOTTOM) And Not CheckFlag(PeekByte(temp_bank, offset_top), PATH_ALL)
				Local pth:TPath = New TPath
					pth.x = that.x
					pth.y = that.y - 1
					pth.z = that.z
					pth.path = that.path + "1"
					ListAddLast(pathmap_path_list, pth)
					PokeByte(temp_bank, offset_top, PATH_ALL)
			EndIf
		EndIf
		' LEFT
		If that.x > 0
			offset_left = (that.z * this.width * this.height) + (that.y * this.width) + that.x - 1
			If Not CheckFlag(PeekByte(temp_bank, offset), PATH_LEFT) And Not CheckFlag(PeekByte(temp_bank, offset_left), PATH_RIGHT) And Not CheckFlag(PeekByte(temp_bank, offset_left), PATH_ALL)
				Local pth:TPath = New TPath
					pth.x = that.x - 1
					pth.y = that.y
					pth.z = that.z
					pth.path = that.path + "3"
					ListAddLast(pathmap_path_list, pth)
					PokeByte(temp_bank, offset_left, PATH_ALL)
			EndIf
		EndIf
		' BOTTOM
		If that.y + 1 < this.height
			offset_bottom = (that.z * this.width * this.height) + ((that.y + 1) * this.width) + that.x
			If Not CheckFlag(PeekByte(temp_bank, offset), PATH_BOTTOM) And Not CheckFlag(PeekByte(temp_bank, offset_bottom), PATH_TOP) And Not CheckFlag(PeekByte(temp_bank, offset_bottom), PATH_ALL)
				Local pth:TPath = New TPath
					pth.x = that.x
					pth.y = that.y + 1
					pth.z = that.z
					pth.path = that.path + "2"
					ListAddLast(pathmap_path_list, pth)
					PokeByte(temp_bank, offset_bottom, PATH_ALL)
			EndIf
		EndIf
		' RIGHT
		If that.x + 1 < this.width
			offset_right = (that.z * this.width * this.height) + (that.y * this.width) + that.x + 1
			If Not CheckFlag(PeekByte(temp_bank, offset), PATH_RIGHT) And Not CheckFlag(PeekByte(temp_bank, offset_right), PATH_LEFT) And Not CheckFlag(PeekByte(temp_bank, offset_right), PATH_ALL)
				Local pth:TPath = New TPath
					pth.x = that.x + 1
					pth.y = that.y
					pth.z = that.z
					pth.path = that.path + "4"
					ListAddLast(pathmap_path_list, pth)
					PokeByte(temp_bank, offset_right, PATH_ALL)
			EndIf
		EndIf
		
		' If the pathmap has 3 dimensions
		If this.depth > 1
			If that.z > 0
				offset_ceil = ((that.z - 1) * this.width * this.height) + (that.y * this.width) + that.x
				If Not CheckFlag(PeekByte(temp_bank, offset), PATH_CEIL) And Not CheckFlag(PeekByte(temp_bank, offset_ceil), PATH_FLOOR) And Not CheckFlag(PeekByte(temp_bank, offset_ceil), PATH_ALL)
					Local pth:TPath = New TPath
						pth.x = that.x
						pth.y = that.y - 1
						pth.z = that.z
						pth.path = that.path + "5"
						ListAddLast(pathmap_path_list, pth)
						PokeByte(temp_bank, offset_ceil, PATH_ALL)
				EndIf
			EndIf
			If that.z + 1< this.depth
				offset_floor = ((that.z + 1) * this.width * this.height) + (that.y * this.width) + that.x
				If Not CheckFlag(PeekByte(temp_bank, offset), PATH_FLOOR) And Not CheckFlag(PeekByte(temp_bank, offset_floor), PATH_CEIL) And Not CheckFlag(PeekByte(temp_bank, offset_floor), PATH_ALL)
					Local pth:TPath = New TPath
						pth.x = that.x
						pth.y = that.y + 1
						pth.z = that.z
						pth.path = that.path + "6"
						ListAddLast(pathmap_path_list, pth)
						PokeByte(temp_bank, offset_floor, PATH_ALL)
				EndIf
			EndIf
		EndIf
		
		' CORRECT PATH FOUND
		If that.x = x2 And that.y = y2 And that.z = z2
			Local path:String = that.path
			ClearList(pathmap_path_list)
			temp_bank = Null
			Return path
		EndIf
		
		' Return false if there is no solution
		If ListIsEmpty(pathmap_path_list) Then
			temp_bank = Null
			Return "[ERROR]"
		EndIf
				
		' Remove the parent
		ListRemove(pathmap_path_list, that)
		that = Null
	Next
	Return "FAILED"
End Function

' Remove pathmap from memory
Function FreePathmap(this:TPathmap)
	this.map = Null
End Function

Damien Sturdy

(Posted 2008) [#2]

Freaking wonderful work :-) Can't test it but thats the simplest bit of code i've seen doing this- ease of use wise!

Ginger Tea

(Posted 2008) [#3]

sorry to be a sod here
but is it REALLY an A* pathfinder or just _A_ pathfinder

i even remember casey's list of alternate names for pathfinders calling themselves A*

A nother path finder
A* 's in their eyes path finder
ok i can only remember two
but if its not A* it shouldnt be called A*

Andres

(Posted 2008) [#4]

nothing to be sorry about, that's why i added it here to get feedback. I've read articles about different search algorithms and if i'm correct then this is my engine's algo?

Ginger Tea

(Posted 2008) [#5]

then as its not A* its kinda like calling a digestive biscuit a hobnob cos thats a biscuit too ;)

maybe its cos A* is well known and becoming a catch all for pathfinding like hoovering with a dyson

Andres

(Posted 2008) [#6]

Well, my friend taught me that Breadth-first search algo, but I thought it was A* :(

Ginger Tea

(Posted 2008) [#7]

taken from the same link http://en.wikipedia.org/wiki/A%2A_search_algorithm

i have no idea which is truely the best
A* is the most well known that is for sure
is it the best? id be lying if i said i knew either way

all i was doing was sticking me oar in and being a sod about a possible misnaming of it ;)

Andres

(Posted 2008) [#8]

We've ran into a problem coz i can't change the topic!

chwaga

(Posted 2008) [#9]

awesome, now convert it to b3d and c++

chwaga

(Posted 2008) [#10]

(that was not a request)

Naughty Alien

(Posted 2008) [#11]

there are good A* libs for B3D already done...as well as few other approaches

Ginger Tea

(Posted 2008) [#12]

the only path finding i do is when im ratted trying to make my way home from some random pub or another :p

Tachyon

(Posted 2008) [#13]

This is very well done. My small request: add diagonal spaces to the pathfinding algorithm.

Andres

(Posted 2008) [#14]

Current and Diagonal space flags wouldn't fit in one byte anymore so the pathmap would be instantly twice the size and FindPath() would return Chr(0)...Chr(17). So i'ts possible that i'll do it :P

I'll add diagonal-space-support parameter to CreatePathmap() and rest of the engine would remain the same, except there are 12 more flags.

[EDIT]

Hmmm, 12 more flags wouldn't fit to even 2 bytes :(

I don't know how exactly bites shiftings works to use it with 3 bytes. There is no 3 byte variable type, so i'd need to poke the 3 ones with 3 different PokeByte()s.

Does the FLAG256 fit into 1 byte?

...
Const FLAG64:Int = $40
Const FLAG128:Int = $80

Const FLAG256:Int = $100
Const FLAG512:Int = $200
...

Pete Rigz

(Posted 2008) [#15]

Surely when the monster/entity whatever is following the path then just analyse the next 3 moves and if it goes north east north then make a diagonal move and skip forward 2 places?

I guess it's extra processing versus extra memory and in both cases I doubt it'd be that much extra to worry about.

TaskMaster

(Posted 2008) [#16]

You can't really do that. As, the option to go diagonal adds more optimization choices. So, the path will more than likely be even more different.

Pete Rigz

(Posted 2008) [#17]

Yeh I guess so, looking at the map above you can see where areas could be cut across diagonally, but it still might be a comprise to stop entities behaving in a slightly less mechanical way.

chwaga

(Posted 2008) [#18]

B3D version (translation courteousy of bram)

pathinc.bb:

Const FLAG1% = $01
Const FLAG2% = $02
Const FLAG4% = $04
Const FLAG8% = $08
Const FLAG16% = $10
Const FLAG32% = $20
Const FLAG64% = $40
Const FLAG128% = $80

Function CheckFlag%(flags%, flag%)
	If flags And flag Then Return True Else Return False
End Function

Const PATH_TOP% = FLAG1
Const PATH_BOTTOM% = FLAG2
Const PATH_LEFT% = FLAG4
Const PATH_RIGHT% = FLAG8
Const PATH_CEIL% = FLAG16
Const PATH_FLOOR% = FLAG32
Const PATH_ALL% = FLAG64

; Pathmap Type
Type TPathmap
	Field width, height, depth
	Field map
End Type

Type TPath
	Field x, y, z
	Field path$
End Type

; Create a New pathmap
Function CreatePathmap.TPathmap(width, height, depth = 1)
	 this.TPathmap = New TPathmap
		this\width = width
		this\height = height
		this\depth = depth
		
		this\map = CreateBank(this\width * this\height * this\depth)
		
	Return this
End Function

; Insert flags To pathmap slot
Function PathmapSlot(this.TPathmap, flags%, x, y, z = 0)
	 offset = (z * this\width * this\height) + (y * this\width) + x
	PokeByte(this\map, offset, flags)
End Function

; Search For a path within pathmap; 1 - north, 2 - south, 3 - west, 4 - east, 5 - up, 6 - down
Function FindPath$(this.TPathmap, x1, y1, z1, x2, y2, z2)
	 Local offset, offset_top, offset_bottom, offset_left, offset_right, offset_ceil, offset_floor
	
	 Local temp_bank = CreateBank(BankSize(this\map))
	CopyBank(this\map, 0, temp_bank, 0, BankSize(this\map))
	
	Delete Each TPath
	 that.TPath = New TPath
		that\x = x1
		that\y = y1
		that\z = z1
		that\path = ""
		Insert that Before First TPath
		Insert that Before First TPath
	
	For that.TPath = Each TPath
		offset = (that\z * this\width * this\height) + (that\y * this\width) + that\x
		
		; TOP
		If that\y > 0
			offset_top = (that\z * this\width * this\height) + ((that\y - 1) * this\width) + that\x
			If (Not CheckFlag(PeekByte(temp_bank, offset), PATH_TOP)) And (Not CheckFlag(PeekByte(temp_bank, offset_top), PATH_BOTTOM)) And (Not CheckFlag(PeekByte(temp_bank, offset_top), PATH_ALL))
				 pth.TPath = New TPath
					pth\x = that\x
					pth\y = that\y - 1
					pth\z = that\z
					pth\path = that\path + "1"
					Insert pth After Last TPath
					PokeByte(temp_bank, offset_top, PATH_ALL)
			EndIf
		EndIf
		; Left
		If that\x > 0
			offset_left = (that\z * this\width * this\height) + (that\y * this\width) + that\x - 1
			If (Not CheckFlag(PeekByte(temp_bank, offset), PATH_LEFT)) And (Not CheckFlag(PeekByte(temp_bank, offset_left), PATH_RIGHT)) And (Not CheckFlag(PeekByte(temp_bank, offset_left), PATH_ALL))
				pth.TPath = New TPath
					pth\x = that\x - 1
					pth\y = that\y
					pth\z = that\z
					pth\path = that\path + "3"
					Insert pth After Last TPath
					PokeByte(temp_bank, offset_left, PATH_ALL)
			EndIf
		EndIf
		; BOTTOM
		If that\y + 1 < this\height
			offset_bottom = (that\z * this\width * this\height) + ((that\y + 1) * this\width) + that\x
			If (Not CheckFlag(PeekByte(temp_bank, offset), PATH_BOTTOM)) And ((Not CheckFlag(PeekByte(temp_bank, offset_bottom), PATH_TOP)) And (Not CheckFlag(PeekByte(temp_bank, offset_bottom), PATH_ALL)))
				 pth.TPath = New TPath
					pth\x = that\x
					pth\y = that\y + 1
					pth\z = that\z
					pth\path = that\path + "2"
					Insert pth After Last TPath
					PokeByte(temp_bank, offset_bottom, PATH_ALL)
			EndIf
		EndIf
		; Right
		If that\x + 1 < this\width
			offset_right = (that\z * this\width * this\height) + (that\y * this\width) + that\x + 1
			If (Not CheckFlag(PeekByte(temp_bank, offset), PATH_RIGHT)) And (Not CheckFlag(PeekByte(temp_bank, offset_right), PATH_LEFT)) And (Not CheckFlag(PeekByte(temp_bank, offset_right), PATH_ALL))
				 pth.TPath = New TPath
					pth\x = that\x + 1
					pth\y = that\y
					pth\z = that\z
					pth\path = that\path + "4"
					Insert pth After Last TPath
					PokeByte(temp_bank, offset_right, PATH_ALL)
			EndIf
		EndIf
		
		; If the pathmap has 3 dimensions
		If this\depth > 1
			If that\z > 0
				offset_ceil = ((that\z - 1) * this\width * this\height) + (that\y * this\width) + that\x
				If (Not CheckFlag(PeekByte(temp_bank, offset), PATH_CEIL)) And (Not CheckFlag(PeekByte(temp_bank, offset_ceil), PATH_FLOOR)) And (Not CheckFlag(PeekByte(temp_bank, offset_ceil), PATH_ALL))
					 pth.TPath = New TPath
						pth\x = that\x
						pth\y = that\y - 1
						pth\z = that\z
						pth\path = that\path + "5"
						Insert pth After Last TPath
						PokeByte(temp_bank, offset_ceil, PATH_ALL)
				EndIf
			EndIf
			If that\z + 1< this\depth
				offset_floor = ((that\z + 1) * this\width * this\height) + (that\y * this\width) + that\x
				If Not CheckFlag(PeekByte(temp_bank, offset), PATH_FLOOR) And (Not CheckFlag(PeekByte(temp_bank, offset_floor), PATH_CEIL)) And (Not CheckFlag(PeekByte(temp_bank, offset_floor), PATH_ALL))
					 pth.TPath = New TPath
						pth\x = that\x
						pth\y = that\y + 1
						pth\z = that\z
						pth\path = that\path + "6"
						Insert pth After Last TPath
						PokeByte(temp_bank, offset_floor, PATH_ALL)
				EndIf
			EndIf
		EndIf
		
		; CORRECT PATH FOUND
		If that\x = x2 And that\y = y2 And that\z = z2
			 path$ = that\path
			Delete Each TPath
			FreeBank temp_bank
			Return path
		EndIf
		
		; Return False If there is no solution
		If First TPath = Null Then
			FreeBank temp_bank
			Return "[ERROR]"
		EndIf
				
		; Remove the parent
		Delete that
	Next
	Return "FAILED"
End Function

; Remove pathmap from memory
Function FreePathmap(this.TPathmap)
	FreeBank this\map
End Function

pathtest.bb:

Include "pathinc.bb"

Graphics 800, 600, 0, 2
SetBuffer BackBuffer()

SeedRnd(MilliSecs())

Global map_width = 80
Global map_height = 60

; Create level
Dim map(map_width, map_height)
For y = 0 To map_height -1
	For x = 0 To map_width - 1
		If Rand(0, 5) < 2 Then map(x, y) = PATH_ALL
	Next
Next

; Create pathmap
Global pathmap.TPathmap = CreatePathmap(map_width, map_height)
Global path$ = ""

; Copy level To pathmap
For y = 0 To map_height -1
	For x = 0 To map_width - 1
		PathmapSlot(pathmap, map(x, y), x, y)
	Next
Next

While Not KeyHit(1)
	Cls()
	
	; Draw level
	For  y = 0 To map_height -1
		For  x = 0 To map_width - 1
			If CheckFlag(map(x, y), PATH_ALL)
				Color(255, 0, 0)
			Else
				Color(255, 255, 255)
			EndIf
			Rect x * 10, y * 10, 10, 10
		Next
	Next
	
	; 1 - north, 2 - south, 3 - west, 4 - east, 5 - up, 6 - down
	path = FindPath(pathmap, map_width / 2, map_height / 2, 0, MouseX() / 10.0, MouseY() / 10.0, 0)
	
	; Draw the PATH
	If Len(path) > 0
		Color(0, 0, 255)
		 x = map_width / 2
		 y = map_height / 2
		
		For  i = 1 To Len(path)
			Select Mid(path, i, 1)
				Case "1"
					y  = y - 1
				Case "2"
					y = y + 1
				Case "3"
					x = x - 1
				Case "4"
					x = x + 1
			End Select
			Oval(x * 10, y * 10, 10, 10)
		Next
	EndIf
	
	Flip()
Wend

FreePathmap(pathmap)

Andres

(Posted 2008) [#19]

nice :)

I'm too busy with other projects to finish the corner code for this pathfind engine :(