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

Question

I’m working on a solution that involves determining the least effort route between two points in a building. (Imagine students on their first day of university, and they need to know where it is and how to get to a given classroom in a building, or how to get from the current classroom to the next class.)

Basically I have a Cartesian structure where each floor is mapped. I also have indicators of access points (doors, ramps for disabled, stairs) and the points where these points connect (Staircase of the Ground Floor connects with staircase of the 2nd floor in X48 Y4, for example), more or less like the image below:

Where cyan indicates a staircase, and odd-blue elevators, among other markers not displayed.

(For color-blind people, my sincere apologies and some additional information: the staircases are located at the top right of the maps; the elevators, near the center.)

I got my code based on a variant of the Dijkstra algorithm called A-Star (A*), which is basically the shortest path problem with some optimizations. (Curiosity: Several games implement variants of A* to determine the character route on a map.)

A* is perfect for determining routes on the same floor, but I have to take into account the various floors, each with a different layout.

Question

Is there any more appropriate way to solve this problem?

_{Or, more clearly (thanks bfavaretto),}

Given the additional factor of N floors, is there any algorithm that is more indicated than A*?

_{Disclaimer:
Original isometric image of Dougillustrations.com.}

Answer 1

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 according to certain conditions. For example, the handicapped configuration would put an infinite cost on the stairs and other roads without accessibility so that these were never selected.

The issue of avoiding elevators at peak times could be another configuration in charge of the user. Already an option to "ride at maximum X floors" would be a little more laborious, requiring storing an additional state for each route.

And for the thing to work well in practice, it would be ideal to have average waiting time metrics of the lifts 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 considered the user’s settings and also traffic information of that stretch.

However, depending on the amount of nodes and the system usage load, this can 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 given point and the nearest staircase or elevator, then gathering this information to select a global one.

Anyway, these are some ideas. They do not answer conclusively or mathematically the question (and they are too big for comments), but I hope they can generate new ideas that enhance your current solution.

Answer 2

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

A* 3D (@bfavaretto)

A possible implementation of this algorithm would map the contact points between the 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 cost calculation.

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

D* / D* Lite (@Gypsy)

This is very interesting for allowing composite cost calculations of time. Some possible situations:

• The point to be reached is on one floor superior. The initial cost of the lift is 10+2 per floor. The cost of stairs is 5 initially, but 10 is added to each floor to be covered (+15, +25, etc.) Going up 1 floor by stairs may be better than waiting for the lift, but it is not the case if you need to climb 10.
• The point to be reached is on one floor inferior. Cost of lift: 10+2 per floor. Cost of stairs: 5+3 per floor (It is not so tiring to go down a ladder, but it takes time.)

Optimizations (@utluiz)

Several good suggestions here, some not directly related to the question but can help create a much better solution.

• Information on the presence of some physical disability in registered users is present, and route optimization by eliminating stairs is possible. A similar configuration can be offered to public users via selection in the interface.

• It is possible to use Opencv to analyze noise on images of the cameras that observe the elevators, entrances and staircases and to trace a histogram per hour. The result could be a cost multiplier.

• One possibility of optimizing this algorithm is to define zones within each floor that have only one possible exit route, and to maintain a cost cache for common predetermined points (access points, etc.) that would save a little bit of the Workload.

Answer 3

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

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