Fix my Flow Field pathfinding

Question

I'm developing prototype of Tower Defense/RTS game and I've implemented simple Flow Field grid. Here is the example (link).

How to use example: First click on S50, this will spawn additional units, then wait till all of them clump together, click on SET_BASE button and click on a free space, this will move the base (red circle) and they'll move to the new location. The problem is that if you click to a relatevely diagonal position, they'll all go straight to the target, while if you give them new order at the same y coordinate, they'll start clumping.

If you click several times to move units around, you'll notice that they're moving pretty well when you order them to move diagonally and clump in a line when going horizontally or vertically.

I ran out of ideas what to do next to fix this, what are yours?

---

A bit more info about my flow field: I do one pass of "Dijkstra distance" and then do second pass of detecting lowest distance neighbor and assign "vector" to that neighbor.

Then, about units movement - every unit every update reads "desired movement vector" from it's current cell, predits its movement, then checks if it will hit the wall, updates movement vector, then checks if it will hit other units and finally updates movement vector.

---

EDIT: Here's the source code of movement logic.(link)

And source of flow field generation (link)

I'm sorry for shitty code and stupid comments, it's all "prototyp-ish" as possible.

---

What I want is to achieve less "diagonal-horizontal" difference, because at the current state it's really seem underwhelming and it's unaccetable that you can move all units faster by zig-zagging them to their destination.

Answer 1

I ran out of ideas what to do next to fix this, what are yours?

Try smoothing the vectors.

Answer 2

I had a similar problem this week, so I thought I'd post what I did. Dijkstra's algorithm is inherently discrete, so it will always give you directions that tend to funnel everyone into the same few cardinal directions.

I would recommend taking a look at Continuum Crowds (Treuille/Cooper/Popovic) and Hybrid Vector Field Pathfinding (Moersch, Hamilton) as a starter. They go over the idea of using cost and potential fields to generate paths to a single source. One key concept is that the potential field satisfies an Eikonal equation at all locations except the goal, and this keeps the potential field smooth.

Once you have a smooth potential field, you can use the gradient to work out which direction to move in at any point.

If you want a bit more of a lighter introduction then take a look at the Froblins (Shopf) presententation from Siggraph 2008 too. One point he mentions in that presentation is that the Fast Marching Method to satisfy the Eikonal equation can be relatively slow due to the need to keep the list of candidate cells sorted (or maintaining a priority queue). An alternative he mentions which I found to be quite a bit faster in my case is the Fast Iterative Method. It's also a bit simpler to implement.

One final thing that's not obvious is that sometimes the quadratic in the Eikonal equation is not solvable. In this case you should drop back to one dimension, as mentioned in another question.

This method is inherently quite expensive to compute I'll warn you! I'm currently calculating paths over a 200 x 200 grid with a 100-step cutoff (so it looks more like a circle), and it takes about 2.23 ms on my 3.4 GHz cpu. This is after some efforts to optimize the obvious things.

Here's an example grabbed from my game showing an overlay of the gradient of the potential field and a path that follows it.

If you have a nice smooth field, one idea I wanted to investigate was that of using the curl of the potential field to send agents on a flanking route for a short while, before returning them back to using the gradient to go directly towards the goal.