Reconciling Flocking and A* (Theory)

Question

For my RTS game I have got A* pathfinding working, and that's fine. Basic collision detection exists too. When a unit is moving it checks if the position it will occupy next move is a node occupied by another unit, and if so it finds another way to the destination. I also think I understand the basics of flocking; that during movement it's just making sure that boids are checking the distance to their flock friends, and then correcting for this.

But I am a little confused. Right now my pathfinding system works on a square grid of nodes, but if I'm to create a flocking system which works by taking a boid's circular footprint into account then this complicates matters, because in a tightly packed flock, or indeed a flock with a number of members with various footprint sizes, then their placement won't always match the square node grid designed for A*.

In theory, how then do a bunch of boids pack together in a ball, or flow through terrain bottlenecks (some nodes flagged unwalkable, etc) in an orderly manner? Is this sort of behaviour emergent from a functional flocking system?

But I'm sure I'm misunderstanding this system and would like someone who understand how to implement it to explain the theory so that I can implement this myself. I assume flocking isn't really congruent with A*: that's just used to find a path, and during movement flocking is the only way it manages collision detection and avoidance for units? But then what about obstacles which can create bottlenecks? How is A* and flocking reconciled? Avoiding boids and terrain obstacles are different systems.

Answer 1

The contradiction

Indeed the two systems are quite exclusive to one another. As you mentioned:

A*: that's just used to find a path, and during movement flocking is the only > way it manages collision detection and avoidance for units

Here are key differences, pros, and cons, to keep in mind:

+---------------------+-------------------------------------+
| A* Algorithm        | Flocking                            |
+---------------------+-------------------------------------+
| Abstract overlay    | Real-world representation           |
+---------------------+-------------------------------------+
| Graph-Based (Nodes) | Free-Form (float coordinates)       |
+---------------------+-------------------------------------+
| Optimal trajectory  | Physical Trajectory (speed, inertia)|
+---------------------+-------------------------------------+
| Individual          | Group dynamics                      |
+---------------------+-------------------------------------+
| Global knowledge    | Local knowledge                     |
+---------------------+-------------------------------------+

If you want to mix the two, then I have to assume you have a way to make either work (but you want advice on how to have them work together). This means you already have:

• A Physical world, where your boids can move around, interact with each other, and collide to world boundaries.
  This can be a 2D set of segments, polygons, circles that form walls and obstacles, also friendly and ennemy units and buildings, slopes, terrain type, materials, political ownership etc. That is, everything that may physically or morally affect your characters.
  Now your boids can move within this representation, have inertia, react to forces (real forces like collisions, or behavioural forces like seeking, fleeing). This is likely not just discrete cells, because boids are usually not constrained to cells, but it could be.
  Ultimately, this is our game simulation/mechanics world so make it what you want.
• A Graph representation of you world, for A-Star to work with.
  This is a high-level, abstract representations (graph with nodes and weighted edges). This needs no information on terrain type or any of that: just nodes and weighted edges. An AI can quite easily handle this abstract representation to navigate it towards a goal, rather than the physical world in all its complexity.
• To let the two representations interact, you'll also need:
  • A way to map any world position to a node in the graph
  • Vice-versa, a way, from any node in the graph, to pinpoint a matching location in physical world.
    (Note, this is not a one-to-one mapping, so you could randomize the physical location of this point within the cell to get organic paths)

(In the rest of this answer, I will italicize Flocking algo and embolden A-Star algo as I did above).

So how can we let these two systems cooperate to get the best of both?

---

Towards cooperation

Split responsibilities between your algos.

1. Let A-Star find a reasonable global path (think guidance system) in the abstract realm. It will be optimal in graph space, and good enough in real-world space.
2. Let Flocking drive your boids locally along the path.

The A-Star will find a way to its objective, by feeding clever temporary 'seek' targets to the Flocking algo.

---

Detailed Implementation:

• Beforehand, prepare some boids each of which have, at all times:
  • A macro objective, and a global path to that objective
  • A local tracking target for the steering behaviour, that we will move along the desired global path
• At each time step, do the following for each boid:
  • Move the boid according its behaviours (point seeking, plus collision, plus flocking etc.) in the physical world
  • Map the boid's current location to its representative graph node
  • If the boid has left its previous node, it needs to recompute its path! We now give it a new target:
    • Perform an A-Star search, from the boid node, to the discretized macro objective node. This returns a global path.
    • Isolate a node further in the global path (The next node, or the one after that to get a more flowing seek behaviour?)
    • Un-descretize it (make it back into a physical location).
    • Assign to the boid a Seeking behaviour towards this local target

---

Note 1: Separation of concerns

You've altered A-Star by having each units look at cell occupancy by other units. This has compromised many benefits of A-Star:

• Path is no longer optimal
• Path is no longer guaranteed to reach the target due to interactions
• Units will go back and forth whenever a path gets blocked/freed

This is because you've mixed concerns by having the algo both find an optimal path AND manage unit interaction. The nice thing about mixing two algorithms, is that this will allow you to resolve this by having A-Star simply find a path (regardless of other units, its the only thing it's good for) and let Flocking resolve conflicts (a task at which it is good for).

Note 2: Unit traffic jam

If you're concerned about groups of units blocking each other (like this (AAAA)--> <--(BB) ) in flocking mode, there are ways of mitigating this.

• Try and recognize unit groups based on their intention (target node) and distribute a repulsive force on every unit of the smaller groups to "make way" (bigger group = bigger priority)
• If you give mass order to big groups, then take that into account in you disretization process: make the discrete graph coarser when dealing with with large groups. Coarse A-Star will only find path through large enough "holes"

Note 3 - Unwalkable terrain

About unit walking into unwalkable terrain: Neither algorithm allows this.
At a high level, A-Star never orders a unit to pass through unwalkable edges, because those edges should not exist in the graph in the first place.
At lower level, Steering behaviout should include collision responses that keep boids out of the walls.

Worked Example

All white space in physical world is navigable, the graph world is a corresponding navmesh. Note that I purposely not followed the geometry in the graph, because it is an abstraction, so it doesn't matter as long as the edges have a correct weight (not shown).
The boid is in A and a, the objective is in E and e, there's a door in D and d.

Physical world             Graph world
+--------+------+          a---b          
|A      B|F    G|          |\ /|
|        |      |          | X |
|        |      |          |/ \| 
|        |      |          c---(d)---f
|        |      |               |\ / |
|        +      |               | X  |
|C       D     E|               |/ \ |
+---------------+               e----g

So the boid is in a, its A-Star path is a->b->d->e. So A-Star decides the next high-level move should be d (two vertices away, to create smooth trajectories). Since d resolves to D, the boid adopts a seeking behaviour towards D. But the boid is also very afraid of an ennemy in B, so here's what happens (the dots show the trajectory):

Physical world             Graph world
+--------+------+          a---b          
|A      B|F    G|          |\ /|
|.       |      |          | X |
|.       |      |          |/ \| 
|.       |      |          c---(d)---f
| .      |      |               |\ / |
|  .     +      |               | X  |
|C       D     E|               |/ \ |
+---------------+               e----g
                    

The boid steered away from B (comination of seek+flee), changed of node in the process, and is now on node c ! We recompute the path, and now get c->d->e. The boid is assigned E as a seeking target. Etc, etc.

We thus get a natural, and emotionally coherent path which is a mix of A-Star and Steering behaviour.