Quote: "Unless, someone can come up with a very well textured matrix that doesn't show the seams between tiles. That would save some collision detection code by just using get ground height"
@Digger412
I think Latch's challange was to create seamless terrain using a matrix. He already provided a model of terrain.
@All
The following code is a speed test of the A* function. No media required. It starts all enemies in the top left corner of the house and the goal is the bottome right corner of the house. I get about .016 sec for 20 enemies and .063 sec for 50 enemies. My PC is pretty old so I'm curious what other get.
remstart
-------------------------------------------------------------------
program name: Speedtest for A*
-------------------------------------------------------------------
written by: NoTimeToCode
date: 11/3/2009
-------------------------------------------------------------------
comments: Test of speed of A* method with a variables amount of enemies
-------------------------------------------------------------------
remend
gosub _program_variables
gosub _astar_variables
gosub _create_nodes
gosub _setup_enemies
search_stage(0) = 0
count = 1
`------------------------------------------------------------------------------
`-------------------------MAIN LOOP--------------------------------------------
do
rem If getting to bottom of screen, clear screen and start at top
If count = 8
Ink rgb(255,0,0),0
Print "Hit any key to continue"
suspend for key
cls
count = 1
ink rgb(255,255,255),0
Endif
rem Get user input
If search_stage(0) = 0
gosub _get_input
If enemynum>0 and enemynum<51
search_stage(0) = 1
Print "SPACEBAR TO START SEARCH"
Else
Print "Enemies must be between 1 and 50"
Endif
Endif
rem Start pathfinding when spacekey is pressed
If Spacekey()=1 and search_stage(0) = 1
search_stage(0) = 2 : rem Actively pathfinding.
pfindtimer# = timer()
`If search in progress go to pathfinding function
wl = Astar(NodesX,NodesZ,allow_diag,wl,enemynum)
Endif
rem Pathfinding is complete print out results
If goalfound(0) and search_stage(0) = 2
Elasped# = (timer() - pfindtimer#)/1000
Print "Time to find paths for " + Str$(enemynum) + " enemies was " + Str$(Elasped#) + " seconds"
search_stage(0) = 0 : rem let user enter a new umber of enemies
goalfound(0) = False
inc count
Endif
loop
end
`---------------------------------------------------------------------------
_get_input:
Input "Enter number of enemies (1 - 50): ",enemynum
Return
`----------------------------------------------------------------------------
_program_variables:
Elasped# = 0 : Rem Time required to find a path
stepctr = 0 : rem number of steps required to find a path
True = 1 : False = 0
toggleview = 1
toggleghost = 1
Return
`----------------------------------------------------------------------------
_astar_variables:
wl = 0 : `Variable for each loop. Will be increased by 5 each loop so I don;t have to zero out which_list array
`Spacing between nodes and size of nodes
node_space = 20
node_size = 10
rem Set up counter for node object #s
objctr = 1
rem Start with getting user input
search_stage(0) = 0
rem Number of nodes in environment
NodesX = 26
NodesZ = 31
path_max = 200 : rem Maximum node to be stored in path
Dim node(NodesX,NodesZ,1) : rem 0 = object number, 1 = Passible (0) or impassible (1),
Dim whichlist(NodesX,NodesZ) : rem Keep track of which list a node is on. 0 = not on any list, 1 = open and 2 = closed
Dim node_start(50,1) : rem (Enemy number,0=X value of start node for this enemy, 1=Z value of start node for this enemy
Dim node_goal(50,1) : `0=X value of goal node, 1=Z value of goal node
Dim node_value(NodesX,NodesZ,4) : `0=Parent node X, 1=Parent node Z, 2= F value , 3=G value , 4=H value
Dim node_current(1) : `Current node X and Z
Dim node_xyz(850,2) : rem Hold xyz position of object nodes (node object#,0=x 1=y 2=z)
Dim lowF(2) : `Lowest lowest F value as for-next loops are running 0 = X, 1 =Z, 2 = F value of this node
Dim path(50,path_max,1) : `Stores found path. 0 = X value, 1 = Z value
Dim step_path(50,0) : `Hold number of step in found path
Dim goalfound(0) : `Value of 1 = True
Dim True(0) : True(0) = 1
Dim False(0) : False(0) = 0
Dim search_stage(0) : `What stage of search process is active 0 = Getting user input, 1 = Ready to search, 2 = Search in progress, 3 = Moving along path
Dim Enemy(5,1) : rem 0=object number of each enemy - 1=movement speed
Dim gotplayer(50) : rem true if enemy got player
Return
`----------------------------------------------------------------
rem Load map data into array
_create_nodes:
rem starting positions of node objects
`nx = -120
`nz = 520
nx = 1880
nz = 2520
Restore node_data
For Z = 1 to NodesZ
For X = 1 to NodesX
Read d
node(X,Z,0) = objctr : rem Assign node object number
node(X,Z,1) = d : rem Assign passible or unpassible value
rem assign xyz pos to nodes
node_xyz(objctr,0) = nx
node_xyz(objctr,1) = 5
node_xyz(objctr,2) = nz
inc objctr
inc nx, node_space
Next X
dec nz, node_space
nx = 1880
Next Z
rem reset starting node positions for use in calculating player position when moving
nx = 1880
nz = 2520
return
`-------------------------------------------------------------------------------------
_setup_enemies:
For e = 1 to enemynum
node_start(e,0) = 5
node_start(e,1) = 5
node_goal(e,0) = 22
node_goal(e,1) = 24
Next e
allow_diag = 0
search_stage(0) = 1
return
rem =============================================================
rem = FUNCTIONS
rem =============================================================
rem A* pathfinding function
function Astar(NodesX,NodesZ,allow_diag,wl,enemynum)
for e = 1 to enemynum
node_current(0) = node_start(e,0) : node_current(1) = node_start(e,1) : rem Define start node as current node
whichlist(node_current(0),node_current(1)) = 1 + wl : rem Add current node to open list
repeat
lowF(2) = 99999 : rem Will hold lowest F value after the following loop
rem Look for lowest F cost square on open list
For Z = 1 to NodesZ
For X = 1 to NodesX
If whichlist(X,Z) = 1 + wl: rem If cell X,Y is on open list
If node_value(X,Z,2) < lowF(2)
lowF(0) = X : lowF(1) = Z : rem Make this the cell with the lowest F score
lowF(2) = node_value(X,Z,2)
endif
endif
Next X
Next Z
rem Swich node with lowest F score to the closed list
whichlist(lowF(0),lowF(1)) = 2 + wl
rem Make this node the current node
node_current(0) = lowF(0)
node_current(1) = lowF(1)
rem If goal is on the closed list construct path
If lowF(0) = node_goal(e,0) and lowF(1) = node_goal(e,1)
path(e,1,0) = node_goal(e,0) : path(e,1,1) = node_goal(e,1) : rem Set first step in path as goal
stp = 1
Repeat
inc stp
path(e,stp,0) = node_value(path(e,stp-1,0),path(e,stp-1,1),0) : rem X value of parent of previous node on path
path(e,stp,1) = node_value(path(e,stp-1,0),path(e,stp-1,1),1) : rem Z value of parent of previous node on path
Until path(e,stp,0) = node_start(e,0) and path(e,stp,1) = node_start(e,1) : rem Current step on path is start node
goalfound(0) = 1
step_path(e,0) = stp : rem Store number of steps in path
If e = enemynum then Exitfunction wl
Else
rem Look for all reachable squares adjacent to starting point
For Z = -1 to 1
For X = -1 to 1
If (allow_diag = False(0) and (X = 0 or Z = 0)) or allow_diag = True(0) :rem If alloq_diag = False don't look at diagonal nodes
If node_current(0)+X > 0 and node_current(0)+X <= NodesX and node_current(1)+Z > 0 and node_current(1)+Z <= NodesZ : rem Check that node is within bounds
If node(node_current(0)+X,node_current(1)+Z,1) = 0 and whichlist(node_current(0)+X,node_current(1)+Z) <> 2 + wl : rem Walkable node and not on closed list
Select whichlist(node_current(0)+X,node_current(1)+Z)
nolist = wl
openlist = wl + 1
Case openlist : rem Already on open list
If X = 0 or Z = 0 : rem On same X or Z axis meaning directly above/below or left/right
G1 = 10
Else : rem Cells is diagonal
G1 = 14
Endif
newG = G1 + node_value(node_current(0),node_current(1),3) : rem G value of going through current node
If newG < node_value(node_current(0)+X,node_current(1)+Z,3) : rem If this new G value is lower the the current G value of this node
node_value(node_current(0)+X,node_current(1)+Z,0) = node_current(0) : rem Make current node the parent of this node X value
node_value(node_current(0)+X,node_current(1)+Z,1) = node_current(1) : rem Make current node the parent of this node Z value
node_value(node_current(0)+X,node_current(1)+Z,3) = newG : rem Change G value to this new lower value
F = newG + node_value(node_current(0)+X,node_current(1)+Z,4) : rem Recalculate F value
node_value(node_current(0)+X,node_current(1)+Z,2) = F : rem Assign new F value
Endif
EndCase
Case Default : rem Not on any list
whichlist(node_current(0)+X,node_current(1)+Z) = 1 + wl : rem add to open list
node_value(node_current(0)+X,node_current(1)+Z,0) = node_current(0) : rem Make current node the parent of this node X value
node_value(node_current(0)+X,node_current(1)+Z,1) = node_current(1) : rem Make current node the parent of this node Z value
rem H score = 10*(abs(currentX-targetX) + abs(currentY-targetY))
H = 10*(abs(node_current(0)+X-node_goal(0)) + abs(node_current(1)+Z-node_goal(1)))
rem G = the movement cost to move from the starting point A to a given square on the grid, following the path generated to get there
If X = 0 or Z = 0 : rem On same X or Z axis meaning directly above/below or left/right
G = 10
Else : rem Cells is diagonal
G = 14
Endif
rem G is cost to move from current cell to this cell + G value of current cell
G = G + node_value(node_current(0),node_current(1),3)
rem Get F score for this cell and store F,G and H in node_values(X,Y,2-4)
F = G + H
node_value(node_current(0)+X,node_current(1)+Z,2) = F
node_value(node_current(0)+X,node_current(1)+Z,3) = G
node_value(node_current(0)+X,node_current(1)+Z,4) = H
Endcase
Endselect
Endif
Endif
Endif
Next X
Next Z
Endif
until goalfound(0) = 1
inc wl,5
goalfound(0) = 0
next e
Endfunction wl
rem =============================================================
rem = DATA STATEMENTS
rem =============================================================
node_data:
rem Load map array
Data 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
Data 0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1,0,0
Data 0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,0
Data 0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,0
Data 0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,0
Data 0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,0
Data 0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,0
Data 0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,0
Data 0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,0
Data 0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0
Data 0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0
Data 0,1,1,1,1,1,1,1,0,0,1,1,1,1,0,0,1,0,0,0,0,0,0,1,0,0
Data 0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0
Data 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
Data 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0
Data 0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0
Data 0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0
Data 0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,1,1,1,1,1,1,1,1,0,0
Data 0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0
Data 0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0
Data 0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0
Data 0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0
Data 0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0
Data 0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0
Data 0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0
Data 0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0
Data 0,0,0,0,0,0,1,1,1,1,0,1,1,1,1,1,1,0,0,0,1,1,1,1,0,0
Data 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
Data 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
Data 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
Data 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
zone_data:
rem zone data
Data 2,15,23,16,19 : rem zone 1 - number of exit nodes = 2, x and z coord of each exit node
Data 1,17,14
Data 1,15,10
Data 2,12,10,14,10
Data 2,9,11,11,11
Data 6,10,12,10,16,2,14,16,14,16,17,16,12
Data 2,12,17,13,23
