Progress reports on funded work

[Shield Bearer]

I believe there's a guy who goes by the name 'silnarm' on the Glest forums who did some pathfinding work for GAE, He showed interest in joining the team, but never got back to me

[plumo]

Keep up the good work ! We follow your progress with amazement.

[ribez]

Phillip, I just want to add that your posts are very interesting and informative to me, and that's beside the improvement to the game itself.

Did you look at other Open Source games like glest and warzone2100 to see how they handled the pathfinding?

Although Warzone2100 is somewhat different in this sense from 0 a.d, glest is pretty similar, and I know they both had lots of problems with their own pathfinding.

If you want and it's relevant, I can do a small research in their (and other's) forums, to see if they thought of something that can find the path to your pathfinding problems.

(oh, and by the way, there is a "glitch" in the pathfinding that makes females that go to get resources bump into females that returns with resources and they both start a pretty "let me pass" dance. I love it! Don't fix it, please. It actually happens to me in reality all the time )

i don't think that the pathfinding in Warzone 2100 is so evolute: sometimes units has bad behaviour, and the maps are much simpler than 0 A.D. ones!

[Android_]

[Bothorth]

Pathfinding is an interesting spatial problem.

I played an island map on the latest build last night and found the fishboats running aground trying to get to a dock on the other side; although, on right-clicking a dock they found their way around, so this seems like an AI problem, not pathfinding.

[ribez]

just for reference (even if is not directly connected with long pathfinding):

PEDSIM is a microscopic pedestrian crowd simulation system. It is suitable for use in crowd simulations (e.g. indoor evacuation simulation, large scale outdoor simulations), where one is interested in output like pedestrian density or evacuation time. Also, the quality of the individual agent's trajectory is high enough for creating massive pedestrian crowd animations (e.g. for motion pictures or architectural visualization). Since libpedsim is easy to use and extend, it is a good starting point for science projects.

http://pedsim.silmaril.org/

examples

PedSim Behavior and Background

[Guest afeder]

just for reference (even if is not directly connected with long pathfinding):

http://pedsim.silmaril.org/

examples

PedSim Behavior and Background

This is probably not optimized for real-time use, but imagine a bustling in-game city with hundreds of citizens coming to life before your eyes with these 'intelligent' pedestrian logics.

Edited January 27, 2012 by afeder

[Android_]

Hmm, I don't really see how AoEO differs from AoM or AoE3 (except in one minor detail). See e.g.

- the formation is a box shape, and the central point of the formation moves tightly around the corners of the buildings, and when that central point 'turns' the whole box shape turns instantly, and all the individual units rush sideways and backwards and forwards to try to stay in their assigned location relative to the formation. See also

- the formation is moving up a narrow path, and the individual units at the edge of the formation run around on the wrong side of the cliff because that's theoretically the closest position to their assigned location relative to the formation.

As far as I'm aware, that's exactly the same as how AoM and AoE3 work (and is what 0 A.D. currently tries to emulate). The one difference I see is that all the units in AoEO stop instantly when the notional central point of the formation reaches the target, regardless of where each unit is, whereas in AoM/AoE3 they continue moving until they're all properly aligned in formation at the target. What else am I missing?

Good points. I guess what I meant by 'fluidity' is what you can see in video 2 if you look at the left flank of the formation - units are able to ignore other units' obstruction radii and thus the formation as a whole is able to contract/spread out very quickly if desired. This is even more visible when you have large formations of 100-200 units. I think this is special compared to the Age games and 0AD?

Edit: In other words, units just completely ignore the obstruction radii of other units in their formation. I think that's new and also highly effective.

Edited January 30, 2012 by Android_

[historic_bruno]

This is probably not optimized for real-time use, but imagine a bustling in-game city with hundreds of citizens coming to life before your eyes with these 'intelligent' pedestrian logics.

I think it would be nice to have some non interactive characters in the game to provide the appearance of bustling towns and cities. They could walk around, in and out of buildings, and of course flee in terror when a raiding enemy approaches It wouldn't add anything to gameplay, but it might be fun eyecandy to watch.

[willvarfar]

I imagine you are maintaining a width*height passability map for the static obstacles? Possibly one per maximum-navigatable-incline if different unit types have different capabilities. Using a trivial neighbour-count you can easily find those those impassible cells that are islands; you can erase them from the passability map perhaps. You might actually store in each cell of the passability map the distance north, south, east and west to the next obstacle. Do keep posting results /Will (from Glest)

[ribez]

I think it would be nice to have some non interactive characters in the game to provide the appearance of bustling towns and cities. They could walk around, in and out of buildings, and of course flee in terror when a raiding enemy approaches It wouldn't add anything to gameplay, but it might be fun eyecandy to watch.

[iap]

I think it would be nice to have some non interactive characters in the game to provide the appearance of bustling towns and cities. They could walk around, in and out of buildings, and of course flee in terror when a raiding enemy approaches It wouldn't add anything to gameplay, but it might be fun eyecandy to watch.

Yes yes! (but only if it will not have that much impact on the performance)

[Android_]

And only if they don't obstruct things otherwise pathfinding will be a nightmare

[lexa]

Hi,

Just to say that I was waiting for the day when you start the task "Better engine support for AI scripts"

Did I miss it??

Thank you Philip for your work!

[quantumstate]

Hi,

Just to say that I was waiting for the day when you start the task "Better engine support for AI scripts"

Did I miss it??

Thank you Philip for your work!

No, that hasn't been done yet. Also I put some of my ideas here http://www.wildfiregames.com/forum/index.php?showtopic=15410 . Any comments would be appreciated.

[JuliusColtranePille]

Yes yes! (but only if it will not have that much impact on the performance)

i think this should be (if implemented) an optional feature (one shall be able to turn it on/off)

[wraitii]

Very interesting stuff on the pathfinding here.

[Ykkrosh]

probably you've already seen it, but there is another paper from the same author:

A Comparison of High-Level Approaches for Speeding Up Pathfinding

Thanks, I hadn't seen that one before. Brief summary: Dragon Age's hierarchical pathfinding over 8x8-tile sectors was slow because the graph of sectors was too large, so they added another 16x16-tile sector graph on top of it. (They couldn't simply increase the first-level sector size because their approach produces non-optimal paths (with various hacks to minimise the problem), and bigger sectors make the paths much less optimal). Then the paper considers Contraction Hierarchies as an alternative to that second-level graph, which involves taking the first-level graph and heuristically removing nodes and adding edges to minimise the size of the graph without changing shortest path weights, and concludes that CH is slightly faster than the second-level graph for very long paths and slightly slower for short paths (and more complex, and hard to update dynamically).

I think the basic problem is that they got stuck with small 8x8-tile (sometimes 16x16-tile) sectors at the start - it seems it would be better to avoid that limit (and support a more efficient, larger sector size) rather than adding an extra abstraction on top of the first not-quite-adequate abstraction, if possible within the various constraints.

http://pedsim.silmaril.org/

As far as I can tell from the documentation and published code, this is currently just a very basic implementation of steering behaviours. (Units have a 1/exp(dist) force away from each other, 1/exp(dist) force away from the nearest obstacle, some perpendicular 'look-ahead' force to avoid running into other units, and some force to the next waypoint, and that's it). The web site makes it look much more interesting than it is

I imagine you are maintaining a width*height passability map for the static obstacles? Possibly one per maximum-navigatable-incline if different unit types have different capabilities.

It stores a width*height bitmap per 'passability class' (where every unit belongs to one class, and the class is defined with max slope and min/max water depth and min distance from static obstacles, which fully determines passability of a tile/cell). (Actually it stores them all in a single array of uint16_t, but they're effectively bitmaps.)

Using a trivial neighbour-count you can easily find those those impassible cells that are islands; you can erase them from the passability map perhaps.

Yeah, might help to do something like that to remove unnecessary trees/rocks/etc from the graph and simplify the search.

You might actually store in each cell of the passability map the distance north, south, east and west to the next obstacle.

Not quite sure what that would be useful for, though for JPS I'm precomputing the distance to the next jump point in each horizontal/vertical direction from each cell, which helps significantly on large empty maps.

[iap]

[quote name='Ykkrosh' timestamp='1328635940' post='233814'

As far as I can tell from the documentation and published code, this is currently just a very basic implementation of steering behaviours. (Units have a 1/exp(dist) force away from each other, 1/exp(dist) force away from the nearest obstacle, some perpendicular 'look-ahead' force to avoid running into other units, and some force to the next waypoint, and that's it). The web site makes it look much more interesting than it is

By the way, Is it not a good idea to have the short site pathfinding be actually a steering, like you describe?

As long as you know there is a way between you and the target, and the long pathfind point to this way, the short pathfing will not initiate pathfind, but just steer to the destination, avoiding obstacles and entities. Of course this approach will only work on short sited pathfind. It will also help very much with the formation, I think, I wrote about it in another thread.

[Ykkrosh]

Day 14

Slow continued pathfinding work. In particular, trying to get all the parts of the game to interact correctly with the new navcell-passability concept. It's important for the design to be clear on what its concepts actually are, so this is my attempt at describing the conceptual details of what I'm trying to implement now. (I'll probably copy this as documentation on the wiki when it's cleaned up and implemented properly.)

First we start with a map like this: (click image for larger and higher quality version)

There's some small units, a large unit (the siege tower), a building, a fence, and some water (with steep terrain around its edges). Units are "dynamic obstructions" - they move around frequently, and they need to perform pathfinding operations, and they generally can't pass through each other. Buildings and fences are "static obstructions" - they don't move, and units can't pass through them.

Dynamic obstructions have a "footprint radius", measured in high-precision units (i.e. not quantised to tiles), corresponding loosely to the graphical size of the unit. Dynamic footprints don't have a separate width vs height, nor an orientation. They don't have a precise shape - they're sort of squares, or sort of circles, or sort of neither, depending on how you look at them.

Static obstructions have a square footprint with width, height, and orientation; or a circular footprint with radius.

Terrain can also block units. Terrain is split into fairly large tiles, and each tile might be passable or impassable, depending on water depth, steepness, etc.

Each unit belongs to a "passability class", which defines the exact limits on water depth, steepness, etc, that should be used for that unit's movement.

The pathfinder uses a "navcell grid", which stores a boolean passability value for every navcell on the map, per passability class. Navcells are smaller than terrain tiles (currently there's 4x4 navcells per tile). ("Navcell" is just a term for the tiles used for navigation, to distinguish them from terrain tiles). The navcell grid is computed from terrain passability and static obstructions, like so: (click for bigger and better)

Here the thin dark blue lines indicate the footprints of all obstructions. Note that the impassable cells from the large building are strictly inside its footprint shape; we take a conservative approach so that if you tell a (zero-sized) unit to walk to the building, it can walk all the way up to the footprint edge without stepping onto any impassable tiles. Unfortunately this mean the fence is invisible to the navcell grid, since it's too narrow to strictly contain any cells. We should enforce that no static obstruction footprints should be that narrow (i.e. narrower than 2*sqrt(2) navcells).

The navcell grid only blocks a unit if that unit's central point enters an impassable tile (regardless of the unit's size). To cope sensibly with large units, each passability class defines a "clearance" value. Navcells within that distance of an obstruction are considered impassable. For standard units with a clearance of 1 navcell we get:

For large units with a clearance of 4 navcells we get:

This stops the large unit moving too close to the buildings or water. (Note that the fence now blocks some navcells. We expand the footprint shape by the clearance, and then compute which navcells are strictly contained within the expanded footprint. In contrast, terrain passability is computed with a kind of blur filter to expand the initial grid outwards by the clearance distance.)

The navcell grid ignores dynamic obstructions entirely. The long-range pathfinder finds paths across the navcell grid. It allows moves from one passable navcell to another if they're horizontally or vertically adjacent (not if there's only a diagonal connection).

The short-range points-of-visibility (POV) pathfinder is based on high-precision (i.e. not navcell-aligned) horizontal/vertical obstruction edges, and finds paths at arbitrary angles. It goes like:

The cyan lines are the obstruction edges that the POV pathfinder will not cross. The green/yellow tiles are the long-range pathfinder's output, and the thin red line is the POV pathfinder's output, for the cavalry unit to move eastwards.

For terrain and static obstructions, the POV pathfinder uses the navcell grid: it adds cyan edges around the red cells. That means a unit can move so that its central point is right up to the impassable cells, regardless of the unit's size. The clearance (used when computing the navcell grid) is what stops the unit walking too close to a building.

Dynamic obstructions are not on the navcell grid, so the POV pathfinder adds a cyan square around each dynamic obstruction's footprint. To prevent units' footprints overlapping, each of those squares is expanded by the footprint radius of the unit that's moving. (When the cavalry unit moves up to the cyan line around an archer, the cavalry's footprint will touch the archer's footprint (dark blue square).)

One slightly dodgy thing here is that a unit's clearance and footprint radius may not be the same. If the footprint is larger than the clearance, the unit might be able to get close enough to a static obstruction that their footprints overlap. I think that's probably not a problem, but I'm not certain yet and will need to clarify.

---

Given those concepts, the rest of the passability-related code can (mostly) be derived:

* Whenever a unit moves by a step, we have to check for collisions in case the pathfinder returned an invalid path (e.g. because the world changed since it computed the path). That means checking the movement is along a sequence of passable navcells; and that it doesn't intersect any dynamic obstruction footprints expanded by the moving unit's radius.

* When a unit is spawned (e.g. from training in a building), we have to pick a valid spawn point that is on a passable navcell and isn't inside an expanded dynamic obstruction.

* When deciding whether it's valid to place a new building, it doesn't really matter what we do. It's easiest to just verify that the new building's navcell shape doesn't touch any already-impassable navcells (computed with a clearance of 0) - that'll prevent it intersecting existing buildings or invalid terrain. When telling an AI where it can place a new building, we can give it a conservative approximation of that navcell grid.

* When placing a building on top of units, we need to tell those units to get out of the way before starting construction. To find precisely which units are affected, we need to look at the new building's navcell shape, expanded by the clearance of each unit that might be in the way, and tell any unit standing on a to-be-impassable tile to move away. But that sounds kind of nasty to implement - ought to find a better way...

* When a unit moves to a static obstruction (to gather resources, or to melee-attack, etc), we can tell the POV pathfinder to stop when it reaches the edge of a high-precision oriented square or a circle, corresponding to the building's footprint. (That avoids the problem when you tell a load of units to attack an enemy building, of having them line up in an ugly stairstep pattern corresponding to the navcell outline). But we need to guarantee that square/circle is not inside the building's impassable tiles, else units will never quite reach it. So we need to expand the static obstruction's footprint by at least the unit's clearance value to guarantee it will be reachable. (Maybe we should actually compute the unit's footprint radius plus its specified minimum attack/gather/etc range, and use that value if it's larger than the clearance, to allow more control over the behaviour without breaking that guarantee.)

---

Hmm, I think that's about all for now.

[Sonarpulse]

Shouldn't the red zones not be so angular at this point? at the corners of the fence, building, and coast, shouldn't the impassible-navcell shape resemble an arc? I think it could be an issue: for example if the fence was a bit closer, the unit with this clearance radius wouldn't be allowed to go between the fence and the coast, even though it really wouldn't fit. I think the "blur filter" method used for terrain passibility would solve this problem, is it too intensive? The cells, as you say, are supposed to be a conservative measure of what is passable, and this method makes them over constrictive at the corners.

Alternatively, I guess you could also do 2 sets of nav cells: "Potentially/indeterminately passable" and "definitely impassible". If the fastest route was definitely passable, Great! If the route has "indeterminately passable" bits, more rough paths are queued until a fail safe is found, and then the precise/slow pathfinder (or whatever it's called) checks all the risky bits of the queued paths.

Edited February 12, 2012 by Sonarpulse

[Pureon]

Day 14

Slow continued pathfinding work...

Brilliant to see and read about the progress in such detail. One question, which i know is much easier to ask than it is to answer at this stage, but are you confident the new pathfinder concept will have less impact on game performance?

[JuliusColtranePille]

Brilliant to see and read about the progress in such detail. One question, which i know is much easier to ask than it is to answer at this stage, but are you confident the new pathfinder concept will have less impact on game performance?

in general i believe with your additional work (ykkrosh) the game will make such a big leap this year

thumbs up,

regards!

[Ykkrosh]

are you confident the new pathfinder concept will have less impact on game performance?

Short answer: No

The main benefit of the navcell-grid-related changes is that it should eliminate a class of problems where units currently get stuck, especially with large units moving through forests or other dense environments. That won't help performance, but pathfinding needs to be correct before making it fast. Using the navcell grid with a higher resolution than the terrain tile grid will make performance much worse, but using the JPS pathfinder optimisations should make it much better again. The reachability testing should help performance massively in certain cases (like a formation walking beside a lake), but it will make other cases a bit slower, but if necessary it could be adapted to make those other cases faster too. There's still the opportunity for multithreading the pathfinder, which would make things faster for most users. I can't really predict how all the factors will balance out, or how much extra work will be needed until it's acceptably fast, but I'm reasonably confident this is at least moving in the right direction.

[willvarfar]

I really enjoy reading these posts.

Could the foot of the siege tower be non-axis-aligned?

The corners of the impassability fringe could be rounded; loci rather than just grown bounds?