239 replies to this topic

[k776]

My thoughts: If path finding over terrain is faster by not finding fastest path, and just finding shortest distance, go ahead and do that.

If someone needs a fast path, they should be using waypoints.

[fabio]

Ykkrosh, on 08 December 2011 - 02:24 PM, said:

(Bit distracted by other work and PhD-related things and thinking about formations etc, so I'm still trying (not quite succeeding) to get a more consistent rhythm...)

Day 9

Did some research into pathfinding. Independent of the ongoing discussions about formations etc, it seems we could benefit significantly from a faster long-range pathfinder. In particular, the pathfinder needs to quickly plan an efficient route from one side of the map to the other, avoiding impassable terrain (cliffs, rivers, etc) and buildings. It doesn't need to be a perfectly smooth path, and it doesn't need to avoid other units - that's the responsibility of a lower-level module that computes the frame-by-frame movement of each individual unit as it follows the high-level planned path.

(I said a while ago that I was only planning to look at the short-range pathfinder, but performance data suggests the long-range one matters, and changes to the long-range one might change the requirements for the short-range one, so I'm focusing on that for a while.)

The current pathfinder is a pretty basic implementation of the A* algorithm, with the terrain and buildings stored as a 2D grid of passable/impassable tiles. It's reasonably fast - after a few minor simplifications and optimisations compared to the code the game currently uses, it can process about 4 million tiles per second on a fast CPU. But a standard map in the game might have 40,000 tiles or more, and in the worst case (when there's a very long and complex path) the pathfinder might have to process every one of those tiles, taking about 10msec. If you send multiple groups of units to attack the enemy at the same time, that adds up to a reasonably significant amount of CPU usage.

That's still not terrible, but a secondary problem is that tiles are quite large. Our typical units are less than half a tile wide, but if two buildings are separated by as much as two tiles then it's possible for there to be no fully-passable tile between them, so the unit won't be able to find a path between them. If we could replace every tile with, say, a 4x4 grid of sub-tiles, then we'll be able to represent gaps that are a quarter of a tile wide, allowing much more accurate movement of units through complex environments. But then the pathfinder will be about 16 times slower, so we'd need to balance it by optimising the pathfinder much more heavily.

There's quite a bit of existing work on pathfinding over tiles, from both practical and academic perspectives. Navigation meshes are common in non-tile-based games, but they're a bit tricky to update dynamically (e.g. when a building is constructed, or a tree is cut down), and the use of tiles allows us to use more specialised algorithms. Navmeshes might not always find the optimal shortest path between two points; they're just designed to find paths that are 'good enough' in most cases. MM-Abstraction (PDF) (designed for the game Dragon Age) is basically tile-based (non-convex) navmeshes. HPA* (PDF) is a bit like MM-Abstraction with higher-quality (closer to optimal) paths, at the expense of performance; you can adjust the tradeoff by tweaking the algorithm. (In particular you can choose the number and location of nodes on entrances into each region, whereas MM-Abstraction assumes a single node somewhere near the middle of each region). Jump Point Search guarantees optimal paths by simply computing the standard A* algorithm in a more efficient way (skipping redundant work).

One concern is that most of this published work is based on maze-style maps, with a series of rooms connected by corridors. In an RTS game we generally have the opposite: most of the world is open space, with trees and buildings dotted around it, and a few very large obstructions (rivers, mountains, walls, etc), and no rooms or corridors. Some algorithms are explicitly designed to identify rooms, so they'll be useless here, and for others we need to be careful that they have the desired performance characteristics.

Another concern is that some algorithms assume movement cost is uniform across the entire map. There are some interesting features you can get with non-uniform costs. E.g. you can make roads very cheap to travel along, which means units will prefer routes that use roads instead of slightly shorter routes that don't use the road. Or you could identify 'dangerous' tiles (within range of enemy defensive buildings) and make them more expensive to travel along, so the pathfinder will prefer paths that avoid dangerous tiles even if they have to travel slightly further. The game's current pathfinder supports non-uniform costs, but I'm now thinking that it's not really all that useful a feature, and it may add significant complexity, so it's probably best to abandon it and focus on getting basic uniform-cost movement working well.

What I'm currently planning to do is experiment with JPS and see if it actually works in practice - it's nice to have optimal paths (to reduce the chances of players noticing weird behaviour), and it claims to be competitive with HPA*, but I think that will depend significantly on implementation details, so it would be valuable to have an implementation to test and optimise.

What about restricting buildings on a 2D grid (it obliviously complicate rotations but many RTS do this, letting them rotate only by 45/90 degrees) and/or adding to every building a border around it (except on some side of buildings like walls that must be connected) to impose a minimum distance and avoiding creating large obstacles to pathfinder? Will these help?

[Ykkrosh]

ac892006, on 08 December 2011 - 06:25 PM, said:

I have an Idea why not implement it as a bidirectional A* with one half moving from goal state to some mid state and the other moving from initial state to the middle state . You could split the path into a number of small sections this way , with each processor core performing part of the task etc .

I expect that computing from both ends doesn't reduce the total amount of work that's needed in common cases (and it definitely doesn't help in the worst case), and it adds significant complexity. Splitting a single pathfind requests across multiple cores is unnecessary (and adds complexity and inefficiency) - performance is only a problem when we have multiple simultaneous requests, and then we could do each one independently in parallel.

errt, on 08 December 2011 - 09:30 PM, said:

I don't think you should drop non-uniform cost as this is really making a difference the players will notice.

They won't notice it compared to the current game's implementation, since only one (rarely-used) terrain type has a non-default cost, and units don't follow the long-range path precisely so they won't stick to the low-cost tiles anyway. So it won't be a regression compared to the current functionality, and I've not noticed that non-uniform-cost functionality in other RTS games, so I don't think it's a major problem for players

Quote

But I don't think you need an algorithm that always finds the shortest (or better: lowest cost) path, players will mostly not even notice a slightly non-perfect path.

They might notice if a unit walks e.g. two tiles west, two north, then two east, instead of just moving straight two north, which I think is possible with non-optimal algorithms like HPA*. That's probably a rare case, and there are probably ways to tweak the algorithm to avoid most such problems, so it should be okay in practice, though it's nicer if we can guarantee optimal paths instead of hacking around it.

Sylvain Gadrat, on 08 December 2011 - 09:52 PM, said:

Note that it is just for calculating pathes. Camels will still be speeder on sand than on grass. Simply if a camel have to choose between a short path over a grass field or a long one over sand, it will always choose the shortest even if it is speeder to.

Yeah, the actual movement speed can still depend on terrain if we want to - the pathfinder just won't automatically try to avoid the slower terrain.

Quote

Having different terrain type and associated costs seems not a big deal while implementing HPA*

Yep, I think HPA* works just as well as normal A* with non-uniform costs, as long as you're careful to include one transition for each differently-costed section of an entrance. (Performance will suffer a bit from the heuristic being less accurate, as with normal A*, but otherwise it should work correctly.)

Quote

But what make it difficult is the fact that the cost calculation change from one unit to the other, So instead of having to store waypoints and one edge between each waypoints pair, we have to store one edge by waypoints pairs and unit type.

I don't think that's a huge problem - in the worst case we can just duplicate the pathfinder data structures for each combination of passability class and movement cost class. (We need passability classes anyway, to distinguish infantry and ships etc). Not great for RAM usage or cache utilisation or precomputation cost, but we could probably afford it if necessary.

Quote

One big feature that can be usefull in the pathfinder is to correctly handle the unit's size for pathing. It could really help with formation's pathing.

I don't think that would help for very large formations - we usually have too high a density of trees and valleys etc so the formations wouldn't be able to move anywhere at all, if we required formation-sized gaps. For small formations, we probably want them to be able to squeeze through single-unit-wide gaps so we'd have to use the normal unit-size-based pathfinder, and then maybe post-process the paths to nudge them away from obstructions when possible so they don't get squeezed except when unavoidable, or some kind of hack like that.

For normal large units (siege, ships, etc), I think we should probably encode the size as part of the passability class. We already effectively compute a separate passability map per class, so we'd just need to expand obstructions by the class's size when rasterising to the passability map.

fabio, on 09 December 2011 - 08:18 AM, said:

What about restricting buildings on a 2D grid (it obliviously complicate rotations but many RTS do this, letting them rotate only by 45/90 degrees) and/or adding to every building a border around it (except on some side of buildings like walls that must be connected) to impose a minimum distance and avoiding creating large obstacles to pathfinder? Will these help?

Even if player buildings are locked to 45/90 degrees, we probably don't want to restrict player walls or scenario designers to those angles (since it would look a bit ugly), so the pathfinder needs to cope with rotated obstructions anyway. Imposing a minimum distance between buildings would probably be sensible for gameplay purposes to prevent people accidentally blocking in their own units (which has been a problem in the past), and would stop them constructing complex mazes that would potentially confuse the pathfinder, so I think it'd be good to do that some time.

[WhiteTreePaladin]

AoE3 snaps buildings together if you try to place them too close. I definitely prefer that approach.

[Mythos_Ruler]

WhiteTreePaladin, on 09 December 2011 - 05:40 PM, said:

AoE3 snaps buildings together if you try to place them too close. I definitely prefer that approach.

Is that with all buildings or just Houses? I remember it with houses, definitely.

[WhiteTreePaladin]

Pretty sure it was for all. I tended to use my structures as rudimentary walls...

[Mythos_Ruler]

WhiteTreePaladin, on 09 December 2011 - 07:02 PM, said:

Pretty sure it was for all. I tended to use my structures as rudimentary walls...

Yep, you're right! They all snap together. Just playtested.

[Android_]

^ yeah snapping is good.

Philip I can't really participate in the discussion but there's some interesting things that you brought up, keep 'em coming .

[Ykkrosh]

Days 10 and 11

Experimented with implementing and optimising the aforementioned JPS algorithm and some related pathfinding things.



These are on the 512x512-tile Peloponnese map, with a path (shown in blue) going north around the gulf. The coloured tiles are the ones processed by the A* algorithm (in particular the red ones are on the closed list, and yellow on the open list). In the first image, the standard A* algorithm searches outwards in a roughly circular pattern from the start point, so the red tiles go a long way south, until it gets to around Plataea and heads north-west to the target. The second image, with the JPS optimisation of A*, searches a similar area but it leaves a load of tiles unexplored (white) inside that area, because it realises they're never going to be interesting tiles (there's always an equally good path that doesn't use those tiles).

(The chosen path is slightly different in the two cases, but of the same length. There are lots of equally good paths and JPS always prefers one that goes diagonally as early as possible before going vertically/horizontally.)

In this particular example and this particular implementation (with various optimisations and hopefully no major bugs), the standard A* takes about 6msec to compute the path, and JPS takes about 1.5msec, so it's 4 times faster.

Because our terrain tiles are quite large, and might mark a passage as blocked when actually a unit could easily fit through, it may be useful to use a higher-resolution version of the map:

Spoiler

Here it's scaled to 2048x2048 cells (i.e. 16x as many as before), so it can represent much narrower gaps. Standard A* takes about 130msec (22x slower than with the low-res map); JPS takes about 11msec (7x slower than low-res). Bumping it up again to 4096x4096, standard A* takes about 680msec (another 5x slower), JPS about 22msec (another 2x slower).

The nice thing about JPS in this situation is that it doesn't care too much about the number of tiles - what matters is the number of 'corners' (in some non-technical sense) that the map contains. That means it'll depend heavily on the number of trees in the map (since each tree adds four corners that paths can wrap around), but if the number of trees remains constant then higher-res maps won't be hugely more expensive.

There's two problems with my current implementations of standard A* (simplified and optimised compared to what's currently in the game) and JPS. (Warning: getting somewhat more technical now). Firstly, they assume the target of the path is a single point. In practice it might be a large square (units want to get within e.g. 1 metre of a square building in order to attack it) or a very large circle (archers want to get between minimum and maximum range of a target unit). That makes it harder to tell when the algorithm has reached the goal, and harder (or at least more computationally expensive) to compute the heuristic distance to the target. Secondly, JPS doesn't behave usefully if the target is unreachable - the standard A* can discover whichever reachable tile is closest to the target but JPS might have never looked at that tile.

Reachability is a problem with the game's current pathfinder already; units are happy to try forever to reach a target that they'll never be able to, and the pathfinder is very slow at determining the target is unreachable. I think the sensible solution would be to do something like the MM-Abstraction method to precompute a graph of connected regions, then find all regions connected to the source, and then find the closest tile to the target out of all the tiles in those reachable regions. That'll help equally for standard A* and JPS.

For non-point targets, I think the easiest efficient solution may be to simply swap the source and target of the path. The source is always a single point (typically the unit that's moving), so it's easy to run A* towards that point. The target may be multiple tiles, but I think it's easy to make A* start with multiple cells (just shove them all onto the algorithm's open list with g=0 at the start). So finding paths from multiple target tiles towards the single source point should be straightforward, unless I'm getting confused as to how this all works. Then it needs to be integrated with the reachability thing for the previous problem, since the target shape might be half reachable and half not.

That's probably all doable; just needs some more work to actually do it.

The other big problem is how to make units follow the long-range paths while avoiding dynamic obstacles (e.g. other units), and also to not constrain units to moving along tile boundaries (which would look very unnatural). Currently that's the job of the short-range points-of-visibility pathfinder, which uses the detailed obstruction geometry (squares with arbitrary (non-tile-based) location and rotation). To fix discrepancies between long and short pathfinders, it would probably be better if it used the same high-res obstruction tile map that the long pathfinder uses, and then it can add on the dynamic unit obstructions (which can have non-tile-based positions but don't support rotation) to find a usable route, with the added benefit that it will now only have to deal with perfectly horizontal/vertical lines. Alternatively, maybe it would be simpler and/or faster to reuse the tile-based A* over a short range with the dynamic obstructions added onto it (perhaps at an even higher resolution). I don't really know about that - I suppose I need to experiment a bit more.

(In any case, this won't get finished before the next alpha release, so I'll have to leave it until afterwards - that's kind of annoying but I think it's worth taking the time to solve the problem properly. Got a PhD viva next week so I won't be able to concentrate on game stuff until then, but I'll try cleaning up some of the quicker problems with saved games and other bugs.)

[historic_bruno]

Ykkrosh, on 14 December 2011 - 03:38 AM, said:

The nice thing about JPS in this situation is that it doesn't care too much about the number of tiles - what matters is the number of 'corners' (in some non-technical sense) that the map contains. That means it'll depend heavily on the number of trees in the map (since each tree adds four corners that paths can wrap around), but if the number of trees remains constant then higher-res maps won't be hugely more expensive.

That's quite a nice benefit! Hopefully our map designers won't make a checkerboard maze of trees I would still like tree obstructions to work differently, but that's not an immediately concern.

Oh and it may be assumed, but your latest changes require uniform terrain cost?

[Android_]

Quote

Got a PhD viva next week

Does that mean you've got more than one?? Anyway good luck! Maybe you guys could push back the Alpha 8 deadline a bit to allow for Philip's pathfinding awesomeness to be implemented in time .

[feneur]

Android_, on 15 December 2011 - 02:16 PM, said:

Does that mean you've got more than one?? Anyway good luck! Maybe you guys could push back the Alpha 8 deadline a bit to allow for Philip's pathfinding awesomeness to be implemented in time .

Well, we could, but then you'd have to wait for all the other awesomeness =) This release has been long in the making as it is, so unless something unexpected happens it will be out reasonably soon. Better to take the time to implement these pathfinding improvements without the stress of trying to get a new release out soon.

[Android_]

Hi guys,

I hate to be a downer but I'm a bit disappointed by the fundraising campaign. Both Pledgies were explicitly set up to hire a full-time programmer in order to speed up development:

Quote

The game is moving along slowly with the great help from community member code contributions. But we’d like to make some leaps and bounds. Help us pay a developer of 0 A.D, who is familiar with the code, to work on the game for a month.

It seems this is not quite what is happening though. It's not that I'm unhappy with Philip's work, not at all, and I do understand he is a busy man, it's just that we donated for a full-time month.

[ribez]

Android_, on 18 January 2012 - 10:15 PM, said:

Hi guys,

I hate to be a downer but I'm a bit disappointed by the fundraising campaign. Both Pledgies were explicitly set up to hire a full-time programmer in order to speed up development:



It seems this is not quite what is happening though. It's not that I'm unhappy with Philip's work, not at all, and I do understand he is a busy man, it's just that we donated for a full-time month.

i don't see the problem... the full month is made of a certain number of work days. Currently Philip have worked for 11 of these days. When he'll be able to dedicate a full day to the game, the days worked will be 12. Meanwhile he's continuing to code to improve the game in his free time:
http://trac.wildfiregames.com/timeline

[Android_]

Well officially the campaigns were intended to speed up the process by having one person working in a professional way rather than in their free time. That's why they said 'full-time month' which clearly is something different than just some number of days or hours. Again, this is what they said:

Quote

The game is moving along slowly with the great help from community member code contributions. But we’d like to make some leaps and bounds. Help us pay a developer of 0 A.D, who is familiar with the code, to work on the game for a month.

Edited by Android_, 18 January 2012 - 10:39 PM.

[liamdawe]

I kinda agree with Android on this one, if funds have already been paid to the developer then it's not really right, we donated for full time work, not 1 full day here, 1 full day there.

[feneur]

liamdawe, on 18 January 2012 - 10:39 PM, said:

I kinda agree with Android on this one, if funds have already been paid to the developer then it's not really right, we donated for full time work, not 1 full day here, 1 full day there.

Philip is only being paid after the work is done. After one week of work has been completed (regardless of whether the five work days that make up said week are in an actual week or spread out over a longer amount of time) the payment for that week of work is paid out. It would of course in many ways be great if the work would be done one day after another, but reality isn't always what one hopes for (especially since we're not a corporation who can fire Philip or anything). Partly it's Philip prioritizing other things over game development, perhaps he doesn't need the money enough or what do I know. Perhaps we should try and be more strict about it, but on the other hand what would be the alternative? At least currently no one else with anywhere near the same knowledge of the code has got the time to work on the game full time (regardless of how you define that), so if we'd "forbid" Philip then no full time work would be done at all for who knows how long time. Partly however it's also Philip finding that the latest part of his paid work, pathfinding, is taking more time to research, and think about, and plan, than he anticipated and he doesn't want to be paid for working full time when it's that kind of work which is hard to put a number of hours to.

It is good that you care though, and I hope seeing your comments will encourage Philip to prioritize working on the game. As I said though, Philip is only getting paid after work has been done, so it's not like he's gotten money for a full month already and just hasn't done all the work yet. If against all odds Philip will not be able to work all the days we have gotten donations for we will find someone else of the programmers who are able to do the same, so even though in the worst case it might take some time the money will go to developing the game and nothing else. With the caveat mentioned on the Pledgie page:

Quote

If we don’t achieve the amount we need for a full month, we’ll get as many full 8 hour days as possible from it.

If the donations go above the target, then we’ll use that excess to pay the developer for as many 8 hour work days as possible until funds run out.

Anything left over will be put aside to help with website, forum, and SVN server maintenance.

However, we should definitely update the Pledgie page to highlight the fact that the month of full time work means 20 days of eight hours of work each, and not necessarily a calendar month. We had originally hoped, and I'm sure Philip had as well, that it would more or less completely correspond to a calendar month which meant we didn't think it was necessary to mention. As things are we should definitely be more clear about it.

[Android_]

Quote

It would of course in many ways be great if the work would be done one day after another, but reality isn't always what one hopes for (especially since we're not a corporation who can fire Philip or anything). Partly it's Philip prioritizing other things over game development, perhaps he doesn't need the money enough or what do I know. Perhaps we should try and be more strict about it, but on the other hand what would be the alternative?

Please; don't go too harsh on him. I do not at all think this is a personal failure, and I am sure we all appreciate his work. Also I do think he could and should list his research activities as working hours and write reports about them.

Basically this seems to be a communication issue. WFG should have come to terms with what the work would be going to entail; whether it would be a calender month or 30 working days etc. beforehand. And then the Pledgies should have been perfectly clear about that. They have been formulated so that it is clear you were aiming for a calender month.

I think there is not much you can do about it now (all you could possibly do is hiring another programmer who will work full-time, but that doesn't make too much sense either). However, this should definitely be avoided in the future.

[Android_]

Well, as much as I appreciate Philip's work, people will ask themselves why they should donate if their money doesn't make a difference.