Seeing as I was working on some pathfinding bots at work, I wanted to share my findings in making the A* routine as fast as possible. Click on the applet to reset random tiles. Wave the pointer over the applet to see it draw the shortest route from the top left corner to the mouse pointer.

This version is four directional searching only, using conditions to test directions. It uses Manhattan distance measuring - this works best with 4 directional because otherwise you get a zigzagging effect. It's also much faster than pythagoras distancing. Also different to the pathfinding library I wrote, it returns a fail safe path if the target cannot be reached, this means you get an AI that tries to stay one step ahead, even when it can't get to the player. The library I wrote does this, but now the A* reserves a "closest_good_node" whilst it searches - eliminating for repeated trawling through arrays.

I guess the best trick I pulled off here was eliminating the need for a closed list. You don't need one, you simply need to tag tiles "open" or "closed". This removes repeated searching through arrays. What about resetting those tags? Don't need to. On creation the AStar object gives each search a unique id. That id is used upon the open and closed tags. In practise: I check a tile to see if it is on the closed list, does Tile.closed_id match the search_id? No? Tile.closed_id = search_id. That tile will now be recognised as being on the closed list for that search only.

Another massive speed boost comes from limiting the iterations the search can perform, this crops the intelligence enough to give the game it's speed back, whilst creating intelligent bots at close range. Then you can simply use a radius test to detect if the player is close enough for path finding. I've used for loops instead of while loops because I was working in Flash, but I kept in the Java version because limiting the iterations reduces overhead when A* can't find the target.

I also don't return the start node in the search. It makes for confusing code when you have to tell your bots to ignore an item on the list. And I inlined a lot. Function nesting is a great way to slow down Flash - I'm not sure about Java, but I guess it pays to play safe.

Source code: fast_astar AStar Tile

Built with Processing