View Issue Details

Jump to NotesJump to History
IDProjectCategoryDate SubmittedLast Update
0025681AI War 2Gameplay IssueOct 25, 2021 1:58 amOct 27, 2021 4:29 am
Reportertom.prince Assigned Totom.prince  
Status resolvedResolutionfixed 
Product VersionBeta 3.712 Loading Hotfix 
Fixed in VersionBeta 3.740 Code Panopticon 
Summary0025681: Oddities in X map type generation code.
DescriptionWhile I was looking at issue 0025317, I noticed some surprising things in the code for the X map type.

- Even when asked for perfect symmetry, the number of spokes can be randomized. I've attached a patch that disables the randomization in that case. If some amount of variability is desired, I think it would be better to randomize at a given recursion depth (and use the same randomization for every branch at the depth).
- There is a logic error in counting the number of nodes in each subtree; at the root at first branch, there is an extra hop added between the centre and branches which wasn't being counted. There are a few pieces of code that are working around that error:
    - For symmetric maps, the undercounting of nodes led to there being 20 extra planets (4 at the root, 4x4 in each subtree). There was some code that adjusted the requested number of planets down to account for this.
    - For non-symmetric maps at small planet counts, the branches were unbalanced, as the first 3 branches would each have 5 extra planets, leaving the last branch fairly empty. To compensate for this, at the root, the number of planets in each tree was reduced by 3 to even out the branches.
   I've attached a patch that fixes the logic, and removes both of the above workarounds.
- For non-symmetric maps, if the number of planets don't divide evenly into subtrees, the extra planets are just not created. This leads to there being fewer planets than requested and (I think) actually make it slightly more symmetric than otherwise. I suspect this might have also been partly to compensate for the undercounting above, as under-populating the first subtrees would leave more for the final subtree. I've attached a patch that does distribute those extra planets. Since the non-symmetric version now always has the requested number of planets, I've also remove the option to add extra satellites, since it will now never add any planets.
- Symmetric maps also have the logic to distribute extra planets among branches. This leads to the various subtrees not being symmetrical. I've attached a patch that gives every subtree extra planets, if there are any extra planets to distribute, for the root of the tree. This leads to at least the 4 main branches being the same, even if the subtrees thereof aren't. This leads to there always being 4x+1 planets. I also experimented with doing this for the first level subtress, which would lead to there always being 16x+9 planets (e.g. 41, 57, 73, 89); but I though that having more control over the number of planets would be better.

One thing to note is that I don't play on the X map type, so while I think the above changes make the code behave more as intended, the combination of logic bug and workarounds may have lead to desirable end results (for example, the under-populating of non-symmetric maps and the addition of extra satellites would lead to some more variability of map layouts, which players might find desirable). I think, though, that if that is the case, it would be possible to implement changes that directly exhibit the desired outcome instead.
TagsNo tags attached.

Activities

tom.prince

Oct 25, 2021 1:58 am

developer  

x-map-symmetric-randomness.patch (1,524 bytes)    
# HG changeset patch
# User Tom Prince <[email protected]>
# Date 1635060090 21600
#      Sun Oct 24 01:21:30 2021 -0600
# Node ID 4bb46c2756b9ffdede49c8b5abf81c09c0652d3b
# Parent  5c4aa4deab6acb1c22ce1ad593716ab1f83cfb75
Don't randomize the number of spokes in a perfectly symmetric X map.

diff --git CodeExternal/AIWarExternalDeepProcessingCode/src/Mapgen/MapGeneration.cs CodeExternal/AIWarExternalDeepProcessingCode/src/Mapgen/MapGeneration.cs
--- CodeExternal/AIWarExternalDeepProcessingCode/src/Mapgen/MapGeneration.cs
+++ CodeExternal/AIWarExternalDeepProcessingCode/src/Mapgen/MapGeneration.cs
@@ -4965,11 +4965,13 @@ namespace Arcen.AIW2.External
             FInt distanceToChildrenForChildren = distanceToChildren / FInt.FromParts( 2, 150 );
 
             int defaultNumChildren = 4;
-            int rand = Context.RandomToUse.Next(0, 100);
-            if ( recursionDepth >= 2 && rand < 40 )
-            {
-                //sometimes only do 3 instead of 4 spokes. Just to add a bit of visual variety
-                defaultNumChildren--;
+            if ( !goForPerfectSymmetry ) {
+                int rand = Context.RandomToUse.Next(0, 100);
+                if ( recursionDepth >= 2 && rand < 40 )
+                {
+                    //sometimes only do 3 instead of 4 spokes. Just to add a bit of visual variety
+                    defaultNumChildren--;
+                }
             }
 
             int numberOfChildren = Math.Min( defaultNumChildren, planetsToPlace );
x-map-symmetric-randomness.patch (1,524 bytes)   
x-map-subtree-count.patch (4,875 bytes)    
# HG changeset patch
# User Tom Prince <[email protected]>
# Date 1635061750 21600
#      Sun Oct 24 01:49:10 2021 -0600
# Node ID bdddf63c3d3763346ce3b98e80dc40c00239ce9e
# Parent  4bb46c2756b9ffdede49c8b5abf81c09c0652d3b
Count the number of planets in X map subtrees correctly.

At recursion depth 0 and 1 in generating the X map, there is an additional node
added between the root, and the leaves, the number of nodes in each subtree
need to be adjusted to account for that.

This wasn't being done, and a couple of things were being done to compensate for it.
- For perfectly symmetric maps, there were an extra 20 planets being generated (4
  extra hops to the center, 4x4 extra hops to each branch's center). There was code
  to adjust the number of planets down to compensate.
- For the non-symmetric case, the number nodes in each subtree of the root was decreased
  by 3, to keep the branches balanced. (As each branch had 5 more planets than were being counted,
  one of the branches would be left empty at 40 planets).

This patch adjust the logic to take into account the extra hops and removes the
two workarounds described above.

diff --git CodeExternal/AIWarExternalDeepProcessingCode/src/Mapgen/MapGeneration.cs CodeExternal/AIWarExternalDeepProcessingCode/src/Mapgen/MapGeneration.cs
--- CodeExternal/AIWarExternalDeepProcessingCode/src/Mapgen/MapGeneration.cs
+++ CodeExternal/AIWarExternalDeepProcessingCode/src/Mapgen/MapGeneration.cs
@@ -4863,39 +4863,6 @@ namespace Arcen.AIW2.External
 
             FInt distanceToChildren;
             int numPlanets = mapConfig.GetClampedNumberOfPlanetsForMapType( mapType );
-            if ( goForPerfectSymmetry )
-            {
-                //160 = 180 for real
-                //150 = 170
-                if ( numPlanets >= 160 )
-                    numPlanets = 140; //will give 160 actual
-                else if ( numPlanets >= 150 )
-                    numPlanets = 130; //will give 150 actual
-                else if ( numPlanets >= 140 )
-                    numPlanets = 120; //will give 140 actual
-                else if ( numPlanets >= 130 )
-                    numPlanets = 110; //will give 130 actual
-                else if ( numPlanets >= 120 )
-                    numPlanets = 100; //will give 120 actual
-                else if ( numPlanets >= 110 )
-                    numPlanets = 90; //will give 110 actual
-                else if ( numPlanets >= 100 )
-                    numPlanets = 80; //will give 100 actual
-                else if ( numPlanets >= 90 )
-                    numPlanets = 70; //will give 90 actual
-                else if ( numPlanets >= 90 )
-                    numPlanets = 70; //will give 90 actual
-                else if ( numPlanets >= 80 )
-                    numPlanets = 60; //will give 80 actual
-                else if ( numPlanets >= 70 )
-                    numPlanets = 50; //will give 70 actual
-                else if ( numPlanets >= 60 )
-                    numPlanets = 40; //will give 60 actual
-                else if ( numPlanets >= 50 )
-                    numPlanets = 30; //will give 50 actual
-                else if ( numPlanets >= 40 )
-                    numPlanets = 20; //will give 40 actual
-            }
             numPlanetTotalToHave = numPlanets;
             if ( numPlanets < 80 )
                 distanceToChildren = FInt.FromParts( 400, 000 );
@@ -4983,6 +4950,7 @@ namespace Arcen.AIW2.External
                 angleToNextChild -= 25;
             for ( int i = 0; i < numberOfChildren; i++ )
             {
+                int nodesForThisSubTree = nodesPerChildTree;
                 Planet extra = null;
                 ArcenPoint childPoint;
                 //put a bit of visual wobble into the longer lines for aesthetics
@@ -5001,9 +4969,9 @@ namespace Arcen.AIW2.External
                     extra.AddLinkTo(center);
                     childPoint = CenterOfSubTree.GetPointAtAngleAndDistance( angleToNextChild, distanceToChildren.IntValue * 2 );
                     planetsToPlace--;
+                    nodesForThisSubTree--;
                 }
 
-                int nodesForThisSubTree = nodesPerChildTree;
                 if ( goForPerfectSymmetry )
                 {
                     if ( extraNodesForChildTrees > 0 )
@@ -5012,11 +4980,6 @@ namespace Arcen.AIW2.External
                         extraNodesForChildTrees--;
                     }
                 }
-                else
-                {
-                    if ( recursionDepth == 0 ) //make it more likely that all of the areas are even
-                        nodesForThisSubTree -= 3;
-                }
                 recursionDepth++;
                 Planet planetToPass = center;
                 if ( extra != null )
x-map-subtree-count.patch (4,875 bytes)   
x-map-nonsymmetric-exact.patch (5,937 bytes)    
# HG changeset patch
# User Tom Prince <[email protected]>
# Date 1635063485 21600
#      Sun Oct 24 02:18:05 2021 -0600
# Node ID aa54a9c5f1462f0a5b349cbc545b9548cf14c11e
# Parent  bdddf63c3d3763346ce3b98e80dc40c00239ce9e
Always divide extra planets among all children.

Along with the previous patch, this ensures there are always the requested
number of planets in the non-symmetric case (and there are always at least as
many in the symmetric case), so this also removes the option to have extra
satellites to hit target.

diff --git CodeExternal/AIWarExternalDeepProcessingCode/src/Mapgen/MapGeneration.cs CodeExternal/AIWarExternalDeepProcessingCode/src/Mapgen/MapGeneration.cs
--- CodeExternal/AIWarExternalDeepProcessingCode/src/Mapgen/MapGeneration.cs
+++ CodeExternal/AIWarExternalDeepProcessingCode/src/Mapgen/MapGeneration.cs
@@ -4877,30 +4877,6 @@ namespace Arcen.AIW2.External
             recursionDepth = 0;
             this.InnerGenerate( galaxy, Context, numPlanets, mapType, Engine_AIW2.Instance.GalaxyMapOnly_GalaxyCenter, (FInt)distanceToChildren, startingAngleOffset, null, goForPerfectSymmetry );
 
-            bool extraSatellitesToHitTarget = BadgerUtilityMethods.getSettingValueMapSettingOptionChoice_Expensive( mapConfig, mapType, "ExtraSatellitesToHitTarget" ).RelatedIntValue > 0;
-
-            if ( extraSatellitesToHitTarget )
-            {
-                List<Planet> planets = new List<Planet>( 500 );
-                galaxy.DoForPlanetsSingleThread( true, delegate ( Planet plan )
-                {
-                    planets.Add( plan );
-                    return DelReturn.Continue;
-                } );
-                int maxAttempts = 1000;
-                while ( galaxy.GetCountOfTotalPlanetsDestroyedAndOtherwise() < numPlanets && maxAttempts-- > 0 && planets.Count > 0 )
-                {
-                    Planet plan = planets[Context.RandomToUse.Next( 0, planets.Count )];
-                    ArcenPoint safePoint;
-                    if ( BadgerUtilityMethods.GetExtremelySafePointNearPoint( null, plan.GalaxyLocation, galaxy, 40, 80, plan, true, 20, Context, out safePoint ) )
-                    {
-                        Planet addon = galaxy.AddPlanet( PlanetType.Normal, safePoint,
-                            World_AIW2.Instance.GetPlanetGravWellSizeForPlanetType( Context.RandomToUse, PlanetPopulationType.None ) );
-                        addon.AddLinkTo( plan );
-                    }
-                }
-            }
-
             int randomExtraConnections = BadgerUtilityMethods.getSettingValueMapSettingOptionChoice_Expensive( mapConfig, mapType, "RandomExtraConnections" ).RelatedIntValue;
             BadgerUtilityMethods.RandomlyConnectXPlanetsWithoutIntersectingOthers( galaxy, randomExtraConnections, 40, 20, Context );
 
@@ -4972,13 +4948,13 @@ namespace Arcen.AIW2.External
                     nodesForThisSubTree--;
                 }
 
-                if ( goForPerfectSymmetry )
-                {
-                    if ( extraNodesForChildTrees > 0 )
-                    {
-                        nodesForThisSubTree++;
-                        extraNodesForChildTrees--;
-                    }
+                // If the planets don't divide evenly into our children, we
+                // want to distribute those extra nodes evenly among the
+                // subtrees.
+                if ( extraNodesForChildTrees > 0 )
+                {
+                    nodesForThisSubTree++;
+                    extraNodesForChildTrees--;
                 }
                 recursionDepth++;
                 Planet planetToPass = center;
diff --git GameData/Configuration/MapType/KDL_MapTypes.xml GameData/Configuration/MapType/KDL_MapTypes.xml
--- GameData/Configuration/MapType/KDL_MapTypes.xml
+++ GameData/Configuration/MapType/KDL_MapTypes.xml
@@ -119,11 +119,6 @@ This map has a number of unique features
               min_planets="40"
               max_planets="300"
   >
-    <map_option name="ExtraSatellitesToHitTarget" display_name="Extra Satellites To Hit Target?"
-      description="Should we add in extra planets in order to hit the target planet count?  Otherwise this map type has a habit of giving too few planets." default_id="1">
-      <choice_value id="0" display_name="No" description="This will look more orderly, but have fewer planets at times." related_int_value="0" />
-      <choice_value id="1" display_name="Yes" description="This will have more disorder, but almost certainly have the number of planets you requested." related_int_value="1" />
-    </map_option>
     <map_option name="RandomExtraConnections" display_name="Random Extra Connections"
       description="How many extra connections should there be between the rings??" default_id="1">
       <choice_value id="0" display_name="None" description="No extra connections beyond the default." related_int_value="0" />
@@ -137,7 +132,7 @@ This map has a number of unique features
     </map_option>
     <map_option name="GoForPerfectSymmetry" display_name="Go For Perfect Symmetry"
       description="If we go for perfect symmetry, we'll have a different number of planets than we actually asked for, so you'll want to keep an eye on that relative to the number of planets you ask for." default_id="1">
-      <choice_value id="0" display_name="No" description="This will look less orderly and may need those extra satellite planets to hit the target number of planets." related_int_value="0" />
+      <choice_value id="0" display_name="No" description="This will look less orderly." related_int_value="0" />
       <choice_value id="1" display_name="Yes" description="This will look more orderly, and if anything will have more planets than you asked for (careful with that, for performance reasons)." related_int_value="1" />
     </map_option>
   </map_type>
x-map-nonsymmetric-exact.patch (5,937 bytes)   
x-map-symmetric-branches.patch (1,558 bytes)    
# HG changeset patch
# User Tom Prince <[email protected]>
# Date 1635063513 21600
#      Sun Oct 24 02:18:33 2021 -0600
# Node ID 40eec34ffecd3c24f9f16f4738d413847ac7fb9f
# Parent  aa54a9c5f1462f0a5b349cbc545b9548cf14c11e
Ensure than main branches of symmetrical X map have the same number of planets.

diff --git CodeExternal/AIWarExternalDeepProcessingCode/src/Mapgen/MapGeneration.cs CodeExternal/AIWarExternalDeepProcessingCode/src/Mapgen/MapGeneration.cs
--- CodeExternal/AIWarExternalDeepProcessingCode/src/Mapgen/MapGeneration.cs
+++ CodeExternal/AIWarExternalDeepProcessingCode/src/Mapgen/MapGeneration.cs
@@ -4921,6 +4921,16 @@ namespace Arcen.AIW2.External
             AngleDegrees degreesBetweenChildren = AngleDegrees.Create( ((float)360) / numberOfChildren );
             int nodesPerChildTree = planetsToPlace / numberOfChildren;
             int extraNodesForChildTrees = planetsToPlace % numberOfChildren;
+            if ( goForPerfectSymmetry && recursionDepth < 1 ) {
+                // We want the main branches of a symmetrical map to have the
+                // same number of planets, so if the desired number of planets
+                // doesn't divide equally, round them up.
+                if (extraNodesForChildTrees > 0) {
+                    nodesPerChildTree += 1;
+                    extraNodesForChildTrees = 0;
+                }
+            }
+
             AngleDegrees angleToNextChild = startingAngleOffset;
             if ( numberOfChildren == 3 )
                 angleToNextChild -= 25;
x-map-symmetric-branches.patch (1,558 bytes)   

tom.prince

Oct 25, 2021 3:03 am

developer   ~0062997

I've attached a patch that implements one way of getting a bit more asymmetry back in the non-symmetric case.

It works by randomly varying how many planets are in each of the first 3 (or 2) subtrees by up to 20% percent of the target number of planets, and allocates the rest to the last branch.

At 40 planets, this tends to leave on of the main branch severely truncated (much like the workaround removed in my second patch above was fixing). However (based on some quick testing in the lobby), it does seem to give reasonable results for 80 planets: instead two leaves with 3 planets and two leaves with 2 planets in each major branch that the symmetric variant gives, this patch results in random amounts of leaves with random amount of planets with between 1 and 4 planets (with occasional outliers).

This probably would want some more tuning, and input from players that play on this style map.
x-map-more-non-symmetry.patch (2,818 bytes)    
# HG changeset patch
# User Tom Prince <[email protected]>
# Date 1635143598 21600
#      Mon Oct 25 00:33:18 2021 -0600
# Node ID 2b26a7fed1468b6478bee49a6fda49d87b3b416f
# Parent  40eec34ffecd3c24f9f16f4738d413847ac7fb9f
Make non-symmetric X map more non-symmetric.

diff --git CodeExternal/AIWarExternalDeepProcessingCode/src/Mapgen/MapGeneration.cs CodeExternal/AIWarExternalDeepProcessingCode/src/Mapgen/MapGeneration.cs
--- CodeExternal/AIWarExternalDeepProcessingCode/src/Mapgen/MapGeneration.cs
+++ CodeExternal/AIWarExternalDeepProcessingCode/src/Mapgen/MapGeneration.cs
@@ -4921,15 +4921,26 @@ namespace Arcen.AIW2.External
             AngleDegrees degreesBetweenChildren = AngleDegrees.Create( ((float)360) / numberOfChildren );
             int nodesPerChildTree = planetsToPlace / numberOfChildren;
             int extraNodesForChildTrees = planetsToPlace % numberOfChildren;
+            Span<int> extraNodes = stackalloc int[numberOfChildren];
+            extraNodes.Clear();
             if ( goForPerfectSymmetry && recursionDepth < 1 ) {
                 // We want the main branches of a symmetrical map to have the
                 // same number of planets, so if the desired number of planets
                 // doesn't divide equally, round them up.
                 if (extraNodesForChildTrees > 0) {
-                    nodesPerChildTree += 1;
-                    extraNodesForChildTrees = 0;
+                    extraNodes.Fill(1);
+                }
+            } else if ( goForPerfectSymmetry ) {
+                for ( int i = 0; i < extraNodesForChildTrees; i++ ) {
+                    extraNodes[i] = 1;
                 }
-            }
+            } else {
+                for ( int i = 0; i < numberOfChildren - 1; i++ ) {
+                    extraNodes[i] = Context.RandomToUse.Next(-nodesPerChildTree/5, nodesPerChildTree/5+extraNodesForChildTrees);
+                    extraNodesForChildTrees -= extraNodes[i];
+                }
+                extraNodes[numberOfChildren - 1] = extraNodesForChildTrees;
+            };
 
             AngleDegrees angleToNextChild = startingAngleOffset;
             if ( numberOfChildren == 3 )
@@ -4961,11 +4972,7 @@ namespace Arcen.AIW2.External
                 // If the planets don't divide evenly into our children, we
                 // want to distribute those extra nodes evenly among the
                 // subtrees.
-                if ( extraNodesForChildTrees > 0 )
-                {
-                    nodesForThisSubTree++;
-                    extraNodesForChildTrees--;
-                }
+                nodesForThisSubTree += extraNodes[i];
                 recursionDepth++;
                 Planet planetToPass = center;
                 if ( extra != null )
x-map-more-non-symmetry.patch (2,818 bytes)   

Issue History

Date Modified Username Field Change
Oct 25, 2021 1:58 am tom.prince New Issue
Oct 25, 2021 1:58 am tom.prince File Added: x-map-symmetric-randomness.patch
Oct 25, 2021 1:58 am tom.prince File Added: x-map-subtree-count.patch
Oct 25, 2021 1:58 am tom.prince File Added: x-map-nonsymmetric-exact.patch
Oct 25, 2021 1:58 am tom.prince File Added: x-map-symmetric-branches.patch
Oct 25, 2021 3:03 am tom.prince Note Added: 0062997
Oct 25, 2021 3:03 am tom.prince File Added: x-map-more-non-symmetry.patch
Oct 26, 2021 6:12 pm BadgerBadger Assigned To => tom.prince
Oct 26, 2021 6:12 pm BadgerBadger Status new => assigned
Oct 27, 2021 4:29 am tom.prince Status assigned => resolved
Oct 27, 2021 4:29 am tom.prince Resolution open => fixed
Oct 27, 2021 4:29 am tom.prince Fixed in Version => Beta 3.740 Code Panopticon