Planetary Annihilation "spiritual successor to T.A"

[uberge3k]

no adjacent areas are processed in parallel. you divide the map into horizontal zones and in the first pass you simulate
all even zones, in the second pass you simulate all odd zones.
processing order is strict within a zone (as a precondition), interaction between units of adjacent zones is in sequence, because adjacent zones are not simulated in parallel.

The concept of adjacency is why this is far more complex than it first appears. You must use both axis when separating the nodes, or else there *will* be edge race conditions at the extreme edges. That means that there are 8 nodes adjacent to every other node:

000
010
000

So, assuming a 10x10 grid for simplicity, the first pass would look like:

0000000000
0101010101
0000000000
0101010101
0000000000
0101010101
0000000000
0101010101
0000000000
0101010101

And the second pass:

0101010101
0000000000
0101010101
0000000000
0101010101
0000000000
0101010101
0000000000
0101010101
0000000000

...And then the 3rd pass:

1010101010
0000000000
1010101010
0000000000
1010101010
0000000000
1010101010
0000000000
1010101010
0000000000

And so on until every node is updated. Assuming that you aren't doing this all in one tick, that is a *lot* of added latency in an engine where latency is already an issue. Furthermore, there would be an obvious "stepping" with units in one zone being updated sooner than those in the adjacent zone. This could of course be covered up by interpolating between a set of timestamped prior states in each unit in order to maintain visual temporal coherency for the player, but the displayed state would necessarily dramatically differ from the internal positions of the units as it is no longer one tick behind, but 1-N ticks behind where N is the number of passes needed to process all nodes without adjacency.

Also note that you still have to account for literal corner cases. Remember that planets are spherical. Assuming that they are generated by taking the 6 faces of a cube and projecting them to a sphere, each node field will have four adjacent node fields which will then need to communicate with each other.

you can enforce access rules (like for example a tank in an even zone can only query the position of a tank in an odd zone or its own zone etc.) in the lua interpreter, or whatever your scripting language would be. you need this only in a debug build. this kind of unallowed access is trivial to detect, since each entity is associated with a zone.
that comes in addition to the fact that the target selection function for a tank will ignore targets that are out of range naturally.

So now there are limitations on what you can only query based on an arbitrary spatial location? As a rule of thumb, if a feature only works some of the time, it may as well not be there. Therefore, this would break a *lot* of functionality, or worse, it would only function inconsistently and for reasons that are clear only to the developer of the spatial division system.

and correctness is a priori easier to ensure than for the precondition: that is making a single thread deterministic.
that is because the spatial independence is not a thing that you have to impose on the code, its a natural property of an RTS.

It's only easier if you are willing to accept the staggering limitations that this method imposes on inter-unit communication, as well as the fact that it will be extremely unoptimized in the very cases that *need* optimization, which is during large scale unit engagements that will tend to occur near the same place. As well as the myriad of subtle edge cases that would need to be handled in order for it to function deterministically.

I do not see any advantages whatsoever over a simple tasklet wrapper utilizing the update-cache-finalize pattern.

[rootbeer23]

The concept of adjacency is why this is far more complex than it first appears. You must use both axis when separating the nodes, or else there *will* be edge race conditions at the extreme edges. That means that there are 8 nodes adjacent to every other node:

000
010
000

So, assuming a 10x10 grid for simplicity, the first pass would look like:

0000000000
0101010101
0000000000
0101010101
0000000000
0101010101
0000000000
0101010101
0000000000
0101010101

it looks like this (first half of 1 simtick):

0000000000
1111111111
0000000000
1111111111
0000000000
....

second half:

1111111111
0000000000
1111111111
0000000000
1111111111
....

And so on until every node is updated. Assuming that you aren't doing this all in one tick, that is a *lot* of added latency in an engine where latency is already an issue. Furthermore, there would be an obvious "stepping" with units in one zone being updated sooner than those in the adjacent zone. This could of course be covered up by interpolating between a set of timestamped prior states in each unit in order to maintain visual temporal coherency for the player, but the displayed state would necessarily dramatically differ from the internal positions of the units as it is no longer one tick behind, but 1-N ticks behind where N is the number of passes needed to process all nodes without adjacency.

you can process every unit in one tick. for the example above you need not simulate 100km^2 sequentially, but only
2*10km^2 sequentially (first you simulate 5*10km^2 on 5 cores, then you simulate the other 5*10km^2 on the same 5 cores), so you only need 2/5th the time given optimal unit distribution. all in one tick, and indistinguishable from pure sequential calculation. (because there has to be a processing order in any case, so it may as well be defined by association with a zone).

Also note that you still have to account for literal corner cases. Remember that planets are spherical. Assuming that they are generated by taking the 6 faces of a cube and projecting them to a sphere, each node field will have four adjacent node fields which will then need to communicate with each other.

like the above example, make zones along the lines of latitude

So now there are limitations on what you can only query based on an arbitrary spatial location? As a rule of thumb, if a feature only works some of the time, it may as well not be there. Therefore, this would break a *lot* of functionality, or worse, it would only function inconsistently and for reasons that are clear only to the developer of the spatial division system.

why would a tank need information about a tank on the other end of the map? the available information is not arbitrary, but is that information which is in the zone of influence of a unit. in principle akin to the speed of light limit in the physical world. same goes for artillery projectiles that travel the whole map and get handed from zone to zone.
only the aiming of the artillery must be a sequential operation to it does aim either at the new or the old position consistently.

It's only easier if you are willing to accept the staggering limitations that this method imposes on inter-unit communication, as well as the fact that it will be extremely unoptimized in the very cases that *need* optimization, which is during large scale unit engagements that will tend to occur near the same place. As well as the myriad of subtle edge cases that would need to be handled in order for it to function deterministically.

supcom simulates 8 player 10x10km games just fine on a single core. the grid can be quite large.

I do not see any advantages whatsoever over a simple tasklet wrapper utilizing the update-cache-finalize pattern.

dunno. i am ambiguous to what method to use. both seem viable.

[uberge3k]

The concept of adjacency is why this is far more complex than it first appears. You must use both axis when separating the nodes, or else there *will* be edge race conditions at the extreme edges. That means that there are 8 nodes adjacent to every other node:

000
010
000

So, assuming a 10x10 grid for simplicity, the first pass would look like:

0000000000
0101010101
0000000000
0101010101
0000000000
0101010101
0000000000
0101010101
0000000000
0101010101

it looks like this (first half of 1 simtick):

0000000000
1111111111
0000000000
1111111111
0000000000
....

second half:

1111111111
0000000000
1111111111
0000000000
1111111111
....

If they were on the same thread, the order wouldn't matter. If they were not, then the order definitely does matter and there will be race conditions. What if a node needs access to a node directly above or below it?

And so on until every node is updated. Assuming that you aren't doing this all in one tick, that is a *lot* of added latency in an engine where latency is already an issue. Furthermore, there would be an obvious "stepping" with units in one zone being updated sooner than those in the adjacent zone. This could of course be covered up by interpolating between a set of timestamped prior states in each unit in order to maintain visual temporal coherency for the player, but the displayed state would necessarily dramatically differ from the internal positions of the units as it is no longer one tick behind, but 1-N ticks behind where N is the number of passes needed to process all nodes without adjacency.

you can process every unit in one tick. for the example above you need not simulate 100km^2 sequentially, but only
2*10km^2 sequentially (first you simulate 5*10km^2 on 5 cores, then you simulate the other 5*10km^2 on the same 5 cores), so you only need 2/5th the time given optimal unit distribution. all in one tick, and indistinguishable from pure sequential calculation. (because there has to be a processing order in any case, so it may as well be defined by association with a zone).

If you can process it sequentially, then you don't need multithreading. The entire point of threading is to improve performance.

The problem is that your method is entirely reliant on a uniform distribution of units among the nodes. This will rarely occur in a real scenario, and thus your algorithm will unfortunately be efficient mostly when performance isn't needed and inefficient when it is.

So now there are limitations on what you can only query based on an arbitrary spatial location? As a rule of thumb, if a feature only works some of the time, it may as well not be there. Therefore, this would break a *lot* of functionality, or worse, it would only function inconsistently and for reasons that are clear only to the developer of the spatial division system.

why would a tank need information about a tank on the other end of the map? the available information is not arbitrary, but is that information which is in the zone of influence of a unit. in principle akin to the speed of light limit in the physical world. same goes for artillery projectiles that travel the whole map and get handed from zone to zone.
only the aiming of the artillery must be a sequential operation to it does aim either at the new or the old position consistently.

As in my example, I'm not speaking of direct unit to unit calculations such as collision detection, but querying unit data from other units as is the case with things like drones. There is no way to implement your algorithm without severely crippling such communication.

It's only easier if you are willing to accept the staggering limitations that this method imposes on inter-unit communication, as well as the fact that it will be extremely unoptimized in the very cases that *need* optimization, which is during large scale unit engagements that will tend to occur near the same place. As well as the myriad of subtle edge cases that would need to be handled in order for it to function deterministically.

supcom simulates 8 player 10x10km games just fine on a single core. the grid can be quite large.

The sim drop you mentioned earlier during critical engagements is hardly "fine". My point is to use a simpler and more efficient algorithm to increase performance in a new engine, not merely match the lackadaisical performance from a much older engine using an inefficient and awkward algorithm.

I do not see any advantages whatsoever over a simple tasklet wrapper utilizing the update-cache-finalize pattern.

dunno. i am ambiguous to what method to use. both seem viable.

Performance optimization should always be done with the worst case scenario in mind.

Take the example of occlusion detection with terrain rendering algorithms. These algorithms fell out of favor for a simple, logical reason: they only work during non-worst case scenarios, where there is performance to spare, and during the worst case scenario of the largest possible section of terrain being in view, they actually add overhead and worsen the problem. [yes, certain games would indeed benefit from it more than other competing techniques, but I'm speaking of the more general cases where the camera is more or less free the majority of the time, as is the case in an RTS]

Performance optimization is all about removing or minimizing those spikes of low frame rates or slow processing, as that is what players notice. In other words, in the context of a game, the player won't care if it's running at 60 FPS or 5000FPS. He will care if it suddenly drops to 10 FPS.

In the context of FA, what is of most concern is the sim speed drops as rendering is independent from the simulation calculation. As in your example, the sim dropping to -5 during an ASF engagement. Your proposed algorithm would not help this scenario. A tasklet wrapper would.

Even if your algorithm was guaranteed to be more efficient during the remainder of the game, it would be irrelevant as the sim would not be running slow either way. But the fact remains that it cannot be more efficient than a tasklet wrapper, and is indeed far more likely to be *less* efficient not only a majority of the time, but assuredly during the performance critical scenarios where efficiency would be needed most.

Lastly, it has already been established that there are far more edge cases to handle than with a general tasklet solution. They are certainly surmountable, but the fact remains that they are there to begin with.

[rootbeer23]

If they were on the same thread, the order wouldn't matter. If they were not, then the order definitely does matter and there will be race conditions. What if a node needs access to a node directly above or below it?

the processing order of adjacent zones is guaranteed to be sequential.
first, all zones marked '0' are processed by N threads, then all threads synchronize, then all zones marked "1" are
processed by N threads. if a unit from zone "0" interacts with a unit in zone "1" then it is guaranteed that no thread
is processing a unit in zones marked "1", because threads processing zone "1" have to wait for threads processing zone "0" to finish. same goes for the inverse interaction.

If you can process it sequentially, then you don't need multithreading. The entire point of threading is to improve performance.

this kind of BS is what first made me hesitate to write anything at all at first.

The problem is that your method is entirely reliant on a uniform distribution of units among the nodes. This will rarely occur in a real scenario, and thus your algorithm will unfortunately be efficient mostly when performance isn't needed and inefficient when it is.

that depends on the size of the zones. if they are small enough, then a single thread can process them in time.
and i said it before, in supcom you can have 10x10 with 1000 units and it runs at +0.
then compare the range of tanks to a 10x10km map. you can easily subdivide it into multiple zones.

As in my example, I'm not speaking of direct unit to unit calculations such as collision detection, but querying unit data from other units as is the case with things like drones. There is no way to implement your algorithm without severely crippling such communication.

drones cannot assist anything beyond a very small radius, so i dont see how they are special.
except if the kennel gets destroyed and the drone has to self-destruct. that requires special handling.
you can easily send a signal from the kennel to the drone that is handed from zone to zone obeying order of execution.
kind of like a very fast (indeed maximum speed) invisible projectile, but way easier to implement.

The sim drop you mentioned earlier during critical engagements is hardly "fine". My point is to use a simpler and more efficient algorithm to increase performance in a new engine, not merely match the lackadaisical performance from a much older engine using an inefficient and awkward algorithm.

i dont agree. it just doesnt bother me if a game slows down for a short time.

In the context of FA, what is of most concern is the sim speed drops as rendering is independent from the simulation calculation. As in your example, the sim dropping to -5 during an ASF engagement. Your proposed algorithm would not help this scenario. A tasklet wrapper would.

you can simulate a lot on the map in parallel, even if none of the units close together could be.
what you can is close to the speed you would have with 500vs500 asf with no other units around.
certainly an improvement.

Even if your algorithm was guaranteed to be more efficient during the remainder of the game, it would be irrelevant as the sim would not be running slow either way. But the fact remains that it cannot be more efficient than a tasklet wrapper, and is indeed far more likely to be *less* efficient not only a majority of the time, but assuredly during the performance critical scenarios where efficiency would be needed most.

keeping a portion of the game state twice is not overhead?
you may be convinced that it performs better, but that is not obvious to me.

Lastly, it has already been established that there are far more edge cases to handle than with a general tasklet solution. They are certainly surmountable, but the fact remains that they are there to begin with.

i wasnt around when that was established.

i have a question of my own:

1) if you simulate a tank being hit by 2 projectiles at the same time and you cannot yet decide which projectile hits first until
after you commit the result of the simulation in sequence to all other results, do you generate 2 possible future states for that tank? then would you not need a mutex each time you modify a future states of a unit? even if its unlikely to be locked that still adds overhead.
2) each time there is a conflict - for example 2 tanks want to drive onto the same location - only one tanks can win.
in the single thread model, the loser tank examines the new situation and decides to move somewhere else.
what happens to the loser tank when his simulation result was aborted because of a conflicting commit by another tank?
does it do nothing at all then?
3) if a tank shoots a projectile but it is later decided that the projectile was generated after the tank was destroyed, you have a lot of cleaning up to do during the commit phase, which has to run in sequence.
4) given that you have less time for the commit phase which has to execute sequentially and only after the simulation phase, are you sure you can process each unit then, even if you do not have to do the actual simulation, which is a few floating point calculations, but does not involve deallocation of a destroyed units resources for example.

i am not argueing that it doesnt work, but i have my doubts.
and in the end, you need more resources and cpu time to achieve the same result, i dont have to keep state twice.

[Swkoll]

Point of interest, loads of people are giving PA a 0 on metacritic because they are upset about the pricing despite it being justified by the kickstarter and those players never playing it.

http://www.metacritic.com/game/pc/planetary-annihilation

[pip]

They made a huge PR mistake. I'm afraid this game's reputation is totally ruined for the non fan boys. I can't find them any excuse : considering the poor state of the Alpha, there was no need whatsoever to offer alpha access and get more players, they had plenty already. I can't help but think the main goal for granting alpha access for such a high price on Steam is the need for more funds.
They can justify it all they want with the kickstarter pledge level: selling an unfinished product outside the kickstarter environment for twice the price of the retail makes no sense except if they need money. It's a way to (not) say : "the kickstarter money we got is not enough to finish the product at the level we promised" and pretend to say : 'we love the community so we offer them to pay double price to have a chance to play our awesome alpha' (even though it's unplayable and buggy).
This is really a bad move, though they did achieve something epic : failure.

Now, if there are hiccups in the game development (delay, poor release with bugs, etc), players won't forgive them. They can't do any more mistep and have a huge pressure to deliver a top notch product, otherwise, nobody the image of the company itself will be irremediably marred.

[eXcalibur]

i agree with pip!

although, there is a legitimate way of explaining the high price of the alpha: the more expensive you make it, the more you get people, who really want to contribute to the development process. later on, the beta and release version become cheaper and therefore more accessible to a wider public.

i see for quite some time now, that they use every chance they can to raise more money (even in the end of the kickstarter they sold "metal planets" way overpriced), despite promising in the kickstarter that 900 k$ was enough to make the game...

every time they implicitly beg for more money, i feel they broke their last promise that they have enough money to make the best game in everyone's mind.

the problem is that the further they come in development, the more decisions they have to make how the game game is supposed to be and therefore, they disappoint a lot of people (e.g. me). this method (first promising everything, then disappointing most of the people) is PR suicide, because the game can never turn out to become as good as as initially promised. it is just impossible!

e.g. everybody, who loves the complexity and/or depth and/or many gameplay possibilities in supcom, just has to be disappointed/underwhelmed by PA.

the only chance i see it that UberEntertainment releases addons to the game (look at sins of a solar empire for comparison) and somebody writes a "complex mod" for this game (maybe it will not be possible to mod something into the game, which is not there from the beginning). but this needs at least a couple of years to become reality...

[Veta]

the backers requested both steam and for the price points to remain the same

i would've preferred early access at $40 though, even as a backer, because steam is generally more forgiving to unfinished games than high price points. it also didn't help that valve wouldn't let PA list its $40 preorder price point, apparently you cannot list preorders and early access on the same store page. a lot of people were confused and thought the game was retailing for this price.

moral of the story, KS backers may be investors but investors don't know marketing