Paid Development: September 2013 Activity Status

[feneur]

It would definitely make it easier to do range checks between formations. However, once a formation is in range, we will still need to target individual soldiers which is again one of the slow cases. I wonder how Total War handles this problem?

We only need to target individual soldiers if we want to allow individual soldiers to be hit individually as part of the simulation. We could also treat units in formations differently, and e.g. distribute health loss, XP gain etc over the entire formation. To allow for some strategy it would probably be more relevant to divide them into say four areas (left/right flanks, and front and back), but four is still a lot less than 40 =) Individual arrows should probably still be shown as hitting individual units, but I believe they're already separate from the simulation (at least in some ways), so that shouldn't be too much of an issue.

And while I don't know about Total War I definitely think they only use formations for everything, the individual units are just graphical representations of them as far as I've understood things.

[Ykkrosh]

Perhaps we could use regular grid subdivision and implement SAP in every subdivision grid? That would eliminate a lot of X-axis alignments for sure.

I'd suggest giving up on SAP, because it seems like a completely unhelpful algorithm for this problem . There may be some things it's good at, but it sounds like this isn't one of them, and trying to twist it to work non-terribly is unlikely to result in something that actually works well.

The current implementation in 0AD SVN would place entity B into both grid tile 1 and grid tile 2. This means we have to sort the results and call std::unique to remove duplicate entities.

CCmpRangeManager deals with points rather than bounding boxes, so it only has to put entities into a single cell (except for the rare cases where an entity is precisely on the edge between cells, which we could avoid by being more careful about the edge conditions). We have to sort the results so that we can do std::set_difference to see which entities have entered/left the range (there's no way to avoid putting an O(n log n) operation somewhere, when we're doing set comparison), and once we've sorted them it doesn't cost much to do a std::unique.

(CCmpObstructionManager does deal with bounding boxes, but that's all tied in with the pathfinder design and needs to be changed anyway.)

I just had a look at the parallel for patch. Don't you think that is a quite painful way of doing multithreading in games? First, I'd assume it would be easier to use some existing implementation with threadpools etc., like even OpenMP. Secondly, I'd think the easiest (and most common afaik) way of doing it is completely putting one component in a seperate thread, like the AI. That way you don't need to make sure that every called method is threadsafe etc., which will be horrible to maintain over time, at least in my experience.

Agreed (I said similar things on IRC yesterday) . Moving self-contained latency-tolerant things like the AI and pathfinder into separate threads should give much greater benefit, with much less pain than will come from uncontrolled access to the entire simulation state from multiple threads.

1 thread: 24ms/turn

On Combat Demo Huge? That's a fairly unrealistic extreme case, and if we were running at full speed then 24ms/turn would still only be about 10% of total CPU time. I had assumed it was worse than that...

[FeXoR]

We only need to target individual soldiers if we want to allow individual soldiers to be hit individually as part of the simulation. We could also treat units in formations differently, and e.g. distribute health loss, XP gain etc over the entire formation. To allow for some strategy it would probably be more relevant to divide them into say four areas (left/right flanks, and front and back), but four is still a lot less than 40 =) Individual arrows should probably still be shown as hitting individual units, but I believe they're already separate from the simulation (at least in some ways), so that shouldn't be too much of an issue.

And while I don't know about Total War I definitely think they only use formations for everything, the individual units are just graphical representations of them as far as I've understood things.

PLZ don't treat formations as units! That will throw away one of the most basic aspect of RTS games and will extremely favor formations (especially those with many units in it) over single units (because focused fire would be impossible against formations).

That would mean a formation with 2 units is about 1/3rd stronger than a the same troops not in a formation.

(Calculation: Assuming a unit dies after 4 attacks. Formation attacks the first non-formation unit. It will die after 2 attacks. by then at least 1 of the attack against the formation would likely hit each unit in the formation (if the target is chosen randomly) so both are still alive (since 4-1 attack at most hit one of them) so in the 3rd attack the formation still has 2 attacks while the single units in total (well, OK in this case only one is left) has only one left).

This effect gets stronger for more units in the formation (because the damage (even if the target is randomly chosen) can be distributed amongst more units).

Additionally (if we are serious with the max. range of the units) big formations would have to run into each other if the formation width is larger than the units ranges (which is quite likely) to guaranty (not possible at all for big formations) the (randomly chosen) unit of the opposing formation is in range.

So at least something will happen breaking unit behaviour/game rules (like max. range) even further.

I strongly opposing this idea from a gameplay and logic point of view!

Edited September 26, 2013 by FeXoR

[scroogie]

Entities are 2D bounding boxes (since they can be buildings, units, flora, fauna...).

CCmpRangeManager deals with points rather than bounding boxes, so it only has to put entities into a single cell (except for the rare cases where an entity is precisely on the edge between cells, which we could avoid by being more careful about the edge conditions).

So I'm a bit confused now. I guess entities have an extent, but the RangeManager ignores it (which is what I meant to ask)? Does the range vary very much or is it quite uniform?

The PFor implementation isn't entirely horrible - though it has quite a few concurrency issues. We don't use OpenMP because we already implement pthreads and there is literally no useful cross-platform library with a PFor. The patch already implements thread pools if you didn't notice, so I wouldn't worry about the implementation efficiency.

Ah, yes, I didn't see the static initialization. I'm still not sure its nicer than using OpenMP, though. The latter would also allow tasks (if 3.0 would be an option), which might even be better suited sometimes. But anyhow, I would still tend to the component-wise solution.

If we push the code into a worker thread - something that works in background to the whole engine, we will definitely reduce the time taken, even on single core CPU's. However, we have to account for situations where calculating ranges takes more than 1 turn and how that will affect the simulation state. We will probably have to wait out the results from previous turn regardless. All in all, it might be worth the shot and it would have less concurrency issues than PFor.

Yes. Regarding the issue of waiting for the results, its virtually a decision between blocking the whole game to wait for a result or live with an old result for some time? Also, you gain some time in a way, which is currently unused because of the sequential processing. If we take the AI again as an example, it could already crunch away while the engine is busy with other stuff. Its in no way trivial, but I guess maintaining a bunch of parallel sections isn't trivial in the long run either?

Anyway, I digress. I hope you don't mind if "externals" chime in, its an interesting topic.

[Mythos_Ruler]

PLZ don't treat formations as units! That will throw away one of the most basic aspect of RTS games and will extremely favor formations (especially those with many units in it) over single units (because focused fire would be impossible against formations).

That would mean a formation with 2 units is about 1/3rd stronger than a the same troops not in a formation.

(Calculation: Assuming a unit dies after 4 attacks. Formation attacks the first non-formation unit. It will die after 2 attacks. by then at least 1 of the attack against the formation would likely hit each unit in the formation (if the target is chosen randomly) so both are still alive (since 4-1 attack at most hit one of them) so in the 3rd attack the formation still has 2 attacks while the single units in total (well, OK in this case only one is left) has only one left).

This effect gets stronger for more units in the formation (because the damage (even if the target is randomly chosen) can be distributed amongst more units).

Additionally (if we are serious with the max. range of the units) big formations would have to run into each other if the formation width is larger than the units ranges (which is quite likely) to guaranty (not possible at all for big formations) the (randomly chosen) unit of the opposing formation is in range.

So at least something will happen breaking unit behaviour/game rules (like max. range) even further.

I strongly opposing this idea from a gameplay and logic point of view!

We would never distribute damage across the entire formation. Even in Total War games each soldier is its own entity of sorts and takes and gives his own damage. We'd likely do formations like in Battle for Middle Earth 2, where they act mostly as a way of controlling large amounts of soldiers and keeping them look nice and neat and not so messy. I posit that the "mosh pit" approach to combat is a dead concept and no new RTS game should adopt it.

[Ykkrosh]

So I'm a bit confused now. I guess entities have an extent, but the RangeManager ignores it (which is what I meant to ask)? Does the range vary very much or is it quite uniform?

Entities have positions, and they have obstruction shapes (units are small axis-aligned squares, buildings are typically large non-aligned rectangles; I think a few buildings are multiple rectangles) centered on those positions. Obstruction shapes should (usually) never overlap other obstruction shapes, and should never overlap an impassable terrain tile.

RangeManager only cares about the distance between entity positions - it ignores obstruction shapes entirely. (That is arguably a bug, since it means units behave badly around very large buildings (e.g. pyramids), but I think it's an acceptable simplification in most situations and there are probably ways to minimise the problems with very large buildings (like splitting them into multiple smaller obstructions).)

Only the pathfinders and ObstructionManager care about obstruction shapes.

(Then units also have footprint shapes (rectangles or circles, used for rendering the selection outlines), and 3D graphical bounding boxes, and 3D selection boxes. And the new WIP pathfinder gives them clearance values too, which determine how close they can get to impassable terrain or to buildings, instead of using the obstruction shape for that. But that's all irrelevant for RangeManager.)

Ah, yes, I didn't see the static initialization.

(Which is not threadsafe, by the way )

If we take the AI again as an example, it could already crunch away while the engine is busy with other stuff.

That's how CCmpAIManager is designed already - StartComputation() is called at the end of one turn, and takes a snapshot of the current simulation state, then PushCommands() is called at the start of the next turn to push the AI's commands onto the command queue. The implementation doesn't actually use threads yet, so it does all the computation synchronously in the PushCommands call, but that's just a matter of writing code.

[FeXoR]

I copied the oft topic parts to:

http://www.wildfireg...41

Edited September 26, 2013 by FeXoR

[Norvegia]

Where is the october update thread? Where is redfox?

Edited October 17, 2013 by Norvegia

[Lion.Kanzen]

Good question, see not movement since a weeks.

[Gallaecio]

He shows up in IRC now and then, however last time I heard he was sick.

[Lion.Kanzen]

Thank you i hope he can recovery from that.

[RedFox]

There is no October update thread. The last work I did was the first week of October where I fixed memory leaks in the new lobby, added VS2012 support for premake4 and some bug-fixes on megapatch (no new features). And the end of September I fell quite ill and was out of action for 2 weeks; actually I've yet to fully recover - I should probably give myself more rest.

Since there has yet to be any discussion on resuming paid development, I'm remaining in stand-by.

[Jeru]

When the fundraiser is over and we verify that we have received all the funds, we will hopefully sign a new contract with Jorma and paid work will resume, including posting updates.

(Jorma, get well soon!)

[Yves]

Yes hopefully that can be sorted out quickly and the development can continue.

I'm looking forward to your work and I also hope you get well soon!

[Ykkrosh]

Given that the megapatch is currently almost entirely unusable (I started trying to split it up here, but nearly every change it makes is adding bugs and replacing working code with more flawed designs - there are some real improvements in there (our existing code is certainly flawed too) but those improvements all still need a lot of fixing and are mixed up with all the other changes, so it generally takes more effort to extract and fix them than to just rewrite them from scratch), hopefully there's also a plan to make sure any future work is focused in a more productive direction?

[RedFox]

I agree Ykkrosh, it's tough working on large scale changes on such a large project - it often looks like operating cancer, really. I'd say my focus would be on reviewing and bugfixing megapatch so that all the problems get fixed. And in the future, we should definitely avoid megapatch situations, since they become increasingly difficult to maintain the longer they remain off the main svn trunk.

[Norvegia]

Whats happening with the paid development? I really miss these weekly updates.