AoM-like pathfinding/movement

[BadassTester]

Yes, that's good. Like in aoe 2

[plumo]

I agree. Foundations should be visible. Like in reality, flags and ropes were used to mark the foundations.

I also propose a second thing. A building should have less "crush armour" during construction than after finishing. F .e. When you are building walls while the enemy attacks, unfinished walls should go down a little easier, even concerning their hitpoints are a little lower than a finished wall part.

[BadassTester]

My feedback: why, in clean area (no obstacle) and a longer distance - the guy follows a curved line instead of a straight line to the goal... ? Perhaps it is caused by a bug in A* heuristics?

Or maybe the old algorithm is not completely replaced by the new one..?

Edited May 7, 2010 by BadassTester

[Ykkrosh]

Over long distances, it uses the tile-based A* pathfinder. That finds a path moving between horizontally/vertically adjacent tiles (so going diagonally doesn't save any movement cost), with an ugly hack (or clever tweak, depending on your point of view) in the cost function to make it prefer 30-degree and 45-degree diagonal paths when it has a free choice. So if you try to walk along a 30/45/90 degree line then it should go pretty straight, otherwise it'll do a curve made of 30/45/90 degree line segments.

(Many of the games I've tested have the same issue except they only use 45/90 degree lines so they're even less straight. I guess our options are to ignore the problem, to find a cleverer trick in the cost/heuristic functions to make it straighter, or post-process the computed path to make it straighter (as long as that doesn't cause it to hit obstacles or expensive terrain etc).)

The unit then picks a waypoint on the long-distance path, and goes in a nice straight line towards it (using the new precise obstacle-avoiding pathfinder), and when it gets close enough it picks another waypoint to head towards. So that part should be mostly a straight line.

[BadassTester]

Why not like this?

It uses a distance_to_goal+distance_to_start heuristics:

sqrt((x-x_goal)^2+(y-y_goal)^2)+sqrt((x-x_start)^2+(y-y_start)^2)

[Ykkrosh]

The heuristic ought to decrease as you get closer to the goal, but I think that one stays the same all the way along the straight line, so that's not going to work so well . It should find the straight path but it'll be inefficient and search far more tiles than it needs to. It could be used as a tiebreaker in the heuristics though, like here, but since it always prefers the straight line between the start and the goal (regardless of any obstacles in the way) it'll find ugly paths like this.

[chlin]

I am new to this and is guided from the post from http://www.wildfiregames.com/forum/index.p...topic=13157&hl=

Now I have a few questions:

1. What does AoM mean? Does it indicate the game - Age of Mythology? That's what I only can found on the internet with key words e.g. AoM.

2. I read the first post saying settings e.g.

showPaths 1
renderPathingQuad 1
renderObstructionManager 1
renderUnitGroups 1

can be configured for observing behaviour of the engine. However, after searching with command such as `find . -name \*.\* -exec grep -iHn showPaths {} \;`, no result appears.

Have the settings been changed? Or anything I may miss?

Thanks for help.

[Ykkrosh]

Yes, it's Age of Mythology. The config commands can go in the game's startup\persistent.cfg file (just add them to the bottom).

[chlin]

Yes, it's Age of Mythology. The config commands can go in the game's startup\persistent.cfg file (just add them to the bottom).

After doing `svn update,` I search the entire folders, but could not find any folder named startup; nor can I found any file named persist.cfg. Any additional steps may need to perform first?

Thanks.

Files I found so far

./source/lib/sysdep/os/win/wstartup.h
./source/lib/sysdep/os/win/wstartup.cpp
./source/tools/autobuild2/startupservice/startupservice.sln
./source/tools/autobuild2/startupservice/startupservice/app.ico
./source/tools/autobuild2/startupservice/startupservice/stdafx.h
./source/tools/autobuild2/startupservice/startupservice/resource.h
./source/tools/autobuild2/startupservice/startupservice/startupservice.vcproj
./source/tools/autobuild2/startupservice/startupservice/stdafx.cpp
./source/tools/autobuild2/startupservice/startupservice/startupserviceWinService.cpp
./source/tools/autobuild2/startupservice/startupservice/AssemblyInfo.cpp
./source/tools/autobuild2/startupservice/startupservice/app.rc
./source/tools/autobuild2/startupservice/startupservice/startupserviceWinService.resX
./source/tools/autobuild2/startupservice/startupservice/startupserviceWinService.h
./source/tools/autobuild2/startup.pl
./binaries/data/mods/public/scripts/game_startup.js
./libraries/spidermonkey-tip/src/build-release/config/system_wrappers_js/workbench/startup.h
./libraries/spidermonkey-tip/src/build-debug/config/system_wrappers_js/workbench/startup.h
./build/autobuild2/startupservice.exe

[Ykkrosh]

persistent.cfg is AoM's config file (in whatever directory AoM gets installed into), and those options were for visualising how AoM's pathfinding works. (Our game now has some buttons in the top-right of the screen when playing the game to enable similar visualisations for our pathfinder.)

[Ykkrosh]

I've added a basic version of the AoM-style group movement thing now. Select a group of units, tell them to walk somewhere, and they'll arrange themselves in a line formation (and run to catch up if necessary) and then move to the destination as a group.

(This isn't intended to be proper formation support - there's no choice over the shape, and the units leave the group when it's reached the destination, and there's no attack/defence bonuses or anything. This is just temporary loose formations used for travelling in groups without everybody crashing into each other. Proper formations can reuse a lot of the code, but they'll come later.)

Also I made the vertex pathfinder about 6x faster - it's still not great but hopefully it'll be a problem less often.

There's lots of missing stuff, particularly:

* Different unit types should go to different parts of the formation (ranged behind infantry etc).

* Non-move commands (attack, gather, etc) should probably move in formation until close to the target, then break up into individuals.

* Moves over long distances should switch to a narrower column formation to improve mobility.

* Turning by 180 degrees should make units just turn around in place, not all run to the opposite point in the formation.

* It assumes all grouped units start near each other, which isn't necessarily true.

* Run speeds need tweaking.

Are there any of these problems or any problems I haven't noticed (especially any newly-introduced bugs), that ought to be fixed soon (like within the next couple of months), or is it adequate for now?

[Shield Bearer]

Great job, Philip. It'd be great to see people moving in formation

Though abt the turning 180 thing, if the different types should have different places in the formation, unit moving to the opposite direction would have to be the case, thats what i think.

[Ykkrosh]

In that case they'll have to move, but they still shouldn't move to the exact opposite point. E.g. if you have a formation like

[1] [2] [3] [4]

[5] [6] [7] [8]

facing upwards, with infantry in the front rank and archers behind, then tell it to move downwards, currently what happens is 1 will swap with 8, and 2 with 7, and 3 with 6, and 4 with 5. Instead it should swap 1 with 5, 2 with 6, etc.

I guess what might be reasonable is to first determine what type of unit should go in each slot, and then for each type the goal is to minimise the worst-case time that any unit will take to reach its assigned slot, so that the formation will be completed in the quickest possible time. Hopefully that means it'll do the right thing when first creating formations, and when turning. Add a bias to prefer units moving forwards to reach a slot and then it'll probably react more nicely with a unit at the front being lost and the ones behind it moving up to fill in the gap. Not completely certain it'll work in practice, though.

[Mythos_Ruler]

I think default would be...

   ^   ^   ^   ^   ^
  [C] [I] [I] [I] [C]
  [C] [I] [I] [I] [C]
  [C] [A] [A] [A] [C]

Or something similar.

Edited September 3, 2010 by Mythos_Ruler

[Pureon]

I'd go with that formation, I guess depending on whether Cavalry cause trample damage in which case they might be better used in front, not on the sides.

BTW great work Ykkrosh!

[Mythos_Ruler]

Allow me to amend.

   ^   ^   ^   ^   ^
  [S] [S] [S] [S] [H]
  [C] [I] [I] [I] [C]
  [C] [I] [I] [I] [C]
  [C] [A] [A] [A] [C]

[Ykkrosh]

Hmm, so I looked around a bit and found a clever idea for improving the pathfinder performance.

The search algorithm finds all the objects near the moving unit, and looks for a path to the destination going between the vertexes of the objects. When it looks at some vertex X, it wants to find all vertexes Y that it can reach in a straight line without intersecting the edges of any objects. The original implementation looped over every Y, and looped over every edge to look for intersections with the line XY. With N objects that's O(N^2) intersection tests, repeated for O(N) vertexes.

Rather than do that, it's possible to effectively map the two endpoints of each edge onto two angles relative to X (kind of like polar coordinates). When looping over Y, you can then compute the angle of Y relative to X, and only edges whose angle-range overlaps Y's angle need to be considered for intersection testing. Finding the overlapping ranges can be done in roughly O(log N) time using an interval tree, which improves on the O(N) cost of looping over every edge.

(In practice there's a lot of lower-level optimisations - edges are split according to the four axis directions, and then instead of computing angles like tan^-1(y/x) it just uses the value y/x (represented as a fixed-point rational), since tan is monotonic over the relevant range, and the interval tree contains enough data that the intersection test can be reduced to a single coordinate comparison. The interval tree doesn't need dynamic updates so it just generates a balanced binary tree inside a std::vector so there's not a lot of memory allocation.)

The only problem is, in all my testing, it's never better than about 50% slower than the naive O(N^2) method . I don't see any obvious bottlenecks, it's just a high constant overhead from sorting lists and setting up the interval tree and searching down the tree.

Then I realised that although the current implementation has lots of optimisations for axis-aligned shapes, our trees were (unnecessarily) set up as non-axis-aligned shapes, so I removed all this new algorithm stuff and changed one line in a data file and then a bunch of units walking through a forest became 6x as fast as before

[WhiteTreePaladin]

Definitely more responsive now with a cavalry horde in the forest.

[Ghost.b88]

What is the current status of the path-finding component?

Are all of the path-finding algorithm found in AOM implemented?

Has caching paths been implemented?

[Ykkrosh]

I think it's close to the AoM approach now. simulation2/components/CCmpUnitMotion.cpp drives the pathfinder. If it can move in a short straight line to the target then it doesn't use the pathfinder at all. Otherwise it uses CCmpPathfinder_Tile.cpp first, which does a simple A* search over a tile representation of the map (based on terrain movement costs and water and buildings and other large obstructions) and returns a list of waypoints between adjacent tiles. Then UnitMotion repeatedly uses CCmpPathfinder_Vertex.cpp to find a precise shortest path to a nearby waypoint tile, based on the exact geometric shapes of buildings (rotated squares) and units (axis-aligned squares) in a small region around the source, so that movement isn't constrained to tiles. (That algorithm is something like O(N^4) in the number of obstacles which is why it has to be restricted to a short range; AoM seems to do the same, with a similar range to us.)

(You can press shift+D in the game and toggle various checkboxes to enable visualisation of the pathfinder state.)

Paths are all computed asynchronously - UnitMotion just registers a request for a path, then CCmpPathfinder::FinishAsyncRequests executes them all. (Eventually this should ideally be in a background thread but it doesn't seem worth the complexity yet - better to improve the serial performance before adding threads and making it impossible to measure.)

There's no caching of paths (except to the extent that each unit's UnitMotion component remembers the tile/vertex paths it's currently moving along, so it doesn't recompute every turn). The Tile pathfinder usually seems fast enough anyway (it's not called very frequently, and it doesn't do anything algorithmically clever, but it's implemented to avoid e.g. dynamic memory allocation so it has low overhead). The Vertex pathfinder is often slow but I haven't seen a feasible way to do caching - little can be cached across simulation turns because the whole world might change in that time, and little can easily be shared between units in a single turn because they've all got different source and target positions and all have different sets of obstacles within their search range.

[Ghost.b88]

Thank you for the explanation, I have a better understanding of how this path-finding works now.

[Ghost.b88]

What does axis-aligned mean? I.e. AA edges and squares?

What makes the vertex path finding so slow? Doesn't it also use A* algorithm?

And Can someone describe the formation system a little bit further?

Also, how is the collision detection and avoidance set up?

Currently I am noticing a large amount of A* path finding when a group of units travel along the buildings in pathfinding demo map. I noticed when collision occurs, most of the units panic and start a new path finding, driving up the computershortestpath time.

I read the article written by the former aoe developer on path finding, and he briefly talked about formation and group path finding, so I'm wondering how that is handled currently.

In addition, the article also brought up the idea of predicting paths, so that collisions can be avoided in the future. Any comment of the feasibility ofthis method? And can anyone think of better methods for collision detection and avoidance?

Edited January 26, 2011 by Ghost.b88

[Ykkrosh]

Axis-aligned just means the shape is lined up with the world's horizontal axes (X and Z). Units are treated as axis-aligned squares since that's a good enough approximation, but buildings can be arbitrarily rotated.

The vertex pathfinding uses A*, but it's running A* over a visibility graph (not over a 2D tile grid), where a visibility graph has an arc between every pair of geometry vertexes (corners of squares) that doesn't cross a geometry edge. The visibility graph generation is mainly what's slow. Every unit is a square so it has 4 vertexes and 4 edges, so N units means (4*N)^2 vertex-pairs to consider, and each vertex-pair is tested against the 4*N edges to ensure unobstructed visibility, so that's (4^N)^3 vertex-pair-edge tests, so it scales poorly as N increases. (There's lots of optimisations so it's usually not that bad in practice (e.g. the graph is generated on-demand inside the A* loop instead of being pre-generated), but the asymptotic complexity will still be O(N^3). The worst case is when the goal is unreachable (e.g. in the middle of a building) because then it'll search the entire visibility graph before giving up and realising there's no way, and that's quite common when telling a formation to walk alongside a building.)

I'm not sure what more detail there is for the formation system. It's just an invisible 'controller' entity moving around like a normal unit, then every unit in the formation pathfinds towards that controller's position plus an offset (depending on their slot in the formation). If they can reach it in a straight line then they do that cheaply, otherwise they run the pathfinding algorithm to catch up with the formation and then look again. Units in the same formation won't block each other's movement, so they can walk through each other and get into position easily.

There isn't really any collision avoidance. Usually the pathfinder ignores non-stationary units (assuming they'll probably move before we reach them), and if UnitMotion detects the unit will collide with something while executing the next step in the path (via cmpPathfinder->CheckMovement) then it will stop moving and restart the pathfinder with the 'avoid moving units' flag so it's more likely to find a valid path.

I've never really understood this article - it uses a lot of words and diagrams to say how to efficiently predict positions (which seems fairly obvious) and then says almost nothing about how to use the predictions. I guess the idea is that if two units are travelling perpendicularly then instead of everyone stopping and recomputing paths, you can just stop one a few turns earlier and tell it to stay out of the way while the other can carry on its original path, or something like that. That doesn't seem to be what AoM/AoE3 do (I think they're largely indistinguishable from what we currently implement) but I haven't played AoK to see if that's doing something like this.

[Ghost.b88]

For the vertices pair, why is the moving unit represented by a square instead of a point? This would make it n^2 instead of (4n)^2, wouldn't it? Also, when forming the pairs, one of the lines will always be obstructed, the point of the obstruction square that's furthest away from the moving unit. Perhaps this can be an optimization?

[Ykkrosh]

The moving unit is treated as a point . The geometry used by the pathfinder is all the other units' squares, expanded outwards by the radius (/half the square width) of the moving unit, so a zero-width path through that expanded geometry corresponds to a path where the non-zero-width units won't collide.

The (4n)^2 is because the shortest path through the geometry will be a series of straight line segments between vertexes of squares (or between them and the special start/end points, so actually it's more like 4n+2 vertexes) - if it wasn't wrapped tightly around vertexes then it wouldn't be the shortest path - and there's 4n vertexes so (4n^2) potential line segments that could be part of the path.

In theory it's fine to skip the vertex on the far corner of a square; and you can also skip the vertex on the near corner, because the shortest path going around the square will always be directly via one of the two silhouette corners. But I think I tried implementing it (as part of the quadrant code that's still in there) and it didn't work too well in practice - it's common for squares to be overlapping or for the path to start or end inside a square (partly due to numerical imprecision), and if you exclude some vertexes then sometimes you get stupid paths (e.g. a unit walks to a tree a dozen tiles away then walks straight back), and I couldn't find any way to make it work acceptably. (The current less-powerful quadrant code still has that problem a little, and it's pretty annoying.)