There's an interesting addition that's linked to flow fields - when you perform a lot of path finding over an area - you can 'touch' an additional bias variable in each cell and use this additional variable as part of the heuristic calculation at each point. For every cell you look at - minus a small amount from the bias value - then when the final path is found or even better when it's actually walked by an entity - you increase this bias value by twice the amount for every cell that's actually visited.

This has the effect of increasing the bias for cells that are walked and decreasing it for cells that are rejected.

Little corners and dead ends end up with very low biases and are rarely checked, because hardly any entities get successful paths through them and thus don't bias them. A corridor connecting two parts of a base would have big bias value etc.

So ultimately you get a kind of 'heat map' of the most regularly traversed cells and the heuristic bias means that these cells are considered first when path finding - greatly reducing the number of cells that are actually checked for all but the most uncommon of paths.

To make it a true flow field - instead of storing this bias heuristic as a single number - store it as a vector and add the direction the path takes over that cell as a bias vector - so you get further reductions in places where just a distance heuristic alone wouldn't favour one or the other direction.

I hope that makes sense - the idea is to check as few cells as possible.

--

Another useful technique is to store previous paths, each path themselves having a bias. Then when you path from one point to another - before walking the cells, you run through the start/end points of stored paths - from the most strongly biased paths to the least biased paths - and you see if your destination and your starting point are close to the start and end of any existing path.

If it is? then just work out the path to get to and from either end of that existing path - then you've just turned a big expensive path calculation into two small ones and a couple of linked list insertions.

It can get complicated with path merging - minimising how often it happens for different biases etc - but it's interesting