#12 ~ A* Algorithm

Today's update shows off my (slightly modified) A* Pathfinding implementation.

This one was a tricky number because of the size of the maps here. The images are 11,520x6,480 ... which Gamemaker can't cope with at all and who can blame it.

Overlaid on this is the isometric grid which comes in at about 10,000 unique tiles on a map that size.

The hard limitations I've put on it are:

-> a maximum of 128 concurrent paths that can be considered at any time

-> each path can't be more than 128 tiles;

-> has to complete within 90 frames and maintain at least 24 fps while processing.

Resource contraints will always govern the accuracy of these type of algorithms and I've been a little arbitray here. 

These constraints will be configuration options for players with more powerful machines, able to scale up the pathfinding accuracy, or lower spec machines being able to scale it down.

My implementation applies the usual checks of pruning any path that is too far from the target, or travelling too many tiles.

The difference I put in there is that it doesn't prune the farthest, it keeps a small selection of the very wrong. This enables it to better handle situations where the agent has to head in the complete wrong direction for a while before turning and coming back.

Given the resource constraints, it can and will fail in some circumstances.

Which is why it tracks the best path (closest to the target) during the pathfinding calculation and in event of failure, just drives the agent towards that. The player will have to guide the agent a little better and that's ok, I kind of like a little interactivity there.

When it fails, it fails predictably, and that's ok :)