I recently have been involved with a big hospital project and it occured to me that a floor plan path finding application would be a nice tool inside a complex facility like hospital. It would be a great help for new employees.
I am thinking about drawing waypoint nodes and connecting edge lines into a new layer and dumping contents of the layer as JSON data. I should be able to parse data into graph. Floor plan could be exported as SVG and as it’s XML based, path route visualisation data could be added programmatically.
bonus points for using the camera on a phone to recognize landmarks and help direct you.
oooh, i know how to make navigating theme parks like Animal Kingdom easier…
Path finding is not the problem, 8th supports a ‘Graph’ data type and I already have some game code that builds a graph from grid map and does path finding.
Parsing exported JSON data from a set of large DWG files, building a graph from the data and manipulating SVG data on the fly to visually display the route is the actual challenge.
How is that reinventing the wheel? I don’t know any ready made solutions that offer path finding directly from CAD drawing.
I would like to know what data structure you would use other than graph for finding the shortest route between network of nodes? There are hundreds of rooms and multiple floors.
Really absurd to bloat an app with precalculated junk when pathfinding can be done in real time.
That is really simple. Single path when in the same floor. If not, one path to the closest elevator that reaches the destination floor, and another path from the elevator to the destination.
There are hundres of game tutorials on line for this. Unles it is only a stunt to use the ‘Graph’ data type in 8th…
You really don’t get it? With graph the path finding can be done in realtime, just like it would be done with a simple grid map! The process and path finding algorithms that can be used are exactly the same, you traverse neigboring nodes and connected edges between nodes give you the cost.
Correct, there are free LibreDWG tools that can export DWG files as JSON data. I plan to draw node points and edge lines that connect nodes into a new layer and export just the contents of that layer as JSON. That should help simplify parsing the nodes and edges from JSON data.
Small hint from somebody has written such application before long time: you can convert the DWG to openstreetmap format and then use simple a navigation lib to provide navigation to all targets you want to. Simply. Why? While there are several algs for openstreetmap mapping which are providing exactly this. Then you have: start position, searched end position and the way conditions you provided and setted for the algorithm. Every other solution is burning time and money.
Graph needs just node and edge lists. I don’t think, I would benefit from using OpenStreetMap data format. I also need to write SVG output code and learning OpenStreetMap data format would take extra time.
Your totally right, I have no clue why you want to reinvent the wheel and make it triangular. Maybe Im missing something
An hour on xojo without Graph data types, JSON, svg, etc, etc. Works on multiple floors, with hundreds of rooms, actually, can work with thousands of points if you want to inlcude point to point directions (bed to bed, any table in the cafeteria, etc)
Sure in the end is graph theory, but you dont need to use/store actual graphs, as @mikey said, just a little linear algebra.
@MGD yes. But you can improve that with a jump point search.
With this as a base, it takes another half hour to add Weighted Terrain Costs to make the path to avoid some areas or even better, use different privileges to create paths for public, staff, restricted staff, etc. Something that looks impractical with your idea.
I am not making it triangular. Navigation data is just stored as node and edge lists instead of grid map. It takes a lot less space to only store waypoint nodes and edge lists than use grid maps. Also, edges can be weighted and directional and it’s all handled automatically. Another big bonus is that the whole building with multiple floors becomes just one big network of nodes.
