FlowField Pathfinding

Posted by : at

Category : MMORTS

Over the last couple of months I've been designing and implementing one of the largest features of this milestone (MVP 2): Pathfinding! I needed something that didn't have so many back-end calculations and could accommodate players rapidly clicking on different spots (which would restart calculations). I'm very happy with the results.

Originally created for Supreme Commander 2 (as far as I could ever tell) and most recently used for Planetary Annihilation, both of these games move thousands of units around a map efficiently. For me the biggest concern was players continuously requesting new move commands. If I used A* or other such pathfinding for this I would have to run a bunch of calculations only to throw all of that out as the player clicks somewhere else.

The way flowfields are supposed to work, is that for every point on the map (which I call waypoints), there exists a map with every other point giving a vector flowing to the original point. That is you can reach any point you choose by following its map of vectors from your current position.

Take the above image as an example. This is a single flowfield for a point; the one on the rightside, about halfway down represented as the magenta dot. If your unit is anywhere in this map area it just needs to follow the path lines forward and it will reach the target point. Each of those line segments is one vector pointing at the next location the unit should move to.

One way to think about it is using letters. If our target is location A our flowfield for A may be J->H, I->F, H->F, G->E, F->E, E->D, D->A, C->B, B->A, and so forth. Picking any letter and following which letter it points to, then which it points to, etc. will eventually lead you to A. All without any calculations; you just pick your point and go where your point says. But remember, you need to have a flowfield for each letter, where all other letters eventually reach it. In this example you will have 26 flowfields each with 25 vectors.

So the benefit is less calculations at run-time, the drawback is more heap usage. You will have to store these flowfields in memory to save time. You could only load the flowfield you need, but that loading takes time itself. The other problem is scaling. A 10 by 10 point map would have 100 flowfields each with 99 vectors. A 100 by 100 map would have 10,000 flowfields each with 9,999 vectors each.

To combat such large maps, I ended up making a "Flowfield of flowfields" I call a 'sector flowfield.' This is where I brake the map up into sectors and then create a flowfield for getting to each flowfield using only the cardinal directions. With this I can make the check of "if I'm in the sector of my target location, just use the flowfield I need. Otherwise find the sector flowfield to see which cardinal direction I need to move, get to any point along that edge and go there. Once at the edge, get the next sector's flowfield, rinse and repeat." So now instead of a 1000 by 1000 map of flowfields (that is 1,000,000 flowfields each with 999,999 vectors), I can have 25 sectors, each with 200 by 200 points (40,000 flowfields each with 39,999 vectors). If you do the math, that means with sectors we are storing roughly 39,999,000,000 vectors in memory instead of 999,999,000,000; a savings of 960 billion. Minus the 25 sector flowfields of 24 vectors each (600 total vectors).

So is this perfect? Eh, not completely. The problem this introduced is that multiple units going to the same location all want to flow into the same point almost at the same time. To fix this I can adjust the way I make the flowfields to attempt to prevent large converging of paths into "mainlines" or add some other flocking AI behavior. Honestly that is work for another time.

Useful Links