a Pathfinder, ClearList() problem

BlitzMax Forums/BlitzMax Programming/a Pathfinder, ClearList() problem

Andres

(Posted 2008) [#1]

I've made a pathfinder (A* ?), but i have problem with ClearList(). If i use it then the engine will "flicker", works-doesn't work-works-doesn't work-works-doesn't work (see function FindPath()). If i don't use the ClearList() it finds the path, but not the smartest way :P and with a "little" memory leak.
When i put the ClearList() in the beginning of the FindPath()function, et won't do anything at all.

The engine has only 4 function so it should be pretty user friendly and it works almost fine, but this little problem :( and i haven't finished the 3rd dimension support.

Example:

SuperStrict

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

' The engine file
Include "pathfind.bmx"

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

Global pathmap:TPathmap = CreatePathmap:TPathmap(32, 32)
Global path:String = ""

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

While Not KeyHit(KEY_ESCAPE)
	Cls()
	
	' Draw level
	For Local y:Int = 0 To 32 -1
		For Local x:Int = 0 To 32 - 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
	
	 path = FindPath(pathmap, 0, 0, 0, MouseX() / 10, MouseY() / 10, 0)
	
	' Draw the PATH
	If Len(path) > 0
		SetColor(0, 0, 255)
		Local x:Long = 0, y:Long = 0
		For Local i:Int = 1 To Len(path)
			DrawOval(x * 10, y * 10, 10, 10)
			Select Mid(path, i, 1)
				Case "1"
					y :- 1
				Case "2"
					y :+ 1
				Case "3"
					x :- 1
				Case "4"
					x :+ 1
			End Select
		Next
	EndIf
	
	Flip()
Wend

FreePathmap(pathmap)

Engine:

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_UP:Int = FLAG16
Const PATH_DOWN: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
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_up:Long, offset_down:Long
	
	Local temp_bank:TBank = CreateBank(BankSize(this.map))
	CopyBank(this.map, 0, temp_bank, 0, BankSize(this.map))
	
	DrawText(pathmap_path_list.Count(), 500, 100)
	
	Local that:TPath = New TPath
		that.x = x1
		that.y = y1
		that.z = z1
		that.path = ""
		ListAddLast(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 - 1 > 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 - 1 > 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 CheckFlag:Int(PeekByte(temp_bank, offset), PATH_RIGHT)
			EndIf
			If CheckFlag:Int(PeekByte(temp_bank, offset), PATH_RIGHT)
			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
End Function

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