Update: Added pathfinding!
Ok, I'm a little bummed out cause I just added a huge amount of tutorial as an edit to my last post but it completely lost it
. I'll just add it to this post.
First, before we get any further into our pathfinding, we need to download an A* library. Go to
this link. Scroll down a bit and download the zip file. Extract the zip file and copy the MapAndSearch.dba file to your project directory. Include this file with your project.
Now for an important lesson for any coder. Do not rewrite what has already been written. As long as you can find something that is efficient and suits your purpose there is no other reason to write what has been written. Unless you just want to learn. I'd love to write a tutorial on how to do pathfinding but that would have to be a tutorial all on its own. For now, we're making a game and IanM has supplied the DarkBasic community with this little gem. A* pathfinding is type of pathfinding that is used in all sorts of RTS games. Please google it or search these forums for more information, but in basics, it creates a tree of possible routes and, based on a simple point system, finds the least costly route to get to the destination.
Ok, now let me show you all of the functions we will be adding to our Critter.dba file. Here's they are. Add these to your Critter.dba source file.
`**********************
`PrepareCritters()
`**********************
FUNCTION PrepareCritters()
FOR i = BasicCritterObjectSeed to BasicCritterObjectSeed+MaxCritters `Delete objects if they already exist
IF OBJECT EXIST(i) = 1
DELETE OBJECT i
ENDIF
NEXT i
GLOBAL DIM Critters#(MaxCritters,14) `Create our critter array where we will store all the critter data
SET DIR CurDir$+"Media" `Go to the correct directory
MAKE OBJECT PLAIN BasicCritterObjectSeed,1,1 `Make a 1x1 plain object
TEXTURE OBJECT BasicCritterObjectSeed,BasicCritterImage `Texture this object with our Critter Image
SET OBJECT BasicCritterObjectSeed,1,1,0 `Set transparency on for our object
XROTATE OBJECT BasicCritterObjectSeed,270 `Rotate the object to be flat against our map
HIDE OBJECT BasicCritterObjectSeed `Hide the object
FOR i = 1 to MaxCritters `Clone our object for our game. We'll make the number of MaxCritters specified.
CLONE OBJECT BasicCritterObjectSeed+i,BasicCritterObjectSeed `The object number for each critter
Critters#(i-1,6) = BasicCritterObjectSeed+i `Store the object number for our critter
HIDE OBJECT BasicCritterObjectSeed+i `Hide our new object
NEXT i
ENDFUNCTION
`********************
`SpawnCritter()
`********************
FUNCTION SpawnCritter(CritterType)
SELECT CritterType `First, find out what type of critter to spawn
CASE BasicCritterType `If it's a basic critter
FOR i = 0 to MaxCritters-1 `Let's cycle through all of the critters
IF Critters#(i,0) = 0 `If the critter is not currently active
Critters#(i,0) = 1 `Make it active
Critters#(i,1) = 10 `Set the health
Critters#(i,2) = Map.SpawnX `Set the current tile
Critters#(i,3) = Map.SpawnZ
Critters#(i,4) = Map.SpawnX*(Map.X/Map.SegX)+(Map.X/Map.SegX)/2 `Set the new position
Critters#(i,5) = Map.SpawnZ*(Map.Z/Map.SegZ)+(Map.Z/Map.SegZ)/2
Critters#(i,9) = 0.05 `Set the critter's speed
Critters#(i,10) = Critters#(i,4) `Set the target position to the current position so
Critters#(i,11) = Critters#(i,5) `the loop will update the pathfinding
Critters#(i,13) = 0
POSITION OBJECT Critters#(i,6),Critters#(i,4),0,Critters#(i,5) `Position the object
SHOW OBJECT Critters#(i,6) `Show the object
i = MaxCritters `Exit the loop
ENDIF
NEXT i
ENDCASE
ENDSELECT
ENDFUNCTION
`*************************
`UpdateCritters()
`*************************
FUNCTION UpdateCritters
FOR i = 0 to MaxCritters-1 `Loop through our critters
IF Critters#(i,0) = 1 `If we find one that is active
CritterArrayToObject(i) `Store the data in our Object so it's easier to manipulate
IF Critter.PosX# = Critter.TargetPosX# and Critter.PosZ# = Critter.TargetPosZ# `If the critter hits the target, let's update it's path for the next tile
UpdateCritterPath() `update the path
ENDIF
UpdateCritterMove() `Update the movement
CritterObjectToArray(i) `Store the data in the array.
ENDIF
NEXT i
ENDFUNCTION
`*************************
`UpdateCritterPath()
`*************************
FUNCTION UpdateCritterPath()
Critter.isBlocked = 0 `Set the critter to currently not blocked
FOR x = 0 to Map.SegX-1 `loop through our map array
FOR y = 0 to Map.SegZ-1
IF Map(x,y) = 3 `If the tile at x,y is a wall
SetSearchMap(x,y,1) `Set the search map to 1 (ie, can't be crossed)
ENDIF
IF TurretMap(x,y) <> 0 `If we have a turret on x,y (TurretMap > 0)
SetSearchMap(x,y,1) `Set the search map to 1 for this tile (can't be crossed)
ENDIF
NEXT y
NEXT x
FOR x = 0 to Map.SegX-1
SetSearchMap(x,Map.SegX,1) `Restrict access to our invisble tiles on the edge of the map
NEXT x
FOR y = 0 to Map.SegZ-1
SetSearchMap(Map.SegZ,y,1) `See above
NEXT y
SearchMapAStar8(0,Critter.TileX, Critter.TileZ, Map.GoalX, Map.GoalZ) `Now we create an 8 direction search map (8 directions means diagonal moves are allowed)
Critter.TargetTileX = GetSearchPathX(0,1) `Set the critter's target tile to the tile determined by the pathfinding function
Critter.TargetTileZ = GetSearchPathY(0,1) `See above
IF Critter.TargetTileX = -1 and Critter.TargetTileZ = -1 `The target tile will equal negative one if there is no path available
Critter.isBlocked = 1 `set the isBlocked to 1
Critter.TargetTileX = Map.SpawnX `The next goal is going to reset to the spawn
Critter.TargetTileZ = Map.SpawnZ `See above
Critter.TargetPosX# = Map.SpawnX*(Map.X/Map.SegX)+(Map.X/Map.SegX)/2 `get position of spawn as target
Critter.TargetPosZ# = Map.SpawnZ*(Map.Z/Map.SegZ)+(Map.X/Map.SegZ)/2 `See above
ELSE
Critter.TargetPosX# = Critter.TargetTileX*(Map.X/Map.SegX)+(Map.X/Map.SegX)/2 `Setup the critter's actual target position to move to (not the tile value, but 3d space coordinate)
Critter.TargetPosZ# = Critter.TargetTileZ*(Map.Z/Map.SegZ)+(Map.Z/Map.SegZ)/2 `See above
ENDIF
ENDFUNCTION
`*************************
`UpdateCritterMove()
`*************************
FUNCTION UpdateCritterMove()
GOALX = Critter.TargetTileX `Rename our variables to cut down on code size
GOALZ = Critter.TargetTileZ
GX# = Critter.TargetPosX#
GZ# = Critter.TargetPosZ#
CX# = Critter.PosX#
CZ# = Critter.PosZ#
IF ABS(CX#-GX#)<0.1 `If the critter's position is pretty close to the target
CX# = GX# `Make it the target position, this way the UpdateCritterPath() function will be called
ENDIF
IF ABS(CZ#-GZ#)<0.1
CZ# = GZ#
ENDIF
IF CZ# <> GZ# and CX# <> GX# `If we need to move on a diaganol
Speed# = Critter.Speed#/SQRT(2) `The speed is reduced by SQRT(2) because of the diaganol move
IF Critter.Affliction = 1 `If the critter is currently slowed, divide the speed by two
Speed# = Speed#/2
ENDIF
ELSE
Speed# = Critter.Speed# `Else, we're not moving in two directions, the speed is the same
IF Critter.Affliction = 1 `If slowed, divide the speed by tw
Speed# = Speed#/2
ENDIF
ENDIF
IF CZ# > GZ# `If our critter is above the goal, move it down
CZ# = CZ#-Speed#
ENDIF
IF CZ# < GZ# `If our critter is below the goal, move it up
CZ# = CZ#+Speed#
ENDIF
IF CX# > GX# `If our critter is to the right, let's move him left
CX# = CX#-Speed#
ENDIF
IF CX# < GX# `If our critter is to the left, let's move him right
CX# = CX#+Speed#
ENDIF
Critter.PosX# = CX# `Store our new positions
Critter.PosZ# = CZ# `Store our new positions
Critter.TileX = int(((Critter.PosX#-MATRIX POSITION X(1))/Map.X)*Map.SegX)
Critter.TileZ = int(((Critter.PosZ#-MATRIX POSITION Z(1))/Map.Z)*Map.SegZ)
POSITION OBJECT Critter.ObjectNum,Critter.PosX#,0,Critter.PosZ#
ENDFUNCTION
`*************************
`CritterArrayToObject()
`*************************
FUNCTION CritterArrayToObject(k)
Critter.Alive = Critters#(k,0)
Critter.Health = Critters#(k,1)
Critter.TileX = Critters#(k,2)
Critter.TileZ = Critters#(k,3)
Critter.PosX# = Critters#(k,4)
Critter.PosZ# = Critters#(k,5)
Critter.ObjectNum = Critters#(k,6)
Critter.TargetTileX = Critters#(k,7)
Critter.TargetTileZ = Critters#(k,8)
Critter.Speed# = Critters#(k,9)
Critter.TargetPosX# = Critters#(k,10)
Critter.TargetPosZ# = Critters#(k,11)
Critter.Affliction = Critters#(k,12)
Critter.isBlocked = Critters#(k,13)
ENDFUNCTION
`**************************
`CritterObjectToArray()
`**************************
FUNCTION CritterObjectToArray(k)
Critters#(k,0) = Critter.Alive
Critters#(k,1) = Critter.Health
Critters#(k,2) = Critter.TileX
Critters#(k,3) = Critter.TileZ
Critters#(k,4) = Critter.PosX#
Critters#(k,5) = Critter.PosZ#
Critters#(k,6) = Critter.ObjectNum
Critters#(k,7) = Critter.TargetTileX
Critters#(k,8) = Critter.TargetTileZ
Critters#(k,9) = Critter.Speed#
Critters#(k,10) = Critter.TargetPosX#
Critters#(k,11) = Critter.TargetPosZ#
Critters#(k,12) = Critter.Affliction
Critters#(k,13) = Critter.isBlocked
ENDFUNCTION
Excuse me posting it like this but I don't have time right now to write it how I had it earlier. I'm going to go through each of the functions and explain what they do. First, PrepareCritters() simply loads and creates the physical critter object. Also, it clones this object as many times as we have MaxCritters set to. You'll notice immediately a jump in loading time for our game, that is because loading and clone objects requires some time and memory. Next we have our SpawnCritter() function. This is very important as it positions and actives a fresh critter at the spawn point. Go back to your UpdateSpawnList() function and uncomment the SpawnCritter() line now that we have it written.
Moving on we get to our UpdateCritters() function. This will be called every game loop and updates the positions and pathfinding of each active critter (notice the FOR loop searching for 1 at each (i,0) element). Also important to notice is that we will only be updating our path for each critter when the critter reaches its destination. This will cut down on processor overhead from the pathfinding routines, plus, it's just not necessary to be constantly updating paths.
Our UpdateCritterPath() function is where the real pathfinding magic happens. Look through the comments for explanation on what is going on. Then we have the UpdateCritterMove() function. The code should be easy to understand, read the comments. Essentially we are just adjusting the critter's position based on the difference between it and the target position. The distance that it moves is based on the speed member. The two final functions simply swap data between the type we created and the array storing the critters. You'll notice these are called in our UpdateCritters() function just before any logic is done and then after. That way we can easily manipulate data and then throw it back into our master critter array to store it. Fairly simple.
Ok, let's step back into our Main.dba file to adjust some things and add these new functions to our game loop. First, we added a new member to our Critter type. Go to the critter type and add the following line to it.
isBlocked as integer `If set to 1, the critter can't move (no path found)
This will keep track of the critter's ability to move. Now replace your current Game Loop Preparation heading and game loop with the following code.
`***************************
`Game Loop Preparation
`***************************
LoadMedia() `This function loads all the media needed for the game
LoadMap() `Load the map file
CreateMap() `This function creates the matrix for our map
PrepareCritters() `Prepare our critters for the game
AppendToSpawnList(BasicCritterType,2,3000)
`***************************
`Pathfinding initialization
`***************************
CreateSearchMap(Map.X, Map.Z)
CreateSearchPathLists(0)
`********************
`GAME LOOP GAME LOOP
`********************
DO
UpdateMouse() `1. Update the mouse's coordinates and tile values
UpdateSpawnList()
UpdateCritters()
ShowDebugInfo()
SYNC `Draw the screen
LOOP
We are calling our PrepareCritters() function to load our critter objects and added 2 critters to our queue. Then we are setting up our pathfinding map. And finally we add the update calls to the game loop. Now we are doing plenty of calculations, but our game loop looks nice and tidy. Go ahead and run it, you should see two little critters circling about your map, avoiding the walls (grey tiles) and heading for the goal point. Once they get to the goal point they will return to the spawn and do it all over again. We'll add some logic later to deal with this and simple destroy the critter when they reach the end. Want to make it even more crazy? On your AppendToSpawnList() function, make it spawn more critters with a shorter interval. See how easy it is to adjust settings like these? Eventually this will be controlled by the map file, but, for now, we'll do it manually.
If your code doesn't compile, please check the top link and download the full source code. If you can find any errors in my tutorial, please tell me and I'll fix them as soon as possible. I feel I may be leaving some important code out after messing up my last post.
