AoM-like pathfinding/movement

[Ghost.b88]

How do the edges come into play?

Also, we noticed when the formation is scrambled, units try to catch up to the formation, and needs to re-calculate their path everytime, so this may lower the performance. What's worse is when units are close to their destinations but goes all the way back to their formation! We are thinking of doing a check there (if closer to destination, go to it, when close to formation, join back), not sure what the performance gain is, but it seems to make more sense this way.

Also, what does the avoid moving unit flag do? Does it do anything intelligent to avoid moving units? such as waiting for few turns for the moving units to leave the position.

As for unit position prediction, perhaps we can build a virtual map for future turns, and all the units who have paths established register their future positions on the virtual maps, and when it comes to path-finding, the unit checks its own future path against the virtual maps, and re-route if a future path is blocked?

Also, how come the Vertex path finder may be in a situation where it ends up in a non-reachable location? Doesn't the tile path finder already assesses the possibility of path-finding?

[Ykkrosh]

Of the (4n)^2 potential line segments, any that intersect an edge are not valid (since they'll involve moving through another unit/building), so the visibility tests exclude them from the visibility graph that the A* searches.

I think the behaviour of units moving into formations is primarily a gameplay design issue - the first step is to work out what players would want their units to do, and then implement it and optimise it (or throw the design out if it's impossible to implement efficiently enough), rather than starting with performance concerns. (The currently-implemented design is definitely not great for players, so I agree it should be improved, but I don't have any particular ideas of how.)

If the avoid-moving-units flag is set then paths will consider moving units to be obstructions at their current positions (so the path will go around them, though it'll probably be invalid once they've actually moved); otherwise it will ignore them entirely, and only path around stationary units (and buildings and terrain).

It'd probably be good to analyse what scenarios the current design fails badly at (e.g. two large groups of units moving through each other? two single-file columns moving through each other? one group moving past a wandering pig? large melee battles?) and see what could improve those - I don't really know yet what the problems are that need solving (though I'm sure there are some).

The tile-based pathfinder is only an approximation, since it ignores units entirely, and since buildings aren't aligned to tiles and we don't want to be too conservative in blocking all the tiles around their edges (since that'd confuse units trying to walk through cities), and buildings might have been constructed (or gates closed) since the path was computed. It's not a strict over-approximation or under-approximation of passability, so the vertex pathfinder is responsible for dealing with any discrepancies.

[bobsaget78]

We are curious as what is being used to produce the dynamic unit formation? From the component diagram it appears to be done through the use of JavaScript. Where might this be located?

Thanks,

Scott

[Ykkrosh]

binaries/data/mods/public/simulation/components/Formation.js computes the shape of the formation, and tells the individual units to all follow it (via the FormationWalk order).

[Ghost.b88]

We found that in the case of a formation travelling along side a bunch of buildings, path-finding eat up a lot of CPU time. This is due to the units travelling in a formation, and the formation assigns positions for the units to move to. Unfortunately, when the formation travels along the buildings, it assigns positions that are un-reachable / un-walkable for the units, so all those units have to re-do path-finding to the impossible location.

I have seen a worst case where the all the units in a formation tries to squeeze into a small gap / corridor, and because only one unit can squeeze through at a time, the ComputeShortPath can go up as far as 20msec / frame.

The problem can be slightly alleviated by increasing the CHECK_TARGET_MOVEMENT_MIN_DELTA_FORMATION value from CELL_SIZE*1 to anything larger than CELL_SIZE*1, but at the sacrifice of deformation. If it is set to CELL_SIZE*2, then the performance in the worst case scenario increases by 50%, i.e. from 20msec / frame to 10ms / frame.

However, the root problem is still fixing formations. Somehow assigning appropriate positions for the individual units (at least avoid the static obstacles). So far we haven't implemented any real solutions.

Below is our profiler results from VTune. CheckVisibility seems to be a bottleneck within the ComputeShortPath.

Function Name Timer samples Timer % Timer events

allmul 4151 29.37% 4151000

CheckVisibility 1345 9.52% 1345000

isqrt64 1210 8.56% 1210000

CheckVisibilityLeft 874 6.18% 874000

pop 866 6.13% 866000

CompareLength 670 4.74% 670000

CheckVisibilityRight 591 4.18% 591000

allshr 538 3.81% 538000

ComputeShortPath 479 3.39% 479000

LosUpdateHelperIncremental 376 2.66% 376000

CheckVisibilityBottom 369 2.61% 369000

CheckVisibilityTop 282 2.00% 282000

push_back 209 1.48% 209000

_Insertion_sort1<std::_Vector_iterator<Edge,std::allocator<Edge> >,EdgeSort,Edge>

204 1.44% 204000

ProcessNeighbour 127 0.90% 127000

find 101 0.71% 101000

CalculateCostDelta 97 0.69% 97000

_Unguarded_partition<std::_Vector_iterator<Edge,std::allocator<Edge> >,EdgeSort>

93 0.66% 93000

SplitAAEdges 83 0.59% 83000

[Ykkrosh]

Unfortunately, when the formation travels along the buildings, it assigns positions that are un-reachable / un-walkable for the units, so all those units have to re-do path-finding to the impossible location.

Yeah, and impossible locations are bad because the algorithm searches the entire visibility graph before realising it's impossible . Maybe the pathfinder could do something like test if the target is inside an obstruction and the unit is outside it, in which case it'll definitely be impossible and it should pick a better target, e.g. change the goal to a CCmpPathfinder::Goal::SQUARE matching the obstruction. That sounds like it should work for buildings, though maybe not for large overlapping groups of obstructions (e.g. tightly-packed ranks of enemy units, or impassable terrain).

allmul

Hmm, that looks like 64-bit multiplication - all my testing so far has been on 64-bit Linux, where a 64-bit multiply is just a single instruction, and I haven't worried much about 32-bit builds. The CheckVisibility functions do a lot of CFixedVector2D::Dot then compare with 0. Dot does 32-by-32-to-64 multiplications (a bit like the mul32by32returnHi but shifting by 16 instead of 32 and hoping the result won't overflow). Maybe it'd be possible to add a specialised DotAndCompareToZero function which uses some trick to multiply more cheaply on 32-bit x86? (It could skip the >>fract_bits too since that's just throwing away precision before the comparison with 0.)

[Ykkrosh]

Hrm... I've been rethinking this a bit, based on insider information.

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).

Experience shows that's not okay, even after trying to optimise the code, so algorithmic changes are needed. What AoM does instead is (I think):

When a unit is moving from A to B, start with the proposed path A-B and check it for obstructions. If the first obstruction you hit is C, let C0 be the point of intersection, and let C1/C2/C3/C4 be the vertexes of C (where C1 and C4 are both on the edge you hit). Construct the paths A-C0-C1-C2-C3-C4 and A-C0-C4-C3-C2-C1 (where the parts in bold are the known obstruction-free segment), and repeat this process for each path in parallel. Check C0-C1 for obstructions, discover it hits D, construct the paths A-C0-D0-D1-D2-D3-D4 and A-C0-D0-D4-D3-D2-D1; check C0-C4 for obstructions, discover happily there's no obstruction, so construct the paths A-C0-C4-C3-C2-C1 and A-C0-C4-B. Now there's four paths, so repeat for them all. In general, when the next step of the path hits an obstruction, throw out the remaining steps and construct two paths that try to circle around the obstruction in each direction; when the next step doesn't hit an obstruction, continue circling in that direction and also try to go directly from there to B.

If I got the details right (I'm not sure I have quite), then this gives an algorithm that heads towards B and then basically walks around the outsides of any overlapping group of obstructions that it hits until it's reached far enough round the other side to leave the group and carry on towards B.

After finding the shortest path by this method, simplify the path. Start at point A, and loop backwards over the waypoints W in the path, and if there's an unobstructed line from A to W then cut out all the intermediate waypoints and go direct from A to W. Otherwise, loop backwards over W and find point P on the line A-C0 such that A-P and P-W are perpendicular; if P-W is unobstructed then go directly along A-P-W and cut out intermediate waypoints. Otherwise, we can't simplify from A, so try again from the next waypoint.

I believe this matches the observable behaviour of AoM, including what could be considered bugs. For example, the red circle wants to reach the green cross, and follows the red path:

It tries to go direct, hits an obstruction, then loops around the line of obstructions. That's longer than a path that goes around the blue obstruction - our current pathfinder implementation will always find the shortest path, but in this case AoM chooses the longer one. If you remove the blue obstruction, then the path simplification takes effect: the first three down/right/up segments of the path get cut out and it goes straight across to the right. It's possible to get pretty crazy paths if you have a complex layout of overlapping obstructions and then carefully arrange obstructions to block this simplification.

About performance: Assume we create at most M extra intersection-vertexes (like C0, D0 in the earlier example) per obstruction, where typically M=1. (This is a bogus assumption - there's no upper limit unless the algorithm explicitly forces it. (In AoM I got a path to create five new intersection-vertexes on the edges of a single wall object, before running out of physical space, so it doesn't impose a visible limit). I'll hand-wave this for now and assume it's a small constant). With N obstructions, we have at most N*(4+M) vertexes. If we process paths in the correct order, I think it's kind of like A* with an admissible heuristic, so we'll only visit each vertex once (since the first time will always be the shortest path through that vertex). So the main loop of the algorithm gets called at most N*(4+M) times, and each time it's checking for intersections with the N obstructions, so that's O(N^2), which is much better than the O(N^3) of the current pathfinder implementation.

I'd be surprised if I explained this well enough to make sense to anyone, but I think I can almost understand it myself now. I suppose I should try implementing it some time soon, before I forget it all - in theory it should be much faster than the current code, and it will sometimes pick sub-optimal paths but probably nobody will notice (and it's good enough for AoM (and AoE3 and AoEO, I think)), and the implementation shouldn't be more complex than the current code. The main risk is that I'm not understanding the algorithm correctly and it won't actually work, but the best way to discover that is probably just to do it and see what breaks.

[Pureon]

Very interesting read. Pathfinding is way beyond my abilities, but after reading through your post twice the AOM method is starting to make sense now.

Another approach used by some RTS games for medium-to-long range movement is to use predefined node networks. These nodes would be added by the map designer, probably using the map editor, to guide units around the map. A simple example looks like this:

This type of pathfinding probably wouldn’t be very useful for 0AD, I don’t like it personally because I find it too linear, but it’s how Supreme Commander worked so I have some experience placing AI nodes. Short-range movement is a whole different story, as are random maps...

[Mythos_Ruler]

As a map designer, I'd find it rather interesting to design "preferred paths" for units on a map. For instance, give certain ambuscade areas pathing preference would be interesting, as well as other choke points. Though, I wonder how easily this could get really effed up in the hands of less experienced designer.

[Pureon]

Though, I wonder how easily this could get really effed up in the hands of less experienced designer.

The answer is very easily, most map designers kept it very simple or didn't even use AI pathing nodes making maps almost useless for singleplayer matches. It took a few years of testing. Alongside the pathing nodes, you also had defense markers, expansion markers, naval (port) markers, and island markers - so a lot of the singleplayer AI gameplay was pre-defined by the map designer for the AI to follow. As I said before, it didn't quite work...

[Ykkrosh]

From what I've read, SupCom didn't support random maps at all - is that right? I think we really want to support that eventually (since it can help a lot with replayability) so we need a purely algorithmic solution, and we can use that solution for hand-made maps too and save the designer some seemingly error-prone work. (Also I think we really want to support less experienced designers, since we like modding, and (unlike commercial games) we can't expect employees to spend a year learning how to make good maps for our engine.)

I think there's actually two largely-separate things here: pathfinding and terrain analysis (briefly described here). The latter involves identifying bases and islands and shores and forests etc, and finding useful choke-points and ambush sites and locations to launch attacks from, to help the AI scripts make decisions about what to do and where to go. That information isn't used at all for human players - humans and AIs both share the pathfinding algorithms to get from A to B, but only AIs need this extra information in order to decide what "B" should be. It sounds like a lot of that SupCom stuff is the terrain analysis, but the map designer is forced to do all the work.

So I think we need an algorithm to do this terrain analysis, though once we've got it it might be possible to give map designers optional control so they can mark in extra ambush sites or forward base locations or whatever. That probably depends on the details of the algorithm, and current I have no idea how it'd work in detail, but it sounds a good thing to keep in mind

[Pureon]

SupCom didn't support random maps, and it's maps were very open with fewer obstructions (because alien worlds are just dust with a few rocks ). A pathfinding algorithm is the best solution for 0AD, I shouldn't have even mentioned pathing nodes really.

[wraitii]

I don't know if you've already read it, but this article might give you some insight about formation pathfinding.

Edited March 4, 2011 by wraitii

[tuan kuranes]

For short "pathfinding", where perofrmance is the most lacking, specially with lots of moving units, we should rather target "crowd" tehcniques.

Those technique evolve around "collision/obstacle avoidance" techniques:

Here's the most relevant papers

http://gamma.cs.unc....esearch/crowds/

http://grail.cs.wash...ts/crowd-flows/

Here's an nice implementation of local obstacle avoidance and lots of post and links about it:

http://digestingduck...-search-results

On formation, a nice idea/feature is "formation sketching" which would give a nice "commander/strategic" capabilities

http://graphics.cs.u...on-preprint.pdf

Edited May 25, 2013 by tuan kuranes

[historic_bruno]

For short "pathfinding", where perofrmance is the most lacking, specially with lots of moving units, we should rather target "crowd" tehcniques.

Should we? Sounds like something that needs to be argued for. What does it offer that we don't have otherwise? Is it a good fit for an RTS like 0 A.D.? Would it improve performance, is it scalable? Would paths be reasonable and what players expect when they order units to move? Would it integrate well with the long pathfinder? Would it work well with formations? Because we don't really need to simulation human crowd behavior (that has its applications, of course), we need predictable, fast, smooth pathfinding that complements 0 A.D. gameplay. If it does that, it will look and feel good and it needn't be realistic crowding behavior IMO.

[tuan kuranes]

@historic_bruno: s/should rather target/could consider... pardon my french.

Short path range is the perf killer as soon as lots of entity are in the game (end of game, or a 6player game), and A*/jps is perf limited, too much computations, too much memory moves, etc.

What I pointed in the crowd techniques is just the "local obstacle avoidance" (loa) parts. What's interesting is that it doesn't "comput" path, but rather "react","adjust" direction when moving to the next waypoint (those computed once from longpath) on a very low range, and only if there's a obstacle (does nothing if not), handling all other moving units (and handling "reciprocal velocity obstacle" (rvo) which is very helpful for formation handling as seen in the nice video in my post which uses loa/rvo techniques), and letting each unit have it's own avoidance technique (units size, speed and event tactical style).

It's very low computation, that's why crowd techniques use that, and therefore very scalable (~15.000 units moving real time on current cpu).

( here's a "sort of" loa/rvo demo with code and source http://software.inte.../samples/colony 65000 units at 20ms/frame using threads or 200ms without)

- Another (related) point is that Its currently very hard and slow to code/test/bench current pathfinding code.

Currently it's a all or nothing thing to make changes on the pathfinder...

I would propose to consider moving all pathfinding code as a static external lib, with a clear and nice interface, but with under the hood, much more flexibility, as in the ability to select/tweak pathfinder algos at runtime. (see the refrence pathfinding library "abstraction" https://code.google.com/p/hog2/ and how researche use it to test code https://code.google....n%2Ftrunk%2Fsrc)

Then we could add a 2D testing/dev wxwidget app that uses it.

Would be a top-down 2d view grid, with real-time pathfinding technique selection and tests. scenario loading, map loading, benchmarks, etc.

(here's some example of what I'm thinking about for the gui and capabilities http://www.cgf-ai.co...acastarexplorer )

Once we have pathfinding code as a more flexible lib, and a testing app, it's a matter of adding algo to the lib, experimenting and discussing on "testable" algos by everyone.(could also experiment with threading/scheduling pathfinding there.). Once everyone agrees, just making the algo the "default" in 0Ad, minimizing breaking changes, but still allowing them.

So adding/testing any other techniques (or formation), or tactical reasonning, would just be adding that to the pathfind lib, then testing/benching it with all scenarios we consider mandatory to be solved by the pathfinder (have to build a nice repository of maps/scenario/case demonstrating the needs.), adding it to svn, and then launch a discuss thread.

Edited May 26, 2013 by tuan kuranes

[wraitii]

I think if someone is willing to take the time, having the pathfinder as a separate library could be interesting in regards to "this could help the rest of the free gaming community, and probably more".

Discussions about pathfinder are however usually fairly sterile, because there is a huge difference between theory and reality in that aspect. Crowd stuffs could be interesting, particularly as your description makes them "simple enough".

It seems to me that pathfinding in RTS could use 4 steps:

-Accessibility checks: as far as we know (we being the unit that moves), is the target accessible or is it not? If inconclusive, assume it is. Philip had implemented that with squares that were connected to each other. (I personally implemented that in JS for the AI using a flood-fill that's never updated after game start.)

-Long-range pathfinder. Returns a few waypoints for avoiding big obstacles. This can also be set up to avoid forests, coasts, stuffs like that. That's the thing I JS-coded in the AI and that is inefficient there (also because it's fairly unoptimized. It's fast enough only because I downscale the map by a factor of 3). I believe that's were A* + JPS shines.

-short-range pathfinder: get the path to X, where X isn't far away.

And on top of that, we could add some crowd stuff in case there are many units around to make movements more fluid. This might make units slightly lose track or where they want to go, but with proper tweaking (and some units perhaps stopping), I'm sure it would get efficient enough. But it means work. Lots of annoying work, as pathfinding never really works properly.

As for formations, I think the theory was that they would resort to snaking in a column (fairly un-cohesive) if moving over long distance, mostly eliminating the issue of rigid formations getting stuck but leading to some pain with short-range pathfinding (this is where crowd movements might be able to shine). Then as they get in formation, they should basically be treated as one big unit. Individual movement in those cases could probably be made simple enough to handle rotation and a few other cases (turning around, turning 90° right…)

That's how I see it. With crowd movements, perhaps (only speculating here), if we add buildings to them, we could have a fairly imprecise short-range pathfinder just to avoid getting stuck in a few edge cases (such as having to make a u-turn to get around an obstacle).

Tuan Kuranes: am I right in believing that crowd techniques basically loop over units and adjust their orientation each frame (or about each frame perhaps)?

(and secondly: are you French?)

[tuan kuranes]

a separate library could be interesting

Looking at actual long pathfinding rewrite patch, that would help even just there, easing the transition and work collaboration. (the patch is a lot of new files mixed with other components, lots of defines in order to keep old methods, a "b" folder, etc.).

huge difference between theory and reality

That's why I'm advocating a test app with run time selection of algo: experimenting made easy, discussing based on facts.

@wraitii the crowd techniques I'm referencing, loa/rvo, does that kind of thing. and secondly, french indeed..

Edited May 26, 2013 by tuan kuranes

[CharlesS]

Hello.

I just thought I would pop in to point out that assistant professor Nathan Sturtevant wrote a path finding test bet called HOG (and now HOG2) that is codded in C++ and open source. It also has a few prebaked path finding algos that might come in handy. If you like, you can pick that up here...

https://code.google....source/checkout

Also, if anyone would like some laypersons info on A*+JPS, there is an interesting read here...

http://aigamedev.com...in-pathfinding/

Long story short, JPS and friends makes a path finding algo much faster because it quickly eliminates calculating multiple possible paths that would all have the same effective length, or at least that's what I had taken away from it. The results on that page are pretty astounding in any case. If you're not already, you should definitely implement something like this.

Anyway, I really hope you devs get the problems in the path finding sorted out soon, it's being a real drag. I'm trying to play with the code myself, but all I managed to do is more or less narrow the problem down to the A* implementation in CCmpPathfinder_Vertex.cpp, which was a foregone conclusion.

[eduh]

Hi, I'll just jump right in without knowing what are you talking about exactly right now, but I wanted to show this:

http://olddevblog.neocoregames.com/blog/devblog/behind-the-scenes-soldier-pathfinding-in-king-arthur-ii/

[Lion.Kanzen]

any news about this?