escape route (distance around several corners)

Hi to all grasshopper experts

following problem is what i'm dealing with at the moment:

it is about escape routes in a complex ground-plan.

from each point in the building, anyone should reach one of the exit points in 40 meters.

to simulate this situation (set the exit point, then test if any point is in the radius), i'm always drawing this scheme:

the blue surface is including each point that is reachable in 40m.

Now i'm searching a tool that could help me doing that more efficiently.

I tried with isovist (doesn't work around the corner), i'm thinking about using kangaroo (no idea if it has the possibility to simulate that, because i do not know it enough).

But maybe i'm completely on the wrong way.

Can anyone give me an advice?

Thanks a lot!

Replies to This Discussion

Permalink Reply by Danny Boyes on October 30, 2013 at 8:28am

Hi Jonas,

You could use Guilio's Shortest Walk Component.

Basically I made a mesh of the floor plan minus the walls and then calculated the shortest path to the exits

Attachments:

ShortestEscapeRoutes.gh, 48 KB
CorrectConnections.png, 109 KB

Permalink Reply by Danny Boyes on October 30, 2013 at 8:33am

Also if you Graft the Starting Point Input you can have multiple positions with multiple exits

Permalink Reply by Danny Boyes on October 30, 2013 at 8:49am

After re-reading your post here is the reachable areas in the 40m limit

Permalink Reply by Danny Boyes on October 30, 2013 at 8:49am

and file

Attachments:

EscapeRoutes40m.gh, 48 KB

Permalink Reply by Jonas Haldemann on November 2, 2013 at 2:56pm

Hey, Danny

Thank you for your help!

The problem ist, that the ways are not really direct. But with the "shortest walk" component, you brought me to a new idea.

For the reason that we have only straight walls, i dissociated myself from my first idea and tried to write a file that just tests each corner of the plan. Because this is what i really need. If the extremities of a room are working, the rest of the room will work anyway.

So this is my new solution:

Too bad that the "shortest walk" component needs to calculate each possible solution to find out the shortest way. This example is working ok, but the much more complex plans of our project are crashing my rhino & grasshopper because of the huge mass of data.

Anyway, it could be a helpful tool

Attachments:

fluchtweg-test.gh, 143 KB

Permalink Reply by Vicente Soler on November 2, 2013 at 6:26pm

I have this definition I did for my gf a while ago to find shortest escape route. You might find it useful.

It takes 40 secs to load on a very simple floorplan so it might take ages on anything complicated. It can probably be sped up a lot.

Attachments:

incendios 04.gh, 36 KB

Permalink Reply by Anders Holden Deleuran on November 3, 2013 at 6:11am

Just a quick comment on a general approach to these types of problems. One usually solves them by constructing a visibility graph from a polygon representing the environment/floorplan and then applies graph theory algorithms such a Dijkstra's shortest path to compute routes. I believe that the plugin Spiderweb plugin supports several graph algorithms which might be useful. Hope that helps.

Permalink Reply by Vicente Soler on November 3, 2013 at 8:17am

Yes, that's basically what we are doing. The Shortest Walk component we are using here implements the A star search algorithm that is an improved variant of Dijkstra's algorithm.

Permalink Reply by Anders Holden Deleuran on November 3, 2013 at 12:10pm

Ah sorry Vicente, missed your post there. Looks like a visibility graph approach indeed :)

Permalink Reply by Richard Schaffranek on December 15, 2013 at 1:38pm

I am sorry to say but:

A* is not necessarily a improved version of Dijkstra. A* solves the shortest path problem between two points. Dijkstra solves the Single Source Shortest Path Problem.

Depending on what you want one or the other is faster (therefore better). If you want to find a shortest path between a startingpoint and a endpoint than A* is better. If you want to measure which corners are within a distance of X meters from a (or multiple) single sources (escape points) than Dijkstra's Algorithmen is better.

So as I understood the conversation so fare the second option seams better.

Jonas Haldemann:

"Too bad that the "shortest walk" component needs to calculate each possible solution to find out the shortest way. This example is working ok, but the much more complex plans of our project are crashing my rhino & grasshopper because of the huge mass of data."

So SpiderWeb would be the better way, can provide you with a sample on Tuesday.

Permalink Reply by Vicente Soler on December 15, 2013 at 4:55pm

Cool. You should only be sorry for not correcting the misinformation earlier :P

Wikipedia's A* search article says: "It is an extension of Edsger Dijkstra's 1959 algorithm. A* achieves better time performance by using heuristics."

I guess that's not the whole story.

Permalink Reply by Richard Schaffranek on December 16, 2013 at 6:12am

No A* does achieve better performance if you want to find a single path from A to B in a graph. If you want the paths from A to all other elements than Dijkstra's algorithm is faster.

According to Wikipedia:

Dijkstra's algorithm preforms in O(|E|+|V|log|V|) (worst-case) to find the paths from A to all other vertices in a graph.

A* needs O(|E|)(worst-case) to find a path.

So given that you want to find the path between A and all other vertices in the graph this would mean that A* needs something like: O(|E| * |V|) (worst case) This is a wild guess of mine and properly isn't true but it would take me a while to figure it out (which I don't want to spend).

Maybe you can read:

http://en.wikipedia.org/wiki/Shortest_path_problem

also for some basics:

http://www.gbl.tuwien.ac.at/_docs/GrasshopperScriptum/GrasshopperSc...

Richard