Progress reports on funded work

[hhyloc]

Any progress lately ? ( I don't want to be rude, just informing)

Yes, please give a progress report! (Not that we don't believe your doing work since we know your working hard, just want to see the magic your doin' ).

Chill out guys, maybe he has been too busy lately to post a progress report here, I'm sure he is too eager to show his works to us .

[Mythos_Ruler]

Chill out guys, maybe he has been too busy lately to post a progress report here, I'm sure he is too eager to show his works to us .

He is also very very active on IRC Channel. You can interact with him every day there if you wish. I know for a fact a very awesome gameplay patch is coming down the pipeline. Something big the game's been missing.

[JuliusColtranePille]

He is also very very active on IRC Channel. You can interact with him every day there if you wish. I know for a fact a very awesome gameplay patch is coming down the pipeline. Something big the game's been missing.

goose bumps

[gudo]

Is it barter? (changeset 10588) Or something even more awesomerer?

[feneur]

Is it barter? (changeset 10588) Or something even more awesomerer?

That's one thing There are a few more things which might make it as well

[Ykkrosh]

Day 7 (the remaining half) and 8

Spent the time reviewing patches (pathfinder optimisation, rally point lines, object selection, bartering, and probably a few other things). (I've been pretty slow since I find it hard to concentrate on reviewing for long, and also I've been clearing out my backlog of tickets and SVN updates etc to read and respond to, and other distractions.)

I don't like reviewing patches, but I don't like not reviewing patches . But I do like that people write patches, since it's valuable to grow the game's developer community. So I get quite conflicted... Maybe it'll help if I try explaining how I see things.

Firstly, I think code quality is important to maintain. There are lots of different ways of measuring the value of code: features, bugs, performance, number of lines, readability, maintainability, cleverness, etc. The most critical measure is features - we want to write an RTS game, and if we haven't implemented the features necessary for an RTS game then we've failed. Patches that add or improve features are therefore good. The other external measures that are visible to players are bugs and performance - if either is particularly bad, then people won't have fun playing the game. The remaining measures are internal to the code and totally irrelevant to players.

But all of these measures are interlinked. More features means more code, and more bugs and worse performance. Performance optimisations hurt readability and maintainability. Clever code might implement the feature with less code but be harder to read and maintain (you have to understand the cleverness before fixing bugs in it); non-clever code might be very verbose which makes it hard to read (it's easy to get lost somewhere in the middle). When code is unmaintainable, its bugs and performance problems will take a lot of effort to fix. And most features have to interact with each other, so if one feature's code is buggy or unreadable then it becomes much harder to add new features that have to interact with it.

That means that when a patch adds useful features, I think we shouldn't automatically accept it, even though it'll make the game better in the short term - we need to balance that with all the other quality measures else it will cause difficulties in the longer term. In the worst case, problems in the code can seem too hard to fix and cause progress to grind to a halt. (I believe that's what happened with our pre-2009 gameplay code; the only way to make major progress was to throw it all out and start again, which was very painful.)

So that's why I think it's important to spend effort on carefully reviewing patches, even if they're clearly solving a valid problem, to provide a second opinion on whether they're solving the problem in a sufficiently good-quality way and identify changes that would improve the solution. That applies especially to new contributors, who are less familiar with the existing code and conventions and typically need to rely more on the second opinion of a more experienced developer, but I think it's also worth having people read and comment on changes implemented by everyone else (possibly after they're committed to SVN) so nobody can get away with doing anything too crazy.

The difficulty is that reviewing can take a lot of effort, since you've got to understand the problem, and the patch's solution, and potential alternative solutions, and explain it all clearly to the original author so they can fix it. Often that takes more effort than just solving the problem yourself, and personally I find it pretty tedious and unenjoyable, but the hope is that the review comments will be something the original author can learn from and apply to any subsequent work they do. (And hopefully the comments will really be about improving code quality, not just about applying the reviewer's insignificant personal style preferences - I think I fall into that trap too much ).

(The other trap is to focus too much on the internal quality measures as a goal in themselves, when they're not what really matters. The code only needs to be maintainable enough that we can finish the game with it, and maybe do some mods or a sequel etc - any extra effort put into quality will just be wasted. I think I fall into that trap too.)

Anyway, that's just my opinion

[Android_]

Cheers Philip. I am not a programmer but I think I do see the point of your critique.

I know for a fact a very awesome gameplay patch is coming down the pipeline. Something big the game's been missing.

Hmmm.... now what could that be?

[WhiteTreePaladin]

Hmm, even I'm not sure.

[Mythos_Ruler]

Hmm, even I'm not sure.

Well, I guess it depends one what you interpret "big" to mean.

I think Bartering (which hadn't been implemented yet when I posted the original comment) and Trading (which could be implemented by Alpha 8 or soon thereafter) are decently "big" gameplay features the game's economy have been lacking. But that's just me.

[WhiteTreePaladin]

Well, Erik said this earlier:

Is it barter? (changeset 10588) Or something even more awesomerer?

That's one thing There are a few more things which might make it as well

So not really sure myself.

[Android_]

haha confusion all around

[WhiteTreePaladin]

Well, there are some other really nice things coming that are pretty big, but they're not new "features."

[ribez]

Day 7 (the remaining half) and 8

Spent the time reviewing patches (pathfinder optimisation, rally point lines, object selection, bartering, and probably a few other things). (I've been pretty slow since I find it hard to concentrate on reviewing for long, and also I've been clearing out my backlog of tickets and SVN updates etc to read and respond to, and other distractions.)

I don't like reviewing patches, but I don't like not reviewing patches . But I do like that people write patches, since it's valuable to grow the game's developer community. So I get quite conflicted... Maybe it'll help if I try explaining how I see things.

Firstly, I think code quality is important to maintain. There are lots of different ways of measuring the value of code: features, bugs, performance, number of lines, readability, maintainability, cleverness, etc. The most critical measure is features - we want to write an RTS game, and if we haven't implemented the features necessary for an RTS game then we've failed. Patches that add or improve features are therefore good. The other external measures that are visible to players are bugs and performance - if either is particularly bad, then people won't have fun playing the game. The remaining measures are internal to the code and totally irrelevant to players.

But all of these measures are interlinked. More features means more code, and more bugs and worse performance. Performance optimisations hurt readability and maintainability. Clever code might implement the feature with less code but be harder to read and maintain (you have to understand the cleverness before fixing bugs in it); non-clever code might be very verbose which makes it hard to read (it's easy to get lost somewhere in the middle). When code is unmaintainable, its bugs and performance problems will take a lot of effort to fix. And most features have to interact with each other, so if one feature's code is buggy or unreadable then it becomes much harder to add new features that have to interact with it.

CUT

i like how you write about programming: it sounds very epic, a struggle between various aspects

[liamdawe]

Thanks for the update, keep going it's really good to see the game being pushed

[Mythos_Ruler]

i like how you write about programming: it sounds very epic, a struggle between various aspects

Philip really missed his calling as a writer. This I truly believe. Though, he's no slouch as a programmer, either.

[feneur]

Well, Erik said this earlier:

I think I meant possibly trade, and the bounding box patch wasn't in then I believe, and perhaps the rally point marker line patch was on my mind as well So something like that.

Great to see that update Philip, and a great write-up of the issues involved in reviewing patches. Perhaps something like that would be good to have written on the committing patches page in Trac? (After the process related stuff of course so people can find the most urgent things without having to read through a lot of text, but it would be nice to have something like this available there so people committing patches get a greater understanding of what's going on with their patches. And why it might take a while.)

[Android_]

Philip while I do understand the trade-off you described between features, bugs, performance, number of lines, readability, maintainability, cleverness, etc. that a programmer has to face, and the importance of reviewing patches (there's already a number of awesome changes coming up in the new alpha because of that!), I think for the purpose of fundraising it could be a good idea to pull out a new feature in the remaining days that you have. New features, as you said, are the most visible improvements to players (/donors) and could therefore make the biggest impact on the effectiveness of future pledgies I figure. So if possible something along the lines of wall placement, viable ship pathfinding, healers, or any other direly needed feature could prove to be some good piece of advertisement?

In the end, after this month, you could make an impressive list that way:

'Implementations that are directly perceivable by the player:

- New feature X

- Saved games

- Reviews of patches allowing for trade, barter, rally point marker lines, etc.'

[UV_Completion]

He has quite some days left so no need to hurry.

Also, I strongly disagree. The best reason for me to donate would be to know that this would get some "unfancy" but important work done, first of all optimizations (and stabilization, but the game seems pretty stable to me already). I also think that Philip is right to spend quite some time on reviewing patches. If 0AD gains only a single regularly contributing person by this, it already was totally worth it (and even if not, you have at least some nice improvements made, even if they come with a more-than-necessary amount of work.)

To make it clear, I actually think that Philip's work is in fact quite fancy, especially the new profiler and the network stabilization work.

Philip while I do understand the trade-off you described between features, bugs, performance, number of lines, readability, maintainability, cleverness, etc. that a programmer has to face, and the importance of reviewing patches (there's already a number of awesome changes coming up in the new alpha because of that!), I think for the purpose of fundraising it could be a good idea to pull out a new feature in the remaining days that you have. New features, as you said, are the most visible improvements to players (/donors) and could therefore make the biggest impact on the effectiveness of future pledgies I figure. So if possible something along the lines of wall placement, viable ship pathfinding, healers, or any other direly needed feature could prove to be some good piece of advertisement?

In the end, after this month, you could make an impressive list that way:

'Implementations that are directly perceivable by the player:

- New feature X

- Saved games

- Reviews of patches allowing for trade, barter, rally point marker lines, etc.'

[Android_]

You're probably right... he will know best what to do. It's just my impatience guys

[Ykkrosh]

(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.

[ac892006]

(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.

I don't think you should change it from non uniform cost to uniform cost . The change will decrease time complexity but the path generated will be of poor quality . Instead of changing the algorithm why not just change the heuristic function . A* efficiency depends on the heuristic function . Optimize it and automatically efficiency will improve . Any change from non uniform cost to uniform cost would be a move backwards not forwards . 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 .

Edited December 8, 2011 by ac892006

[ribez]

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.

swamp, desert, and grassland will cost the same? no, please

it cut away much of the fun of strategic choices

[iap]

I've read in other RTS forum about how they optimized the pathfinding, I'll try to describe it as I remember.

The idea was to make a low resolution tiles of the map for pathfinjding. I mean, to take groups of 4X4 tiles and count them as one tile, and their traveling costs calculate as the average of all. The algorithm then will calculate a combined path, using normal size tiles for near distance, and grouped size tiles for not so near. The distant calculated path will be coarse, but it will constantly update. Maybe making it "recursive" can increase performance even more, for example, near tiles circle will be calculated as single tiles, not so near will be calculated as groups of 4X4 tiles, and far will be calculated as groups of 4X4 groups of 4X4.

Is this a relevant solution?

[errt]

I don't think you should drop non-uniform cost as this is really making a difference the players will notice. 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. In fact, non-perfect paths even might ADD to the experience as they might feel more natural: Humans will almost never use the perfect path. So I suggest on priorizing for a high performance non-uniform cost algorithm without guarantee for perfect paths over a lower performance algorithm with perfect outcome or uniform cost algorithms. But that's just my two cents.

@iap: afaik that's almost what 0ad is already doing: A long range path finder that's discussed here for the long distances and a short range pathfinder for the details. Just that 0ad currently doesn't update the long path while moving along it (at least that's what I think it does and what I think you suggested).

[Sylvain Gadrat]

Instead of changing the algorithm why not just change the heuristic function . A* efficiency depends on the heuristic function . Optimize it and automatically efficiency will improve.

The current heuristic function already do a pretty descent job by avoiding square root. Optimizing only the heuristic function have it's limits. While it may be possible to improve it a little, dividing by 16 the time consumed by the current pathfinder, and being able to change current tiles to 4x4 little ones, seems unrealistic if we want to only change this function. And beware, sacrifying the heuristic quality for speed can leed to far worst pathes than ignoring terrain cost.

swamp, desert, and grassland will cost the same? no, please

it cut away much of the fun of strategic choices

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. Since maps are often made of large fields of grass/sand/water/... and, for long travels, we usually group different units in formation, I think such a change will go unnoticed.

The idea was to make a low resolution tiles of the map for pathfinjding. I mean, to take groups of 4X4 tiles and count them as one tile, and their traveling costs calculate as the average of all. The algorithm then will calculate a combined path, using normal size tiles for near distance, and grouped size tiles for not so near.

Seems really imprecise, specially dealing with not passable tiles. If there is a small gate in a wall, the big tile may be tagged as impassable. So the coarse path will go round the entire wall, then refinments will caclulate a more accurate path around the wall.

To avoid it, it force the alogrithm to check from which entrance of the big tile we could go to which exit... It sounds a lot like HPA* presented by Phillip

Stop quoting, here's my own thoughs :

Having different terrain type and associated costs seems not a big deal while implementing HPA* (I don't have the time to explore HPA*, so I didn't even tried to implement anything else after areas). 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. Making it hard to precompute sub-pathes and having to do advanced things for the first shot implementation.

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.