{"id":49297,"date":"2024-06-21T07:35:24","date_gmt":"2024-06-21T07:35:24","guid":{"rendered":"https:\/\/www.bravent.net\/?p=49297"},"modified":"2024-06-21T07:46:17","modified_gmt":"2024-06-21T07:46:17","slug":"algorithmic-solution-for-building-navigation-using-a-and-dijkstra","status":"publish","type":"post","link":"https:\/\/www.bravent.net\/en\/news\/algorithmic-solution-for-building-navigation-using-a-and-dijkstra","title":{"rendered":"Algorithmic solution for building navigation using A* and Dijkstra"},"content":{"rendered":"

Nowadays, orientation within large buildings can be a challenge, especially for visitors who are unfamiliar with the environment.<\/p>\n

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.<\/p>\n<\/div>

Client Challenge<\/h2>\n

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.<\/p>\n

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.<\/p>\n<\/div>[vc_single_image image=”49304″ img_size=”full” alignment=”center”]

Implementation of Algorithm A*<\/h2>\n

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.<\/p>\n

Here we detail how we implemented it to solve our client’s problem:<\/p>\n

    \n
  1. Map Conversion:<\/strong> We transformed the building plan into a matrix of 1s and 0s, where 1 represents passable paths and 0 represents walls or inaccessible areas.<\/li>\n
  2. Origin and Destination Identification:<\/strong> We assigned specific coordinates for each room and points of interest within the building.<\/li>\n
  3. Path Finding:<\/strong> 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.<\/li>\n<\/ol>\n<\/div>

    Advantages of A*<\/h2>\n