A few months ago, I wrote that I was working on interactive illustrations for my A* pages. Has it taken that long? Well, I've actually had things working for a while now. I just haven't published it. Why? It turns out that my A* pages, which I wrote a long time ago, are really out of date. As I was trying to illustrate various concepts, I was trying to illustrate the concepts from my pages, but not all of them worked well in my Flash program. I eventually realized that some of those concepts are just unimportant in practice. I also discovered that the style I used in my diagrams only works for very simple maps. Once you add terrain into the maps, the visual style fails to convey the concepts I wanted to illustrate.
I haven't yet resolved these issues, which are taking a lot more time than writing the code itself. The algorithm and data structure code is complete, so I've uploaded them to my web site. You can see source code and the applet running on a square grid. The code is released under the MIT license; feel free to use it. I made the A* portion work on any graph, and included square, hexagonal, and triangular grids. This isn't the most efficient approach, but I wanted something flexible so that I could later use it in my article on grids. I haven't finished the hexagonal grid code yet; the only thing missing is the pixel coordinate to hex coordinate transformation. Enjoy!
Once I figure out the best way to display the important concepts for A*, I'll update my A* pages to use the interactive diagrams.
Did u try to use a Dictionary to cache visited nodes and costs ? This my speedup calculations in complex situations because Dictionary lookup is usually faster then Objects lookup.
You can also implement a Node class to be used instead of the Object you use to store nodes. Then, implementing a factory to generates Nodes you can reuse objects and use those objects directly as keys of the Dictionary,
I'm not sure it will speed up your code for simpler grids, but I think it will do for more complex ones.
I considered using a Dictionary but it complicated the API for graphs. For this release, I'm going for simplicity, not speed.
Using Nodes and Dictionaries would be the next step for speed. However, even better I think would be to assign each node a unique integer, and then pass ints around. Then index into an array instead of using a Dictionary or Node objects.
yes, using an Array as a pool of Nodes will be better, and will make you also able to reuse Node objects if they are no more needed. I don't know which will be the overhead involved in creating a new Node every time u need it, but probably u can do a test and check if reuse of instances is a good idea.
Just to explain abit better, I think u should keep a list of "free" node IDs, and reuse free node instances for new nodes if there are more then 0 free nodes. When u don't need a Node no more, simply add its index to the free list.
Instanciating objects in flash is pretty fast, but it you can gain a boost in performances if you reuse instances when u are working with a lot of objects.
Just my 2 cents
At least for the small maps I'm working with, I can statically allocate nodes, so there's no need to manage a free list. There will be no node allocations at all, so it should be even faster than allocating and then managing a free list.
Post a Comment