Z Pathfinding Library

This code has been declared by its author to be Public Domain code.

Z Pathfinding Library by Zenith

2002

VERSION 2.0

What does this library do? -- Well it's a simple-to-use fast pathfinding library
What all can it do?
Unlimited amounts of pathfinds at once, all in realtime! (uses a banks for paths)
4 or 8 direction pathfinding, zpath_Init(dir%), where dir = 4 or 8 IN REALTIME!
Generate a path layout list with one function, zpath_PathFind()
Very OPTIMIZED uses types, but using handle() and object() 90% of the time
Very EASY to use, get the X and Y of the current path: zpath_GetPathX(bank) etc..
Want to go on to the next Path after you're done this one? zpath_GotoNextPath(bank)
The ability to draw the Path layout (if you ever want that debuggin need!)
Clean, Commented, and EASY to understand/modify code (I hope so? :))
Save and Load - Map files, Path layout Files

Honestly, I doubt you'd want to copy paste it -- here's the url to it. EXAMPLE INCLUDED:
http://zen.noelcower.com/zpath.zip

moop

Comments

Spacechimp

2006

moop indeed! link broken

Naughty Alien

2006

its 3 years old post ..

Spacechimp

2006

^_^

puki

2006

I can email this.

Naughty Alien

2006

@Puki..Email me if you dont mind Puki-master :)

Zenith

2007

Hey sorry, fixed the url to my current one: http://zen.noelcower.com/zpath.zip
Good luck!
I don't really advise using it anymore, its pretty bad code, but you be the judge of it. :)

chwaga

2007

that's broken too

Zenith

2008

oh right, lost that site also, hold a sec..

http://gamingseed.deviousbytes.com/zpath.zip

(how ya doing, chwaga? :))

2008

; ===================================================================================
; A* lib -- By Zenith
; ===================================================================================
; VERSION 2.0
; 
; What does this library do? -- Well it's a simple-to-use fast pathfinding library
; What all can it do?
; @ Unlimited amounts of pathfinds at once, all in realtime! (uses a banks for paths)
; @ 4 or 8 direction pathfinding, zpath_Init(dir%), where dir = 4 or 8 IN REALTIME!
; @ Generate a path layout list with one function, zpath_PathFind()
; @ Very OPTIMIZED uses types, but using handle() and object() 90% of the time
; @ Very EASY to use, get the X and Y of the current path: zpath_GetPathX(bank) etc..
; Want to go on to the next Path after you're done this one? zpath_GotoNextPath(bank)
; @ The ability to draw the Path layout (if you ever want that debuggin need!)
; @ Clean, Commented, and EASY to understand/modify code (I hope so? :))
; @ Save and Load - Map files, Path layout Files
; ===================================================================================

; Important variables:
; ===================================================================================
; zpath_maxX = maximum map width
; mayY = maximum map height
Global zpath_maxX, zpath_maxY
; zpath_max_dirs = Change how many directions you have (3 or 7)
Global zpath_max_dirs
; the astar map array
Dim zpath_map(zpath_maxX,zpath_maxY)
; Reading in the direction vector data table
Global zpath_dir[7]

; ===================================================================================

; the pathfinding node type, they are the guys that find the exits.
Type node
; the array holds which other nodes it has created, 0 if it couldnt.
Field array[7],x,y,mapped,id
; id is the ammount of times this node has tried to place another node.
; when mapped = 1 it means the node has been placed on the map.
End Type

; This is the path layout node, with these you can find your way home.
Type path
Field x,y
End Type

;-----------------------------------------------------------------------------;
; Read in the direction vector table										  ;
;-----------------------------------------------------------------------------;
; THIS MUST BE CALLED!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!				  ;
;-----------------------------------------------------------------------------;
Function zpath_Init(ammount_of_directions=4)

	zpath_max_dirs = ammount_of_directions-1
	
	If		zpath_max_dirs = 3
		Restore zpath_direction4
	ElseIf 	zpath_max_dirs = 7
		Restore zpath_direction8
	Else
		Return 1
	EndIf
	
	For i=0 To zpath_max_dirs
		Read a
		Read b
		zpath_dir[i] = (a Shl 2 ) Or b
	Next
	
End Function

;-----------------------------------------------------------------------------;
; Convert the binary version of the direction to a usable direction vector    ;
;-----------------------------------------------------------------------------;
; Example: zpath_ConvDir(0-7,0-1)     id = direction  index= 1=x, 0=y         ;
;-----------------------------------------------------------------------------;
Function zpath_ConvDir(id,index)
	Local out
	out = zpath_dir[id] Shr (index*2) And %11
	If out = 2 out = -1
	Return out
End Function

;-----------------------------------------------------------------------------;
; Clean out all knowledge of the current path on the map array                ;
;-----------------------------------------------------------------------------;
; Example: zpath_CleanMapNodes()                                              ;
;-----------------------------------------------------------------------------;
Function zpath_CleanMapNodes()
	For x=0 To zpath_maxX
		For y=0 To zpath_maxY
			; if its not a wall, delete it
			If zpath_map(x,y)>1 zpath_map(x,y) = 0
		Next
	Next
	Delete Each node
End Function

;-----------------------------------------------------------------------------;
; Pathfind all the way to the exit from S to E                                ;
;-----------------------------------------------------------------------------;
; Example: zpath_FindEnd(sx,sy,ex,ey,max_time,bank) 						  ;
;-----------------------------------------------------------------------------;
Function zpath_PathFind(startx,starty,endx,endy,max_time=1200,bank=0)
	Local done,newx,newy
	
	; Clean up the last pathfinding
	Delete Each path
	
	; Create the start node
	n.node = New node
	n\x = startx : n\y = starty

	timing = MilliSecs()			; Got to make sure you're not stuck...
	
	While Not done
		If KeyHit(2) done=1			; Just in case you get stuck, press 1
		
		; Make sure I havn't used cpu for over a second..
		If MilliSecs()-timing>max_time
			zpath_cleanmapnodes()
			done = 1
		EndIf
		
		If done=0
			; Go through each node, and create a new node from them (if they can)
			For n.node = Each node
				If n\mapped = 0									; I havn't been mapped yet
					If zpath_map(n\x,n\y)=0						; There's nothing on this spot in the map
						zpath_map(n\x,n\y) = Handle(n)+1		; So lets map me..
						n\mapped=1
					Else										; There is something else on the map
						Delete n								; Welp, good bye
					EndIf
				EndIf
				
				If n<>Null										; Ok, I'm still here..
					If n\id<zpath_max_dirs+1
						If n\x = endx And n\y = endy done = 1:Exit		; Hey! I found the exit
						
						; Add a new node to my list
						If n\id<zpath_max_dirs+1					; As long as I havn't made max nodes..
							newx = n\x + zpath_convdir(n\id,1)		; Lets get those vectors
							newy = n\y + zpath_convdir(n\id,0)
							If newx>-1 And newy>-1 And newx<zpath_maxX+1 And newy<zpath_maxY+1	; Make sure I'm in limits
								If zpath_map(newx , newy) = 0		; There's nothing on this spot!
									e.node = New node				; So lets make another node..
									e\x = newx  : e\y = newy
									n\array[n\id] = Handle(e.node)
								EndIf
							EndIf
							n\id = n\id + 1							; Even if I couldn't make a node, inc ID
						EndIf
					EndIf
				EndIf
				
			Next
		EndIf
	Wend

	
	;n.node = Last node          <--- this seems to have caused a weird error
	If n<>Null
		bank=zpath_MakePath(zpath_map(n\x,n\y)-1,bank)	; Ok.. So we HAVE nodes let's layout the path
	Else
		Return -1										; Couldn't find a way to the exit!
	EndIf
	Return bank
End Function

;-----------------------------------------------------------------------------;
; Count how many paths there are in the path layout type list                 ;
;-----------------------------------------------------------------------------;
; Example: zpath_CountPaths()                                                 ;
;-----------------------------------------------------------------------------;

Function zpath_CountPaths(bank)
	Return PeekShort(bank,0)-2
End Function

;-----------------------------------------------------------------------------;
; Root out the next path and delete the old                                   ;
;-----------------------------------------------------------------------------;
; Example: zpath_GotoNextPath()                                               ;
;-----------------------------------------------------------------------------;

Function zpath_GotoNextPath(bank)
	zpath_DelPath(bank)
End Function

;-----------------------------------------------------------------------------;
; Get the X position of the current Path node                                 ;
;-----------------------------------------------------------------------------;
; Example: zpath_GetPathX()                                                   ;
;-----------------------------------------------------------------------------;

Function zpath_GetPathX(bank,index=-1)
	If index<>0
		Return PeekShort(bank,(index*4)-2)
	Else
		SP = PeekShort(bank,0)
		Return PeekShort(bank,(SP*4)-2)
	EndIf
End Function

;-----------------------------------------------------------------------------;
; Get the Y position of the current Path node                                 ;
;-----------------------------------------------------------------------------;
; Example: zpath_GetPathY()                                                   ;
;-----------------------------------------------------------------------------;

Function zpath_GetPathY(bank,index=-1)
	If index<>0
		Return PeekShort(bank,(index*4))
	Else
		SP = PeekShort(bank,0)
		Return PeekShort(bank,(SP*4))
	EndIf
End Function

;-----------------------------------------------------------------------------;
; Draw the path that you laid out from nodes                                  ;
;-----------------------------------------------------------------------------;
; Example: zpath_DrawPath()                                                   ;
;-----------------------------------------------------------------------------;

Function zpath_DrawPath(bank,gx=32,gy=32)
	hgx = gx/2
	hgy = gy/2
	SP = PeekShort(bank,0)
	For i=2 To SP-2
		xa=zpath_GetPathX(bank,i)
		ya=zpath_GetPathY(bank,i)
		xb=zpath_GetPathX(bank,i+1)								; Get the path after this one
		yb=zpath_GetPathY(bank,i+1)																
		Line (xa*gx)+hgx,(ya*gy)+hgy,(xb*gx)+hgx,(yb*gy)+hgy	; Now lets draw a line from it
	Next
	; Draw the current path block
	If SP>0 Rect (zpath_GetPathX(bank,0)*gx)+2,(zpath_GetPathY(bank,0)*gy)+2,gx-2,gy-2
End Function

;-----------------------------------------------------------------------------;
; Find the shortest distance from end to start and then lay out the path type ;
;-----------------------------------------------------------------------------;
; Example: zpath_MakePath(Handle(n.node)) Uses that node to find the start    ;
;-----------------------------------------------------------------------------;

Function zpath_MakePath(target,bank)
	Local cur,done,newx,newy,test
	
	cur = target ; current = the exit node
	c.node = First node
	start = Handle(c) ; start = the start node
	
	p.path = New path
	p\x = c\x
	p\y = c\y
	
	While Not done
		n.node = Object.node(cur)		; Now lets refresh the current node
		p.path = New path				; Layout a new path from this node
		p\x = n\x
		p\y = n\y
		If KeyHit(3) done=1				; Press 2 to escape lockup (just in case)
		
		; Go through each tile to find which has the lowest value
		; EXAMPLE:
		; 03|01|04|32	XX = 05 (which we are currently at)
		; 10|00|XX|12	cur = 05
		; 08|07|06|30
		; Basically we're trying to go from a high number to the lowest number
		; Our target number is higher than the start number, so we work backwards
		; So as we see here, the lowest number here would be 00. You just basically loop until you
		; get a lower number, until cur = start
		For i=0 To zpath_max_dirs
			; Setup those direction vectors
			newx = n\x-zpath_convdir(i,1)
			newy = n\y-zpath_convdir(i,0)
			; Make sure we're in map bounderies
			If newx>-1 And newy>-1 And newx<zpath_maxX+1 And newy<zpath_maxY+1
				; We added 1 to map() before hand so we could use 1 for walls
				test = zpath_map(newx,newy) - 1
				; If test is lower than cur, then that's how much closer we are to the target number
				If test < cur And test > 0
					cur = test				; So then lets set our current number to it, which
											; We will point to for our next node
				EndIf
			EndIf
		Next
		
		If cur = start done=1				; We've found the start, so lets get out of here!
	Wend
	
	; Lay down the start path
	p.path = New path
	p\x = c\x
	p\y = c\y
	; Clean up all the old pathfinder nodes, (not the path nodes)
	zpath_cleanmapnodes()
	bank=zpath_ConvertPath(bank)
	Return bank
End Function

;-----------------------------------------------------------------------------;
; Converts a list of path types to the new bank dataform					  ;
;-----------------------------------------------------------------------------;
; You usually won't need this one.. (more of an internal command)			  ;
;-----------------------------------------------------------------------------;

Function zpath_ConvertPath(bank)
	If bank<>0 FreeBank(bank)
	For p.path = Each path
		i=i+1
	Next
	
	DebugLog i+" path nodes"
	
	bank = CreateBank(2+(i*4))
	
	For p.path = Each path
		zpath_AddPath(p\x,p\y,bank)
		Delete p
	Next
	Delete Each path
	Return bank
End Function

;-----------------------------------------------------------------------------;
; Add a path's X and Y to the current bank stack							  ;
;-----------------------------------------------------------------------------;
; You usually won't need this one.. (more of an internal command)			  ;
;-----------------------------------------------------------------------------;

Function zpath_AddPath(x,y,bank)
	SP = PeekShort(bank,0)
	If SP*4 < BankSize(bank)-4 SP = SP + 1 : PokeShort bank,0,SP
	PokeShort bank,(SP*4)-2,x
	PokeShort bank,SP*4,y
End Function

;-----------------------------------------------------------------------------;
; Deletes a path's X and Y from the current bank stack						  ;
;-----------------------------------------------------------------------------;
; You usually won't need this one.. (more of an internal command)			  ;
;-----------------------------------------------------------------------------;

Function zpath_DelPath(bank)
	If bank
		SP = PeekShort(bank,0)
		PokeInt bank,(SP*4)-2,0
		If SP > 0 SP = SP - 1 : PokeShort bank,0,SP
	EndIf
End Function

;-----------------------------------------------------------------------------;
; Save the zpath_map array to a binary map file for later usage				  ;
;-----------------------------------------------------------------------------;
; Example: zpath_SaveMap("blah.extension")									  ;
;-----------------------------------------------------------------------------;

Function zpath_SaveMap(filename$)
	zpath_CleanMapNodes()
	file = WriteFile(filename)
	WriteShort file,zpath_maxX
	WriteShort file,zpath_maxY
	For x=0 To zpath_maxX
		For y=0 To zpath_maxY
			If zpath_map(x,y) WriteShort file,x:WriteShort file,y:WriteByte file,zpath_map(x,y)
		Next
	Next
	CloseFile(file)
End Function

;-----------------------------------------------------------------------------;
; Load a binary map to the zpath_map array									  ;
;-----------------------------------------------------------------------------;
; Example: zpath_LoadMap("blah.extension")									  ;
;-----------------------------------------------------------------------------;

Function zpath_LoadMap(filename$)
	zpath_CleanMapNodes()
	file = ReadFile(filename)
	zpath_ReDimMap(ReadShort(file),ReadShort(file))
	While Not Eof(file)
		zpath_map(ReadShort(file),ReadShort(file)) = ReadByte(file)
	Wend
	CloseFile(file)
End Function

;-----------------------------------------------------------------------------;
; Save a binary path node list for later usage								  ;
;-----------------------------------------------------------------------------;
; Example: zpath_SavePath("blah.extension")									  ;
;-----------------------------------------------------------------------------;

Function zpath_SavePath(bank,filename$)
	file = WriteFile(filename)
	For i=0 To BankSize(bank)-1
		WriteByte(file,PeekByte(bank,i))
	Next
	CloseFile(file)
End Function

;-----------------------------------------------------------------------------;
; Load a binary path node list												  ;
;-----------------------------------------------------------------------------;
; Example: bank = zpath_LoadPath(bank,"blah.extension")						  ;
;                                 ^-- doesn't have to equal anything		  ;
;-----------------------------------------------------------------------------;

Function zpath_LoadPath(bank,filename$)
	file = ReadFile(filename)
	If bank<>0 FreeBank(bank)
	bank = CreateBank(FileSize(filename))
	While Not Eof(file)
		PokeByte bank,FilePos(file),ReadByte(file)
	Wend
	CloseFile(file)
	Return bank
End Function

;-----------------------------------------------------------------------------;
; Rebuild the map with a new maximum map size (will delete all old data)      ;
;-----------------------------------------------------------------------------;
; Example: zpath_ReDimMap(6,4)												  ;
;-----------------------------------------------------------------------------;
; x = Maximum Map X
; y = Maximum Map Y
Function zpath_ReDimMap(x,y)
	zpath_maxX = X
	zpath_maxY = Y
	Dim zpath_map(zpath_maxX,zpath_maxY)
End Function

; set all data to 0 from map array
Function zpath_CleanMap()
	Dim zpath_map(zpath_maxX,zpath_maxY)
End Function

; The direction vector table
; Data x,y
; 8 Direction's
.zpath_direction8
Data 1,0
Data 1,1
Data 0,1
Data 2,1
Data 2,0
Data 2,2
Data 0,2
Data 1,2

; 4 Direction's
.zpath_direction4
Data 1,0
Data 0,1
Data 2,0
Data 0,2

example:

;-----------------------------------------------------------------------------;
; Example main loop                                                           ;
;-----------------------------------------------------------------------------;
Include "zpath.bb"
Graphics 640,480,16,2
SetBuffer BackBuffer()

;=======================
; some global variables
;=======================
; mx = mouse x
; my = mouse y
; imx = tile mouse x
; imy = tile mouse y
; sx = start x
; sy = start y
; ex = end x
; ey = end y
;=======================
Global mx,my,imx,imy,sx,sy,ex,ey
;=======================

; Set ammount of directions you will use. MUST BE EITHER 4 or 8
zpath_Init(8)
gridsize = 6;16
zpath_ReDimMap((GraphicsWidth()/gridsize-2),(GraphicsHeight()/gridsize)-2)

While Not KeyDown(1)
	; Set the mouse variables
	mx = MouseX()
	my = MouseY()
	imx=mx/gridsize
	imy=my/gridsize
	
	; As long as you're in the map boundery, you can draw
	If imx>-1 And imy>-1 And imx=<zpath_maxX And imy=<zpath_maxY
		
		If KeyDown(42)			; #### while left shift is down          ####
		
			If MouseDown(1) sx = imx : sy = imy			; set the start point
			If MouseDown(2) ex = imx : ey = imy			; set the end point
			
		Else				; #### while the left shift is not down ####
		
			If MouseDown(1) zpath_map(imx,imy) = 1		; plot wall
			If MouseDown(2) zpath_map(imx,imy) = 0		; delete wall
			
		EndIf
		
	EndIf
	
	; Self-Explainitory.. ;)
	If KeyHit(3) zpath_GotoNextPath(bank)
	If KeyHit(4) zpath_SavePath(bank,"example.path")
	If KeyHit(5) bank=zpath_LoadPath(bank,"example.path")
	If KeyHit(6) zpath_SaveMap("example.map")
	If KeyHit(7) zpath_LoadMap("example.map")
	
	; If you press space, it will then pathfind to the exit.
	If KeyHit(57)
		Cls:Flip
		time = MilliSecs()
		zpath_CleanMapNodes()
		max_time = zpath_maxX*zpath_maxY
		test = zpath_PathFind(sx,sy,ex,ey,max_time)
		If test=-1
			Color 255,0,0
			FlushKeys()
			Cls
			Print "Could not find an exit: "+test+" ms taken."
			AppTitle "ms taken: "+(MilliSecs()-time)+" / max: "+max_time
			Flip
			WaitKey
		Else
			bank = test
			AppTitle "ms taken: "+(MilliSecs()-time)+" / max: "+max_time
		EndIf
	EndIf
	
	; Redraw the screen
	Cls
	Color 0,150,0:Rect (sx*gridsize)+1,(sy*gridsize)+1,gridsize-1,gridsize-1		; Draw the Start point
	Color 150,0,0:Rect (ex*gridsize)+1,(ey*gridsize)+1,gridsize-1,gridsize-1		; Draw the End point
	
	Color 255,255,255
	; Render the map
	For x=0 To zpath_maxX
		For y=0 To zpath_maxY
			; Draw Grid
			Plot x*gridsize,y*gridsize
			; Draw a wall
			If zpath_map(x,y)=1
				Color 0,0,150
				Rect (x*gridsize)+1,(y*gridsize)+1,gridsize-1,gridsize-1
				Color 255,255,255
			EndIf
			
			; ==================================
			;  Draw a node (uncommon to happen)
			; ==================================
			
			;If zpath_map(x,y)>1
			;	Color 255,255,0
			;	Rect (x*32)+1,(y*32)+1,31,31
			;	Color 0,0,0
			;	Text (x*32)+1,(y*32),zpath_map(x,y)-2
			;EndIf
			
		Next
	Next
	
	If bank
		If zpath_CountPaths(bank)
			Color 255,255,255
			Text 0,GraphicsHeight()-gridsize,"Path increments remaining: "+zpath_CountPaths(bank)
			zpath_DrawPath(bank,gridsize,gridsize)
		EndIf
	EndIf
	Flip
Wend
End

maybe someone can do a Bmax port.

Zenith

2008

I wrote this 5 years ago.. BEWARE :)

chwaga

2008

lol, I've re-embarked upon the endless quest for simple A*, I asked Xyle to help lol....
(Doing fine, how about you?)

I'd use yours, but it's too slow :(

Code Archives Forum