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