Pathfinding across multiple levels

Question

For a final school project, I have implemented an A* algorithm for pathfinding across a tile graph. So far, it has worked far surpassing my expectations. However now I'm in the process of adding a bit more complexity to the level and I am not sure that tile graphs will cut it any longer.

I would like to add multiple floors, but for the sake of simplicity I will just create two floors. At the present moment, I have a 2D array of Nodes that represent the single floor in a level. I don't think this will be scalable any more to anything besides one floor. I am proposing a method to find paths across two floors using multiple clusters containing nodes for different sections of the map where some nodes are flagged as exit nodes that will lead to other clusters. Moreover exit nodes will also be marked for the ones that lead up stairs to a second floor. The heuristic cost of moving from one floor to another will be higher than if an agent was to simply move across the same level.

I'm thinking if an agent is trying to traverse from one path to the next, it first checks to see if the start node and exit node are on the same floor. If so, then the cost is simply the euclidean distance, otherwise it tries to find the path to the exit node on the cluster it's currently on, compute the path to that node, then compute the cost to the next exit node within that same cluster. Repeat ad nauseam.

So as a visual representation of this, this is a terrible representation of a floor plan. The only highlighted nodes are the exit nodes

This is what I could come up with. Is there any other way besides searching through a ton of tiles and clustering? So far on a tile of 100X100 performance seems to be ok and not an issue. I have heard of using nav meshes, but I'm not entirely sure how to implement them in my project. Since this class is an advanced game development class, if we do use nav meshes, we need to create and implement our own and not use Unity's built in navmesh

Answer 1

Add a meta graph that explains the route between floor entrances / exits from floor x to floor y. The vertices are entrances / exits, the edge length is the path between an entrance A and an exit B in tiles on floor z. Each entrance / exit is connected by such weighted edges to all entrances and exits that are accessible from it through the floor(s) it's on.

Use your existing tile-graph A* per floor to find a path from an entrance to a desired exit. The path length will serve as the edge weight on the meta graph.

The meta graph will be used to quickly know, which entrances and exits need to be accessed but it's edges and their weights should be computed in advance. It explains through which floors you need to travel to get from floor x to floor b. The meta graph uses actual vertices and not tiles, in the sense that you need a list of neighbors for each vertex. A floor is not interesting as an object and is only used to connect it's entrances and exits with edges computed by the tile based path on each floor between them.

Remember that if an area on some floor is blocked, that floor should be logically divided to several sub-floors as entrances in one blocked sub-floor, do not allow direct access to other sub-floors.

Once you use the meta graph to figure out which floors or sub-floors you need to travel, you simply use the same tile based path-finding on each floor to get from entrance x to exit y.