Pathing algorithms

[pear]

The alt-b debug display shows that pathing-related computations are one of the leading CPU sinks. I'm curious to investigate whether pathing CPU efficiency can be improved using ideas from one of the many research papers on pathing-related topics. (The relatively well known A* algorithm is just the beginning.) I'm having trouble doing so because I don't know the details of the pathing code's requirements. The requirements would ideally be documented in the source code but do not appear to be: https://github.com/spring/spring/tree/d ... th/Default. Can someone explain the requirements of the pathing code? If said explanation is done via commenting the source it'll be readily available to the next person who wants it.

BTW here's a description of techniques many games apparently use: http://www.ai-blog.net/archives/000152.html . I'm mentioning this not as something to add (spring probably has something similar) but for other readers of this post who like me aren't very familiar with pathing yet.

[Google_Frog]

I don't believe in a one-size-fits-all approach. Different games require different representations for pathfinding.

If you're making a strategy game that's entirely 2D, then an approach based on a grid is usually better, since grids give you fast random access to any cell.

Just pointing out that the article says this.

Spring would have to automatically generate navigation meshes on the fly. Quad tree path finding system may do something like this.

[knorke]

Not sure how helpful/related that article is to spring, since two things important to spring are just mentioned in "it is so easy" style sentences.
For example reacting to dynamic obstacles (needed in RTS all the time)

We do a bit of raycasting against the barrel and adjust our path around it

Like what if just stepping around a barrel is not possible but must take an entirely different route now?

Units with more movement physics more complex than Pacman:

Unlike human soldiers, motorcycles can't turn on a dime while they're moving. [...]
With a navigation mesh, this is relatively easy to do. We just test the turn angles and distances as we're doing the pathfinding and reject any paths that require steep turns over short distances.

Also the article only covers single units but RTS has many units moving in groups etc.

[Kloot]

Navigation meshes are a no-go for a heightmap-based engine like Spring.

To be more specific they are not an option for Spring because the heightmap (as well as the occupation map) constantly changes and nav-mesh structures are painfully slow to rebuild even locally. You would also need a unique mesh per movement definition ("MoveDef", of which games can have dozens) making them even more unsuitable.

I know the article and had it bookmarked for a long time, but RTS is not comparable to FPS/RPG/whatever where level geometry is still mostly static. See also Google_Frog's quote.

[pear]

Thanks for your (plural) comments about the article. The issues you raise suggest that a navigation mesh is unlikely to be the right solution.

The main point of my post was the requirements spring's pathing engine satisfies, not navigation meshes or that article. Could someone please explain the high-level requirements and design of the pathing code or point me to somewhere that info can be found?

[PicassoCT]

There is a insane guy around here, who has terraforming as a centrall element of gameplay. He, and the Zero-K guys defined those non-static requirements..

Kloot made manny funny videos.

http://www.youtube.com/watch?v=BQnh10suib0

And yes, the performance with the new pathfinder is better now then 91.0

[Anarchid]

QTPFS is pretty nice, but it has two fatal flaws that prevent its use right now:

- Hideous RAM usage on larger maps, easily exceeding gigabytes.
- Quite noticeable lag between when unit receives move order and whe it actually starts moving. Spamclicking a unit to move move move to some location where you need it like right now just causes it to freeze in place, as each click resets the path-calculation delay.

[Kloot]

Could someone please explain the high-level requirements and design of the pathing code or point me to somewhere that info can be found?

The only place that lists them is the source.

A good starting point would be to look at the IPathManager interface class.

[pear]

Here are some specific questions:

1. A typical map size displayed in SpringLobby is "16x16". What are the dimensions of the max resolution grid used for pathfiding on such a map?

2. I'm guessing that when heavily loaded the path manager is handling on the order of a few hundred new or updated paths per second. Is that right?

3. Have you tried more sophisticated (admissible) heuristics than the modified manhattan distance heuristic in PathFinderDef.cpp? For example the "landmark" technique, which involves computing distances from a dozen or so points near the edge of the map to everywhere and using the triangle inequality to deduce lower bounds on distances between other pairs of points.

[Kloot]

1. Multiply both sides by 64.
2. Yes.
3. Not really, but the specific one you mention (ALT) requires a heavy preprocessing step (landmark selection, which happens to be NP-hard so it again involves heuristics) and my first reply should already tell you why this is not applicable here.

[pear]

Thanks for the numbers in 1 & 2. Those help me predict which algorithms would work well.

Surely landmark selection is not a real bottleneck. Landmarks are a heuristic anyway so picking landmarks heuristically is not a problem. I bet the problematic preprocessing step is computing the distance from the landmarks to every grid point. Doing this every second for the full detail grid is probably too expensive to be worth it. Landmarks could be useful if done more cleverly, e.g. do landmark searches with a low res grid that's designed to always underestimate travel times.

I'll think about possible solutions for spring's pathing and post more later.

[raaar]

how about using a pathing cache?

- could use a lower resolution grid, for example with 256x256 or 512x512 cells

- having a cache table indexed by <srcCell, dstCell, moveDef, commandId(?)> and with data including the gameFrame where it was recorded

- when calculating stuff grab from cache if available and "fresh", else do the processing and update the cache

if i order 20 peewees to move from one location to the other side of the map, some of the data generated for the first one would go into the cache table, then the other ones could use at least some of it making the calculations lighter. If i repeat the order a second later the units would still be eligible to take advantage of the same data as it'd still be "fresh".

Large groups of similar units are often given similar orders within short time frames

[jK]

@raar
all already done

[pear]

From CPathCache::GetCachedPath (https://github.com/spring/spring/blob/d ... hCache.cpp):

Code: Select all

unsigned int hash=(unsigned int)(((((goalBlock.y)*blocksX+goalBlock.x)*blocksZ+startBlock.y)*blocksX)+startBlock.x*(pathType+1)*max(1.0f,goalRadius));

std::map<unsigned int,CacheItem*>::iterator ci=cachedPaths.find(hash);
if(ci!=cachedPaths.end() && ci->second->startBlock.x==startBlock.x && ci->second->startBlock.y==startBlock.y && ci->second->goalBlock.x==goalBlock.x && ci->second->pathType==pathType){
    ++numCacheHits;

1. Why are goalBlock.y and goalRadius included in the hash function but not checked for equality?

2. CPathCache::Add does nothing if the cache already includes an item with the same hash as was added. Normally this is what we want but in event of a hash collision it would seem better to handle the collision in another way, either using traditional hash table methods or simply evicting the old path and replacing it with the new like a direct-mapped L1 CPU cache). What's the rationale for the current choice?

3. How big are the blocks the path cache uses? Are those the same blocks which many popular maps have 16 by 16 of?

[Kloot]

1. you would have to ask its original author (who is long gone)
2. see 1: we can only discuss design decisions about code we wrote and this one has so far not given us cause to question or replace it (cached paths only live for a short timespan anyway)
3. as big as the resolution of the estimator that owns it

[pear]

1. you would have to ask its original author (who is long gone)
2. see 1: we can only discuss design decisions about code we wrote and this one has so far not given us cause to question or replace it (cached paths only live for a short timespan anyway)
3. as big as the resolution of the estimator that owns it

1. I was trying to phrase things in a polite manner. More bluntly, the omission of some of the properties from the equality test appears to be a bug.

2. Suppose the engine makes pathing 100 requests to path from point A to point B followed by 100 requests to path from point C to point D. If there's a hash collision the current scheme will never cache the C->D path and hence will make a total of 101 pathing computations. If hash collisions were handled more intelligently only 2 pathing computations would be required.

[jK]

1. you would have to ask its original author (who is long gone)
2. see 1: we can only discuss design decisions about code we wrote and this one has so far not given us cause to question or replace it (cached paths only live for a short timespan anyway)
3. as big as the resolution of the estimator that owns it

2. Suppose the engine makes pathing 100 requests to path from point A to point B followed by 100 requests to path from point C to point D. If there's a hash collision the current scheme will never cache the C->D path and hence will make a total of 101 pathing computations. If hash collisions were handled more intelligently only 2 pathing computations would be required.

what told you there are any collisions, did you profiled it?

[pear]

what told you there are any collisions, did you profiled it?

I have not profiled the number of collisions. However within the past couple of hours rt has added code to do this profiling: https://github.com/spring/spring/commit ... hCache.cpp .

---

Here's another oddity:

4. PathCache uses std::map, which is typically implemented using a binary search tree of some kind: http://www.cplusplus.com/reference/map/map/ . For this sort of application it's more traditional and efficient to use a hashtable, e.g. std::unordered_map. However changing this probably wouldn't make a significant difference because the cache is limited to 100 items and new paths are created only a few hundred times per second (right?).

[Silentwings]

For this sort of application it's more traditional and efficient to use a hashtable

Well, I got tempted and skimmed the code, seems its mostly about using ::find which is generally better with unordered_map but there are some cases (idk which) where unordered_map does worse than map.

I think unordered maps only exist since C++ 11; idk when that code was written but I'd guess it was well before C++ 11

[gajop]

I think unordered maps only exist since C++ 11; idk when that code was written but I'd guess it was well before C++ 11

Much like most new things in C++11, unordered maps existed in boost well before that.