Pathfinding

[ScionOfWar]

I've been playing around with the pathfinding engine and I found it to be extremely laggy. Even on short distance paths (IE around my buildings) there's substantial lag.

I really am interested in the scripting behind pathfinding and I've been reading an article for the last two hours or more about the A* Pathfinding algorithm. It looks very interesting and potentially effective, *if* it has the proper settings (eg the heuristic or 'guestimate' on where it should check). I was wondering if the triangulation calcs that I see in the pathfinding engine are truly necessary or if they're just adding a ton of overhead to the simulation when it comes to actually moving the units around.

From my understanding the A* algorithm applies a value to every point on the grid based on distance to the goal (h) and distance to the starting point (g). The actual algorithm is f(n) = g(n) + h(n), where f is the total 'cost' of the point on the grid. Using the heuristic 'guess', it snakes to the goal and on contact searches for the least costly route back. It seems pretty straightforwards and there's some real-time programs based off it which lead me to think we can possibly fix the 0 A.D. pathfinding lag and issues. Here's some examples: http://pixelwelders.com/experiments/Pathfinder2/ http://www.vision.ee.ethz.ch/~cvcourse/astar/AStar.html# http://theory.stanford.edu/~amitp/GameProgramming/index.html

After studying A* I think it would be possible not only to have units avoid other units, but also to have them prefer roads over grasslands, or one elevation over another - realistic features for a realistic game!

To be honest I'm still trying to figure out the logic behind the 0 A.D. engine. I'd love at least tinker with it but maybe someone can give me some pointers on how it's working? Is it using A* math or something else I could research to get myself up to par? It looks like fun!

Edited February 9, 2010 by ScionOfWar

[Ykkrosh]

As part of a general redesign of the simulation system, I've actually reimplemented the pathfinding code in the past week - it's still pretty basic (we need to find someone who can spend a lot of time making it work nicely with terrain and unit sizes and groups and formations and then worry about making it all faster), but I think it probably works better than the old version. It's off by default (since the new simulation system is quite incomplete), but you can try it by using the "-sim2" command-line option. The code is here, and it's pretty much just doing A* over the map tiles with some tweaks(/hacks) to make it prefer more smoothly diagonal paths.

One thing to be careful about is that the game compiles in Debug mode by default, with no optimisations, and (particularly with MSVC's STL) there's a lot of extra checks that slow things down - you ought to use Release mode to get an accurate view of the performance. (There's something in MSVC's GUI to change it, or "CONFIG=Release make" on Linux and run the pyrogenesis (not _dbg) executable). With optimisations, the new pathfinder only seems to take a few milliseconds maximum to compute long paths, which is okay for a single unit (though not great if you have hundreds all moving at once).

Another thing is that the simulation (both old and new) only updates once every 350ms (I think), and whenever you give a command it can't take effect until the next simulation update, and there might be some extra turns of delay to handle multiplayer latency (it can't execute the command until every player knows about it and can execute it simultaneously). I think we need to adjust the timings a bit, but the result will probably be that commands could still be delayed by a few tenths of a second in total, which is usually fast enough that players won't notice much (particularly if there's an immediate audio or animation response, before the unit actually starts moving).

The triangulation code (in the old pathfinding system) is disabled by default, partly because of problems with licensing. If I understand correctly (though I've never looked at this closely so I may easily be wrong), the idea was that instead of doing an A* search over every tile in the map (which can be a hundred thousand nodes), you split the map up into a smaller number of large triangular areas and do A* over them. One of the main difficulties with A* is that doing anything a hundred thousand times is going to be a bit slow, so simplifying the map into a much smaller graph is going to help even if the simplification is fairly complex. But I don't know how much of a practical improvement it makes, or how it compares to other optimisations. I've set up a very rough performance testing thing for the new system (run "./test -test TestCmpPathfinder" (or test.exe on Windows, or test_dbg or test_dbg.exe for debug version) in a profiler, or record how long it takes and try to subtract any constant overhead), so it'd be good to see what effect any changes have.

After studying A* I think it would be possible not only to have units avoid other units, but also to have them prefer roads over grasslands, or one elevation over another

Yeah, you can do that by changing the costs for movement between adjacent tiles. The tricky bit is that if your heuristic overestimates the true cost then A* might never discover the best path, and if your heuristic underestimates the true cost then it'll have to explore a lot more tiles before it's confident it's found the best path. So you need a careful balance between complex movement costs (used to model terrain types and slopes and keeping distance from enemy units etc) and reliable heuristics, to get correct and efficient behaviour.

Pathfinding is interesting since you can easily get something that basically works, but then you can spend months adding features and optimising it - I think I've mostly stopped working on it myself (since it would take too long to gain enough expertise to do a good job of it, and I need to work on other things instead), but I'd like to see what other people can do with it

[ScionOfWar]

Pathfinding is interesting since you can easily get something that basically works, but then you can spend months adding features and optimising it

lol I have to agree here. The basic logic behind A* seems simple enough, but as the third link I posted above kinda proves, there's endless ways to design the heuristic. I heard one person compare it to art haha! I'm going to definitely have to experiment with it, since it's so interesting (read: confusing as hell)

You need a careful balance between complex movement costs (used to model terrain types and slopes and keeping distance from enemy units etc) and reliable heuristics, to get correct and efficient behaviour.

I was wondering if something like this is feasible as a rough concept for how the heuristic would place the cost on open nodes. The differences could even be made smaller so it spends less time differentiating if it was a problem:

Unfavorable terrains (marsh or forests) - 1.01

Grasses/Easily passable Terrains - 1.0

Favorable terrains such as roads- 0.99

Nodes containing human units, or trees, could be 'passable but highly unfavorable' (maybe a value like 2.0) to prevent the blockage we see sometimes between two units. This may make it possible for units to pile up on eachother, but it would potentially fix the chokehold problem of big armies (unless buildings enter the fray)

Cliffs and occupied building slots would be closed completely, and might even alter the heuristic of nearby nodes to make them 'unfavorable'.

This way it would choose any one of the three normally available nodes, but perhaps differentiate especially on longer paths so units might prefer a small detour around a forest over going through it. This could be especially increased when you're using armies, rather then individuals, since a platoon of 30 soldiers is clearly going to take more space so they detour around congested regions. Of course the numbers above are just to demonstrate the idea, the exact figures could be anything.

For speeding it up I was reading some interesting things which we could maybe put into practice. One is to calculate long paths using a smaller grid system (like what you mentioned with the triangulation), then calculate the active 'branch' of the path only. This way you can spend less time calculating how to get from point A to B to C to D, and just focus on point A to B first, and then B to C, and finally C to D.

Another point I noticed mentioned several times is that overestimating the heuristic is always better then underestimating. It may not guarantee the shortest path, but it can help to guarantee the faster calculation. But this may be easier said then done heh. I'm personally of the opinion that longer paths may sometimes be interesting, and that we might want to entertain them especially if it means quicker computations. After all, units in reality sometimes choose their own route, not necessarily the absolutely quickest or even the one given by their commanding officer. Then again people may expect their soldiers to march through the forest only to be surprised (and slaughtered) when they instead flank around the left into a fortified enemy base, and too much of this can definitely be detrimental.

I will continue to play with this, my mind is full of ideas. Most of them I'm sure you and others have hashed through, but perhaps I'll offer a fresh perspective

It's a learning curve though, this is my first time working in Java so I'm a little unfamiliar with some of the rules. Luckily, all scripting languages seem to be similar at least in the thick of things. It's just all those -> and .push commands I will have to figure out hehe

As a question for setting up the alternative pathfinding system: you said "you can try it by using the "-sim2" command-line option." ...I know this may sound stupid, but ehh, how do I do that? I'm new also to building in the workspaces so I'm a bit clumsy with it. In case it matters, I'm on Windows XP.

I would love to dedicate some time toying with pathfinding though. Off the topic slightly, I had a dream about pathfinding last night

Anyways thanks for the reply, I will go spend some time dissecting the file you mentioned

Edited February 10, 2010 by ScionOfWar

[Ykkrosh]

Grasses/Easily passable Terrains - 1.0

Favorable terrains such as roads- 0.99

This would mean it would prefer a 99-tile-long path on grass over a 101-tile-long path on road, so it would rarely pick the road. The differences need to be much bigger in order to have visible effects. I don't know exactly where a sensible cutoff is, though.

this is my first time working in Java

This is C++, not Java . (Some of the code (in .js files) is JavaScript, but that's not Java either - they're unrelated except for their names.)

As a question for setting up the alternative pathfinding system: you said "you can try it by using the "-sim2" command-line option." ...I know this may sound stupid, but ehh, how do I do that?

In the VC++ IDE, I think you need to right-click on "pyrogenesis" in the project explorer panel on the left of the screen, and select "Properties", "Debugging", "Command-line arguments", and put -sim2 in there, and then run it from the debugger as normal (press F5 or whatever). Hope that works

[ScionOfWar]

It certainly does work! I love the ability to see the calculated path, that's a very nice feature for debugging and tweaking. I am going to play with this for a while and I'll probably pop back up asking questions again in no time

I did notice a possible problem - when you right click on an impassible node, the script searches an enormous radius. Maybe something worth detecting because that could result in sizeable calc times if you select 30 units and right click a tree hehe.. though it may be possible to treat grouped armies as one unit, at least for the pathfinder (speculating lol)

However the lag I mentioned seems remedied by the changes in the pathfinding, even with the debug visuals and the aforementioned problem. It looks pretty efficient too in terms of searching. The best I can do is maybe tweak and play with it and show you guys my results lol

Thanks again for your help and keep up the good work. Hopefully as I get better I will be able to contribute

Edited February 12, 2010 by ScionOfWar

[Ykkrosh]

I did notice a possible problem - when you right click on an impassible node, the script searches an enormous radius.

That's an inherent difficulty with A* - if it can't reach a destination node, it doesn't know it can't reach it, because as far as it's concerned there could be a wormhole from the other side of the map directly into that seemingly unreachable location, so it wants to explore the entire map before it can be sure there's no valid path. I've currently got an arbitrary search limit of 5000 tiles so it won't actually explore the whole map, but it's still a performance concern.

I expect part of the proper solution is to not compute paths to unreachable locations - if you're attacking a building or harvesting a tree etc, it ought to compute a path to the edge of the object rather than the center. Currently it sort of does that, by setting the goal to a circular range rather than a point, but not very well.

Since we have a grid, there might be other ways to avoid the problem in special cases: if the pathfinder has explored tiles in a ring around the goal, but hasn't been able to reach the goal, it should give up immediately because there's no point searching further outside that ring. Haven't thought about this much, but it seems like a simple matter of detecting topological holes - when a tile is added to the 'closed' set that will fill in a gap (it's closed on at least two sides and unexplored on at least two sides), the algorithm could walk around each edge of the closed tile set and if it finds one is the outline of a hole (if you walk with closed tiles on your left and when you get back to the start you've turned 360 degrees rightwards, then it's a hole), and the goal is in the hole, then don't bother searching further outside the hole. Or something like that.

[rjs23]

Im curious... Will this game take advantage of muiltcores processors?

Like you could assign pathfinder to cpu 1, assign AI to cpu 2, assign sounds/networking to cpu 3, and etc so on.

[Ykkrosh]

No. To do that well would need the engine to be designed from the ground up to support multithreading, and we haven't done that (since we started writing it long before multicore processors existed), so it would take a lot of effort to redesign everything for that and to make it work reliably. It would also require the gameplay system to be redesigned for parallelism - e.g. the player AI can trigger pathfinding which can affect player AI, but if those parts are running in parallel then it needs to be changed so that neither has to wait for the other.

So it's technically challenging and we already have enough challenges simply making the game work at all, so it's not something we're planning.

[DGMurdockIII]

please do not short hand AI take your time on it and make it the best you can and allow people to people to make improvement to ai engine that would also be included in to the base game

[Kimball]

Not to worry, Murdock. The AI will not be written in haste.

[DGMurdockIII]

good AI is not something to take lightly even if you keep start off with just basic path-finding keep improving it to add more complected stuff during the alpha/ beta test that would be the best way to do it so you can get feedback

[Kimball]

That's exactly how we intend to handle this.