Speed Up Flow Field Algorithm?

Question

I am slowly creating a flow field pathfinding solution for Unity3D. I'm trying to follow Elijah Emerson's description, which appears in the book 'Game AI Pro' (volume 1). In this question I ask about the Coordinates object which I use here. I have subsequently cached some variables.

In my tests, the stop watch has recorded times for each part of the flow field generation, for example:

FlowField calculations complete 1.0664ms
 path request complete 0.1309ms
 reset complete 0.014ms
 goal allocation complete 0.1427ms
 integration fields complete 0.4417ms
 flow fields complete 0.3318ms 

Integration and flow passes are the slowest parts, and I wonder is there anything I can do to speed them up some more?

I've followed some more advice from the aforementioned book, such as saving node neighbours on initialisation, instead of trying to find them at run time. That has helped. I also used James McCaffrey's priority queue with an internal binary heap. Getting rid of lists, and list comparisons (flagging a boolean property instead works wonders), and replacing them with priority queues seems the biggest gain by far.

I realise it may be trying to squeeze blood from a stone at this point (having dropped calculation time from 100ms to 1.1ms), but I'm eager for any ideas which can help.

Integration Pass:

public void IntegrationPass(PriorityQueue<Coordinates> openList)
{
 while (openList.Count > 0)
 {
 Coordinates theseCoordinates = openList.Dequeue();
 // Update Integration value. 
 //foreach (Coordinates neighbour in FindNeighbours(theseCoordinates, true, true))
 foreach (Coordinates neighbour in IntegrationPassNeighbours[theseCoordinates.sectorX, theseCoordinates.sectorY])
 {
 if (neighbour.Flag)
 {
 continue;
 }
 byte cost = neighbour.Cost.Value;
 int oldIntegration = neighbour.Integration.Value + cost;
 int newIntegration = theseCoordinates.Integration.Value + cost;
 if (neighbour.IsWalkable && newIntegration < oldIntegration)
 {
 neighbour.Integration.Value = newIntegration;
 neighbour.SetFlag(true);
 openList.Enqueue(neighbour, newIntegration);
 }
 }
 }
}

Flow Pass:

public void FlowPass()
{
 foreach (Coordinates node in CoordinatesField)
 {
 if (node.IsBlocked)
 {
 continue;
 }
 int bestValue = ushort.MaxValue;
 Coordinates bestNode = Coordinates.zero;
 //foreach (Coordinates neighbour in FindNeighbours(node, false, false))
 foreach (Coordinates neighbour in FlowPassNeighbours[node.sectorX, node.sectorY])
 {
 int neighbourValue = neighbour.Integration.Value;
 if (neighbourValue < bestValue)
 {
 bestValue = neighbourValue;
 bestNode = neighbour;
 }
 }
 if (!bestNode.Equals(Coordinates.zero))
 {
 int comparisonX = bestNode.worldX - node.worldX;
 int comparisonY = bestNode.worldY - node.worldY;
 // North
 if (comparisonX == 1 && comparisonY == 0)
 {
 node.Flow.Value = 1;
 }
 // North East
 else if (comparisonX == 1 && comparisonY == -1)
 {
 node.Flow.Value = 2;
 }
 // East
 else if (comparisonX == 0 && comparisonY == -1)
 {
 node.Flow.Value = 3;
 }
 // South East
 else if (comparisonX == -1 && comparisonY == -1)
 {
 node.Flow.Value = 4;
 }
 // South
 else if (comparisonX == -1 && comparisonY == 0)
 {
 node.Flow.Value = 5;
 }
 // South West
 else if (comparisonX == -1 && comparisonY == 1)
 {
 node.Flow.Value = 6;
 }
 // West
 else if (comparisonX == 0 && comparisonY == 1)
 {
 node.Flow.Value = 7;
 }
 // North West
 else if (comparisonX == 1 && comparisonY == 1)
 {
 node.Flow.Value = 8;
 }
 }
 }
}

For clarity, here is the lookup referenced by Flow.Value:

public static Vector3[] DirectionLookUp =
{
 Vector3.zero,
 new Vector3(1, 0, 0),
 new Vector3(1, 0, -1),
 new Vector3(0, 0, -1),
 new Vector3(-1, 0, -1),
 new Vector3(-1, 0, 0),
 new Vector3(-1, 0, 1),
 new Vector3(0, 0, 1),
 new Vector3(1, 0, 1)
};

Answer 1

Since I don't know the pipeline of C# source code to executable (and I don't have enough experience to make an educated guess) you'll have to (micro)benchmark all the suggestions yourself. Potentially the code changes I'm pushing for are made obsolete by compiler, but hopefully these are improvements that give the compiler more room to do its thing.

I'm also only able to offer half an answer, I don't know the algorithim so I can't suggest any major improvements. I reckon you'll have more success improving the algorithms and data structures involved as the code looks pretty clean.

---

Integration Pass

The neighbour loop skips any neighbours with a Flag set, does some work, and then checks another boolean associated with the neighbour. You could do both these checks at the start, and avoid unnecessary work if the second check fails.

foreach (Coordinates neighbour in IntegrationPassNeighbours[theseCoordinates.sectorX, theseCoordinates.sectorY])
{
 if (neighbour.Flag || !neighbour.IsWalkable)
 {
 continue;
 }
 byte cost = neighbour.Cost.Value;
 int oldIntegration = neighbour.Integration.Value + cost;
 int newIntegration = theseCoordinates.Integration.Value + cost;
 if (newIntegration < oldIntegration)
 {
 neighbour.Integration.Value = newIntegration;
 neighbour.SetFlag(true);
 openList.Enqueue(neighbour, newIntegration);
 }
}

The cost calculation does slightly more work than it needs to, and the result is not needed unless a condition passes. Looking at the code (below byte cost = ...) without names or types looks a little bit like this

D = A + C;
E = B + C;
if (E < D)
{
 // Use E
}

(Assuming no overflow) we don't need to compare D and E if we compare A and B. In other words, lets delay the computation of D and E until inside the block, and see what happens

if (B + C < A + C) // Replacing E and D with their definitions
{
 D = A + C
 E = B + C
 // Use E
}

Now it should be more obvious that 1) we can drop the + C from both sides of the condition and 2) we don't need D.

if (B < A)
{
 E = B + C
 // Use
}

Or back to code

foreach (Coordinates neighbour in IntegrationPassNeighbours[theseCoordinates.sectorX, theseCoordinates.sectorY])
{
 if (neighbour.Flag || !neighbour.IsWalkable)
 {
 continue;
 }
 int neighbourIntegration = neighbour.Integration.Value;
 int theseIntegration = theseCoordinates.Integration.Value;
 if (theseIntegration < neighbourIntegration)
 {
 byte cost = neighbour.Cost.Value;
 int newIntegration = theseIntegration + cost;
 neighbour.Integration.Value = newIntegration;
 neighbour.SetFlag(true);
 openList.Enqueue(neighbour, newIntegration);
 }
}

---

Flow Pass

foreach (Coordinates node in CoordinatesField)
{
 if (node.IsBlocked)
 {
 continue;
 }
 ...
}

If this is an unpredictable condition at the start of the loop, it might be a source of performance pain. Can you somehow remove this check? If the number of nodes which are clear (not labelled as blocked) is tiny, and this condition is met most of the time, you might be better off maintaining a separate data structure just for those nodes. It would be at a small memory cost, but it might alleviate pain for other tools like the JIT or branch predictor. If most nodes are clear, it might be worth doing the computation anyway, and doing the check later or somehow ignoring the result.

If it is not unpredictable, can you take advantage of the pattern, and still remove the condition?

If I have the general algorithm down, you find the smallest neighbour in a neighbourhood around the current node, and point in the direction of it. I'm sure there are a million ways to optimise this pattern, such as running the function in parallel over all the neighbourhoods at once, or doing some magic with a sliding window, but I don't know how easy they would be to implement. Perhaps you might be able to express each node is a pixel in an image, and use some highly optimised routine for computing gradients using convolutions.

Answer 2

In FlowPass you have a long sequence of if .. {} .. else if {} statements.

I suggest trying a lookup table to compute the value, say

 node.Flow.Value = Lookup [ (comparisonX+1)*3 + (comparisonY+1) ]

where Lookup is initialised as

int [] Lookup = new int[] { 3, ... }

It may even be possible to compute this with a simple arithmetic expression, although I cannot immediately see an expression that works. From the code supplied I am not clear how Flow.Value is used, it may be possible to choose a different encoding which is simpler and faster to calculate.

• inappropriateCode: This is a good point. It's funny because Flow.Value is used to reference a lookup table of Vector3 directions (N, NE, E, etc).
• inappropriateCode: I have added the table to the question. I have also changed the value range from 0-7 to 1-8.
• Thomas Ward: once you have an answer DO NOT alter your code. That tends to invalidate the answers.
• inappropriateCode: It looks like a 2D array lookup would make sense.
• Mast: @inappropriateCode Ordinarily I'd agree with Thomas here, but it seems George simply was too fast with the answer and should've left a comment instead of an answer if the question was unclear. For now, we'll leave the edit as-is unless a moderator decides otherwise. Please keep in mind for next time we do take answer invalidation seriously, even if it only looks like one.