Algorithmic solution for building navigation using A* and Dijkstra

Nowadays, orientation within large buildings can be a challenge, especially for visitors who are unfamiliar with the environment.

In this article, we will explore an algorithmic solution that is useful for those businesses and organizations that need an application capable of guiding visitors within a large space or building, from the entrance to specific rooms or locations using navigation algorithms such as A* and Dijkstra.

Client Challenge

The client faced a common problem: new visitors arriving at their building and needing guidance to find specific rooms or other facilities. The solution had to be efficient and easy to use, allowing visitors to scan a QR code upon entering and receive precise instructions on how to reach their destination.

The use of images with predefined routes from various points of origin to different destinations is a solution that is a priori simple to implement but not scalable. It is advisable to use more automatic and efficient alternatives, which adapt to any size of surface and multiple routes.

Solución Algorítmica para la Navegación en Edificios Usando A* y Dijkstra

Implementation of Algorithm A*

The A* algorithm is widely used in the video game industry to find paths in complex maps. This algorithm combines least-cost-first search and heuristic search, which allows finding the shortest path efficiently.

Here we detail how we implemented it to solve our client’s problem:

  1. Map Conversion: We transformed the building plan into a matrix of 1s and 0s, where 1 represents passable paths and 0 represents walls or inaccessible areas.
  2. Origin and Destination Identification: We assigned specific coordinates for each room and points of interest within the building.
  3. Path Finding: Using A*, the algorithm searches for the shortest path from the origin point to the destination, avoiding obstacles represented by the 0s in the matrix.

Advantages of A*

  • Efficiency: A* is fast and efficient in finding the shortest path, especially on maps with clearly defined areas.
  • Flexibility: It easily allows the incorporation of new rules and restrictions, such as avoiding stairs or using elevators.

Comparison with Dijkstra Algorithm

We also evaluated the Dijkstra algorithm, known to always find the shortest path but at a cost of increased processing time due to its exhaustiveness. While A* can provide fast and adequate solutions in most cases, Dijkstra guarantees the optimal path, albeit at a slower speed.

When to use Dijkstra

Dijkstra can be used in situations where shortest path accuracy is critical, and computation time is not a severe constraint. This can be particularly useful in buildings with complex configurations or multiple levels.

Results and Benefits

The final implementation allowed visitors to scan a QR code that indicated their current location and provided visual directions to their destination. This solution also included the option to select whether they wanted to use stairs or elevators, providing alternative routes based on the user’s preferences.

Potential Use Cases

  • University campuses: Facilitates navigation for students and visitors within large campuses.
  • Shopping malls: Helps shoppers find specific stores, ATMs, and other services.
  • Hospitals: Enables patients and visitors to find medical departments, waiting rooms, and other critical services.
  • Large crowded events or hotel complexes: In the end, any sporting event or complex space that hosts crowds that have to move through different areas are situations where these technologies can help provide a better user experience.

The combination of A* and Dijkstra algorithms allows us to create an efficient and flexible solution for in-building navigation. This solution not only improves the user experience, but can also be adapted to various environments and specific customer needs.

Implementing advanced technologies such as these search algorithms not only solves logistical problems, but also opens up new opportunities to improve usability and accessibility in large and complex spaces.

 

We hope this article has provided a clear view of how these algorithms can be applied to improve orientation and navigation within buildings. If you are interested in implementing a similar solution in your organization, please do not hesitate to contact us.

For more details, you can contact us at Info@bravent.net