My first A*pathfinding

This week my job has been to create a pathfinding system for our game Green Warden. For tower-defence-like game it needs a pathfinding system thats not just functional but also cheap for the processor to handle. As some probably know a tower-defence game could have hundreds of enemies on screen at the same time searching their way through a maze and obstacles. Sometimes the enemies must also be able to interrupt their current path to attack nearby towers and then, if they survived the tower of course, they return to the path towards the main destination.

There are certainly different methods to tackle this problem, and maybe some techniques works better for some projects than other. For tower-defence type games, where all foes on screen share the same target on the map (in most cases in tower-defences), there are for example one method to make all units share just one pathsystem that covers the whole map instead of having every unit search for unique paths themselves.. I’ll mention more of that later in this text.

Experiencewise, I’ve never coded any pathfinding or AI before. Last weekend I started looking around on internet for good information about this subject. Quickly I stumbled upon a technique called ”A*(a-star)-pathfinding”. At first was difficult to grasp.. As a half-novice programmer I can take some time to find tutorials on the internet thats actually easy to understand.. Actually I found a video on youtube that explained A*pathfinding in a way that made total sense to me. Here’s a link to that for those who are interested: https://www.youtube.com/watch?v=-L-WgKMFuhE

I was lucky this too because our programming-teacher just so happened to talk to us students about the A* methology.

Since then I’ve been working to create a pathfinding that we can use in our project, for now.

Sooo. the result,

For the type of pathfinding I’m doing I need a grid or tilemap. I think posted 2 weeks ago explaining about a tilemap I made. Since that post it has been some changes and upgrades to make the tilemap more easy to use and optimized. I’ll explain that tilemap quickly: first you create the whole tilemap with specific number of tiles and the size of each tile in pixels. Then you can access each tile by index, position or coordinate. Each tile has the values ”state”(can be ‘true’ or ‘false’), position and index. Every tile with the ”state”-value = ‘true’ tells the tile is occupied by something, tower, tree, obstacle, whatever. Every tile with the state ‘false’ means its empty from stuff, and therefor passable,

The pathfinding has to check each tile on the tilemap whether the state of the tile is ‘true’ or ‘false’; ”obstacle” or ”empty space”. The code for my Pathfinding is written seperately from the Tilemap, so the pathfinding has to now what states each tile has on the map, position and coordinate of each tile and etc. After that comes all the math and logics for the pathfinder to generate a path from point A to B on the map.

I made a small program to test and debug the code. It consist of a tilemap with obstacles (in this case some trees) and the code for pathfinding. You can chose were the start and the goal should be with an easy function ”set_start position” & ”set_goal position”.

(Btw, I’m not going too much into the technical details so just enjoy the pictures if you want)

Each time I press a key on the keyboard the character moves one tile-step on the calculated path.

This picture may be confusing, but it’s a result of the calculation from the example above written to a text-file. I’ll do my best to explain whats happening short and concise.

The @:s represent the trees, which are nonpassable. The dots represent tiles that has been checked as ”maybe a possible path to our goal?”. Why is it checking AWAY from goal?? To be honest, I’m not 100% sure, but I think it’s just a consequense for the of alghorithm that A* uses. I need to read more about that however. The O:s places that’s passable but not checked because there’s a tile somewhere else that’s closer to the goal destination… I hope I didn’t make you more confused! Please check that youtube-link I mentioned before if so..

Heres an example of a much more complex route. What’s nice is no matter how complex the path is the principle falls the same as the simple example above. It checks all tiles that passable with no tree on it and prioritize tiles currently closest to the goal till it finally found the goal tile. Of course, with this map the pathfinding system has to check more tiles but as soon as the pathfinding algorithm works properly it pretty much do all the work by itself.

I said before that there’s not just one pathfinding techniques out there. Now it looks like were going to use this pathfinding I made for the project as a temporary solution, but we will probably come to a point where we have to optimize it so it works well with lots of enemies on screen at the same time. I mentioned, instead of having every enemy calculate a unique path for themselves you can instead calculate a ”global” path for the whole map that starts from the target destination which all enemies share. More explanation here:

http://www.redblobgames.com/pathfinding/tower-defense/

The goal from now on is to focus on other stuff that must be done for Green Warden. Next week I’ll start making all sounds as I’m responsible for that. I’ll probably write about that next week too.

See ya for now!

// Johannes

fixed TileMap

The game I’m working on, as a programmer, is (temporary called) Green Warden. This game is sort of a Tower Defence where the player runs around with an avatar, planting seeds that grow up to projectile-shooting trees (towers) against army of lumberjacks (and flamethrowers).

When the players are building their trees/towers we wanted each tower to fit in in a fixed grid of tiles; like chess, where only one piece can be place on one tile.

I wrote a tile map class with three main components: dimensions for each tile (in this case 32x32px), width and height for the whole map (i.e. 30tiles x 20tiles) and an array of bool values where each element of the array represent a tile on the whole tile map. The idea is, when an object is created on a tile, that tile recieves the value ‘true’ so other objects cannot be placed there again, and when that object is destroyed that tile returns to the value ‘false’. This method is hopefully applicable for our oncoming pathfinding too, where, for example, an enemy is looking for empty tiles that has the value ‘false’ which to set a path to walk. All tiles that has value ‘true’ is translated to a non-walkable area for the enemies.

In short sense, tiles where the player builds a tower, that tile should block enemies paths and the player.

When the player places a tower I had to figure out a way to calculate so the tower gets a fixed position one of the tiles on the tile map. The player could be on the position 197×579 on the screen and place a tower and that tower should fit in to a correct position on the tile map.

On this picture I used my mouse to place out the trees. You can see that every tree is positioned on a even order with each tile.

The calculation is pretty simple:

sf::Vector2i TileMap::getFixedPosition(sf::Vector2i point)

{

            sf::Vector2i fixedPos;

            fixedPos.x = (point.x / m_tilewidth) * m_tilewidth;

            fixedPos.y = (point.y / m_tileheight) * m_tileheight;

            return fixedPos;

}

where ‘m_tilewidth’ and ‘m_tileheight’ has both the value 64 in this example.

Till next time, adios!