Algorithm for faster route calculation between two points in parallel Cartesian layers (3D)

A * is what is commonly used, but there is a family of algorithms called D * which considers that the calculation might vary from step to step, but this would be interesting if the path was not constant, as I believe is the case of your reality.

There is even a simpler version to be implemented called D * Lite , which is quite different of the original D *.

In a very simple way, connecting the floors by an edge, creating a kind of three-dimensional graph seems to me the most appropriate solution.

The algorithm, however, must be customized under certain conditions. For example, the disabled setting would place an infinite cost on stairs and other non-accessible ways so that they would never be selected.

The issue of avoiding elevators at peak times could be another configuration at the user's expense. Already an option to "walk at maximum X floors" would be a bit more labor intensive, requiring you to store an additional state for each route.

And for the thing to work well in practice, it would be ideal to have average lifts waiting time metrics at each time.

The general idea is that the weights of each edge, that is, of walking each stretch, would have to be based on a dynamic function that considers the user settings and also traffic information of that stretch.

However, depending on the number of nodes and the system load, this may be inefficient. In this case, it would be possible to define sub-optimal routes, for example by pre-calculating for each floor the shortest distance between a certain point and the nearest stairway or elevator, then joining this information to select a global.

Anyway, these are some ideas. They do not answer the question in a conclusive or mathematical way (and are too big for comment), but I hope they can generate new ideas that will enhance their current solution.

Disclaimer : This is not a answer per se , just a compilation of the answers / possibilities so far. I imagine the final result will be a combination of the suggestions presented.

A * 3D (@bfavaretto)

A possible implementation of this algorithm would map the points of contact between floors, implemented the 'slabs' as described by @bacco. The height of each layer can be set to 1, since we will not use jetpacks, thus avoiding the horizontal costing.

In the picture, red would indicate elevators and blue, staircases; green, walls (insurmountable objects) and white the navigational space. (I hope this color combination is valid for color blind!)