Pathfinding

I worked on a 3D first person shooter and created an algorithm that creates graphs for the level generation. The levels in this game were generated with bitmaps and are attached to each other. In order to have the enemies navigate the rooms correctly, I made an algorithm that turns the room into a graph.

Platform: 

PC

Tools used:

Ogre3D

Duration:

Finished

Team Size:

7 (this part was just me)

Role:

Game designer and programmer

This algorithm consists of two parts. Creating the nodes and linking them to each other.
In order to see whether a tile is valid and a node needs to be created. I check all tiles around the tile and check them against some conditions I created. If any of these conditions are true the tile is valid and a node gets created for it.

Create nodes (You only check the tile in the middle of a 3x3 grid)
1. Pick a tile in the room that has not been checked
2. If it is not empty (empty and enemy tile)go back to 1
3. If either of the conditions below are true place a node
a. If there are 1 or more diagonal adjacent and no horizontal/vertical adjacent.
b. If there are 3 or 4 diagonal adjacents and only 1 horizontal/vertical
c. If there are 1 or 2 diagonal adjacents and only 1 horizontal/vertical adjacent and not all diagonals have a neighbour
d. If there are 2 horizontal/vertical adjacent and 1 of the diagonal adjacent is lonely (No horizontal/vertical tiles)
4. If there are tiles left go back to 1

In order to check whether you can reach one node from another, I use an altered version of the Bresenham’s line drawing algorithm. When I created this I made one assumption and that is that the character that uses the graph is around the same size as one tile. So what happens is that you created four lines, one from the top middle of the tile, one from the bottom middle, one from the middle left and one from the middle right. Then I check in steps of one for both x and y direction what the other coordinate is. Then I round it to the closest integer and you check if the tile with that coordinate is walkable or not. If all tiles are walkable I create link between the two nodes.

If you’ve applied these steps to the room then you should have a graph that ensures every tile is reachable by one or more nodes.