Cool, I’m glad you like it. I’ve had very little feedback from non-JGO people, yet seems like there’s about 2 downloads of the source per day. Maybe the downloads are all just google’s indexing bot lol. I linked to the project on wikipedia’s path finding and A* pages and I’m getting a lot of traffic from there according to google analytics.
I uploaded a new version which has an improved A* pathfinding algorithm thanks to Nate’s suggestion of storing the open/closed/unprocessed state of the nodes in the nodes themselves instead of keeping an open and closed list/set and doing contains(obj) all the time. I don’t know why I didn’t think of that! I must have got carried away with the idea of open and closed lists like they had in the A* tutorials I read
Also the linking of nodes is much quicker. I thought of a smarter way of doing it. When connecting nodes I used to just connect all nodes that were reachable. By reachable, I mean that a line from one node to another is not intersected by any obstacles.
This led to lots and lots of connections. The thing is that not all of these connections are actually useful for finding a path between obstacles.
I found an efficient way to determine if a connection is useful or not. By ignoring useless connections, the nav-mesh is a lot smaller and faster to calculate, and the path finding algorithm works more quickly because there are less connections to process. On the demo maps, there was a decrease of between 80 to 95% in the number of connections 8)
To see the impact, look at these before and after screenshots:
Before, with 26,444 node connections
After, with only 1,735 node connections
BTW to see the demos run with the new innovations, just click the web start or applet demo and press ‘C’ to toggle wire frame view and connection-rendering.