This week’s most of my efforts where focused in adding more content into the game. More specifically I worked on adding a new dungeon into the overworld. Here is a picture of the inside layout of a future dungeon:
So adding the model and the collisions into the game was pretty easy and fast because of groundwork that was done a few months before. (This “groundwork” was porting the engine to use bulletphysics). Here is a picture of the dungeon ingame:
Instead, the development bottleneck was making the AI work smoothly. Currently the AI for the mobs uses AStar which is an algorithm for finding a shortest path from a grid of points. This works fine in the overworld terrain however when mobs are inside structures there are too many grid points to sample so the AI becames too slow to do anything.
My first idea for solving this issue was to use navigation meshes this would allow me to clearly define “walkable zones” that the AI can traverse. Then I would build a graph out of those “walkable zones” and use it as waypoints. [0] Here is an ingame picture:
Now finding shortests paths isn’t something very hard to do since it’s well explored topic. For solving this particular problem I used Dijkstra’s algorithm
Here is a simple explanation from wikipedia:
Suppose you would like to find the shortest path between two intersections on a city map: a starting point and a destination. Dijkstra’s algorithm initially marks the distance (from the starting point) to every other intersection on the map with infinity. This is done not to imply that there is an infinite distance, but to note that those intersections have not been visited yet. Some variants of this method leave the intersections’ distances unlabeled. Now select the current intersection at each iteration. For the first iteration, the current intersection will be the starting point, and the distance to it (the intersection’s label) will be zero. For subsequent iterations (after the first), the current intersection will be a closest unvisited intersection to the starting point (this will be easy to find).
I managed to implement it and now the AI is working correctly inside the buildings.
With nothing more to show I will end this week’s post :)
Notes:
[0] This is basically applying AStar but on graph thats not built in realtime.