Pathfinding and flocking question

For code related discussions and questions
Post Reply
New user
Posts: 1
Joined: 05 Jun 2018, 21:33

Pathfinding and flocking question

Post by causative » 05 Jun 2018, 22:15

warzone2100 has pretty good pathfinding and flocking. I notice that, first, even with many units it doesn't lag (at least in single player), and second, you can move a big flock of units and they will remain as a flock for a while instead of narrowing down to a single file column. 0ad, another open source RTS game, has trouble with this. I'd be interested in applying some pathfinding techniques from warzone2100 to 0ad. Before I dive into the warzone2100 code, could I get a big picture overview of how it works?

Here's an explanation of how 0ad pathfinding works, to give an idea of what I'm looking for. There is the "long pathfinder" and the "short pathfinder." The long pathfinder uses a fine-grained grid, on which it uses an algorithm called "jump point search," an optimization of A*, to produce a set of waypoints. It has a different terrain grid for each size of unit (passability class) so it can check if a cell is passable to a unit in O(1) time. The long pathfinder grid includes buildings and terrain, but not units. Each turn (500 ms turn length in multiplayer), each unit walks towards the next long pathfinder waypoint. If a unit is about to collide with another unit, it uses the "short pathfinder" to find a way around that unit to the next long pathfinder waypoint.

The short pathfinder does not use a grid - it does A* on a visibility graph that includes nearby units, moving or not. The short pathfinder gives another list of waypoints, and the unit follows these short pathfinder waypoints until it reaches a long pathfinder waypoint, or until it collides with another unit, in which case it calls the short pathfinder again.

There is no flocking. At all times, units are either walking precisely on a line between two waypoints from the long pathfinder, or walking precisely on a line between two waypoints from the short pathfinder.

Two problems with this approach: first, it's slow, particularly the short pathfinder. Second, over medium to long distances, the long pathfinder waypoints for units going to the same place tend to converge into a single file path. This means that units don't remain clumped together, and will walk single file over long distances, which is not desirable for gameplay. I've noticed that warzone pathfinding doesn't seem to have either of these problems.

Some specific questions:

How many ticks per second? How many multiplayer synchronization steps per second? Is there a time unit for pathfinding or pushing that's finer grained than a tick?

Does warzone use lockstep synchronization for multiplayer, sending only a player's commands and relying on clients to keep their simulation in sync? Or does it send unit positions every turn?

Does warzone use multiple threads for pathfinding?

How does A* and flocking interact? Do units only follow their A* path approximately?

Is there any horizon search used? Is there unit pushing?

Does A* use a grid that includes stationary units? Does it include moving units?

Warzone 2100 Team Member
Warzone 2100 Team Member
Posts: 3777
Joined: 03 Aug 2006, 19:39

Re: Pathfinding and flocking question

Post by Per » 06 Jun 2018, 00:30

That is a lot of questions... Short answers: Warzone's has no flocking algorithm, just basic collision detection and some (quite bad) obstacle avoidance. We run 10 game ticks per second, path-finding is multi-threaded but the threads are joined after a specific number of ticks to make it deterministic, every client carries out the same game simulation to keep things in sync, the A* path is followed unless there is an obstacle, and there is no unit pushing.

Post Reply