New pathfinding and grouping

[zesterer]

Presumably you use some form of grid-based A* algorithm? Maybe it is better to 'group' nearby searches to reduce the stress of re-calculating paths that are very similar.

[zesterer]

I recommend you try out a game called 'Liquid War'. It's FOSS, and is in most mainstream distro repositories. It involves a game where you control this pathfinding fluid (composed of tens of thousands of entities) that move towards the cursor, avoiding obstacles. Perhaps this would be a good bit of inspiration? Liquid War does it all at 60 fps, and often with very high resolution grids, so perhaps taking a peek within it's source code might be worthwhile?

[TheJJ]

Never heard of it, but it looks cool and has probably nice inspiration for some areas.

[Jon0]

Having a few modular path finding systems would be interesting, while having one path finding system as close to the original is good, it would be cool having many options like these newer techniques, which may considerably affect gameplay / balance

[TheJJ]

The thing most complained about by aoe2 players i think is pathfinding bugs and especially blockages. So i guess we can try doing something awesome and wait for feedback. Imagine your huge armies just flowing through each other naturally without blocking :cake:

• Long range stuff to find involved chunks
  • Invoked for each group to navigate to some destination
  • Any "old-school" algorithm like A* or D*lite
  • It's fast and just selects areas to take into account for the continuum planning
  • maybe use target following
  • maybe use jump point search extension to speed up A*
• Short range continuum crowd steering awesomeness
  • Density grid/flow field pathfinding
  • 2006: https://www.youtube.com/watch?v=lGOvYyJ6r1c
  • 2009: https://www.youtube.com/watch?v=Hc6kng5A8lQ
  • 2012: https://www.youtube.com/watch?v=I09heZbBcys
  • We'll add lots of improvements and updates for handling heterogenous crowds

-> Basically we'll create a multi-layer navigation system, using ideas from all those (awesome) papers:

• 2006: Treuille, Adrien, Seth Cooper, and Zoran Popović. "Continuum crowds."
• 2008: Yersin, Barbara, et al. "Real-time crowd motion planning."
• 2009: ClearPath: Guy, Stephen J., et al. "Clearpath: highly parallel collision avoidance for multi-agent simulation."
• 2011: Harabor, Daniel Damir, and Alban Grastien. "Online Graph Pruning for Pathfinding On Grid Maps."
• 2012: Van Toll, Wouter G., Atlas F. Cook, and Roland Geraerts. "Real‐time density‐based crowd simulation."
• 2013: Emerson, Elijah. "Crowd Pathfinding and Steering Using Flow Field Tiles." Game AI Pro
• 2014: Golas, Abhinav, et al. "Hybrid long-range collision avoidance for crowd simulation."
• 2014: Harabor, Daniel Damir, and Alban Grastien. "Improving Jump Point Search."
• 2014: Best, Andrew, et al. "Densesense: Interactive crowd simulation using density-dependent filters."
• 2015: Ninomiya, Kai, et al. "Planning approaches to constraint‐aware navigation in dynamic environments."
• 2015: Fuentes, Carlos Eduardo. "Hierarchical Path Finding to Speed Up Crowd Simulation."
• 2015: Van Toll, Wouter, Norman Jaklin, and Roland Geraerts. "Towards believable crowds: A generic multi-level framework for agent navigation."

Especially the "believable crowds" paper seems to be promising in combination with the "crowd pathfinding using flow fields" chunk navigation paper.

If this works and performs, it's probably the best RTS pathfinder ever.

If anyone wants to implement any of these ideas, go for it.

[zesterer]

I think it's important with large groups with the same goal to preserve some kind of locality and flocking behaviour. If they are unable to share data among one-another, substantial optimisation will be impossible.

[TheJJ]

http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter23_Crowd_Pathfinding_and_Steering_Using_Flow_Field_Tiles.pdf

This is more or less the implementation design I was trying to come up with, but with awesome portals between the chunks. It's probably what we want! The portal-navigation can still be done with jump point search or D*-lite, in the description they use plain A*.

some other example: https://vonwolfehaus.github.io/flow-field/

the gameaipro-thing seems to be based on (although it doesn't cite them):

• 2008: Real-time scalable motion planning for crowds, older version.
• Demeulemeester, Aljosha, et al. "Hybrid path planning for massive crowd simulation on the gpu." International Conference on Motion in Games. Springer Berlin Heidelberg, 2011. (no public pdf, sorry..)
• The continuum crowds paper, of course.

[coffenbacher]

Awesome paper. I'm excited for pathfinding in openage... it could easily be the "killer app" for eventually getting aoe2 players to switch. It's one of a handful of things that can be a massive improvement while staying totally true to the original gameplay (especially compared to HD, which had some big pathfinding regressions).

[elnabo]

A hierarchical solution seems to be a good idea. However, I wonder how the gameai paper handle an heterogeneous crowd with different speeds.

[TheJJ]

(this post is subject to change because of adding new ideas or detecting problems)

So in a simplified explanation:

• We wanna have flow field pathfinding, but in gigantic areas it's inefficent as fuck
• We split up the world in chunks (already done since day 0)
• We use A* or similar to choose the chunks involved in the flow pathfinding
• We calculate the weight field within each chunk by looking at the static obstacles
  • For the "awesome but computation intensive mode" we add all units to the grid as well
  • If we don't use it, the units have to do some other collision avoidance as they don't "see" each other as far as I understood it
  • The gameai chapter 23 paper doesn't add the units at each step but does not explain how they do their steering
  • Otherwise, we can reuse the same chunk fields from a cache
• For a group's destination, use eikonal flood fill accross all involved chunks, save them to the cache again
• We calculate the direction field within each chunk by using gradient descent on the flooded chunks (can be cached as well if not using the "awesome but recalculate at each timestep mode", because of adding changed unit positions at each step to the fields)
• Steer units along that field

[Wandalen]

Good problem for GPU.

[heinezen]

i'll just add the thoughts about formation pathfinding from #705 here:

• For long distances find the path for the "leading unit", then make the other units follow behind it. The "long-distance-walking"-formation in AoE2 is only 1 tile wide, so it should be able to follow every path a single unit can go, e.g. a narrow passage
• For obstructions in short distances, let the formation (and not individual units) handle splitting.
• When a formation is forming, compute a path for the individual units to their place inside the formation. Once they are inside, the pathfinding is delegated to the leading unit.

This should compute faster than doing pathfinding across long distances for every single unit in a selection.

[TheJJ]

https://web.archive.org/web/20200414093657/https://www.blog.drewcutchins.com/blog/2018-8-16-flocking

(Updated link with web-archived one)

[simonsan]

http://web.archive.org/web/20190803092008/https://richg42.blogspot.com/2018/02/on-age-des-pathingmovement.html?m=1

[TomJansen]

This hackernews thread could be interesting: https://web.archive.org/web/20200414093542/https://news.ycombinator.com/item?id=22848106

(Updated link with web-archived one)

[zesterer]

I'd recommend not throwing the baby out with the bathwater. A can be very* fast if you throw enough good information at the heuristic function. There's absolutely no need to stick with distance(pos, tgt).

One solution I've seen before is a "heirarchical" pathfinding technique where the world is split into progressively largely chunks, where each chunk is either "empty" or "non-trivial" (i.e: the algorithm needs to walk down the heirarchy into lower-down chunks to figure out whether it's possible to path through it). Over long distances and with large maps with frequent open spaces as is common in an AoE game, this could be extremely fast.

Take a look at this article for how something similar was implemented for massive Factorio maps: https://web.archive.org/web/20200415175445/https://factorio.com/blog/post/fff-317

[TheJJ]

Thanks for the links and ideas :) The concrete plan for our pathfinding is definitely not cut in stone. We have all options and I'd go for a extensible, step-by-step solution. This pretty much depends on how we store the map state, and that is something (among the game simulation itself) that we have to resolve first (i.e. in #1066, I'm on it :D).

The factorio hierarchical pathfinding sounds very promising for the large-scale search, what we have to resolve then is the formation/local avoidance behavior between units. What approach is best there, I can't tell yet.

[sandsmark]

Ref liquid war: The algorithm is described here, though I'm not sure at least I'd be able to implement it from that description alone: https://github.com/bkil/liquid-war-5/blob/master/doc/xml/algorithm.xml

I think this is the interesting part of the algorithm: https://github.com/bkil/liquid-war-5/blob/master/src/spread.s

It's in fairly straightforward assembly, and fortunately it's documented. Unfortunately in french (I don't know french).

As for other (aoe1/2-clone) implementations:

• OpenEmpires uses some kind of fields. It's very efficient, but last I tried it felt kind of "unnatural" (imho units shouldn't move like boids). The meat of the implementation is here: https://github.com/glouw/openempire/blob/master/src/Field.c + https://github.com/glouw/openempire/blob/master/src/Unit.c#L38-L102 + https://github.com/glouw/openempire/blob/master/src/Grid.c

• iirc. FreeAge used a fairly standard a-star, but with some modifications to work more efficiently with the collision sizes of units (though not standard JPS iirc). Like everything else (except the intellectual property part) it was very proper, though I don't remember how it behaved wrt. look and feel.

• aoe (as in https://github.com/FolkertVanVerseveld/aoe) I don't remember if actually has any pathfinding, I can't find it with some simple grepping at least.

• and lastly in freeaoe I implemented a slow mess of different crap that shouldn't be an inspiration for anything (something that resembles a-star, mashed together with something bresenham-like that bresenham would cry if he saw, and some other hacks). while it looks and feels okay, it is slow, unreadable and buggy. I've tested e. g. JPS, but couldn't really get it faster than what I had.

In general, trying to make it both look good (there's a very limited number of angles after all), feels good, and is efficient is hard. Throw in unit formations, minimum attack distances, gates (messes with caching/reuse), fog of war, etc. and it gets even more complex.

(As for a bit more far-out ideas I remember seeing some paper about efficient path finding using something that kind of reminded me of the original aoe2 pathfinding from IIIM. I'll post it if I find it again.)

edit: oh, and for the factorio stuff, that kind of looks like the original aoe2 pathfinding, I think? one high-level tile pathfinder used for long distance discovery, and a low-level one for the smaller parts.