Software Inc., as you can imagine by looking at the pictures, is a grid based game. As such, it was really easy to decide on using a gridbased pathfinding algorithm. My problem was that I wanted multiple floors and if I just made a giant grid for each floor, if I then wanted to go from one building on the fifth floor to another building on the tenth, I would have to doa lot of testing to see which floor led where while also navigating each floor.
My solution was to implement a layered pathfinding algorithm, which probably seems completely obvious to you, but bear with me. Instead of measuring how far away something is geometrically when using a pathfinding algorithm we can use any definition of distance that we desire, we might say, “What is the distance between happiness and cake?”, as long as we can figure out some way to actually measure that distance we can find the shortest path from A to B (it is direct in this case).
What I did was to ask: “What is shortest amount of doors/elevators to traverse to get from room A to room B?”, notice the distance is not in meters or feet, but in number of doors and elevators between room A and room B. Then, for each room I want to traverse to get from A to B, I ask: “What is the shortest distance from door A to door B?”, which I work out by giving every room its own little grid for the pathfinding algorithm. In the end, I append all the paths found in to one big path, piece of cake. To make people avoid rooms I simply ask, before pathfinding through a door: “Does this room belong to a team, and if so, is it my team?”. Both of these algorithms are implemented using A*, which I think is pretty neat.
In conclusion, we have rooms which connect to each other by gateways, i.e. doors and elevators, and rooms are grids that can be traversed. To put the icing on the cake, I make a giant invisible room on the ground floor that connects all rooms to the outside, because logic.
