[MX]Node based path finding

[andreaskrenmair]

I wanted to know how fast this would be in Flash. So I coded this version of a node based path finder:

Just click on a node. The start node is in the upper left corner.

http://mitglied.lycos.de/andreaskrenmair/flash/bfs.html

I used the breadth-first search algorithm for the pathfinding. The graph was built with simple objects that are linked together.

I was quite surprised that it is that fast with Flash Player 9.

[SaphuA]

What exactly is the point of this thread? Do you want feedback or.. ?

25ms for the farthest path isn't too bad of a result imo.

However, if it's not fast enough I think you might need to rethink your logic behind it. I've seen some ultra fast nodebased pathfinders around here which were still made in a version other then Flash 9.

PS. I don't think search that the search results are accurate. The path to the node above the one in the lower right corner, is not the shortest.

[andreaskrenmair]

Hi,

actually I had two reasons creating this thread: feedback an to show an alternative for pathfinding examples for tilebased games. Eventhough this example is in an tilebased environment you could adapt it to every sort of map. Sorry, I forgot to mention that.

...were still made in a version other then Flash 9.

That´s the point. I made it with mx in AS1. With Flash Player I got 160 - 183 ms for the longest path. With Flash Player 9 I got 26 - 30 ms.

PS. I don't think search that the search results are accurate. The path to the node above the one in the lower right corner, is not the shortest.

That´s because I did not distinguish the different edges (I was a bit lazy). So even an edge is longer as the shortest one for example they are treated as equal. If you count the nodes to the path the trace for the actual shortest path will have the same(or more) amount of nodes of the trace the pathfinder returns.

[renderhjs]

Originally Posted by andreaskrenmair

...show an alternative for pathfinding examples for tilebased games. Eventhough this example is in an tilebased environment you could adapt it to every sort of map.

like you said not only tile- based, I made a node based pathfinding a while ago for my ortho engine wich has something like a polygonal map structure:
http://board.flashkit.com/board/show...4&postcount=13

mine is propapbly slower (esspecially with AS2) but back then I really gave it some thoughts so I added features within the editor such as zones or unique node directions that speed up searches (used for example as dead ends = level leaving).

(screenshot of a level in the editor as top view)

I wrote about this as well some time ago in a pacman thread and described excactly what you did (pacman with node- based pathfinding)

edit:
could it be that you dont compare the actual node distances all together but instead right now only the amount of nodes within the path to determine the shortest path (wich is very wrong if so).
Sometimes I had as well the feeling the the result was not the fastest path but always the path with the smalest amount of nodes

[andreaskrenmair]

could it be that you dont compare the actual node distances all together but instead right now only the amount of nodes within the path to determine the shortest path (wich is very wrong if so).

Yes, I did not add something that calculates the distance between two nodes. So this two nodes are treted as equal:

O--O == O-----O

but I could either add a simple cost function or create a workaround and split long paths up.
So actually it is not working correctly. I will try to fis that without loosing too much speed.

I am curious about the unique node directions. How did you achieve that?

The algorithm looks for every node he vistits if there are connctions to other nodes if so store them and treat them as visited.

I think I can make it a little bit faster if I use a heap to store the visited nodes, but that will only pay of if the list of visited nodes is very big.

EDIT: Updated the version and added two extra nodes in order to get better paths.