A* Pathfinding utilizing banks

Blitz3D Forums/Blitz3D Tutorials/A* Pathfinding utilizing banks

Klaas

(Posted 2004) [#1]

Advanced A* Pathfinding utilizing banks
---------------------------------------
Programm: B3D and BP
State: intermediate and advanced users

This Tutorial does not explain A* itself!
For an excelent A* Pathfinding Tutorial check http://www.policyalmanac.org/games/aStarTutorial.htm

You should fully understand A* before continuing this tutorial.
This tutorial explains how to avoid arrays and types while pathfinding.

Why not Arrays?
- arrays are not dynamic and consume lots of memory
- arrays cannot be created on runtime
- arrays are always global

Why not types?
- since types cannot be nested into eachother its hard to parallel process pathfindings. This would take some managment and its hard to deal with.
- types are always global

so my choice is to entirely use banks for pathfinding
Why banks?
- there fast!
- they are small in memory
- they can be nested (will cover this later)
- they are not global
- they can even be stored easily or send through networks

Sorry, but i havent any webspace so i cant include the media.

First you should draw a small image (about 32x32) the background should be black and then paint some walls with pure white(255,255,255).
Save it as Bitmap or PNG. We will call the file "map.png" in the following code

Now we will initialise the graphics

Graphics 1024,768,32,2
SetBuffer(BackBuffer())

We need some globals

;map width and height
Global as_dim_x
Global as_dim_y

;this is the variable to store the image ... see below
Global as_map_bank
;stores how many pathfindings are in progress
Global as_count

;the treshhold when tiles are unwalkable
Global as_unwalk = 120

;some constants i will explain later
Const DEF_AS_MANHATTEN = 10

Const DEF_AS_OPEN = 1
Const DEF_AS_CLOSED = 2

Const DEF_OFF_F = 0
Const DEF_OFF_G = 4
Const DEF_OFF_H = 8
Const DEF_OFF_X = 12
Const DEF_OFF_Y = 16
Const DEF_OFF_PARENT = 20

Because accessing images with ReadPixel is much slower than reading in memorybanks we will convert our "map.png" to a bank with this function

Function img2bank(img)
	;store the image dimension as global map width and height
	as_dim_x = ImageWidth(map)
	as_dim_y = ImageHeight(map)
	
	mx = as_dim_x
	my = as_dim_y
	
	;now we create a bank that has as much bytes as pixels in the image
	bank = CreateBank(mx * my)
	
	buffer = ImageBuffer(img)
	LockBuffer(buffer)
	
	;step through each pixel
	For y=0 To my-1
		For x=0 To mx-1
			;we use the blue channel to determ the brightness
			b = ReadPixelFast(x,y,buffer) And $FF
			PokeByte(bank,(x + mx * y),b)
		Next
	Next
	
	UnlockBuffer(buffer)
	Return bank
End Function

This one is quit simple. We create a bank thats imagewidth x imageheight and store the bluevalue row by row, column by column in the bank

Okay now lets convert our image

map = LoadImage("map.png")
as_map_bank = img2bank(map)

At this point you should have read the A* Tutorial as mentioned above (or know how A* works), or you wont get it !!!

I've said no types ... i was lying ;-)
I will use types to store the running pathfinding processes
So here we go!

Type as_path
	Field info_bank
	Field node_bank
	Field sort_bank
	Field temp_bank

	Field result_bank
	
	Field start_x,start_y
	Field end_x,end_y
	
	Field data_size
	Field status
	Field current_node
	Field time
End Type

So whats that all about?:
info_bank
- this bank will be link between the map and the "A* node's". Each entry in there contains the current status of the node(open, closed, untouched) and the "handle" to the nodes data.(i will explain that later)
node_bank
- this one stores all the nodes data
sort_bank
- this bank contains the sorted "open" list. Each entry consists of the F-value and the node "handle"
temp_bank
- this bank is for swaping memory blocks. you will see later

result_bank
- this one will containe the resulting path in reverse order.
Why reverse? Because A* traces back the best way and you dont know how many steps you need. It can only be "stored" in reverse order from targetpoint to startpoint.

start_x,start_y
end_x,end_y
- that not too hard to guess

data_size
- this one stores how much data is stored per node. this could be different for some reasons (i will cover this later)

status
- stores if the process of pathfinding is still running or cant be solved etc.

current_node
- the current node. Thats importent to continue the search after a break

time
- stores how much time the pathfind can consume

Okay,now we've got all we need to get started.
now we need a function to create and initialise our "as_path"-object

Function as_createPath.as_path()
	a.as_path = New as_path
	
	a\info_bank = CreateBank(as_dim_x * as_dim_y * 5)
	a\node_Bank = CreateBank()
	a\sort_Bank = CreateBank()
	a\result_Bank = CreateBank()
	a\temp_bank = CreateBank(1024*4)
	
	as_count = as_count + 1
	Return a
End Function

the function is declerated as returntype ".as_path".
!!! To all that dont know about types as returns you should check the forum about that !!!
so what do we do here:

1. we create the info_bank
--------------------------
each entry in this bank consits of 5 byte
1 Byte - status of the tile (open, closed, untouched)
4 Byte Int - this will containe the handle of the node in the node_bank. Its not truely a handle its the offset to the nodes data.

so we got (mapwidth * mapheight * 5)

2.create the node_bank
----------------------
this is left blank cause we dont have any nodes now

3.create the sort_bank
----------------------
this is left blank cause we dont have any nodes to sort now

4.create the result_bank
----------------------
yep, no results till now

5.create the temp_bank
----------------------
The size of the tempbank results from the size of the map and should be guessed at startup.
I will cover this later in detail

6. increment the as_count
-------------------------
its always good to know how many threads we got

Now we need a function to start the process

Function as_pathfind(a.as_path,start_x,start_y,end_x,end_y)
	size = BankSize(a\info_bank)-1
	For i=0 To size Step 5
		PokeByte(a\info_bank,i,0)
	Next
	ResizeBank(a\node_bank,0)
	ResizeBank(a\sort_bank,0)	

	a\start_x = start_x
	a\start_y = start_y
	a\end_x = end_x
	a\end_y = end_y
	
	a\data_size = 4 * 6
	a\status = 1
End Function

The whole thing is setup that "entitys" dont have to delete there as_path object. They use always there personal pathfinding object. But this depents on the game and can be changed easily.

1.cleaning up
-------------
step through all the enrys in the info-bank and set the status-byte to zero(untouched). We dont clear the handles cause they will be overwritten. Reseting this would cosume time and time is short!

2. reset node_bank and sort_bank
--------------------------------
no comment

3. store start and endpoint
---------------------------
no comment

4. setting datasize
-------------------
now its time to explain the nodes data:
each node consits of
4 byte int - the F value
4 byte int - the G value
4 byte int - the H value
4 byte int - the Xposition
4 byte int - the Yposition
4 byte int - handle to the PARENT node

check the constants from the start .. that are the offsets in the nodes data

5. set status
-------------
set to 1 ... initialised and ready to go

Switching status
----------------
Now we we should switch each status in the pathfinding process

Function as_calc(a.as_path,time = 99999999)
	a\time = time
	
	map_bank = as_map_bank
	
	mx = as_dim_x
	my = as_dim_y
	
	Select a\status
	Case 1 ;initialise	
		If a\start_x => mx Or a\start_x < 0 Or a\start_y => my Or a\start_y < 0 Then 
			;the startpoint is off the map
			a\status = 4
			Return False
		EndIf
		If a\end_x => mx Or a\end_x < 0 Or a\end_y => my Or a\end_y < 0 Then
			;the endpoint is off the map
			a\status = 4
			Return False
		EndIf
		
		;start oder endpunkt ist nicht begehbar
		If PeekByte(map_bank,a\start_x + mx * a\start_y) => as_unwalk Then 
			;the startpoint is not walkable
			a\status = 4
			Return False
		EndIf
		If PeekByte(map_bank,a\end_x + mx * a\end_y) => as_unwalk Then 
			;the endpoint is not walkable
			a\status = 4
			Return False
		EndIf
		
		;open the startnode
		a\current_node = as_openNode(a,f,g,h,a\start_x,a\start_y,parent)

		a\status = 2
		;start the search
		Return as_path(a.as_path)
	Case 2 ;calculating
	
		;continue the search
		Return as_path(a.as_path)
	
	Case 3 ;finished
		Return 3
	Case 4 ;cannot calculate
		Return 4
	End Select
	
End Function

so each time we run through the list of as_path objects we will call "as_calc"
on status 1 we first check if the search can be made. If the start or end tile is off the map or not walkable the search cannot be successfull so the status is set to 4(cannot calculate)
if the search can be successfull the status is set to 2(calculating) and the startpoint will be stored in the "openlist"

if status is 2 the search is still in progress and will be continued now

status 3 means the path is allready calcualated and the result can be found in the result_bank

status 4 means there is no wy from start to endpoint

Storing nodes in the "openlist"
-------------------------------
now stuff gets serious and we should take a detailed look on the node_bank

the nodebank is a list of all known nodes
it looks like this:

Offset	Datablock
	+---+---+---+---+---+------+
0	| F | G | H | X | Y |PARENT|
	+---+---+---+---+---+------+
24	| F | G | H | X | Y |PARENT|
	+---+---+---+---+---+------+
48	| F | G | H | X | Y |PARENT|
	+---+---+---+---+---+------+
	  .
	  .
	  .
	+---+---+---+---+---+------+
n*24	| F | G | H | X | Y |PARENT|
	+---+---+---+---+---+------+

the handle to a node is the offset in the bank

to store an additional node we increase the size of the bank by the datamount per node (24 bytes)

	+---+---+---+---+---+------+
0	| F | G | H | X | Y |PARENT|
	+---+---+---+---+---+------+
24	| F | G | H | X | Y |PARENT|
	+---+---+---+---+---+------+
48	| F | G | H | X | Y |PARENT|
	+---+---+---+---+---+------+
72	|   |   |   |   |   |      |
	+---+---+---+---+---+------+

then we store the nodes data into the last block

	+---+---+---+---+---+------+
0	| F | G | H | X | Y |PARENT|
	+---+---+---+---+---+------+
24	| F | G | H | X | Y |PARENT|
	+---+---+---+---+---+------+
48	| F | G | H | X | Y |PARENT|
	+---+---+---+---+---+------+
72	|   |   |   |   |   |      |  <<< Poke new values
	+---+---+---+---+---+------+

since we need to access the node with the lowest f score we will always sort the newly added nodes into rthe sortbank
now lets take a closer look into the sortbank:

Offset	Datablock
	+---+--------+
0	| F | HANDLE |
	+---+--------+
5	| F | HANDLE |
	+---+--------+
10	| F | HANDLE |
	+---+--------+
	  .
	  .
	  .
	+---+--------+
n*5	| F | HANDLE |
	+---+--------+

and we want to be F sorted descending so that the last entry is the lowest F
now we have to ad one new

	+---+--------+
new	| 25| HANDLE |
	+---+--------+


	+---+--------+
0	| 30| HANDLE |
	+---+--------+
5	| 20| HANDLE |
	+---+--------+
10	| 10| HANDLE |
	+---+--------+

first we run through from bottom to top until the new f-value is smaler or equal the f value

size = BankSize(a\sort_bank)
offset = size
While offset > 0
	other_f = PeekInt(a\sort_bank,offset - 8)
	If f <= other_f
		Exit
	EndIf
	offset = offset - 8
Wend

We got offset 0 cause the new F=25 is smaler then the F=30
Now we copy everything belowe this entry to the tempbank

count = size - offset
nOffset = offset + 8
CopyBank(a\sort_bank,offset,a\temp_bank,0,count)

	+---+--------+
0	| 30| HANDLE | 
	+---+--------+        +------------+
5	| 20| HANDLE |  >>>   |     TEMP   |  
	+---+--------+        +------------+
10	| 10| HANDLE |  >>>   |     TEMP   |
	+---+--------+        +------------+

now increase the size of the bank

size = BankSize(a\sort_bank) + 8

	+---+--------+
0	| 30| HANDLE |
	+---+--------+
5	| 20| HANDLE |  
	+---+--------+  
10	| 10| HANDLE |  
	+---+--------+  
15	|   |        |  
	+---+--------+

now we have to write back the value

ResizeBank(a\sort_bank,size)
CopyBank(a\temp_bank,0,a\sort_bank,nOffset,count)

	+---+--------+
0	| 30| HANDLE |
	+---+--------+
5	| 20| HANDLE | 
	+---+--------+        +------------+ 
10	| 20| HANDLE |  <<<   |     TEMP   | 
	+---+--------+        +------------+
15	| 10| HANDLE |  <<<   |     TEMP   |
	+---+--------+        +------------+

now there is space for our new entry

PokeInt(a\sort_bank,offset,f)
PokeInt(a\sort_bank,offset+4,hoffset)

	+---+--------+
0	| 30| HANDLE |
	+---+--------+
5	| 25| HANDLE | <<< Poke new values
	+---+--------+ 
10	| 20| HANDLE | 
	+---+--------+
15	| 10| HANDLE |
	+---+--------+

now we wil take a closer look into the info_bank
this is a representation of the known map:

S = status of the Tile (opend, closed or untouched)
H = handle -> Offset to the nodes data in the node_bank

Offset		DATA(5 byte per tile)
		+-------+-------+-------+     +-------+
0*width*5	| S & H | S & H | S & H |     | S & H |
		+-------+-------+-------+     +-------+
1*width*5	| S & H | S & H | S & H | ... | S & H |
		+-------+-------+-------+     +-------+
2*width*5	| S & H | S & H | S & H |     | S & H |
		+-------+-------+-------+     +-------+
		  .                                   
		  .                                   
		  .                                   
		+-------+-------+-------+     +-------+
n*width*5	| S & H | S & H | S & H | ... | S & H |
		+-------+-------+-------+     +-------+

here we will now mark the node as opend

offset = (x + (y * as_dim_x)) * 5
PokeByte(a\info_bank,offset,DEF_AS_OPEN)
PokeInt(a\info_bank,offset+1,hOffset)

Function as_openNode(a.as_path,f,g,h,x,y,parent)
	;increase the bank to one more entry
	hOffset = BankSize(a\node_bank)
	ResizeBank(a\node_bank,hOffset + a\data_size)
	
	
	size = BankSize(a\sort_bank)
	offset = size
	While offset > 0
		other_f = PeekInt(a\sort_bank,offset - 8)
		If f <= other_f
			Exit
		EndIf
		offset = offset - 8
	Wend
	
	count = size - offset
	nOffset = offset + 8
	CopyBank(a\sort_bank,offset,a\temp_bank,0,count)

	size = BankSize(a\sort_bank) + 8
	ResizeBank(a\sort_bank,size)
	CopyBank(a\temp_bank,0,a\sort_bank,nOffset,count)
	
	;write the f and the handle in the sort_bank
	PokeInt(a\sort_bank,offset,f)
	PokeInt(a\sort_bank,offset+4,hoffset)

	;write the data into the new node space
	PokeInt(a\node_bank,hOffset + DEF_OFF_F,f)
	PokeInt(a\node_bank,hOffset + DEF_OFF_G,g)
	PokeInt(a\node_bank,hOffset + DEF_OFF_H,h)
	PokeInt(a\node_bank,hOffset + DEF_OFF_X,x)
	PokeInt(a\node_bank,hOffset + DEF_OFF_Y,y)
	PokeInt(a\node_bank,hOffset + DEF_OFF_PARENT,parent)

	;mark the tile as opend
	offset = (x + (y * as_dim_x)) * 5
	PokeByte(a\info_bank,offset,DEF_AS_OPEN)
	PokeInt(a\info_bank,offset+1,hOffset)
	
	;return the handle
	Return hoffset
End Function

that was tough ... :-)

A* main
-------
now here comes the big block of A*

Function as_path(a.as_path)
	map_bank = as_map_bank
		
	mx = as_dim_x
	my = as_dim_y
	
	begin = MilliSecs()
	;as long we are in time ...
	While (MilliSecs() - begin) < a\time
		;close the node
		;the below for this function
		as_closeNode(a,a\current_node)
		current_x = PeekInt(a\node_bank,a\current_node + DEF_OFF_X)
		current_y = PeekInt(a\node_bank,a\current_node + DEF_OFF_Y)
		current_g = PeekInt(a\node_bank,a\current_node + DEF_OFF_G)

		;check to see if the endpoint has been reached
		If current_x = a\end_x And current_y = a\end_y Then
			;the endpoint has been reach
			;create and fill the resultbank
			; i will explain this at the end of this tutorial .. so leave this now
			a\result_bank = CreateBank(8)
			size = 8
			
			current_node = a\current_node
			x = PeekInt(a\node_bank,current_node + DEF_OFF_X)
			y = PeekInt(a\node_bank,current_node + DEF_OFF_Y)
			PokeInt(a\result_bank,0,x)
			PokeInt(a\result_bank,4,y)
			
			scale = 55
			While current_node
				current_node = PeekInt(a\node_bank,current_node + DEF_OFF_PARENT)
				x = PeekInt(a\node_bank,current_node + DEF_OFF_X)
				y = PeekInt(a\node_bank,current_node + DEF_OFF_Y)
				size = size + 8
				
				ResizeBank(a\result_bank,size)
				PokeInt(a\result_bank,size - 8,x)
				PokeInt(a\result_bank,size - 4,y)
			Wend
			
			a\status = 3
			Return True
		EndIf

		;open all surrounding nodes
		For y = current_y - 1 To current_y + 1
			For x = current_x - 1 To current_x + 1
			
				;if its not the center ...
				If x <> current_x Or y <> current_y
					;.. and not off the map ...
					If x < mx And x >= 0 And y < my And y >= 0 Then						
						offset = (x + mx * y)
						offset2 = offset * 5

						new_status = PeekByte(a\info_bank,offset2)
						b = PeekByte(map_bank,offset)
						
						;... and not allready closed or unwalkable
						If new_status <> DEF_AS_CLOSED And b < as_unwalk
							g = 14
							If x = current_x Or y = current_y Then g = 10
							g = current_g + g; + (b / 10)
							
							Select new_status
							Case DEF_AS_OPEN
								;this one is allready open check if this one should be edited
								new_node = PeekInt(a\info_bank,offset2+1)
								new_g = PeekInt(a\node_bank,new_node + DEF_OFF_G)
								new_h = PeekInt(a\node_bank,new_node + DEF_OFF_H)
								
								If g < new_g
									;this node must be edited ... as_updateNode will sort this into the sort_bank
									; will explain this later
									f = g + new_h
									;update the values in the nodebank
									PokeInt(a\node_bank,new_node + DEF_OFF_PARENT,a\current_node)
									PokeInt(a\node_bank,new_node + DEF_OFF_G,g)
									PokeInt(a\node_bank,new_node + DEF_OFF_F,f)
									
									;resort the sortlist
									as_updateNode(a.as_path,new_node,f)
								EndIf
							Default
								;this  tile is still untouched ... add this to the openlist
								h = (Abs(a\end_x - x) + Abs(a\end_y - y)) * DEF_AS_MANHATTEN
								f = g + h
								parent = a\current_node
								as_openNode(a.as_path,f,g,h,x,y,parent)
							End Select
						EndIf
					EndIf
				EndIf
			Next
		Next
		;this one is for debbuging and uses the draw function(see below)
		draw(a)
		WaitKey
		
		; get the next node with the lowest F score
		size = BankSize(a\sort_bank)
		If size = 0 Then
			;oops .. no more nodes .. there is no path to the endpoint
			;set status to 4 (cannot calculate)
			a\status = 4
			Return False
		Else
			;get next node for next loop
			a\current_node = PeekInt(a\sort_bank,BankSize(a\sort_bank)-4)
		EndIf
	Wend
	
	Return True
End Function

i will not get into this to deep
the nodes data can be accessed by there handle + the offset of the data
like:
node_g = PeekInt(a\node_bank,node_handle + DEF_OFF_G)

Closing nodes
-------------
okay ... now lets check what happens if a node gets closed

Function as_closeNode(a.as_path,node)
	size = BankSize(a\sort_bank)

	ResizeBank(a\sort_bank,size - 8)
	
	x = PeekInt(a\node_bank,node + DEF_OFF_X)
	y = PeekInt(a\node_bank,node + DEF_OFF_Y)
	
	offset = (x + y * as_dim_x) * 5
	PokeByte(a\info_bank,offset,DEF_AS_CLOSED)
	Return 
End Function

thats easy ...
first we reduce the sortbank by one set of data cause the node to be closed is allways the last one in the list
then we mark the tile in the infobank as closed

now lets see how we can resort the list of handles if we edited one of the nodes

Updating nodes and sort them
----------------------------
This one gave me some headache and i dont know if this is the optimal approach to do this!

first we will search the node to be updated

offset = size
While offset > 0
	offset = offset - 8
	other_node = PeekInt(a\sort_bank,offset + 4)
	If node = other_node
		Exit
	EndIf
Wend

then we will erase the node

	+---+--------+
0	| 30| HANDLE |
	+---+--------+
5	| 20| HANDLE |  <<< should be erased
	+---+--------+ 
10	| 10| HANDLE | 
	+---+--------+ 
15	| 5 | HANDLE | 
	+---+--------+

copy everything below

	+---+--------+
0	| 30| HANDLE |
	+---+--------+ 
5	| 20| HANDLE | 
	+---+--------+         +------------+
10	| 10| HANDLE |   >>>   |            |
	+---+--------+         +---TEMP-----+
15	| 5 | HANDLE |   >>>   |            |
	+---+--------+         +------------+

write the data back on the position of the node to be erased

	+---+--------+
0	| 30| HANDLE |
	+---+--------+         +------------+ 
5	| 10| HANDLE |   <<<   |            | 
	+---+--------+         +---TEMP-----+
10	| 5 | HANDLE |   <<<   |            |
	+---+--------+         +------------+
15	| 5 | HANDLE |
	+---+--------+

then do the same as descriped when adding a node to the openlist (see above)
but dont increase the size of the bank ... we allready got one free entry

Function as_updateNode(a.as_path,node,f)
	size = BankSize(a\sort_bank)
	
	;find the node to update
	offset = size
	While offset > 0
		offset = offset - 8
		other_node = PeekInt(a\sort_bank,offset + 4)
		If node = other_node
			Exit
		EndIf
	Wend
	
	;erase the node
	count = size - offset
	CopyBank(a\sort_bank,offset,a\temp_bank,0,count)
	CopyBank(a\temp_bank,8,a\sort_bank,offset,count-8)
	
	offset = size - 8
	While offset > 0
		other_f = PeekInt(a\sort_bank,offset - 8)
		If f <= other_f
			Exit
		EndIf
		offset = offset - 8
	Wend
	
	count = size - offset - 8
	CopyBank(a\sort_bank,offset,a\temp_bank,0,count)

	nOffset = offset + 8	
	CopyBank(a\temp_bank,0,a\sort_bank,nOffset,count)
	
	;write the f and the handle in the sort_bank
	PokeInt(a\sort_bank,offset,f)
	PokeInt(a\sort_bank,offset+4,node)	
	
End Function

Tracing back the path
---------------------
at this point we have found the endpoint in our openlist
now lets resize our resultbank back to 8
then step from parent to parent and add the X and Y value to the resultbank until there is no more parent node
this will lead from endpoint to the startpoint and the resultbank contains the X,Y Positions leading to the target in reverse order.

Offset	Datablock
	+---+---+
0	| X | Y |
	+---+---+
8	| X | Y |
	+---+---+
16	| X | Y |
	+---+---+
	  .
	  .
	  .
	+---+---+
n*8	| X | Y |
	+---+---+

;create and fill the resultbank
resizeBank(a\result_bank,8)
size = 8

current_node = a\current_node
x = PeekInt(a\node_bank,current_node + DEF_OFF_X)
y = PeekInt(a\node_bank,current_node + DEF_OFF_Y)
PokeInt(a\result_bank,0,x)
PokeInt(a\result_bank,4,y)

scale = 55
While current_node
	current_node = PeekInt(a\node_bank,current_node + DEF_OFF_PARENT)
	x = PeekInt(a\node_bank,current_node + DEF_OFF_X)
	y = PeekInt(a\node_bank,current_node + DEF_OFF_Y)
	size = size + 8
	
	ResizeBank(a\result_bank,size)
	PokeInt(a\result_bank,size - 8,x)
	PokeInt(a\result_bank,size - 4,y)
Wend

a\status = 3
Return True

Debugging and drawing
---------------------
this is a small function to draw the result
this is for very small maps only (13 x 13)

[code]
Function draw(a.as_path)
Cls()
scale = 55

If a\result_bank Then
Color(100,0,20)
size = BankSize(a\result_bank)
For i=size To 0 Step -8
xs = PeekInt(a\result_bank,i - 8) * scale
ys = PeekInt(a\result_bank,i - 4) * scale
Rect(xs,ys,scale,scale,1)
Next
End If

For y=0 To as_dim_y-1
For x=0 To as_dim_x-1
xs = x * scale
ys = y * scale

offset = (x + y * as_dim_x)
b = PeekByte(as_map_bank,offset)
Color(b,b,b)
Rect(xs,ys,scale,scale,0)

offset = (x + y * as_dim_x) * 5
status = PeekByte(a\info_bank,offset)
node = PeekInt(a\info_bank,offset + 1)

Select status
Case DEF_AS_OPEN
Color(20,250,20)
Rect(xs,ys,scale,scale,0)

Color(200,250,200)
f = PeekInt(a\node_bank,node + DEF_OFF_F)
g = PeekInt(a\node_bank,node + DEF_OFF_G)
h = PeekInt(a\node_bank,node + DEF_OFF_H)

parent = PeekInt(a\node_bank,node + DEF_OFF_PARENT)

px = PeekInt(a\node_bank,parent + DEF_OFF_X)
py = PeekInt(a\node_bank,parent + DEF_OFF_Y)

Text xs + 1,ys + 1,f
Text xs , ys + scale - 1 - (FontHeight()),g
Text xs + scale - StringWidth(h) - 1 , ys + scale - 1 - FontHeight(),h

Line(xs+scale/2,ys+scale/2,px*scale+scale/2,py*scale+scale/2)
Case DEF_AS_CLOSED
Color(20,20,250)
Rect(x*scale,y*scale,scale,scale,0)

Color(200,200,250)
f = PeekInt(a\node_bank,node + DEF_OFF_F)
g = PeekInt(a\node_bank,node + DEF_OFF_G)
h = PeekInt(a\node_bank,node + DEF_OFF_H)

parent = PeekInt(a\node_bank,node + DEF_OFF_PARENT)

px = PeekInt(a\node_bank,parent + DEF_OFF_X)
py = PeekInt(a\node_bank,parent + DEF_OFF_Y)

Text xs + 1,ys + 1,f
Text xs , ys + scale - 1 - (FontHeight()),g
Text xs + scale - StringWidth(h) - 1 , ys + scale - 1 - FontHeight(),h

Line(xs+scale/2,ys+scale/2,px*scale+scale/2,py*scale+scale/2)
End Select
Next

Next

x = PeekInt(a\node_bank,a\current_node + DEF_OFF_X)
y = PeekInt(a\node_bank,a\current_node + DEF_OFF_y)

Color(250,20,20)
Rect(x*scale,y*scale,scale,scale,0)

Color(250,20,20)
Rect(a\end_x*scale,a\end_y*scale,scale,scale,1)

Color(20,250,20)
Rect(a\start_x*scale,a\start_y*scale,scale,scale,1)

size = BankSize(a\sort_bank)-1
While i < size
count = count + 1
Text 800,count * 17, i + " -> f:" + PeekInt(a\sort_bank,i) +" - node:"+ PeekInt(a\sort_bank,i+4)
i = i + 8
Wend

Flip()
End Function
[\code]

so, thats it for now

I hope you find this usefull.

My english isnt that good so if anyone could correct this tutorial to be more understandable please mail the corrected thread to:
rayzor-s-edge@...
i will then update this post.
thx in advance.

If you got some improvements or questions ... please drop a line.

Dustin

(Posted 2004) [#2]

Very detailed tutorial! And the english is just fine.

Thanks!

GW	(Posted 2004) [#3]

Why not Arrays?
- accessing arrays in Blitzbasic is slow *WRONG*
- arrays are not dynamic and consume lots of memory *WRONG*
- arrays are always global *WRONG*

Why not types?
- since types cannot be nested into eachother *WRONG*
- types are always global *SO WHAT*

Klaas

(Posted 2004) [#4]

@GW
- accessing arrays in Blitzbasic is slow *WRONG*
i've benchmarked arrays and banks ... accessing arrays was about 1/2 that fast
[edit]my mistake ... they are not slow[/edit]

- arrays are not dynamic and consume lots of memory *WRONG*
arrays can be redimed - YES
.. but you cannot redim without losing all values in the array, this means you have to make the array as big as the highest possible nodecount therefor you consum lots of extra memory without need!

- arrays are always global *WRONG*
arrays are always global ... except Blitzarrays and those are always constant

- since types cannot be nested into eachother *WRONG*
Types cannot be nested
for t.type = each type
would allways get ALL existing entries of "type"
for t.type = each parent\type
cannot be done

- types are always global *SO WHAT*
calculating pathes paralel would result in a mess in the typelist. you allways have to sort the types by there "task"

MSW	(Posted 2004) [#5]

- accessing arrays in Blitzbasic is slow *WRONG*
i've benchmarked arrays and banks ... accessing arrays was about 1/2 that fast

erm...okay...thats very doubtful, but if you say so.

- since types cannot be nested into eachother *WRONG*
Types cannot be nested
for t.type = each type
would allways get ALL existing entries of "type"
for t.type = each parent\type
cannot be done

erm...I hope you realise that there are other ways to perform loops accessing types... "For t.type = each type" is but ONE way Blitz allows you to loop through types...course the other ways require a little bit more work from the programmer, but then again C/C++ users are used to that sort of thing and they have no problems with haveing to implament thier own parent/child data nesting schemes.

Anyway, very good tutorial overall.

Klaas

(Posted 2004) [#6]

okay, its true that it can be done ...
i've wrote:
"since types cannot be nested into eachother its hard to parallel process pathfindings. This would take some managment and its hard to deal with."

i wanted to say that doing this with types would have some managment overhead that you do not have when using banks. I correct the statements in the tutorial soon to avoid confusion about that.

morduun

(Posted 2004) [#7]

Banks in this case are a =lot= more useful than arrays, if for no other reason than individual a* banks can be attached to individual pathfinding entities via their handle in an appropriate type field. In theory you could do the same with BlitzArrays but then you'd need to futz around with constant and inflexible dim values, so in the end I think Klaas has the most flexible and best overall method here.