Monday, May 4, 2009

Street Path Finding in AS3

Just finished reading Keith Peter's ActionScript 3.0 Animation book, and I very highly recommend it. Chapter 4 is all about pathfinding using A* but is based on a tiled grid network. So I adjusted it, in such a way that the nodes and arcs are derived from street features off a shapefile. The resulting application enables you to select a starting and ending street intersection and a path is displayed. In addition, you can add street barriers so that the calculated path will go around the defined barriers. The nodes and arcs are spatially indexed. This enables live reverse geocoding as the mouse moves - that means that once the mouse is close enough to a street segment, a snap point is calculated and based on the side of the street, an interpolated address is calculated and displayed. Check out the application here, make sure to zoom in to enable snapping and path finding. Again, once you move close enough to a street segment, a snap point is displayed and the address is displayed on the top right corner. You can type the 'x' character to toggle the street as a barrier. Upon a mouse click, the closest node is selected as a starting node. Next, move the mouse to another node and click, and a path is displayed. The last selected node is now the starting node, click again and a path is calculated and displayed. Type 'C' to clear the resulting path. Like usual the source code is here. Have fun.
PS: People have reported some drawing issues :-( that have been resolved if you use FP10.

14 comments:

phile13 said...

The link to the code seems broken.

ThunderHead said...

Power is down :-(

Abdelhameed said...

awesome Mr. Mansour

ThunderHead said...

Glad u like it :-)

harley said...

this is cool.

Mohamed El Kerdany said...

thx mansour for this gr8 application really amazing. i need to do some customizations in it , the first problem i faced how to generate shapfiles with this structure but with another data ?

ThunderHead said...

glad u like it - any intersecting polyline feature class can do the trick - I convert the intersecting lines into a network (graph) that is used by the A* Algorithm for path finding.

Mohamed Mostafa said...

gr8 Application it is amazing, can this be applied to regular street network dataset and if yes what is the customization need to be done
thx

ThunderHead said...

Glad u like it - yes it can be applied to regular street networks - but (there is always a but :-) u have to take into account the street direction - so every edge has to be a single direction edge - like that u can control the impedance - not difficult - just work.

Mohamed Mostafa said...

This is gr8 but(as you said there is always but:) ) i tried to load a street network dataset with the Application but it could not be loaded i think i need to know the mapping between the shape file you are using and the network dataset as i tried to open the shape file you use in the sample but it give me error . Thx in advance

ThunderHead said...

Hum - make sure that u have the same spatial reference - in addition, can u create a _small_ set of ur street data in shapefile and email to my esri account ? I can see what I can do

Steve.McKinney@SICS said...

As always u r one bad mutha'!

Thanks for the great code! :) I am using some of it in the National Hydrography Dataset web mapping. URL to follow soon...

Trisha Krishnan said...

Hi,
I just want to do my own routing on street shape file.

I wish to do it without the grid that you have created could you help me on this.

may i have your email ID?

Thanks

ThunderHead said...

can always be reached at mraad@esri.com