This week I will talk a bit about our pathfinding. (Warning: Confusing)
There are a couple of different pathfinding algorithms out there, on the internet. There are Breath-first, Best-first, Dijkstra, A*(A-star), etc. Almost everyone, on different forums, suggest A* as pathfinding algorithm for most games. It is reasonable fast in most instances, even though some of the others were quicker in some scenarios.
A*, like most other algorithms, needs a tile based system to search through.
Each Tile, or Cell, is given three values: F, G and H.
- G is the cost to move from the starting Cell to this cell.
- H is the guessed cost to move from this Cell to the goal, as if there was no collision in between.
- F is the sum of G and H. (G + H), the approximated cost to move from start to finish through that cell.
Each cell also holds a pointer that points to its “parent”, which is the cell that put the active cell on the open list.
It uses three lists to store cells in: Open, Closed and Final.
- In Closed all the checked cells are stored, so we don’t check the same cell more than once.
- In Open all the cells still to check are stored.
- In Final we store the final path, when we have found our goal. We get the path by backtracking from the goal and go through all the “parent” cells until we are at the first cell.
Each iteration of the algorithm takes the cell with the lowest F-value in the Open list, and puts it on the Closed list. Then it checks all the surrounding cells that is not already on the Closed list and gives them values. It one of the cells is already on the Open list, it checks if the new F-value is smaller than the last. If it is, it changes the parent of that cell so it points to the new, cheaper, parent.
When the goal cell is finally found in the Open list, we backtrack from there. Going from parent to parent, storing each cell and when we are back at the start cell we have the shortest path.
The picture shows an example of A*. The Green tile is Start, Red is Goal, Gray are walls, Blue is on Closed list, Green on Open list and the yellow line shows the path we got at the end.
Unlike the other Escape-concept groups, we chose not to have tile based. The reason for this is that we felt that tiles are too limiting when it comes to placement of walls and furniture’s. We wished to have more freedom, to rotate and place assets “however” we wanted, to give each room a unique feel.
Because of this I had to simulate a grid to use A*, otherwise, each pixel had to represent the tiles, and that would be too many squares to search through. The grid is stored in:
- std::vector<std::vector<bool>>
Which is vectors in vector. The outer vector is the tiles Y-position and the inner its X-position.
Instead I divided the map into equal sized squares and checked each square for collision. If collision was detected I put its bool-value to false, otherwise true.
Then, to see if the grid worked I drew the grid on top of the level ingame, and each walkable tile was colored red and the unwalkable teal.
As the picture shows, it looks like it is working.
I hope I made myself clear, but I’m afraid that would be really wishful thinking…
Spörk 
Great work!
It’s a nice thing reading about someone else that have been working on A* and to read their thoughts around it. It seems like you managed to grasp the principles around it in a very good manner, and also that you managed to explain them in a good way.
It’s also interesting to read about how you split up your map in-game and converted it into tiles. One interesting part would’ve been to see how a path looked like in-game and to see it in action a little more.
One interesting call you’ve seemed to make is to ignore if diagonal nodes are passable or not. When I worked on my path finding I didn’t make it possible to go towards tiles if you’d have to cross the edge of one that was unpassable, but here it seems like you didn’t apply that rule. That might be a rule for you to consider adding, otherwise the path finding might lead the characters to walk through corners and such.
Also, it would’ve been interesting to hear about how the way you are splitting up the tiles have affected the performance of the loading and runtime of the game.
Altogether this was a very well composed post with a lot of interesting details, keep it up!
First of, I think it takes about one second to load the level as it is now, in Debug.
I totally forgot to check if diagonal movement was blocked, thanks for pointing it out. I have now changed the code so that if either of the two connecting to “from” and “to” cells is unwalkable, that movement is impossible. 🙂