Android - Indoor Pathfinding suggestions

Question

I'm working currently on a indoor pathfinding project. You can imagine it like this: enter image description here

In my application i have two searchviews for a start room and a destination room, which i've already implemented. After entering the two rooms the application should start an algorithm, for example A*, to calculate the shortest path between these two rooms. Suddenly the user can see a drawn line between those two rooms.

Do you have any suggestions on how i can do this to implement an A* algorithm on Android like the picture shows?

Answer 1

A* algorithm rely on graph theory.

So, first you should plot your room as a graph (each room/floor is a vertex, or node, and each door is an edge). I suggest you use well-known implementations for that (here is an example).

Based on your schema, your graph should look like this

Keep a HashMap (or something else) to keep track of which room is mapped to which node, as well as which corridor is linked to which edge.

Then, when your use calls for a path, calculate your A* algorithm. The example I linked to you will look something like this

List<Node> path = aStar.findPath();

Remap back the List of nodes to a list of Rooms and show it to your user.

NB: If you want to make it very clean, you could re-write the AStar.java as to accept a list of Room, and make it spit out another list of Room.