Update on Progress

[Polestar]

Quick performance update. About 2.5 years into my latest test campaign. Five races in Sol and all five are active in Alpha Centauri as well. In VB6, this has such an impact on turn times that there is an option to turn off sensor checks in a system. The 1-day increments (which including 48 separate detection phases) are running in about 2.2 seconds.

Updates like this are great, and the gain versus VB Aurora is clearly huge. I'm almost ashamed to post anything but "good news!".

But I propose that 2.2 seconds per day is still significant. The story of a space empire in Aurora extends (or should extend) for decades, even centuries. If you were to play out this game for one century, with no more ships or missiles constructed, and no more systems discovered, you would be watching the busy icon for a bit over 22 hours. Almost a day and a night.

Now, I'm not going to ask for anything now, at this stage of C# development. Don't want to get lynched by fellow players. ;-/

However, I will say that the biggest reason I appreciate this update post is for the heads-up that my first game of C# Aurora needs to play out in a small universe, with one or two other colonizing non-player realms (NPRs), tops, and that I don't go crazy with colonizing or building.

[Ynglaur]

Are the sensor checks multi-threaded?  If so, maybe somebody could get Aurora running on spot instances of AWS or something just for processing.  :p

[Desdinova]

Another idea would be to pre calculate the next turn while the game is idle. That is, while the player is making decisions, designing ships, etc. The game is calculating the results of the next time advancement. This would not save time if time is advanced immediately back to back, but on turns you pause to do something it'd make time advancement seem instantaneous.

[Ayeshteni]

Another idea would be to pre calculate the next turn while the game is idle. That is, while the player is making decisions, designing ships, etc. The game is calculating the results of the next time advancement. This would not save time if time is advanced immediately back to back, but on turns you pause to do something it'd make time advancement seem instantaneous.

But how can it calculate the next turn advancement when the next turn could be 5 seconds or 30 days (or anything inbetween)?

Aye

[alex_brunius]

But how can it calculate the next turn advancement when the next turn could be 5 seconds or 30 days (or anything inbetween)?

A pre calculation could for example logically assume that the next time advancement will be of same length as the previous one.

[Execrated1]

I need this so bad. I like Stellaris, but it doesn't fill the emptiness in my soul that this game does.

[Tikigod]

Another idea would be to pre calculate the next turn while the game is idle. That is, while the player is making decisions, designing ships, etc. The game is calculating the results of the next time advancement. This would not save time if time is advanced immediately back to back, but on turns you pause to do something it'd make time advancement seem instantaneous.

But how can it calculate the next turn advancement when the next turn could be 5 seconds or 30 days (or anything inbetween)?

Aye

The next player initiated step doesn't really matter, the game still has a preset 'tick' duration for various activities as well as a preset number of pulse durations.

There isn't any real reason Steve couldn't have the game crunching away at certain things like construction/research activities, potential fleet locations and such in set tick steps before the player initiates any kind of time progression, other than the fact that the overall time reduction may very well be negligible at best.

I'd assume at least he's already doing performance shaving when handling things like sensors by introducing some measures like not calculating each individual ship sensor detection and just summarising it based on the first instance of a ship type per fleet in system.... if you have 15 ships of the same design in the same system, all with actives enabled, if the ships are only marginally spread out you could frankly just take the furthest distance between the ships, sanity check it's within a tolerance range and then just calculate the sensor interactions for the first instance of that design and forego calculating the rest of the same-design ships sensors.

Also doing things like not calculating additional sensor contacting of a target within a fleet if a ship in the fleet has already picked up the target and would only perform additional calculations for targets within the sensor radius yet not flagged as detected.


As given that active targeting is shared between similar deployed ships in a fleet, there is absolutely no reason to be having 25 ships all calculating active sensor detection of a target already known to have been detected. You only really need to calculate if the first ship that detected the target can still detect the target and then run checks for if each ship can detect anything known to be within sensor range but to have a low enough signature to have avoided detection yet.... and even with that you could pre-sample the sensors in play for signature detection strength and if Steve felt especially ballsy set up a series of generalised sub-detection groups on a fleet level where the game doesn't even bother to perform sensor checks for detecting anything below a certain signature threshold that's within that area as there really would be no point in checking.

[LoSboccacc]

Quick performance update. About 2.5 years into my latest test campaign. Five races in Sol and all five are active in Alpha Centauri as well. In VB6, this has such an impact on turn times that there is an option to turn off sensor checks in a system. The 1-day increments (which including 48 separate detection phases) are running in about 2.2 seconds.

Some questions: About how long would that increment take in VB6? How normal is that load? Is there a difference to performance when races operate in the same system or different systems?

No idea, because I haven't run this same game and situation in VB6. However, it would be considerably longer. In VB6 games with several races in Sol, I usually turn off sensor checks in busy systems unless there is conflict.

The performance is hit for multiple races is exponential because of the sensor checks. If you assume all races are the same size and have similar number of ships then two races just check each other (2 checks). Three races is 6 checks (each race checking two others). Five races is 20 checks, so my current campaign has ten times more sensor checks than a normal game.

are you running checks for every present ship or there's some kind of optimization there?

[Bughunter]

Should maybe move this discussion elsewhere, but one way to optimize could be saving calculation results from previous turns.

So every time a ship enters a system you calculate detection range both ways between it and every other ship in the system and save in memory for that system object. Per increment you only check against the precalculated ranges when a ship moves (and here you could maybe also group ships by detection range as suggested above). If anything else changes like thermal signature etc. you recalculate detection ranges for that ship as needed.

[db48x]

The performance is hit for multiple races is exponential because of the sensor checks. If you assume all races are the same size and have similar number of ships then two races just check each other (2 checks). Three races is 6 checks (each race checking two others). Five races is 20 checks, so my current campaign has ten times more sensor checks than a normal game.

Forgive me if this has come up before, but do you use quadtrees (or anything similar) to reduce the number of other ships that each ship must do a sensor check with?

Are the sensor checks multi-threaded?  If so, maybe somebody could get Aurora running on spot instances of AWS or something just for processing.  :p

That _has_ come up before

Adding multiple processing threads to a program is always easier said than done. You have to really think hard about how the order you check everything matters to the simulation. If the order matters in any way at all, then making it multi-threaded will break it, or just make the results random and unreproducible. I think one problem that has been brought up in the past is that sensor checks depend on when ships enter or leave a system, but ships entering and leaving the system also depends on sensor checks.

[vorpal+5]

How quadtrees would work? Genuinely curious, that's not a trap
Explain as if I'm not too good in maths also!

[Steve Walmsley (OP)]

Quick performance update. About 2.5 years into my latest test campaign. Five races in Sol and all five are active in Alpha Centauri as well. In VB6, this has such an impact on turn times that there is an option to turn off sensor checks in a system. The 1-day increments (which including 48 separate detection phases) are running in about 2.2 seconds.

Some questions: About how long would that increment take in VB6? How normal is that load? Is there a difference to performance when races operate in the same system or different systems?

No idea, because I haven't run this same game and situation in VB6. However, it would be considerably longer. In VB6 games with several races in Sol, I usually turn off sensor checks in busy systems unless there is conflict.

The performance is hit for multiple races is exponential because of the sensor checks. If you assume all races are the same size and have similar number of ships then two races just check each other (2 checks). Three races is 6 checks (each race checking two others). Five races is 20 checks, so my current campaign has ten times more sensor checks than a normal game.

are you running checks for every present ship or there's some kind of optimization there?

No, I am dumb and checking every sensor against every ship

Each location in which there are sensors uses the single best passive sensor of each type and the best active sensor for each unique resolution. When a ship is detected for a specific sensor type (active, thermal, EM, GPD, Transponder) by a specific race, it is ignored for further checks of the same type by the same race.

I have considered multi-threading, but as anyone who has used it in action will know, there are downsides to that. Firstly, each thread has a performance overhead, so unless you save enough time overall, multi-threading can actually be slower. Secondly, multi-threading adds considerable complexity, so even if I saved a few microseconds in performance I will lose out in additional, hard-to-find bugs.

Sensor check speed is not a concern for me. Even if one entire second of the turn is spent in detection for five races detecting each other, its ONE SECOND! Frankly, I am amazed how fast it is running. I am not going to rip apart the sensor code and add multi-threading in an effort to get that down to half a second, even if that were possible.

[sloanjh]

How quadtrees would work? Genuinely curious, that's not a trap
Explain as if I'm not too good in maths also!

Think about a fractal checkerboard:  take a single square, and subdivide into a 2x2 "quad" of sub-squares.  (For 3D, this is a cube divided into a 2x2x2 "oct" of sub-cubes hence "octree" for 3D.)  Take each of those sub-squares and subdivide them, so now you've got a 4x4 checkerboard divided up into 4 2x2 quadrants (the original level-1 sub-squares).  Rinse and repeat to get 8x8, 16x16 etc.

Let's say max sensor range is roughly 1/128 of the board size (the original square).  You can think of the region of the board that needs to be checked for a particular ship as a disk with diameter 1/64 (of the board size) - think of putting a penny down on the checkerboard.  So you only need to check enemy ships that lie within the disk.  If you think about cells (sub-sub-...squares) that are 1/32 the board size, then most (75%) of the time the disk is completely within the cell and you only need to check enemy ships that are in the same cell as you.  So if you pre-sort all enemy ships into bins corresponding to the cells, then 75% of the time you only need to check the enemy ships in the bin/cell you're in.  If the ships are uniformly distributed over the board, this will give you roughly a 1 million-fold speed up since there are 1/32*1/32 = 1/1K cells of that size on the board.

The algorithm is more subtle when the ship is near a cell boundary (the other 25%) - you have to identify and check all the neighboring cells that the disk overlaps -  but that's a rough flavor of how quadtrees (and octrees) work to speed up searches.  In 1D this is very closely related to the "divide and conquer" logarithmic search and sort algorithms, where you recursively take the region of interest, divide it in two, and ask if you're interested in the upper or lower half.

[EDIT] This is also intimately related to a really cool sorting algorithm for points in 2D, 3D etc space that is (logarithmically) good at keeping points that are close to each other in space close to each other in the sorted sequence: it's called Morton order (or Z-order): https://en.wikipedia.org/wiki/Z-order_curve  As I write this the Wikipedia page has a good picture of this fractal subdivision (unfortunately it doesn't have the cell boundary lines themselves), but since reality is malleable and retcon happens in Wikipedia land I can't guarantee it's still there   This is the technical way that you would use quadtree ideas to find nearest neighbors - a nifty property of Morton ordering is that if you look at the first an last points on an interval of the sorted set, then the smallest quadtree cell that contains both start and end guaranteed to contain all the points between in the sorted list, so those are the only points you need to check.  So if you think about your penny of the (hierarchically subdivided) checkerboard, then you just need to find the smallest cell that the disk lies completely in in order to find the points you need to check. [/EDIT]

John

[LordPC]

Was thinking the easiest way to parallelize depending on how exactly the code works might be to have one level of parallelization over systems and another over races.  But maybe the races act subsequently to each other so one might in fact depend on the result of the other not sure how that works in the games at a sufficiently short time interval.  (One reason the former might also make sense is because movement calculations for moving celestial bodies could also be parallelized on the system level with a potential secondary level for bodies orbiting another. ) The number of levels and type of parallelization that would be ideal may depend on the architecture one is hoping to utilize for the software.

While using some sort of tree algorithm based gird could be cool and might be part of an optimal in run time program for certain situations.

I was thinking that one way to optimize would be do see if ships with longer sensor ranges completely covered the sensor range of other ships with lessor sensor ranges.  But whether this would have significant impact might depend on one's play and ship design styles.

I realize there can be more important consideration like developer time.  At this point I will be glad for a faster functioning release even if it is not theoretically optimized (maybe especially so since at some point there would be diminishing return and time to release might approach infinity ).  But I do enjoy considering possibilities for parallelization and optimization.

[Jovus]

You don't need quadtrees for sensor checks, though. A binning algorithm would achieve O(n) time with significantly less complexity.