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


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, who need to know where they are 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 people, staircases) and the points where these points connect (Ground floor staircase connects with 2nd floor staircase in X48 Y4, for example), more or less as the image below:



IstartedmycodebasedonavariantoftheDijkstraalgorithmcalled A-Star (A *) , which is basically the shorter path problem with some optimizations. (Curiosity: Several games implement variants of A * to determine the route of characters on a map.)






Disclaimer: Original isometric image of .

asked by anonymous 12.09.2014 / 22:41

3 answers


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 *.

12.09.2014 / 23:03

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.

13.09.2014 / 00:02

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!)

13.09.2014 / 23:27