Manipulating maps.

Question

Given a set of floorplans (in Autocad, svg, or whatever format need be...), I would like to programatically generate directions from point A to point B. Basically I would like to say: "How do I get from room 101 to room 143?" (or for triple bonus points, from room 101 to room 323). Anyone have any ideas how to go about this? I am pretty language agnostic at this point, although I know C(++), Erlang, PHP and Python the best. I do realize this is a tall order.

Thanks!

Answer 1

The general term for this is pathfinding. The problem has been studied extensively for 2D diagrams. I would break apart the problem into these sections:

1. Convert CAD model of floor into a simple model of rooms, doors, halways.
2. Run a pathfinding algorithm on that floor from source to destination, with constraints for human motion.
3. Convert the results to text directions (turn right, go straight, etc.). The addition of landmarks may be helpful

For multiple floors, you could just use the one floor implementation and go from (e.g.) 104 to the 1st floor stairs, 3rd floor stairs to 311. The conversion of the CAD drawing to a semantically useful format seems like the most difficult step to me.

Answer 2

read about the traveling salesman algorithm there are an infinite number of paths from point A to point B. are you looking for the shortest? what is your means of transport? can you fly or are you forced to walk or drive? these are factors in determining a solution.

Answer 3

I know you want to use php, but i recommend python and networkx. you have to convert your building into a set of (origin, Destination, cost) and then run either a TSP (as mentioned by still standing) or A* or Dijkstra