AoM-like pathfinding/movement

[Ykkrosh]

I was looking at AoM for some ideas about unit movement, and this post is an attempt to briefly describe what it's doing technically. I'm ignoring some edge cases and probably making various mistakes and invalid assumptions, but I think this is the general idea of what it implements.

There's some useful settings you can put in a config file, to help understand the internal behaviour:

showPaths 1
renderPathingQuad 1
renderObstructionManager 1
renderUnitGroups 1

The collision shape of a unit is an axis-aligned square. The largest looks like exactly one tile, the smallest normal unit is half a tile width (things like arrows are smaller), some are somewhere in between. Buildings are non-axis-aligned rectangles.

There's four different colours of obstruction: buildings, static units, moving units, non-obstructing units (flying units, arrows, corpses, etc).

There's an adaptive quadtree type of thing, initially with 8x8-tile regions, subdividing down to 1x1-tile regions depending on the presence of buildings and terrain. For each region, each edge can be marked as impassable.

There's two main levels of pathfinding. The first level seemingly uses that quadtree to compute long-distance paths, i.e. based on just terrain and sufficiently obstructive buildings. (A single building is usually not enough to split a region and make an edge impassable, so it gets ignored here, but cities and walls typically have an effect). That gets converted into a series of waypoints, at most 8 tiles apart but sometimes closer, though it seemingly uses more terrain detail to compute the waypoint positions. That path is kept and never recomputed.

The second level computes a path towards a future waypoint from the first path, keeping about 10 tiles ahead of the unit. That new path takes account of the exact shapes of buildings and static units (not moving units), and computes a series of waypoints around them. It recomputes every so often, to smooth out the path and to stop the unit getting stuck if some units move into its way. It's exact (based on the unit/building squares), not tile-based.

Movement then consists of travelling in a straight line towards the next second-level waypoint. If it's blocked by moving units, then one of the units seems to stop for a fraction of a second and the other tries recomputing a new path.

When you tell a (non-widely-separated) group of units to move, the game does a single pathfinding operation (the same as for moving an individual unit). It also picks a desired formation for the units (e.g. a 4x2 grid with some spacing between points). A single group proxy object moves along the path, and all the units attempt to move in a straight line to their position in the formation relative to that moving proxy object. They speed up a bit if they're lagging behind.

When a unit can't find any way to reach its next waypoint, it gives up and stops.

[Ykkrosh]

Thinking a bit more about implementation: Squares seem a good idea.

If everything is squares, and if a unit doesn't rotate its square as it moves, it's straightforward to produce a list of waypoints for the unit to navigate through a collection of obstructions. Treat the unit as a point, and expand each obstruction square outwards by the size of the unit's square in order to get shapes representing the closest the unit point can get to the obstruction. If the obstruction and unit have the same alignment, the expanded shape is a square; otherwise it's an octagon. Treat impassable terrain tiles like any other square obstruction.

Now you've got a load of vertexes and a load of impassable edges. Add the start and end points as vertexes. Connect every vertex to every other vertex by a straight line, if that line doesn't cross an impassable edge. Now you've got a graph of lines that the unit can safely travel along, so you just do A* over the graph to find a path from the start vertex to the end vertex, and the unit can follow that path precisely. I think the worst-case cost is O(n^3) in the number of shapes, which is probably okay over very short distances (which is all this should be used for).

Circles break this because you can't convert them to a list of vertexes. Rotating square units break this because the set of vertexes becomes invalid each time the unit turns. Non-rotating squares seem like they should work gameplay-wise for most units, though they'll be a bit rubbish for ships.

Does anyone happen to know other ways of solving the problem of having units navigate busy environments (with lots of buildings and other moving units) over short distances? I've seen loads of articles about pathfinding but basically nothing about this aspect of RTS unit movement . I'll keep looking, but it'd nice to have a roughly decent implementation in the game soon so that units can walk near other units and attack without it all breaking.

[Ykkrosh]

Continuing my general rambling and checking briefly for other implementations to potentially copy:

Glest/GAE looks like it just forces units to stick to tile centers (movement between tiles is purely graphical interpolation), which is not good for smooth movement or for non-axis-aligned formations. Buildings are snapped to tiles and have tile-based footprints and can't rotate.

Spring snaps buildings to tiles and doesn't allow rotation and has square tile-based footprints. Units have slow acceleration and slow turning etc, so ground units all do roughly vehicle-type steering. They seem to pathfind around buildings and just steer to try to avoid hitting other units. It seems very unreliable - they keep sliding around buildings and hitting each other and randomly running off in the wrong direction if they can't quite reach the target.

ORTS makes my computer's video output freeze so I have to reboot. Looks like units/buildings can have arbitrary positions, and are either circles or axis-aligned squares or arbitrary lines. Don't know how the movement actually works (it's designed as a extensible framework so it's hard to find the code that will actually run).

Since this is now the 21st century, I think we really want rotatable square buildings (like in AoM) so that the game doesn't look blatantly tile-based. So none of these games are helpful here, since they have different constraints and don't seem to do anything very fancy.

[Jeru]

Some person on the Ubuntu forums suggests pinching code from Spring RTS.

[feneur]

Judging by

Spring snaps buildings to tiles and doesn't allow rotation and has square tile-based footprints. Units have slow acceleration and slow turning etc, so ground units all do roughly vehicle-type steering. They seem to pathfind around buildings and just steer to try to avoid hitting other units. It seems very unreliable - they keep sliding around buildings and hitting each other and randomly running off in the wrong direction if they can't quite reach the target.

and

Since this is now the 21st century, I think we really want rotatable square buildings (like in AoM) so that the game doesn't look blatantly tile-based. So none of these games are helpful here, since they have different constraints and don't seem to do anything very fancy.

it doesn't seem it's very useful in this case.

[Jeru]

Whoops, missed that

[BadassTester]

I think I got

your idea

Yes, this is going to be really fast for macro pathfinding and It will support formations, rotated buildings and all the other amazing features.

It might only be slow when the number of vertexes is really big... For example when the map is big or with too many obstacles.

The other half of the problem is micro pathfinding in busy enviroments. For example with a lot of peasants running around (many players do that). Althought that can be solved other ways (caching paths).

But the main problem is still here and that's avoiding moving units. Because the movement of other unit can not be predicted, this had to be done in real time, what do you think?

[Ykkrosh]

Yeah, a lot like that, though the collision outline is more like this for rotated obstacles. It won't work if there's many dozens of obstacles, since there'd be a huge number of potential edges to check, but hopefully it should be okay if it's only over a distance of a few tiles. The normal tiled-based A* pathfinder would still be used for long distances - this is just for avoiding collisions while following the path's waypoints. AoM's approach seems to be to ignore moving units in all of this, and then just stop if there's ever a collision and resolve it somehow (one unit can have a higher priority and try to move around the other), which may be fine for us. We don't have worker units running backwards and forwards between resource supplies and collection buildings (they just stay at the resource) so there's less need for more complex cooperative avoidance.

[Ykkrosh]

Actually the octagonal outline is just complicating things for no good reason - nobody's going to notice if they're kept as squares. So I've got some code now that does this - white is the tile-based pathfinder, dark blue is the collision outline of units/buildings, cyan is the outlines expanded by the radius of the current unit (i.e. the closest that the unit's centre can get to the objects), the green lines are connecting each vertex to every reachable vertex, and red is the shortest path to the destination using those lines.

The code's very hacked-together and inefficient and missing important features but it still looks like it actually works quite nicely when it's integrated with the tile-based pathfinder. (The tile-based pathfinder is also very hacked-together etc but it can be replaced independently of this new code). So I'm continuing to think that copying AoM is good

[BadassTester]

Keep in mind an edge case like this:

edge case

Might be exploited for cheating

By the way, there is more room for an optimizations...

First, removing a redundant nodes. Six guys near each other can be optimized to one rectangle, that removes 20 nodes.

And this

[Ykkrosh]

That edge case is a theoretical issue, but I don't think it will be a gameplay problem - a unit of width 'w' will be able to walk between two parallel buildings (regardless of orientation) that are a distance w apart, and can only walk between those opposing corners if they're sqrt(2)*w apart, but that's okay because units are quite small so it's not much difference. Just build the buildings further apart if you want your units to get through, or further apart if you want to keep the enemy out

I think optimising the collision outline seems likely to be complex and a bit slow (unless there's some simple clever method I'm unaware of). There aren't many buildings and the biggest problem is units (since there can be a huge number in a small space), but units keep moving so you can't easily precompute anything. In typical cases the A* algorithm will quickly find the goal and doesn't have to bother constructing much of the visibility graph (it doesn't compute the edges for a given node until the A* has decided to look at that node), so any extra up-front computation is likely to slow down those cases.

The worst case is when the goal is unreachable (since it has to examine the entire visibility graph to determine that), so I think the most important optimisation is avoiding that case: if the goal is inside a building/unit then pick a new goal that's outside and more likely to be reachable, etc. That seems quite messy - you could try to pick the nearest point that's on the obstruction's collision outline, but if that's obstructed by another object then you're a bit stuck, and I can't think of a better way to recover than spiralling outwards from the goal until finding an unobstructed location and hoping the player didn't fill the entire map with buildings so there's no free space anywhere. I guess I should focus on simply making it work first, and then it'd be good to look more at optimisations

[BadassTester]

I'm just saying that a different pathfinder might be able to pass trough there..

Collision with a moving unit would still be a problem.. One of the unit should stop for a while, the other will find a new path, maybe reserve some terrain for the next few moments and then the other unit will find a new path...

And shroud of war would be considered as a free space, or not?

When an unit collides with an obstaclee that wasnt there before, would it try to find a new path or follow the old one?

[Ykkrosh]

Looked briefly at Warzone 2100 too; buildings are locked to tiles (no rotation or arbitrary placement), units all do acceleration/steering etc and try to steer their way smoothly between waypoints. Roughly the same as Spring. (Also it has 12,000-line source code files - I think I prefer 0 A.D.'s rather more modular approach...)

I've currently got an implementation of the AoM-style system that appears to mostly work now - you can make units move to a point (vaguely avoiding walking through other moving units), move to a target (units spread around the edges of the target when attacking/repairing/gathering), move to inside a maximum range from a target (for ranged attackers), move to outside a minimum range (for ranged attackers who are too close, or for telling units to get away from construction sites or volcanoes etc). Still quite a few missing features (impassable terrain, group/formation movement, etc) and probably a number of bugs, but I think it's almost ready to commit and start testing properly.

I'm just saying that a different pathfinder might be able to pass trough there..

That's true, but I think that only becomes a danger when the tile-based long-distance pathfinder thinks there's space there and so the unit runs up to that point and then gets stuck because it can't quite fit. As long as the two pathfinders generally agree then the game should be self-consistent and hopefully nobody will notice

Collision with a moving unit would still be a problem.. One of the unit should stop for a while, the other will find a new path

Yeah, currently I have it so that both units stop and try to find a new path simultaneously. That doesn't work well when one unit comes from the east and one from the west, and they collide and both decide to head around the north of the other unit, so they both move north and hit each other again, then both decide to head around the south of the other unit, and repeat many times. I guess simply telling one unit (based on some arbitrary priority) to wait for ~1 second before computing a new path would help with that.

And shroud of war would be considered as a free space, or not?

Don't know. It wouldn't be nice if units appeared to have perfect information about the world while the player could see very little of it; but recomputing paths every time visibility changes is inefficient. I guess it needs some balance between using imperfect information and recomputing paths when the information has got sufficiently better to make it worthwhile. Maybe the new short-range pathfinder should use perfect information (its range is currently limited to a distance of 12 tiles around the unit so most of that should be visible anyway), and the long-range tile-based one should treat shrouded areas as passable but expensive (so it'll prefer to avoid them) and recompute the path every ~32 tiles or whenever it gets stuck, or something like that.

When an unit collides with an obstaclee that wasnt there before, would it try to find a new path or follow the old one?

Currently it keeps the old long-range path, and recomputes a new short-range path to the next waypoint (avoiding the new obstable). I don't think that's great, though - it might get stuck weirdly if e.g. someone builds a long wall in its path. Need to make the code more robust when paths become invalid or the unit gets stuck, without allowing one unit to eat up an unfair amount of CPU time, but I'm not sure how to do that properly - it'll probably needs lot of testing and tweaking.

[feneur]

One small thought on the "buildings too close to each other" issue, would it be possible to simply limit buildings to only be built far enough from each other that units always will be able to pass between them? With the exclusion of walls (and perhaps towers ) of course =)

[WhiteTreePaladin]

If shroud of war/darkness is not considered free space, then exploration requires many mouse clicks and constant attention. In AoK, one could simply send a scout to some distant unknown place and check up on his discoveries later at a more opportune time. It's an issue of what level of knowledge the unit should have and how much exploration should be micromanaged by the player.

[Cygal]

An Age of Empires developer explained how they handled the problem of group movement, if you want to look at it:

Coordinated Unit Movement : http://gamecareerguide.com/features/19990122/movement_01.htm

Implementing Coordinated Movement : http://gamecareerguide.com/features/199901...ementing_01.htm

Yeah, currently I have it so that both units stop and try to find a new path simultaneously. That doesn't work well when one unit comes from the east and one from the west, and they collide and both decide to head around the north of the other unit, so they both move north and hit each other again, then both decide to head around the south of the other unit, and repeat many times. I guess simply telling one unit (based on some arbitrary priority) to wait for ~1 second before computing a new path would help with that.

According to litterature there are two main ways to solve this. The first is named "Steering behaviors", which is what you want here, and the other one is about crowd simulations, wich is out of scope and still an area of research. Note that it is also possible to cheat and allow units to cross each other.

Steering Behaviors For Autonomous Characters : http://www.red3d.com/cwr/steer/gdc99/

Currently it keeps the old long-range path, and recomputes a new short-range path to the next waypoint (avoiding the new obstable). I don't think that's great, though - it might get stuck weirdly if e.g. someone builds a long wall in its path. Need to make the code more robust when paths become invalid or the unit gets stuck, without allowing one unit to eat up an unfair amount of CPU time, but I'm not sure how to do that properly - it'll probably needs lot of testing and tweaking.

If the new short-range path fails (rare), then you can always ask for a new path. Concerning CPU cycles, it's possible to give the pathfinding code a budget each frame, and ask him to continue the computations the next frame if it's not finished. There are a lot of possible optimisations too but I guess they should only be performed if pathfinding takes too much time.

[Ykkrosh]

One small thought on the "buildings too close to each other" issue, would it be possible to simply limit buildings to only be built far enough from each other that units always will be able to pass between them?

Hmm, that's a good point. We'd probably have to limit the closeness of buildings anyway because of their terrain-flattening behaviour - it's not good if a new building change the terrain underneath an older building, so we'd probably want to guarantee at least one free tile between them (which means a distance of sqrt(2) tiles apart in case they're going diagonally). That's probably enough space for any individual unit to fit through. As long as the tile-based pathfinder underestimates the size of buildings (i.e. it considers partially-obstructed tiles to be passable) it should find the gaps between them, and as long as the buildings are far enough apart then that gap really will be large enough for the unit to fit, so units won't get unexpectedly stuck. (Just got to be careful not to underestimate the size of e.g. thin walls so much that they effectively disappear.)

That doesn't prevent the spacing problems entirely (there's still buildings placed by scenario designers, and trees and rocks and all sorts of other things that mean the tile-based approximation will never be perfect), but it should make it less common in normal play when you're telling units to walk through a player-built town. Once the fundamentals are in place I expect we'll need a lot of heuristic tweaks like this to make certain cases work more intuitively for players, so it'll need a lot of user testing

[Ykkrosh]

An Age of Empires developer explained how they handled the problem of group movement, if you want to look at it

Thanks, I've seen those before and they have some useful ideas.

According to litterature there are two main ways to solve this. The first is named "Steering behaviors", which is what you want here, and the other one is about crowd simulations, wich is out of scope and still an area of research. Note that it is also possible to cheat and allow units to cross each other.

Steering Behaviors For Autonomous Characters : http://www.red3d.com/cwr/steer/gdc99/

Hmm, that paper is about units with linear and rotational momentum, which I don't think is a good model for most units in our game - we currently have instantaneous acceleration and turning and I believe that's a sensible approach in terms of the gameplay (real humans can change direction very quickly and shouldn't feel 'floaty' like the robots in Spring) and implementation complexity/robustness (it makes it easier to not get stuck and to go exactly where the player commanded). The steering model with no momentum seems to degenerate into the original problem of picking which waypoints to move towards, so I don't think it adds much that helps.

(We might want a momentum-based model for ships and charging cavalry, because it's silly if they can turn instantly and it's okay if they're cumbersome and can't follow the player's commands precisely, but I think it's easier for that to be done separately from the normal unit movement code - we should be able to mix different movement algorithms and shouldn't need a single all-encompassing one.)

Concerning CPU cycles, it's possible to give the pathfinding code a budget each frame, and ask him to continue the computations the next frame if it's not finished.

Yeah, I think it'll be necessary to make pathfinding asynchronous - a unit requests a path on one simulation turn, and doesn't get the result until the next turn (or even later), so the engine can schedule the computations to spread the load. But it may be okay for each pathfinding operation to be uninterruptible (it rarely takes more than a millisecond with the current not-very-optimised code) so that only batches of multiple pathfinding requests have to be split across frames, which should simplify things.

[Cygal]

Hmm, that paper is about units with linear and rotational momentum, which I don't think is a good model for most units in our game

Sorry! I was thinking about something like that, but I can't find the URL.

Yeah, I think it'll be necessary to make pathfinding asynchronous - a unit requests a path on one simulation turn, and doesn't get the result until the next turn (or even later), so the engine can schedule the computations to spread the load. But it may be okay for each pathfinding operation to be uninterruptible (it rarely takes more than a millisecond with the current not-very-optimised code) so that only batches of multiple pathfinding requests have to be split across frames, which should simplify things.

It's quick, but in the map you use you never have to check a lot of tiles. If you plan for huge maps with a lot of units pathfinding a lot where you will encounter A* worst case (when used with the Manhattan distance), then it could become a problem.

[Ykkrosh]

I've committed the current version now (see r7484), which I think is basically working (though certainly not perfect or complete). (The precompiled Windows binaries should be in SVN within an hour.)

Some things to try:

Run the "techdemo3" map. Select the four horsemen on the left, right click on a nearby corral building - they should walk to the nearest point on its edge.

Find the group of archers on the right, and select them all. Tell them to attack the temple they're standing around, and they should spread out to their minimum range (in a square pattern) and attack. Tell them to attack the temple on the far right, and they should move to within their maximum range (in a circular pattern) and attack. Tell the spearmen on the right to attack the temple, and they should move to their maximum range (in a square pattern).

Tell some people to gather resources. Tell some people to build a building. (Click and drag to rotate during building placement. It should prevent you building on top of other units or buildings, but not enforce any gap.)

Use the "pathfinder overlay", "obstruction overlay", "motion overlay" options to see some of the internal operation.

Run the "techdemo1" map and train some units. They should spawn in locations that don't collide with any other buildings or units. (I've made training times 10x faster than normal so it's less tedious to test). Find the archers in the lower right, turn on "control all units", tell one to attack an enemy then make the enemy run away or run very close and the attacker should move to keep the target in range.

Some known problems:

* Occasionally units can walk inside each other or get stuck walking past each other, which I believe is due to some numerical accuracy issues. All the geometry code is done with 23.8-bit fixeds which is a bit rubbish (especially for unit vectors) so I think I just need to be better at using appropriate ranges and precisions.

* Units don't respond sensibly when colliding with other moving units.

* Units animate incorrectly if they're stuck and can't move at all.

* Some important algorithmic optimisations are missing (like using quadtrees to efficiently find nearby objects).

* Lots of low-level optimisations are missing (like somehow making CheckVisibility not do so many 64-bit multiplications, since it's called many times).

* (It's particularly slow in debug-mode builds - on Linux you need to compile with CONFIG=Release for the faster optimised version.)

* I don't like UnitAI.js - it's a poor attempt at a state machine and units blindly follow orders regardless of how the world changes around them.

* I've not tested any of the code much, and keep finding various dumb bugs (particularly in the geometry algorithms).

* It doesn't work nicely when you tell a large group of units to walk to the same point; it probably needs group/formation code so they don't all try walking to the same point.

* And more! But hopefully not a lot more. Feedback on problems (preferably very specific details about what's wrong and how to reproduce it, or just general concerns about the whole approach) may be appreciated

[Mythos_Ruler]

Tell some people to build a building. (Click and drag to rotate during building placement. It should prevent you building on top of other units or buildings, but not enforce any gap.)

I think the player should be able to place a building beneath units. The units would then move out of the way when the builder approaches to begin construction. Thoughts?

[Ykkrosh]

That's my current understanding of what ought to happen (based on what other games seem to do) - units are ignored when placing the foundation, then it tells friendly units to get out of the way and blocks them from walking over the foundation any more, and a builder can get the building to above 0% build progress once there's no units in the way (including enemy units), and after that point the foundation blocks enemy units walking over it too. (That avoids your own units blocking the building, but also avoids the exploitation of foundations to block enemies). Just need to implement it

[janwas]

I think the player should be able to place a building beneath units. The units would then move out of the way when the builder approaches to begin construction. Thoughts?

Just mentioning this for completeness:

Starcraft II (going by the battle report videos), as did the original Starcraft, don't allow building over enemy units. If one has spare time for micromanagement and the map is small, cheap units can be sent to block important expansion points (dodging like crazy so they survive long enough to matter).

I'm not sure we want or need that particular gameplay mechanic, though (ugh).

(That avoids your own units blocking the building, but also avoids the exploitation of foundations to block enemies). Just need to implement it

hm, is it really "exploitation" to spam foundations in the enemies' way, knowing that it's expensive and the foundation can be obliterated with a single attack? If so, an alternate workaround would be to only place the foundation when the builder is nearby (thus making exploitation in the face of ranged units much more difficult).

[Ykkrosh]

hm, is it really "exploitation" to spam foundations in the enemies' way, knowing that it's expensive and the foundation can be obliterated with a single attack?

With the current construction system, it's not expensive - if an under-construction building is destroyed then you get back (100%-progress)*original resources.

If so, an alternate workaround would be to only place the foundation when the builder is nearby (thus making exploitation in the face of ranged units much more difficult).

That sounds basically the same as immediately placing a special non-obstructing 0%-progress foundation, and only making it obstruct movement when a builder reaches it and gets it above 0%. I think it's better for those almost-foundations to be visible objects, so you can plan around them or cancel them or send multiple builders to them, rather than being invisible until the original builder gets close enough.

[janwas]

Ah, I see - then the proposed solution sounds good!

BTW, as mentioned in the meeting, the 5000 tile limit might be a bit low - it's reached when ordering the right group of infantry to move to the end of the maze. Given that a hierarchical pathfinder would remove much of the performance penalty of a higher search distance, and that incorrect paths are much more surprising than a stall after a long-distance move order, how about we slightly increase that distance for now? (That's easier than changing the map, hehe)