4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I've never done anything with flow fields before, but the inherent problem seems to me to be that when you set a diagonal path for them to follow, the vectors are parallel -- so each unit moves in a parallel direction without trying to bump into each other until they start clumping around the target... When you use a horizontal or vertical path, the vectors are actually pushing inwards and not parallel except on the precise cell in line with the target, so now they all want to jam into each other. \$\endgroup\$ – user77245 Jan 9 '18 at 17:31
  • \$\begingroup\$ Do the vectors have to be up/down/left/right/up-left/up-right/down-left/down-right? If they had a great range of angular freedom instead of constrained to 45 degree increments, it seems like you'd get more consistent behavior no matter what you do. \$\endgroup\$ – user77245 Jan 9 '18 at 17:32
  • 1
    \$\begingroup\$ @DrunkCoder cell vectors have no restriction, however I don't know algorithm for good "non-strict" flow field generation. \$\endgroup\$ – Fen1kz Jan 9 '18 at 18:31
  • \$\begingroup\$ I ended up deleting my old post since it was getting down-voted and don't blame the people since I was probably doing all sorts of dumb things. I'll paste a final version of the code in a bit though in the comments! \$\endgroup\$ – user77245 Jan 13 '18 at 2:51
  • \$\begingroup\$ @DrunkCoder woah dude, your post was really great, could you restore it or post it again, please? \$\endgroup\$ – Fen1kz Jan 13 '18 at 20:55
6
\$\begingroup\$

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

Try smoothing the vectors.

\$\endgroup\$
  • 1
    \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. Please continue this conversation over there. \$\endgroup\$ – Vaillancourt Jan 11 '18 at 1:51
  • 1
    \$\begingroup\$ Please continue any off-topic discussion of this post in the above chatroom. Subsequent comments that are not directly request clarification or providing critique will be removed without further warning. \$\endgroup\$ – Josh Jan 11 '18 at 19:34
3
\$\begingroup\$

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.

Potential Field and path

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.

Curl of potential field

\$\endgroup\$
  • \$\begingroup\$ Looks awesome! One thing that was popping in my head just now -- dunno if it's an issue in most use cases (maybe just cause I'm throwing so many agents at it).. is that a flow field only stores one direction to the target. That can cause the agents to jam together when there could be alternate paths just as quick to the exit. Was thinking it might be beneficial in some cases if a unit can't proceed using the first vector to use the second, or third, etc stored in a cell suggesting alternate paths they could take. \$\endgroup\$ – user77245 Jan 12 '18 at 5:02
  • \$\begingroup\$ It' something I just noticed now -- there was a case where I was trying to guide the guys through a maze with two openings -- and they ended up just waiting in line to get through the first opening when they could have taken an alternate path which would have been just as short. \$\endgroup\$ – user77245 Jan 12 '18 at 5:04
  • 1
    \$\begingroup\$ You can allow each of the agents to drop values onto the cost field which should cause subsequent agents to want to go down that path less. The dynamic costs can attenuate to zero so that it can eventually be used again. \$\endgroup\$ – Rory Driscoll Jan 12 '18 at 5:11
  • 1
    \$\begingroup\$ If the field is updating in real time, then I think that agents that are following behind would just get rerouted dynamically. If there are 3 possible paths to the goal, maybe the first couple of agents get through path 1 before they make the cost so high that path 2 becomes the best option for all that follow. Same goes for 2 to 3, and hopefully by then the first path is back open again. \$\endgroup\$ – Rory Driscoll Jan 12 '18 at 5:17
  • 1
    \$\begingroup\$ I don't have enough reputation to post in the chat for the other answer I think, but I wanted to say how good it looks with the dynamic cost field. It's really interesting to see the problem being worked through, and the various iterations. @DrunkCoder \$\endgroup\$ – Rory Driscoll Jan 12 '18 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.