download/file.php?mode=view&id=22516
One call
download/file.php?mode=view&id=22517
Seven calls
And there we have it. Significantly better than before. I rewrote the program from the ground up, because I was having to duct tape every inch of the original program, and eventually, I hit a bug that I had absolutely no explanation for because of it. The A* search algorithm is also much more detached from the map than it was before. It has support for any arbitrarily shaped map (squares, rectangles, hexagons, world maps, 3D space (well maybe...), whatever), you just have to build a flattenMap() function to accommodate it. I'll write a little blurb about what is required to implement it. If you don't want the hassle of making your own flattenMap(), I've packaged a non-optimized version to flatten a square map
As you can see from the images, a single call has no impact on FPS, even in our worst case from before.
As an aside, the worst case in my new implementation is actually a straight diagonal line, since the number of open nodes to search through for the next best guess is far larger than anything inside the swirl case. My problem with the original implementation was during the buildPath() phase at the end of the algorithm. Previously, I just searched through the entire closed set of nodes (the nodes that I had explicitly tested to see it was the exit node), pruning the closed set only if it was a parent to the path nodes. For the above case, that meant looping through at most 312 nodes every time I didn't find my way back from the exit node! Which for the above case, meant I had to check 48516 times! Now, when I assign a parent, I also assign its location on the closed set. So now, I only have to check at most 312 times!
I did a few more tests with different modules turned off, as well as turning off vsync, and the most it helped was maybe 1 more call was capable before it dropped below 30 FPS.
Keep in mind that all of these FPS numbers also take into account the graphics and my flattenMap() algorithm, which can clearly be improved upon, and should be something that you build yourself inside your game.
This is probably the most optimized I, alone, can get the A* search without moving to like C or something closer to the hardware. There are plenty of ways to accommodate for more enemies using A*, which have been linked to or posted on in this thread, but for just a straight up stress test, this is the best I've got. When I upload the "finished" version, I'll probably add a few links to that stuff on the original post.
EDIT: Here's a sneak peek at it before I update the first post. Most of the controls are the same.
Left click places the start position;
Right click places the exit position;
Shift+left click places a wall;
F2 resets the map;
TAB runs the algorithm once;
P toggles the stress test;
[ decreases the number of calls to the algorithm during every dt;
] increases the number of calls;
ESC quits.
