Progress reports on funded work

[liamdawe]

Well I am perfectly happy now i know he isn't paid until the work is done that is perfect and yes thank you as well for changing the text is was slightly misleading.

I have donated to both and also as above would donate to a third

[Ykkrosh]

If he counted every hour so far, he'd probably have done a month already, with nothing concrete (yet) to show for it.

Instead, he's taking unpaid time to test various things (because many ideas don't work out).

In general I'm only counting time spent on long periods of focused work, since that's the only thing I can realistically count - that could be writing code or researching algorithms, and could be successful or could be unsuccessful (I'll still count it if it gets thrown away later). The rest of the time, I've been partly doing game-related stuff but without much focus and I have no idea how many hours of real work it's equivalent to, so I can't count that fairly; part of that has been thinking about pathfinding but more has probably been other bugs and features and forum discussions and IRC discussions etc, while being distracted by other activities (finalising PhD dissertation, playing games, looking for a proper job, reading, living, wasting time on the web, etc).

I think my recent problem is that I find pathfinding quite painful to work on, but I'm unwilling to just give up (since it really needs to be solved and (perhaps overestimating my abilities) I think I really ought to be able to solve it adequately), so I've been putting it off and spending more time on distractions . The main pain is that if I want to fix the long-range pathfinder algorithm, I also have to change the short-range pathfinder code, and the obstruction management code, and the unit spawning validity-checking code, and the building placement validity-checking code, and the AI building placement selection code, and the debug visualisation code, and probably some other bits, since these things are unavoidably interconnected - it's easy to come up with ideas for individual parts but it's hard to come up with a design that works for the game as a whole. But I think I've generally settled on a way to attack the problem now, so hopefully I'll be able to make some proper progress again (though I've said that kind of thing before...)

If he didn't have this, he'd be looking for a job and then working, and then have even less time to work on the game.

Yeah, the main difference the funding makes is that it has removed the pressure to immediately search for a full-time job. I assume I'll have much less time for the game once I start one, so this lets me put it off until later and continue doing some work for the game (even if it's nowhere near 40 hours per week on average) in the meantime. So I suppose it's more about delaying a slowing of progress, rather than speeding up progress.

(On the assumption that I'll have less time in the future, I think that towards the end of this period I should probably focus on writing some high-level technical documentation so that it's easier for other people to carry on the work that I've been hoarding. Writing documentation is painful and boring, which is why I haven't really done any in the past, but I should be able to put up with it if I'm getting paid for it )

[plumo]

Philip, I love your honesty

The importance of pathfinding improvements can't be underestimated, so I hope you find a good way of dealing with it. Take your time.

[Mythos_Ruler]

Regarding pathfinding... I'm incredulous that there isn't some kind of ready-made solution already out there to use. I mean, I'm sure someone else has figured it all out already. Is there no resource for this? I feel like the gaming industry (including us) spends an inordinate amount of time solving the same problems over and over that have already been solved a hundred times over by others. Why is there no central resource to store these solutions? Why must the wheel be rediscovered again and again and again? It holds us back. It holds the entire industry back.

[WhiteTreePaladin]

Well, there is such a thing called trade secrets... Commercial games have no incentive to share. There really aren't many open source RTS games, so this type of code may not really be available publicly. (It will be after 0 A.D though.)

[Ykkrosh]

Every pathfinding solution has a different set of restrictions and assumptions, and most are so restricted that they're only really usable by a single game. There are still a few reusable solutions, e.g. the open source Recast library is used in a number of games, but it seems to be designed primarily for FPS-style or RPG-style games where you have a small number of independent characters moving small distances around a mostly-static world. (Also e.g. PathEngine used by lots of commercial games). If you're making a game like that and don't have any unusual requirements then I think it's largely a solved problem.

RTS-style games are very different - large numbers of characters, often in formation, moving large distances (e.g. from one corner of the map to the opposite in a single path), and the maps are often randomly generated and are updated dynamically when walls and buildings are constructed (so we can't rely on a map designer manually adjusting waypoints/navmeshes/etc). Something like Recast would probably have poor performance when used this way, if it would even work at all. A fully general solution for RTS games is very hard (maybe impossible), so most games make various tradeoffs to simplify it - no random maps, or small numbers of independent units, or no formations, or align everything to coarse grids, or let units pass through each other, etc - and that still doesn't stop players frequently complaining about rubbish pathfinding in commercial RTSs. So that's not a solved problem yet . There's various articles in books and on the web about how various RTS games approach the problem, and they provide useful ideas and inspiration so we don't have to start completely from scratch, but they usually focus on a small area and I don't think there's anything describing a complete comprehensive system that we could simply copy.

I agree it's stupid and a massive pain, of course

[ribez]

i'm not a programmer, but only an enthusiast, so please forgive me if i say stupid things

instead of improving the pathfinding algorithm, which, as you said, is a very hard thing, how hard is it to implement an algorithm which is not too much clever, but that can take advantage of parallel programming?

http://software.intel.com/en-us/articles/the-secrets-of-parallel-pathfinding-on-modern-computer-hardware/

http://cs.hood.edu/~xliu/566/curpros/cs566-miller-astar-06262010.pdf

http://graphics.tudelft.nl/~rafa/myPapers/bidarra.MIG2011.pdf

[quantumstate]

i'm not a programmer, but only an enthusiast, so please forgive me if i say stupid things

instead of improving the pathfinding algorithm, which, as you said, is a very hard thing, how hard is it to implement an algorithm which is not too much clever, but that can take advantage of parallel programming?

http://software.inte...puter-hardware/

http://cs.hood.edu/~...ar-06262010.pdf

http://graphics.tude...rra.MIG2011.pdf

I don't think this would help particularly. In terms of hardware support we are aiming to support reasonably old hardware. Even if we only supported dual core chips, a theoretical 2x speedup probably still isn't enough for a four player game to run smoothly. This combined with the extra implementation difficulty means it probably isn't worthwhile. To make use of extra processing capacity it is easier to run separate parts of the game onto their own cores e.g. AI on one part, pathfinding on another, etc.

[Guest afeder]

I don't think this would help particularly. In terms of hardware support we are aiming to support reasonably old hardware. Even if we only supported dual core chips, a theoretical 2x speedup probably still isn't enough for a four player game to run smoothly. This combined with the extra implementation difficulty means it probably isn't worthwhile. To make use of extra processing capacity it is easier to run separate parts of the game onto their own cores e.g. AI on one part, pathfinding on another, etc.

The disadvantage I see in that approach is that in the cases where you don't need a lot of AI (e.g. in human-vs-human multiplayer), processing power would go to waste.

[plumo]

What about SpringRTS engine as help for pathfinding?

[Ykkrosh]

I tried the latest released version of Spring (85.0, with BA 7.63) and its pathfinding seems terrible. If I tell a unit to walk from one side of a solar collector to the other, it often walks towards one corner of the collector and then shoots off sideways to a cliff half a screen away and then shoots back and then shoots outwards again to a nearby unit and then back and eventually ends up where it should. In other cases it crashes into the side of the building and bounces off. If I tell a unit to walk to the other side of a group of units, it sometimes walks around them but sometimes just barges straight through and pushes them out the way. I don't know what their implementation does but it looks like it doesn't work yet

[Ykkrosh]

Day 12

As mentioned previously, we need two separate pathfinders (one for planning long-range paths that avoid rivers and buildings and walls etc, and one for finding short-range diversions around other units while following the long-range paths), and there are problems (like units getting stuck) when the two pathfinders disagree on whether a unit can fit through a gap.

What the game currently does is like this: (click for larger image)

The grid pattern on the terrain shows the tiles (each split into 4x4 small cells). The cavalry unit has been told to walk from by the water up to the flag.

The long-range pathfinder works with tiles: the red-shaded tiles are impassable (blocked by buildings or water or steep terrain), and the green- and yellow-shaded tiles are where the pathfinder has searched to find the shortest path. It's finding a path that travels through a piece of wall, because the wall is too narrow to have blocked an entire tile.

The short-range pathfinder works with the cyan squares. Each building (and each tile that is blocked by water or steep terrain) has a square around it. Instead of using tiles, it moves between the corners of the squares, making sure it never crosses one of the cyan edges (since then it would collide with an obstacle). The thin red line indicates the path it's found, walking around the edges of the walls and then heading towards the flag. In this case it luckily doesn't have to diverge too much from the long-range path (which went straight through the wall) so it works okay, but in other cases the inconsistency is a problem.

I've been changing it to instead look like:

The long-range pathfinder is basically as before, but instead of using whole tiles it uses the small cells, so the red/green/yellow-shaded regions are a much higher resolution. That means it can fairly accurately represent small obstacles like the wall, without hugely over-estimating or under-estimating its size.

The short-range pathfinder no longer uses a single square around a building(/wall/etc) - it computes the cyan edges to exactly match the boundary of the red-shaded (impassable) cells. The little yellow circles indicate corners that the path can go between. If the long-range pathfinder found a path, it's guaranteed that the short-range pathfinder will be able to find the same path (or a better one), assuming no dynamic obstacles (i.e. other units) get in the way, because they're using the same cell-based view of passability.

I think that's good - it means the pathfinders now have some better correctness guarantees, and can make some simplifying assumptions (e.g. the long-range pathfinder doesn't have to worry about the short-range pathfinder moving a unit onto an impassable tile), and that makes it easier to implement optimisations to improve performance without worrying about breaking everything.

[Ganon]

Philip, I think that you are making good job

[ribez]

it seems a big step ahead

[Android_]

Thanks for your comments and your newest report Philip, most interesting . I too think you're doing a great job! Please remember my criticism was targeted only at the funding campaign that raised false expectations.

On the issue of not having ideal or out-of-the-box pathfinding solutions: Take the Age games for instance; pathfinding has improved in every instalment of the series. Now with AoEO it is almost perfect but remember how long it took them .

By the way I think we could learn a lot from AoEO's pathfinding. The way it handles formations is most interesting: Units tend to close ranks very tightly when necessary, making them move almost like a fluid mass while still looking realistic enough. It works out quite nicely.

[Mythos_Ruler]

The problem lies in duplicating that fluidity. It's doubtful Robot Entertainment would be forthcoming on this.

[plumo]

I played the original Age of Empires recently and I forgot how terrible the pathfinding was back than

Interesting developments, Philip. Did you test your new approach ? I mean: ms increase ? or lowered?

[Android_]

The problem lies in duplicating that fluidity. It's doubtful Robot Entertainment would be forthcoming on this.

True but I mean we haven't even tried a 'fluid' approach yet. Formations are more or less rigid with strict minimum distances, as they were in the older Age games. Maybe this is something worth investigating.

[Ykkrosh]

Did you test your new approach ? I mean: ms increase ? or lowered?

No - it's too early to meaningfully test performance yet. Need to get all the related functionality working correctly first (there's no point having something that's fast but that doesn't work properly), and then measure performance, and then do whatever high-level and low-level optimisations will have a significant effect, and only then will it be possible to tell whether it works fast enough. (Hopefully it will, but it's hard to predict )

[Ykkrosh]

On the issue of not having ideal or out-of-the-box pathfinding solutions: Take the Age games for instance; pathfinding has improved in every instalment of the series. Now with AoEO it is almost perfect but remember how long it took them .

By the way I think we could learn a lot from AoEO's pathfinding. The way it handles formations is most interesting: Units tend to close ranks very tightly when necessary, making them move almost like a fluid mass while still looking realistic enough. It works out quite nicely.

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?

[Ykkrosh]

Day 13

One of the problems with pathfinding is what to do when there is no path. That's common in normal gameplay - the player will tell a unit to walk to the middle of a lake, or to a tree inside a dense forest, or to a point on another island, or to a point inside an enemy city completely enclosed by walls.

The basic A* pathfinding algorithm handles that situation very badly: it's entirely short-sighted so it won't realise the target is unreachable until it's searched through every single reachable tile in the entire map (maybe tens of thousands), which is extremely slow (maybe tens of milliseconds). On the plus side, A* is able to easily find the tile which is closest to the target and still reachable from the source, which is usually what the player wants - tell a unit to walk into a lake and it'll move to the nearby shoreline, tell it to walk into an enclosed city and it'll walk up to the wall, etc. On the minus side, A* can't do that if we add the JPS performance optimisations to it, because of boring technical details.

So what we really need is a fast way to guarantee there is at least one path to the target, before telling the A* algorithm to find the best of all possible paths. If there isn't a path then we need to pick a new target that is nearby but is definitely reachable.

What I've added now is this: (click for larger image)

Each coloured region is a collection of cells, such that there is a path between any pair of cells in that region. See e.g. the maroon region near the top-center - a unit can move from any maroon cell to any other, but the vertical line of walls defines the edge of that region and there's a separate small light-grey region on the other side of the walls. There's no direct path from maroon cells to light-grey cells so they're detected as separate regions.

This is basically the same as a flood fill in a paint program, except we prevent any region growing larger than 64x64 cells, resulting in the patchwork pattern. The size limit makes it faster to handle dynamic changes (e.g. constructing or destroying buildings) - we can throw away a 64x64 chunk of data and recompute it, instead of recomputing the entire map at once.

When two regions are touching each other, there's a path from any cell in one region to any cell in the other. In this image, the white lines are linking all these adjacent regions. E.g. from the maroon region you can move to the region above, or below, or right, but not left.

Now we can easily tell if there is a path between two points anywhere on the map. For each point, check which region it belongs to, and then search along those white lines to see if there's a sequence of adjacent regions connecting the points. Instead of perhaps a million cells to search through, there's maybe two hundred regions, so this can be very fast.

If there isn't a path, we can easily pick a new target that there is a path to. First find every region that can be reached from the source, sort them by approximate distance from the original target, then check every cell within each reachable region until we've found the one that's precisely nearest the original target, and use that cell as the new target.

After all of this, we can now run the A* algorithm as normal, but with the guarantee that the A* will never have to deal with the unreachable-target case by itself, so we avoid its worst-case performance and allow the JPS optimisations. So that's nice.

This is basically the first part of the MM-Abstraction design (used by Dragon Age). But they use the high-level region graph to find actual paths, whereas I'm (currently) only using it for testing reachability. Their approach can compute non-shortest paths (potentially making units move in ways that look stupid to the player), and they have to include various hacks to minimise that problem and smooth out the paths. I think a better approach might be to use the high-level graph to compute a more accurate heuristic in the JPS-optimised A* algorithm, so that it still guarantees optimal paths but will tend to find the target in fewer steps. But that's future work and not needed at this stage.

Another difference is their design tries to optimise memory usage, whereas my implementation is pretty dumb and totally unoptimised and is happy to throw dozens of megabytes of RAM at the problem. I think my next steps are to ensure everything's working correctly and consistently, and integrate it properly with the rest of the engine, and then do some performance measurements and optimisations, and then it should actually be usable.

[ribez]

Day 13

One of the problems with pathfinding is what to do when there is no path. That's common in normal gameplay - the player will tell a unit to walk to the middle of a lake, or to a tree inside a dense forest, or to a point on another island, or to a point inside an enemy city completely enclosed by walls.

The basic A* pathfinding algorithm handles that situation very badly: it's entirely short-sighted so it won't realise the target is unreachable until it's searched through every single reachable tile in the entire map (maybe tens of thousands), which is extremely slow (maybe tens of milliseconds). On the plus side, A* is able to easily find the tile which is closest to the target and still reachable from the source, which is usually what the player wants - tell a unit to walk into a lake and it'll move to the nearby shoreline, tell it to walk into an enclosed city and it'll walk up to the wall, etc. On the minus side, A* can't do that if we add the JPS performance optimisations to it, because of boring technical details.

So what we really need is a fast way to guarantee there is at least one path to the target, before telling the A* algorithm to find the best of all possible paths. If there isn't a path then we need to pick a new target that is nearby but is definitely reachable.

CUT

it looks like a brilliant solution... waiting for performance measurements

[feneur]

As far as I understand that it sounds like a really good solution to at least part of the problems, nice work so far Philip

[ribez]

This is basically the first part of the MM-Abstraction design (used by Dragon Age). But they use the high-level region graph to find actual paths, whereas I'm (currently) only using it for testing reachability. Their approach can compute non-shortest paths (potentially making units move in ways that look stupid to the player), and they have to include various hacks to minimise that problem and smooth out the paths. I think a better approach might be to use the high-level graph to compute a more accurate heuristic in the JPS-optimised A* algorithm, so that it still guarantees optimal paths but will tend to find the target in fewer steps. But that's future work and not needed at this stage.

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

[iap]

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 )