using Arcen.Universal;
using Arcen.AIW2.Core;
using System;
using System.Collections.Generic;
using System.Text;

namespace Arcen.AIW2.External
{

    public enum ClusterLinkAlgorithm
        {
         Large,
//         Microcosm,
         Medium,
         Nebula,
         Small,
         Butterfly,
         Fractured,
//         Unnamed3,
         Length
        }

  public enum LinkMethod
  {
    None,
    SpanningTree,
    Gabriel,
    RNG,
    SpanningTreeWithConnections
  }
    /* This is a helper class. It mostly contains routines for "Connect a list of planets
       according to a given algorithm" and "Place planets in an interesting but
       pleasing fashion", with a few others */

  internal static class BadgerUtilityMethods
  {
        /// <summary>
        /// For a given setting, get the int value for it.
        /// This is NOT reading out of the GameSettings.Current.GetIntBySetting( "SettingName" ) anymore, as that was not multiplayer-safe.
        /// And also not something that would always be correct.  Whatever is stored in GameSettings.Current we don't even care about anymore.
        /// We care about what is stored in mapConfig.CustomInts, at the integer offset that is related to the SettingName.
        /// This means we have to build the list of custom settings from the mapType, which is on the expensive side, so don't call this super repeatedly.
        /// </summary>
        public static int getSettingValueInt_Expensive( MapConfiguration mapConfig, MapTypeData mapType, string settingName )
        {
            if ( mapConfig == null )
            {
                ArcenDebugging.ArcenDebugLogSingleLine( "Null mapConfig passed into getSettingValueInt_Expensive!", Verbosity.ShowAsError );
                return 0;
            }
            if ( mapType == null )
            {
                ArcenDebugging.ArcenDebugLogSingleLine( "Null mapType passed into getSettingValueInt_Expensive!", Verbosity.ShowAsError );
                return 0;
            }
            if ( mapType.Generator == null )
            {
                ArcenDebugging.ArcenDebugLogSingleLine( "Null generator for mapType " + mapType.Name + " in getSettingValueInt_Expensive.", Verbosity.ShowAsError );
                return 0;
            }
            List<string> settingsForThisMapType = mapType.Generator.LobbyGetSettingNamesForMapIn( mapConfig, mapType );
            int indexOfSetting = settingsForThisMapType.IndexOf( settingName );

            if ( indexOfSetting < 0 || indexOfSetting >= settingsForThisMapType.Count )
            {
                ArcenDebugging.ArcenDebugLogSingleLine( "indexOfSetting " + indexOfSetting + " for mapType " + mapType.Name + 
                    " in getSettingValueInt_Expensive, when list of settingsForThisMapType.Count: " + settingsForThisMapType.Count +
                    " for setting '" + settingName + "'", Verbosity.ShowAsError );
                return 0;
            }
            if ( indexOfSetting >= mapConfig.CustomInts.Length )
            {
                ArcenDebugging.ArcenDebugLogSingleLine( "indexOfSetting " + indexOfSetting + " for mapType " + mapType.Name +
                    " in getSettingValueInt_Expensive, when list of mapConfig.CustomInts.Length: " + mapConfig.CustomInts.Length +
                    " for setting '" + settingName + "'", Verbosity.ShowAsError );
                return 0;
            }
            return mapConfig.CustomInts[indexOfSetting];
        }

        public static bool getSettingValueBool_Expensive( MapConfiguration mapConfig, MapTypeData mapType, string settingName )
        {
            //they are all stored as ints internally
            int intValueForSetting = getSettingValueInt_Expensive( mapConfig, mapType, settingName );
            return intValueForSetting > 0;
        }

    //Note from Chris: this is commented-out because I don't think we want to use this anymore, as it's a bit too direct of access
    //public static ArcenSetting getSettingByName(string settingName)
    //{
    //  //return the ArcenSetting for the setting name
    //  ArcenSetting setting = null;
    //  ArcenSparseLookup<string, ArcenSetting> settingMap =  ArcenSettingTable.Instance.LookupByName;
    //  if(settingMap.GetHasKey(settingName))
    //    {
    //      setting = settingMap[settingName];
    //    }
    //  return setting;
    //}

      internal static void limitLinksForAllPlanets( List<Planet> planetsForMap, ArcenSimContext Context, int maxLinks)
      {
          bool debug = false;
          if(debug)
              ArcenDebugging.ArcenDebugLogSingleLine("Capping links for " + planetsForMap.Count + " planets at " + maxLinks + " links", Verbosity.DoNotShow );
          for(int i = 0; i < planetsForMap.Count; i++)
          {
              Planet planet = planetsForMap[i];
              List<Planet> neighbors = getNeighborList(planet);
              int numAttempts = 0;
              while ( neighbors.Count > maxLinks && numAttempts < 20)
              {
                  if(debug)
                      ArcenDebugging.ArcenDebugLogSingleLine("Planet " + i + " has " + neighbors.Count + " neighbors. Attempt to remove one", Verbosity.DoNotShow );
                  int neighborIdx = Context.RandomToUse.NextWithInclusiveUpperBound( 0, neighbors.Count - 1 );
                  Planet neighbor = neighbors[neighborIdx];
                  planet.RemoveLinkTo(neighbor);
                  //List<Planet> connectedPlanets = null;
                  numAttempts++;
                  neighbors = getNeighborList(planet);
              }
          }
      }
      
      internal static void removeSomeLinksBetweenPlanets(int maxToRemove, List<Planet> planetsForMap, ArcenSimContext Context)
      {
        //attempts to remove up to maxToRemove links at random
        int linksToRemove = maxToRemove;
        int linksRemovedSoFar = 0;
        int numAttempts = 0;
        int maxAttempts = 100;
        while(linksRemovedSoFar < linksToRemove)
          {
            numAttempts++;
            if(numAttempts > maxAttempts)
              break;
            int planetIdxForDel = Context.RandomToUse.NextWithInclusiveUpperBound( 0, planetsForMap.Count - 1 );
            Planet planetToDelLink = planetsForMap[planetIdxForDel];
            List<Planet> neighbors = getNeighborList(planetToDelLink);
            if(neighbors.Count < 2) //skip planets with only one neighbor
              continue; 
            int neighborIdx = Context.RandomToUse.NextWithInclusiveUpperBound( 0, neighbors.Count - 1 );
            Planet neighbor = neighbors[neighborIdx];
            planetToDelLink.RemoveLinkTo(neighbor);
            List<Planet> connectedPlanets = null;
            if(isGalaxyFullyConnected(planetsForMap, ref connectedPlanets))
              {
                linksRemovedSoFar++;
              }
            else
              planetToDelLink.AddLinkTo(neighbor); //since this unconnected the galaxy, put the link back
             }
      }
    internal static List<Planet> getNeighborList(Planet planet)
      {
        List<Planet> neighbors = new List<Planet>();
        planet.DoForLinkedNeighbors( delegate (Planet neighbor)
                                            {
                                                if ( neighbor == null )
                                                    return DelReturn.Continue;
                                              neighbors.Add(neighbor);
                                              return DelReturn.Continue;
                                            } );
        return neighbors;
      }
      //this is similar to isGalaxyFullyConnected
      internal static void makeSureGalaxyIsFullyConnected(List<Planet> planetsForMap)
      {
          bool debug = false;
          List<Planet> connectedPlanets = null;
          isGalaxyFullyConnected(planetsForMap, ref connectedPlanets);
          while(connectedPlanets.Count < planetsForMap.Count)
          {
              //after the inner loop runs, we will link
              //the closest connected and unconnected planets
              Planet closestUnconnectedPlanet = null;
              Planet closestConnectedPlanet = null;
              //find the closest planet not in connectedPlanets
              for(int i = 0; i < planetsForMap.Count; i++)
              {
                  Planet test = planetsForMap[i];
                  if(connectedPlanets.Contains(test))
                      continue;
                  //now we have an unconnected planet
                  for(int j = 0; j < connectedPlanets.Count; j++)
                  {
                      if(closestUnconnectedPlanet == null && closestConnectedPlanet == null)
                      {
                          closestUnconnectedPlanet = test;
                          closestConnectedPlanet = connectedPlanets[j];
                          continue;
                      }
                      int previousMinDistance = Mat.DistanceBetweenPointsImprecise(closestConnectedPlanet.GalaxyLocation, closestUnconnectedPlanet.GalaxyLocation);
                      int distance = Mat.DistanceBetweenPointsImprecise(test.GalaxyLocation, connectedPlanets[j].GalaxyLocation);
                      if(distance < previousMinDistance)
                      {
                          closestConnectedPlanet = connectedPlanets[j];
                          closestUnconnectedPlanet = test;
                      }
                  }
              }
              if(debug)
                  ArcenDebugging.ArcenDebugLogSingleLine("Adding extra link between " + closestConnectedPlanet.Name + " and " + closestUnconnectedPlanet.Name, Verbosity.DoNotShow );
              closestConnectedPlanet.AddLinkTo(closestUnconnectedPlanet);
              isGalaxyFullyConnected(planetsForMap, ref connectedPlanets);
          }
      }
    internal static bool isGalaxyFullyConnected(List<Planet> planetsForMap, ref List<Planet> connectedPlanets )
    {
          //check for map connectivity (which will be done after stripping a few connections out)
          Planet firstPlanet = planetsForMap[0];
          List<Planet> localConnectedPlanets = new List<Planet>();
          if(connectedPlanets == null)
              connectedPlanets = new List<Planet>(); //only allocate one of these, then we'll clear it each time

          localConnectedPlanets.Add(firstPlanet);
          
          for(int i = 0; i < connectedPlanets.Count; i++)
            {
              Planet planetToCheck = localConnectedPlanets[i];
              planetToCheck.DoForLinkedNeighbors( delegate (Planet neighbor)
                                                  {
                                                    if(!localConnectedPlanets.Contains(neighbor))
                                                       localConnectedPlanets.Add(neighbor);
                                                    return DelReturn.Continue;
                                                  } );
            }
          connectedPlanets = localConnectedPlanets;
          if(connectedPlanets.Count == planetsForMap.Count)
            return true;
          return false;
    }
    //Note this needs to take a method of giving probabilities
    internal static LinkMethod getRandomLinkMethod(int percentSpanningTree, int percentGabriel,
                                                   int percentRNG, int percentSpanningTreeWithConnections,
                                                   ArcenSimContext Context)
    {
        if(percentSpanningTreeWithConnections + percentRNG + percentGabriel + percentSpanningTree != 100)
          {
            ArcenDebugging.ArcenDebugLogSingleLine("BUG! percentages given to getRandomLinkMethod do not add up to 100", Verbosity.DoNotShow);
          }
        LinkMethod val = LinkMethod.None;
        int linkingMethodRand = Context.RandomToUse.NextWithInclusiveUpperBound(0, 100);

        if(linkingMethodRand < percentGabriel)
          val = LinkMethod.Gabriel;
        else if(linkingMethodRand < percentGabriel + percentRNG)
          val = LinkMethod.RNG;
        else if(linkingMethodRand < percentGabriel + percentRNG + percentSpanningTree)
          val = LinkMethod.SpanningTree;
        else if(linkingMethodRand <= percentGabriel + percentRNG + percentSpanningTree + percentSpanningTreeWithConnections)
          val = LinkMethod.SpanningTreeWithConnections;
        else
        {
            ArcenDebugging.ArcenDebugLogSingleLine("Using random linking method number " + linkingMethodRand, Verbosity.DoNotShow );
        }
        return val;
    }
    
    //adds a circle of points
    internal static List<ArcenPoint> addCircularPoints(int numPoints, ArcenSimContext Context, ArcenPoint circleCenter, int circleRadius,
                                                       ref List<ArcenPoint> pointsSoFar)
      {
        float startingAngle = Context.RandomToUse.NextFloat( 1, 359 );
        List<ArcenPoint> pointsForThisCircle = new List<ArcenPoint>();
        for ( int i = 0; i < numPoints; i++ )
          {
            float angle = ( 360f / (float)numPoints ) * (float)i; // yes, this is theoretically an MP-sync problem, but a satisfactory 360 arc was simply not coming from the FInt approximations and I'm figuring the actual full-sync at the beginning of the game should sync things up before they matter
            angle += startingAngle;
            if ( angle >= 360f )
              angle -= 360f;
            ArcenPoint pointOnRing = circleCenter;
            pointOnRing.X += (int)Math.Round( circleRadius * (float)Math.Cos( angle * ( Math.PI / 180f ) ) );
            pointOnRing.Y += (int)Math.Round( circleRadius * (float)Math.Sin( angle * ( Math.PI / 180f ) ) );
            pointsForThisCircle.Add(pointOnRing);
            pointsSoFar.Add(pointOnRing);
          }
        return pointsForThisCircle;
      }
    //adds an ellipse of points
    internal static List<ArcenPoint> addElipticalPoints(int numPoints, ArcenSimContext Context, ArcenPoint ellipseCenter, int ellipseMajorAxis,
                                                        int ellipseMinorAxis, double rotationRad, ref List<ArcenPoint> pointsSoFar) {
      float startingAngle = Context.RandomToUse.NextFloat(1, 359);
      List<ArcenPoint> pointsForThisCircle = new List<ArcenPoint>();
      for(int i = 0; i < numPoints; i++) {
        float angle = (360f / (float)numPoints) * (float)i; // yes, this is theoretically an MP-sync problem, but a satisfactory 360 arc was simply not coming from the FInt approximations and I'm figuring the actual full-sync at the beginning of the game should sync things up before they matter
        angle += startingAngle;
        if(angle >= 360f)
          angle -= 360f;
        double angleRad = angle / 180 * Math.PI;
        ArcenPoint pointOnRing = ellipseCenter;
        double tan = Math.Sin(angleRad) / Math.Cos(angleRad);
        double x = ellipseMajorAxis * ellipseMinorAxis / Math.Sqrt( ellipseMinorAxis * ellipseMinorAxis + ellipseMajorAxis * ellipseMajorAxis * tan * tan); //not using Mat.SqrtFast because of need for double precision
        //heck if I know why this has to be done, but the ellipse gets twisted without it
        if(angle >= 90) x = -x;
        if(angle >= 270) x = -x;
        double y = x * Math.Sin(angleRad) / Math.Cos(angleRad);
        double xn = x * Math.Cos(rotationRad) - y * Math.Sin(rotationRad);
        double yn = x * Math.Sin(rotationRad) + y * Math.Cos(rotationRad);
        pointOnRing.X += (int)xn;
        pointOnRing.Y += (int)yn;
        pointsForThisCircle.Add(pointOnRing);
        pointsSoFar.Add(pointOnRing);/**/
      }
      return pointsForThisCircle;
    }

    internal static List<ArcenPoint> addGrid()
      {
        return null;

      }
    
    //this version of AddPointsInCircle can provide some other points that must be avoided
    internal static List<ArcenPoint> addPointsInCircleWithExclusion(int numPoints, ArcenSimContext Context, ArcenPoint circleCenter, int circleRadius,
                                             int minDistanceBetweenPlanets, ref List<ArcenPoint> pointsSoFar, List<ArcenPoint> pointsToAvoid, int distanceFromAvoidance, int divisibleByX = 0)
    {
        //keeps track of previously added planets as well
        int numberFailuresAllowed = 1000;
        List<ArcenPoint> pointsForThisCircle = new List<ArcenPoint>();
        List<ArcenPoint> pointsToAvoidWithoutThisCenter = new List<ArcenPoint>(pointsToAvoid);
        pointsToAvoidWithoutThisCenter.Remove(circleCenter);
         for ( int i = 0; i < numPoints; i++)
           {
             ArcenPoint testPoint = circleCenter.GetRandomPointWithinDistance(Context.RandomToUse, 0, circleRadius);
             if(divisibleByX != 0)
               {
                 testPoint.X -= testPoint.X%divisibleByX;
                 testPoint.Y -= testPoint.Y%divisibleByX;
               }
             if ( UtilityMethods.HelperDoesPointListContainPointWithinDistance( pointsSoFar, testPoint, minDistanceBetweenPlanets))
               {
                 i--;
                 numberFailuresAllowed--;
                 if(numberFailuresAllowed <= 0)
                   {
                     numberFailuresAllowed = 1000;
                     minDistanceBetweenPlanets -= 10;
                   }
                 continue;
               }
                 if (UtilityMethods.HelperDoesPointListContainPointWithinDistance( pointsToAvoidWithoutThisCenter, testPoint, distanceFromAvoidance))
                   {
                     i--;
                     numberFailuresAllowed--;
                     if(numberFailuresAllowed <= 0)
                     {
                         numberFailuresAllowed = 1000;
                         distanceFromAvoidance -= 10;
                     }
                     continue;
                   }

             pointsForThisCircle.Add(testPoint);
             pointsSoFar.Add(testPoint);
           }
         return pointsForThisCircle;
    }

    internal static ArcenPoint  GetRandomPointWithinRectangle( ArcenPoint topL, ArcenPoint topR,
                                                                          ArcenPoint bottomL, ArcenPoint bottomR,
                                                                          ArcenSimContext Context)
    {
      int minLegalX = Math.Min( topL.X, bottomL.X);
      int maxLegalX = Math.Min( topR.X, bottomR.X);
      int minLegalY = Math.Min( bottomL.Y, bottomR.Y);
      int maxLegalY = Math.Min( topL.Y, topR.Y);
      int newX = Context.RandomToUse.Next( minLegalX, maxLegalX );
      int newY = Context.RandomToUse.Next( minLegalY, maxLegalY );
      ArcenPoint newPoint = ArcenPoint.Create( newX, newY );
      return newPoint;
    }

    //adds in a rectangle to roughly cover the screen
    //The X and Y values here were arrived at by crude trial and error
    internal static List<ArcenPoint> addPointsInStartScreen(int numPoints, ArcenSimContext Context, int minDistanceBetweenPlanets,
                                                            ref List<ArcenPoint> pointsSoFar, bool allowClustersInPoints, int divisibleByX = 1)

      {
          int x = 1200;
          int y = 600;
          if(numPoints > 80)
          {
              x = 1300;
              y = 800;
          }
          if(numPoints > 180)
          {
              x = 1900;
              y = 1400;
          }
          if(numPoints > 200)
          {
              x = 2300;
              y = 1900;
          }
          if(numPoints > 300)
          {
              x = 3000;
              y = 2000;
          }
          if(numPoints >= 300)
          {
              x = 3500;
              y = 2500;
          }
          
            //ArcenPoint GalaxyMapOnly_GalaxyCenter = Engine_AIW2.Instance.GalaxyMapOnly_GalaxyCenter;
            ArcenPoint topL = ArcenPoint.Create(-x,y);
            ArcenPoint topR = ArcenPoint.Create(x ,y);
            ArcenPoint bottomL = ArcenPoint.Create(-x,y);
            ArcenPoint bottomR = ArcenPoint.Create(x,-y);
            if(!allowClustersInPoints)
            {
                return addPointsInRectangle(numPoints, Context, minDistanceBetweenPlanets, ref pointsSoFar,
                                            divisibleByX, topL, topR, bottomL, bottomR);
            }
            else
            {
                return addPointsInRectangleWithClusters(numPoints, Context, minDistanceBetweenPlanets, ref pointsSoFar,
                                            divisibleByX, topL, topR, bottomL, bottomR);
            }
      }

        internal static List<ArcenPoint> addPointsInRectangle( int numPoints, ArcenSimContext Context, int minDistanceBetweenPlanets,
                                                            ref List<ArcenPoint> pointsSoFar, int divisibleByX, ArcenPoint topL, ArcenPoint topR,
                                                            ArcenPoint bottomL, ArcenPoint bottomR )
        {
            //keeps track of previously added planets as well
            int numberFailuresAllowed = 1000;
            List<ArcenPoint> pointsForThisRectangle = new List<ArcenPoint>();
            int workingMinDist = minDistanceBetweenPlanets;
            for ( int i = 0; i < numPoints; i++ )
            {
                int minDistForThisPoint = workingMinDist;
                // if ( i % 10 == 0 )
                //     minDistForThisPoint *= 3;
                // if ( i % 5 == 0 )
                // {
                //     minDistForThisPoint *= 3;
                //     minDistForThisPoint /= 2;
                // }
                // if ( i % 11 == 0 )
                //     minDistForThisPoint *= 7;


                ArcenPoint testPoint = GetRandomPointWithinRectangle( topL, topR,
                                                                     bottomL, bottomR, Context );
                if ( divisibleByX != 0 )
                {
                    testPoint.X -= testPoint.X % divisibleByX;
                    testPoint.Y -= testPoint.Y % divisibleByX;
                }

                if ( UtilityMethods.HelperDoesPointListContainPointWithinDistance( pointsSoFar, testPoint, minDistForThisPoint ) )
                {
                    i--;
                    numberFailuresAllowed--;
                    if ( numberFailuresAllowed <= 0 )
                    {
                        numberFailuresAllowed = 1000;
                        minDistForThisPoint -= 10;
                        if ( minDistForThisPoint < 0 )
                        {
                            Engine_AIW2.Instance.LogErrorDuringCurrentMapGen( " NOT GENERATE A PLANET BAD JUJU GURU #253421 (more than 1000 failures trying to add planets in rectangle, so maybe not room?)" );
                            return pointsForThisRectangle;
                        }
                    }
                    continue;
                }
                pointsForThisRectangle.Add( testPoint );
                pointsSoFar.Add( testPoint );
            }
            return pointsForThisRectangle;
        }

        internal static List<ArcenPoint> addPointsInRectangleWithClusters( int numPoints, ArcenSimContext Context, int minDistanceBetweenPlanets,
                                                                          ref List<ArcenPoint> pointsSoFar, int divisibleByX, ArcenPoint topL, ArcenPoint topR,
                                                                          ArcenPoint bottomL, ArcenPoint bottomR )
        {
            //keeps track of previously added planets as well
            int numberFailuresAllowed = 1000;
            List<ArcenPoint> pointsForThisRectangle = new List<ArcenPoint>();
            //int pointsToAdd = numPoints;
            //int currPoint = 0;
            int interClusterDist = minDistanceBetweenPlanets * 4;
            bool debug = false;
            int intraClusterDist = minDistanceBetweenPlanets * 2;

            List<ArcenPoint> clusterCenters = new List<ArcenPoint>();
            int minClusters = 0;
            int maxClusters = 0;
            if ( numPoints > 100 )
                maxClusters = 5;

            else if ( numPoints > 70 )
                maxClusters = 4;
            else if ( numPoints > 40 )
                maxClusters = 3;
            else if ( numPoints < 30 )
                maxClusters = 1;
            else
                maxClusters = 0;
            int numClusters = Context.RandomToUse.NextWithInclusiveUpperBound( minClusters, maxClusters );
            int minClusterSize = 5;
            int maxClusterSize = 10;
            //First let's choose our cluster centers
            for ( int i = 0; i < numClusters; i++ )
            {
                ArcenPoint testPoint = GetRandomPointWithinRectangle( topL, topR,
                                                                     bottomL, bottomR, Context );
                if ( numberFailuresAllowed <= 0 )
                {
                    numberFailuresAllowed = 1000;
                    break;
                }
                if ( UtilityMethods.HelperDoesPointListContainPointWithinDistance( clusterCenters, testPoint, interClusterDist ) )
                {
                    numberFailuresAllowed--;
                    continue;
                }
                clusterCenters.Add( testPoint );
            }
            if ( debug )
                ArcenDebugging.ArcenDebugLogSingleLine( "Got " + clusterCenters.Count + " clusters", Verbosity.DoNotShow );
            //now let's allocate points for the clusters:
            for ( int i = 0; i < clusterCenters.Count; i++ )
            {
                int clusterSize = Context.RandomToUse.NextWithInclusiveUpperBound( minClusterSize, maxClusterSize );
                if ( debug )
                    ArcenDebugging.ArcenDebugLogSingleLine( "Cluster " + i + " adding " + clusterSize + " points", Verbosity.DoNotShow );
                List<ArcenPoint> newPoints = addPointsInCircle( clusterSize, Context, clusterCenters[i], intraClusterDist,
                                                               minDistanceBetweenPlanets, ref pointsForThisRectangle, divisibleByX );
                pointsSoFar.AddRange( newPoints );

            }
            //now let's allocate the rest of the points
            int numP = 0;
            while ( pointsForThisRectangle.Count < numPoints )
            {
                int tempMinDist = minDistanceBetweenPlanets;
                // if ( numP % 10 == 0 )
                //     tempMinDist *= 3;
                // if ( numP % 5 == 0 )
                // {
                //     tempMinDist *= 3;
                //     tempMinDist /= 2;
                // }
                // if ( numP % 3 == 0 )
                //     tempMinDist *= 7;

                ArcenPoint testPoint = GetRandomPointWithinRectangle( topL, topR,
                                                                     bottomL, bottomR, Context );
                if ( divisibleByX != 0 )
                {
                    testPoint.X -= testPoint.X % divisibleByX;
                    testPoint.Y -= testPoint.Y % divisibleByX;
                }

                if ( UtilityMethods.HelperDoesPointListContainPointWithinDistance( pointsSoFar, testPoint, tempMinDist ) )
                //                UtilityMethods.HelperDoesPointListContainPointWithinDistance(clusterCenters, testPoint, interClusterDist))
                {
                    numberFailuresAllowed--;
                    if ( numberFailuresAllowed <= 0 )
                    {
                        numberFailuresAllowed = 1000;
                        tempMinDist -= 10;
                        minDistanceBetweenPlanets -= 10;
                        if ( tempMinDist < 0 )
                        {
                            Engine_AIW2.Instance.LogErrorDuringCurrentMapGen( " NOT GENERATE A PLANET BAD JUJU GURU #253421 (more than 1000 failures trying to add planets in rectangle with clusters, so maybe not room?)" );
                            return pointsForThisRectangle;
                        }
                    }
                    continue;

                }
                pointsForThisRectangle.Add( testPoint );
                pointsSoFar.Add( testPoint );
                numP++;
            }
            if ( debug )
                ArcenDebugging.ArcenDebugLogSingleLine( "forRect points " + pointsForThisRectangle.Count + " so far points" + pointsSoFar.Count, Verbosity.DoNotShow );
            return pointsForThisRectangle;
        }

        //Add points within a circle defined by circleCenter and circleRadius
        //It gives a more ordered appearance when the points are on "more reasonable" numbers, so include the
        //divisible
        internal static List<ArcenPoint> addPointsInCircle( int numPoints, ArcenSimContext Context, ArcenPoint circleCenter, int circleRadius,
                                                 int minDistanceBetweenPlanets, ref List<ArcenPoint> pointsSoFar, int divisibleByX = 0 )
        {
            //keeps track of previously added planets as well
            int numberFailuresAllowed = 1000;
            List<ArcenPoint> pointsForThisCircle = new List<ArcenPoint>();
            bool debug = false;
            if ( debug )
                ArcenDebugging.ArcenDebugLogSingleLine( "generating " + numPoints + " with minDistance " + minDistanceBetweenPlanets + "and radius " + circleRadius + " centered on " + circleCenter.X + ", " + circleCenter.Y, Verbosity.ShowAsInfo );
            int workingMinDist = minDistanceBetweenPlanets;
            for ( int i = 0; i < numPoints; i++ )
            {
                int minDistForThisPlanet = workingMinDist;
                // if ( i % 10 == 0 )
                //     minDistForThisPlanet *= 3;
                // if ( i % 5 == 0 )
                // {
                //     minDistForThisPlanet *= 3;
                //     minDistForThisPlanet /= 2;
                // }
                // if ( i % 3 == 0 )
                //     minDistForThisPlanet *= 7;

                ArcenPoint testPoint = circleCenter.GetRandomPointWithinDistance( Context.RandomToUse, 0, circleRadius );
                if ( divisibleByX != 0 )
                {
                    if ( debug )
                    {
                        string s = String.Format( "addPointsInCircle: previous {0},{1}",
                                                 testPoint.X, testPoint.Y );
                        ArcenDebugging.ArcenDebugLogSingleLine( s, Verbosity.DoNotShow );
                    }
                    testPoint.X -= testPoint.X % divisibleByX;
                    testPoint.Y -= testPoint.Y % divisibleByX;
                    if ( debug )
                    {
                        string s = String.Format( "addPointsInCircle: Adjusting planet to {0},{1}",
                                                 testPoint.X, testPoint.Y );
                        ArcenDebugging.ArcenDebugLogSingleLine( s, Verbosity.DoNotShow );
                    }
                }
                if ( UtilityMethods.HelperDoesPointListContainPointWithinDistance( pointsSoFar, testPoint, minDistForThisPlanet ) )
                {
                    i--;
                    numberFailuresAllowed--;
                    if ( numberFailuresAllowed <= 0 )
                    {
                        //If we have exceeded the number of allowed failures,
                        //decrease the minDistance and retry
                        numberFailuresAllowed = 1000;
                        workingMinDist -= 10;
                        minDistForThisPlanet -= 10;
                        if ( workingMinDist < 10 )
                        {

                            Engine_AIW2.Instance.LogErrorDuringCurrentMapGen( " NOT GENERATE A PLANET BAD JUJU GURU #253421 (more than 1000 failures trying to add planets in circle, so maybe not room?) workingMinDist " + workingMinDist + " minDistForThisPlanet " + minDistForThisPlanet + " we placed " + pointsForThisCircle.Count + " planets." );
                            return pointsForThisCircle;
                        }
                    }
                    continue;
                }
                pointsForThisCircle.Add( testPoint );
                pointsSoFar.Add( testPoint );
                if ( debug )
                {
                    string s = String.Format( "addPointsInCircle: Adding planet {0} at location {1},{2}", i,
                                             testPoint.X, testPoint.Y + " so far " + numberFailuresAllowed + " failures.");
                    ArcenDebugging.ArcenDebugLogSingleLine( s, Verbosity.DoNotShow );
                }
            }
            return pointsForThisCircle;
        }

      internal static bool wouldLinkCrossOtherPlanets(Planet firstPlanet, Planet secondPlanet, List<Planet> planetsForMap)
      {
          //figure out if the line crossing these two planets would hit another planet
          bool debug = false;
          int firstPlanetIdx = firstPlanet.PlanetIndex;
          int secondPlanetIdx = secondPlanet.PlanetIndex;

          ArcenPoint p1 = firstPlanet.GalaxyLocation;
          ArcenPoint p2 = secondPlanet.GalaxyLocation;

          for(int crossIdx1 = 0; crossIdx1 < planetsForMap.Count; crossIdx1++)
          {
              if((crossIdx1 == firstPlanetIdx) || (crossIdx1 == secondPlanetIdx))
                continue;
              ArcenPoint crossP1 = planetsForMap[crossIdx1].GalaxyLocation;
              for(int crossIdx2 = 0; crossIdx2 < planetsForMap.Count; crossIdx2++)
                {
                  if(crossIdx1 == crossIdx2)
                    continue;
                  if((crossIdx2 == firstPlanetIdx) || (crossIdx2 == secondPlanetIdx))
                    continue;
                  if(!planetsForMap[crossIdx1].GetIsDirectlyLinkedTo(planetsForMap[crossIdx2]))
                    continue;
                  ArcenPoint crossP2 = planetsForMap[crossIdx2].GalaxyLocation;

                  if(Mat.LineSegmentIntersectsLineSegment(p1, p2, crossP1, crossP2, 10))
                    {
                      if(debug)
                        {
                          string s = String.Format("Planets {0} ({4},{5}) and {1} ({6},{7}) connection overlaps with {2}-{3} ({8},{9})-({10},{11})",
                                                   firstPlanetIdx, secondPlanetIdx, crossIdx1, crossIdx2,
                                                   p1.X, p1.Y, p2.X, p2.Y, crossP1.X, crossP1.Y, crossP2.X, crossP2.Y);
                          ArcenDebugging.ArcenDebugLogSingleLine( s, Verbosity.DoNotShow);
                        }
                      return true;
                    }
                }
            }
          return false;
      }
    //the random connections can't be too close; they must be at least
    //minumum hops apart
    //if numRandomConnections == -1 then "use an appropriate number"
    internal static void addRandomConnections(List<Planet> planetsForMap, int numRandomConnections, ArcenSimContext Context, int minimumHops)
    {
      int firstPlanetIdx = 0;
      int secondPlanetIdx = 0;
      List<int> usedPlanetsForConnections = new List<int>();
      int maxRetries = 1000;
      int numRetries = 0;
      bool debug = false;
      if(numRandomConnections == -1)
        {
          if(planetsForMap.Count < 20)
            numRandomConnections = 1;
          else if(planetsForMap.Count < 40)
            numRandomConnections = 2;
          else if(planetsForMap.Count < 50)
            numRandomConnections = 3;
          else if(planetsForMap.Count < 60)
            numRandomConnections = 4;
          else if(planetsForMap.Count < 80)
            numRandomConnections = 5;
          else if(planetsForMap.Count < 100)
            numRandomConnections = 6;
          else
            numRandomConnections = 8;
        }
      if(debug)
        {
          string s = String.Format("Adding {0} random connections", numRandomConnections);
          ArcenDebugging.ArcenDebugLogSingleLine( s, Verbosity.DoNotShow);
        }
      for(int i = 0; i < numRandomConnections; i++)
        {
            int firstPlanetRetries = 0;
          do{
            firstPlanetIdx = Context.RandomToUse.Next(0, planetsForMap.Count);
            //make sure we don't use this planet twice
            if(debug)
              {
                string s = String.Format("Attempt at first planet: {0} ", firstPlanetIdx);
                ArcenDebugging.ArcenDebugLogSingleLine( s, Verbosity.DoNotShow);
              }

            for(int j = 0; j < usedPlanetsForConnections.Count; j++)
              {
                if(firstPlanetIdx == usedPlanetsForConnections[j])
                  firstPlanetIdx = -1;
              }
            firstPlanetRetries++;
          }while(firstPlanetIdx == -1 && firstPlanetRetries < maxRetries);
          if(firstPlanetIdx == -1)
          {
              numRetries++;
              continue;
          }
          if(debug)
            {
              string s = String.Format("First random planet: {0}", firstPlanetIdx);
              ArcenDebugging.ArcenDebugLogSingleLine( s, Verbosity.DoNotShow);
            }

          //let's get all the planets within X hops of the first planet,
          //to make sure we get an interesting link
          int[] neighbors;
          minimumHops++; //increment this now to make the following loop easy
          do{
            minimumHops--; //decrease the hops until we get enough planets to work with
            neighbors = getNeighbors(firstPlanetIdx, minimumHops, planetsForMap);
          }while(planetsForMap.Count - neighbors.Length > numRandomConnections - i);

          //use the neighborhood generated above to find a potential planet
          //to link to the first planet
          int maxSecondPlanetRetries = 1000;
          int secondPlanetRetries = 0;
          do{
            secondPlanetIdx = Context.RandomToUse.Next(0, planetsForMap.Count);
            if(secondPlanetIdx == firstPlanetIdx)
              secondPlanetIdx = -1;
            for(int j = 0; j < usedPlanetsForConnections.Count; j++)
              {
                if(secondPlanetIdx == usedPlanetsForConnections[j])
                  secondPlanetIdx = -1;
              }
            if(isNeighborAlready(neighbors, planetsForMap.Count, secondPlanetIdx))
              secondPlanetIdx = -1;
            secondPlanetRetries++;
          }while((secondPlanetIdx == -1) && (secondPlanetRetries < maxSecondPlanetRetries));
          if(secondPlanetIdx == -1)
          {
              //this can happen if we have a very small number of planets we are working with
              numRetries++;
              continue;
          }
          //Two potential planets are selected for random connections (neither has
          //a random connection yet)
          //Let's make sure a link between t hem does not cause any overlap in lines
          Planet firstPlanet = planetsForMap[firstPlanetIdx];
          Planet secondPlanet = planetsForMap[secondPlanetIdx];


          if(wouldLinkCrossOtherPlanets(firstPlanet, secondPlanet, planetsForMap))
            {
              i--; //discard this pair, since there's an overlap
              neighbors = null; //let's not leak memory
            }
          else
            {
              //Found a valid link, create it
              firstPlanet.AddLinkTo(secondPlanet);
              usedPlanetsForConnections.Add(firstPlanetIdx);
              usedPlanetsForConnections.Add(secondPlanetIdx);
            }
          numRetries++;
          if(numRetries > maxRetries)
            {
              numRetries = 0;
              if(debug)
                {
                  string s = String.Format("Exceeded retry limit with {0} hop minimum; retry", minimumHops);
                  ArcenDebugging.ArcenDebugLogSingleLine( s, Verbosity.DoNotShow);
                }
              if(minimumHops > 2)
                {
                  minimumHops--; //make it easier to find matches
                }
              else
                {
                  return;
                }
            }
        }
      }
    //this code is for addRandomConnections; we want to not link
    //planets already close to eachother
    internal static int[] getNeighbors(int planetIdx, int degreeOfNeighbors, List<Planet>planetsForMap)
    {
        bool debug = false;
        if(debug)
          {
            string s = String.Format("returning list of all planets {0} or fewer hops from {1}", degreeOfNeighbors, planetIdx);
            ArcenDebugging.ArcenDebugLogSingleLine( s, Verbosity.DoNotShow);
          }
        Planet testPlanet = planetsForMap[planetIdx];
        int[] neighbors = new int[planetsForMap.Count];
        int neighborsSoFar = 0;
        for(int i = 0; i < planetsForMap.Count; i++)
          neighbors[i] = -1;
        //test for all immediate neighbors
        for(int i = 0; i < planetsForMap.Count; i++)
          {
            if(i == planetIdx)
              continue;
            Planet potentialNewNeighbor = planetsForMap[i];
            if(testPlanet.GetIsDirectlyLinkedTo(potentialNewNeighbor))
              {
                neighbors[neighborsSoFar] = i;
                neighborsSoFar++;
                if(debug)
                  {
                    string s = String.Format("{0} --> one hop {1} ({2} neighbors so far)", planetIdx, i, neighborsSoFar);
                    ArcenDebugging.ArcenDebugLogSingleLine( s, Verbosity.DoNotShow);
                  }
              }
          }
        //now count down remaining degrees
        //note that for a large number of hops and a small number of planets, we might
        //get all the planets before we run out of hops
        while(degreeOfNeighbors > 1 && neighborsSoFar < planetsForMap.Count)
          {
            int newNeighbors = 0;
            for(int i = 0; i < neighborsSoFar; i++)
              {
                //now we check all the current neighbors to see who their neighbors are,
                //which will give us the next degree of neighborness

                int planetIdxForNeighbor = neighbors[i];
                if(debug)
                  {
                    string s = String.Format("Checking for connections to {0}", planetIdxForNeighbor);
                    ArcenDebugging.ArcenDebugLogSingleLine( s, Verbosity.DoNotShow);
                  }
                for(int j = 0; j < planetsForMap.Count -1; j++)
                  {
                    //check this planet (a neighbor) for all connections that
                    //are not itself and are also not on the list
                    if(j == planetIdx)
                      continue;
                    if(isNeighborAlready(neighbors, neighborsSoFar + newNeighbors, j))
                      {
                        if(debug)
                          {
                            string s = String.Format(" {0} is on the list already, skip it", j);
                            ArcenDebugging.ArcenDebugLogSingleLine( s, Verbosity.DoNotShow);
                          }
                        continue;
                      }

                    if(debug)
                      {
                        string s = String.Format("Checking {0} against {1} (out of {2} total planets). We have {3} neighbors so far", planetIdxForNeighbor, j, planetsForMap.Count, neighborsSoFar);
                        ArcenDebugging.ArcenDebugLogSingleLine( s, Verbosity.DoNotShow);
                      }

                    Planet currentNeighbor = planetsForMap[planetIdxForNeighbor];
                    Planet potentialNewNeighbor = planetsForMap[j];
                    if(currentNeighbor.GetIsDirectlyLinkedTo(potentialNewNeighbor))
                      {
                        if(debug)
                          {
                            string s = String.Format("{0} is directly linked to {1} (neighborsSoFar {2} newNeighbors {3}", planetIdxForNeighbor, j, neighborsSoFar, newNeighbors);
                            ArcenDebugging.ArcenDebugLogSingleLine( s, Verbosity.DoNotShow);
                          }

                        neighbors[neighborsSoFar + newNeighbors] = j;
                        newNeighbors++;
                        if(debug)
                          {
                            string s = String.Format("{0} --> {1} hop {2}", planetIdxForNeighbor, degreeOfNeighbors, j);
                            ArcenDebugging.ArcenDebugLogSingleLine( s, Verbosity.DoNotShow);
                          }
                      }
                  }
              }
            neighborsSoFar += newNeighbors;
            degreeOfNeighbors--;
          }
        return neighbors;
    }

    //checks if element is already in array. I don't always want to look at every
    //element
    internal static bool isNeighborAlready(int [] neighborList, int numElemToCheck, int element)
    {
      for(int i = 0; i < numElemToCheck; i++)
        {
          if(neighborList[i] == element)
            return true;
        }
      return false;
    }

    internal static List<Planet> convertPointsToPlanets(List<ArcenPoint> vertices, Galaxy galaxy, ArcenSimContext Context)
    {
      List<Planet> planetsForMap = new List<Planet>();
      for(int i = 0; i < vertices.Count; i++)
        {
          Planet planet = galaxy.AddPlanet(PlanetType.Normal, vertices[i], Context);
          planetsForMap.Add(planet);
        }
      return planetsForMap;
    }
    /* This returns a matrix where matrix[i][j] == 1 means point i and point j should be connected 
       Has the same algorithm as createMinimumSpanningTree, but it doesn't do the linking. */
    internal static int[,] createMinimumSpanningTreeLinks(List<ArcenPoint> pointsForGraph)
    {
        int [,] connectionArray;
        connectionArray = new int[pointsForGraph.Count, pointsForGraph.Count];
        for(int i = 0; i < pointsForGraph.Count; i++)
          {
            for(int j = 0; j < pointsForGraph.Count; j++)
              {
                connectionArray[i,j] = 0;
              }
          }
        List<int>verticesNotInTree = new List<int>();
        List<int>verticesInTree = new List<int>();

        // ArcenDebugging.ArcenDebugLogSingleLine("Creating minimum spanning tree now", Verbosity.DoNotShow);
        for(int i = 0; i < pointsForGraph.Count; i++)
          verticesNotInTree.Add(i);
        //Pick first element, then remove it from the list
        int pointIdx  = verticesNotInTree[0];
        verticesNotInTree.RemoveAt(0);
        verticesInTree.Add(pointIdx);

        //initialize adjacency matrix for Prim's algorithm
        //the adjacency matrix contains entries as follows
        //pointIdxNotInTree <closest point in tree> <distance to closest point>
        //In the body of the algorithm we look at this matrix to figure out
        //which point to add to the tree next, then update it for the next iteration
        int[,] spanningAdjacencyMatrix;
        spanningAdjacencyMatrix = new int[pointsForGraph.Count, 3];
        for(int i = 0; i < pointsForGraph.Count; i++)
          {
                spanningAdjacencyMatrix[i,0] = i;
                spanningAdjacencyMatrix[i,1] = -1;
                spanningAdjacencyMatrix[i,1] = 9999;
          }
        //loop until all vertices are in the tree
        while(verticesNotInTree.Count > 0)
          {
            //update the adjacency matrix
            //for each element NOT in the tree, find the closest
            //element in the tree
            for(int i = 0; i < verticesNotInTree.Count; i++)
              {
                int minDistance = 9999;
                for(int j = 0; j < verticesInTree.Count; j++)
                  {
                    int idxNotInTree = verticesNotInTree[i];
                    int idxInTree = verticesInTree[j];
                    ArcenPoint pointNotInTree = pointsForGraph[idxNotInTree];
                    ArcenPoint pointInTree = pointsForGraph[idxInTree];
                    int distance = Mat.DistanceBetweenPointsImprecise(pointNotInTree, pointInTree);
                    if(distance < minDistance)
                      {
                        spanningAdjacencyMatrix[idxNotInTree,1] = idxInTree;
                        spanningAdjacencyMatrix[idxNotInTree,2] = distance;
                        minDistance = distance;
                      }
                  }
              }

            //now pick the closest edge
            // s = System.String.Format("Examine the remaining {0} vertices to find which to add",
            //                          verticesNotInTree.Count);
            // ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);
            int minDistanceFound = 9999;
            int closestPointIdx = -1;
            int pointToAdd = -1;
            for(int i = 0; i < verticesNotInTree.Count; i++)
              {
                pointIdx = verticesNotInTree[i];
                // s = System.String.Format( "To find closest edge, examine {0} of {1} (idx {4}), minDistance {2} dist for this point {3}",
                //                           i, verticesNotInTree.Count , minDistanceFound, spanningAdjacencyMatrix[pointIdx, 2], pointIdx);
                // ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);
                if(spanningAdjacencyMatrix[pointIdx,2] == 0)
                  {
                    //don't try to link a point to itself
                    continue;
                  }
                if(spanningAdjacencyMatrix[pointIdx, 2] < minDistanceFound)
                  {
                    minDistanceFound = spanningAdjacencyMatrix[pointIdx,2];
                    closestPointIdx = spanningAdjacencyMatrix[pointIdx,1];
                    pointToAdd = pointIdx;
                  }
              }
            // s = System.String.Format( "Adding point idx {0} closest neighbor ({1}. distance {2} to tree", pointToAdd,
            //                           closestPointIdx, minDistanceFound);
            // ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);
            //Now let's add this point to the Tree
            verticesNotInTree.Remove(pointToAdd);
            verticesInTree.Add(pointToAdd);
            spanningAdjacencyMatrix[pointToAdd, 2] = 9999;
            connectionArray[pointToAdd,closestPointIdx] = 1;
            connectionArray[closestPointIdx,pointToAdd] = 1;
          }
        return connectionArray;
    }
    /* This returns a matrix where matrix[i][j] == 1 means point i and point j should be connected 
       Has the same algorithm as createGabrielGraph, but a seperate implementation */
    internal static int[,]  createGabrielGraphLinks(List<ArcenPoint> pointsForGraph)
    {
        //Algorithm: for each node
        //                          find midpoint to another node
        //                          Check that no other planets are in the circle connecting the two nodes
        //                              If no other planets, link these two planets
        //see htts://en.wikipedia.org/wiki/Gabriel_graph
      int [,] connectionArray;
      connectionArray = new int[pointsForGraph.Count, pointsForGraph.Count];
      for(int i = 0; i < pointsForGraph.Count; i++)
        {
          for(int j = 0; j < pointsForGraph.Count; j++)
            {
              connectionArray[i,j] = 0;
            }
        }
        //Here i and j iterate over potential pairs. For each potential pair, iterate over k,
        //which is every other point, to make sure k is not too close to i and j
        for(int i = 0; i < pointsForGraph.Count ; i++)
          {
            // s = System.String.Format("Outer Loop: Point {0} of {1}", i, pointsForGraph.Count);
            // ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);
            for(int j = 0; j < pointsForGraph.Count  ; j++)
              {
                if(j == i)
                  continue;

                ArcenPoint pointOne = pointsForGraph[i];
                ArcenPoint pointTwo = pointsForGraph[j];
                ArcenPoint midPoint = ArcenPoint.Create(
                                                        (pointOne.X + pointTwo.X)/2,
                                                        (pointOne.Y + pointTwo.Y)/2);
                int radiusOfCircle = Mat.DistanceBetweenPointsImprecise( pointOne, midPoint );

                bool isThereAnotherPoint = false;

                for(int k = 0; k < pointsForGraph.Count; k++)
                  {
                    //Now check each other planet to see if they would fall into the circle
                    //centered on the midpoint between i and j
                    if((k == i) || (k == j))
                      continue; //don't compare to yourself
                    int distanceFromMidpoint;
                    ArcenPoint pointForCircleCheck = pointsForGraph[k];
                    distanceFromMidpoint = Mat.DistanceBetweenPointsImprecise(pointForCircleCheck, midPoint);
                    if((distanceFromMidpoint - radiusOfCircle) <= 0)
                      {
//                        s = System.String.Format("Inner Loop: Compare {0}-->{1}. Planet {2} overlaps circle", i, j, k);
//                        ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);
                        isThereAnotherPoint = true;
                        k = pointsForGraph.Count; //don't bother checking any other planets, since we have one in the circle
                      }

                  }
                if(!isThereAnotherPoint)
                  {
                    // s = System.String.Format("Inner Loop: Putting link between {0} --> {1}", i, j);
                    // ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);

                    //if there were no other planets, link planetOne and planetTwo
                    connectionArray[i, j] = 1;
                    connectionArray[j, i] = 1;
                  }
              }
          }
        return connectionArray;
    }
    /* This returns a matrix where matrix[i][j] == 1 means point i and point j should be connected 
       Has the same algorithm as createGabrielGraph, but a seperate implementation */
    internal static int[,]  createRNGGraphLinks(List<ArcenPoint> pointsForGraph)
    {
      //Algorithm: for each pair of nodes i and j
        //           check if any other node k is closer to both i and j than they are to eachother
        //           if no such k exists, link i and j
        int [,] connectionArray;
        connectionArray = new int[pointsForGraph.Count, pointsForGraph.Count];
        for(int i = 0; i < pointsForGraph.Count; i++)
          {
            for(int j = 0; j < pointsForGraph.Count; j++)
              {
                connectionArray[i,j] = 0;
              }
        }

        for(int i = 0; i < pointsForGraph.Count ; i++)
          {
            //the minus one is because the last planet in the last can't compare itself to itself
            // s = System.String.Format("Outer Loop: point {0} of {1}", i, pointsForGraph.Count);
            // ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);
            for(int j = 0; j < pointsForGraph.Count  ; j++)
              {
                if(i == j)
                  continue;
                // s = System.String.Format("  Middle Loop: Point {0} of {1}", j, pointsForGraph.Count);
                // ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);

                ArcenPoint pointOne = pointsForGraph[i];
                ArcenPoint pointTwo = pointsForGraph[j];
                int distanceBetweenPoints = Mat.DistanceBetweenPointsImprecise( pointOne, pointTwo );
                bool isThereAnotherPoint = false;
                for(int k = 0; k < pointsForGraph.Count; k++)
                  {
                    if((k == i) || (k == j))
                      continue;

                    ArcenPoint pointForCheck = pointsForGraph[k];
                    int distanceFromOne = Mat.DistanceBetweenPointsImprecise(pointForCheck, pointOne);
                    int distanceFromTwo = Mat.DistanceBetweenPointsImprecise(pointForCheck, pointTwo);
                    if((distanceFromOne < distanceBetweenPoints) && (distanceFromTwo < distanceBetweenPoints))
                      {
                         // s = System.String.Format("    Inner Loop: Compare {0}-->{1}. Point {2} is close enough to prevent a link", i, j, k);
                         // ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);
                        isThereAnotherPoint = true;
                        k = pointsForGraph.Count; //don't bother checking any other planets
                      }
                    }
                if(!isThereAnotherPoint)
                  {
                    // s = System.String.Format("    Inner Loop: Putting link between {0} --> {1}", i, j);
                    // ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);

                    //if there were no other planets, link planetOne and planetTwo
                    connectionArray[i, j] = 1;
                    connectionArray[j, i] = 1;

                    // ArcenDebugging.ArcenDebugLogSingleLine("    link added sucessfully", Verbosity.DoNotShow);
                  }
              }
          }
        return connectionArray;
      }
    internal static  void createMinimumSpanningTree(List<Planet> planetsForMap)
    {
        List<int>verticesNotInTree = new List<int>();
        List<int>verticesInTree = new List<int>();
        // ArcenDebugging.ArcenDebugLogSingleLine("Creating minimum spanning tree now", Verbosity.DoNotShow);
        for(int i = 0; i < planetsForMap.Count; i++)
          verticesNotInTree.Add(i);
        //Pick first element, then remove it from the list
        int planetIdx  = verticesNotInTree[0];
        verticesNotInTree.RemoveAt(0);
        verticesInTree.Add(planetIdx);

        //initialize adjacency matrix for Prim's algorithm
        //the adjacency matrix contains entries as follows
        //planetIdxNotInTree <closest planet in tree> <distance to closest planet>
        //In the body of the algorithm we look at this matrix to figure out
        //which planet to add to the tree next, then update it for the next iteration
        int[,] spanningAdjacencyMatrix;
        spanningAdjacencyMatrix = new int[planetsForMap.Count, 3];
        for(int i = 0; i < planetsForMap.Count; i++)
          {
                spanningAdjacencyMatrix[i,0] = i;
                spanningAdjacencyMatrix[i,1] = -1;
                spanningAdjacencyMatrix[i,1] = 9999;
          }
        //loop until all vertices are in the tree
        while(verticesNotInTree.Count > 0)
          {
            //update the adjacency matrix
            //for each element NOT in the tree, find the closest
            //element in the tree
            for(int i = 0; i < verticesNotInTree.Count; i++)
              {
                int minDistance = 9999;
                for(int j = 0; j < verticesInTree.Count; j++)
                  {
                    int idxNotInTree = verticesNotInTree[i];
                    int idxInTree = verticesInTree[j];
                    Planet planetNotInTree = planetsForMap[idxNotInTree];
                    Planet planetInTree = planetsForMap[idxInTree];
                    int distance = Mat.DistanceBetweenPointsImprecise(planetNotInTree.GalaxyLocation, planetInTree.GalaxyLocation);
                    if(distance < minDistance)
                      {
                        spanningAdjacencyMatrix[idxNotInTree,1] = idxInTree;
                        spanningAdjacencyMatrix[idxNotInTree,2] = distance;
                        minDistance = distance;
                      }
                  }
              }

            //now pick the closest edge
            // s = System.String.Format("Examine the remaining {0} vertices to find which to add",
            //                          verticesNotInTree.Count);
            // ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);
            int minDistanceFound = 9999;
            int closestPlanetIdx = -1;
            int planetToAdd = -1;
            for(int i = 0; i < verticesNotInTree.Count; i++)
              {
                planetIdx = verticesNotInTree[i];
                // s = System.String.Format( "To find closest edge, examine {0} of {1} (idx {4}), minDistance {2} dist for this planet {3}",
                //                           i, verticesNotInTree.Count , minDistanceFound, spanningAdjacencyMatrix[planetIdx, 2], planetIdx);
                // ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);
                if(spanningAdjacencyMatrix[planetIdx,2] == 0)
                  {
                    //don't try to link a planet to itself
                    continue;
                  }
                if(spanningAdjacencyMatrix[planetIdx, 2] < minDistanceFound)
                  {
                    minDistanceFound = spanningAdjacencyMatrix[planetIdx,2];
                    closestPlanetIdx = spanningAdjacencyMatrix[planetIdx,1];
                    planetToAdd = planetIdx;
                  }
              }
            // s = System.String.Format( "Adding planet idx {0} closest neighbor ({1}. distance {2} to tree", planetToAdd,
            //                           closestPlanetIdx, minDistanceFound);
            // ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);
            //Now let's add this planet to the Tree
            verticesNotInTree.Remove(planetToAdd);
            verticesInTree.Add(planetToAdd);
            spanningAdjacencyMatrix[planetToAdd, 2] = 9999;
            planetsForMap[closestPlanetIdx].AddLinkTo(planetsForMap[planetToAdd]);
          }
    }

    
    internal static void createGabrielGraph(List<Planet> planetsForMap)
    {
        //Algorithm: for each node
        //                          find midpoint to another node
        //                          Check that no other planets are in the circle connecting the two nodes
        //                              If no other planets, link these two planets
        //see htts://en.wikipedia.org/wiki/Gabriel_graph
        //Here i and j iterate over potential pairs. For each potential pair, iterate over k,
        //which is every other planet, to make sure k is not too close to i and j
        for(int i = 0; i < planetsForMap.Count ; i++)
          {
            // s = System.String.Format("Outer Loop: Planet {0} of {1}", i, planetsForMap.Count);
            // ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);
            for(int j = 0; j < planetsForMap.Count  ; j++)
              {
                if(j == i)
                  continue;
                Planet planetOne = planetsForMap[i];
                Planet planetTwo = planetsForMap[j];
                ArcenPoint pointOne = planetOne.GalaxyLocation;
                ArcenPoint pointTwo = planetTwo.GalaxyLocation;
                ArcenPoint midPoint = ArcenPoint.Create(
                                                        (pointOne.X + pointTwo.X)/2,
                                                        (pointOne.Y + pointTwo.Y)/2);
                int radiusOfCircle = Mat.DistanceBetweenPointsImprecise( pointOne, midPoint );

                bool isThereAnotherPlanet = false;

                for(int k = 0; k < planetsForMap.Count; k++)
                  {
                    //Now check each other planet to see if they would fall into the circle
                    //centered on the midpoint between i and j
                    if((k == i) || (k == j))
                      continue; //don't compare to yourself
                    int distanceFromMidpoint;
                    Planet planetForCircleCheck = planetsForMap[k];
                    distanceFromMidpoint = Mat.DistanceBetweenPointsImprecise(planetForCircleCheck.GalaxyLocation, midPoint);
                    if((distanceFromMidpoint - radiusOfCircle) <= 0)
                      {
//                        s = System.String.Format("Inner Loop: Compare {0}-->{1}. Planet {2} overlaps circle", i, j, k);
//                        ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);
                        isThereAnotherPlanet = true;
                        k = planetsForMap.Count; //don't bother checking any other planets, since we have one in the circle
                      }

                  }
                if(!isThereAnotherPlanet)
                  {
                    // s = System.String.Format("Inner Loop: Putting link between {0} --> {1}", i, j);
                    // ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);

                    //if there were no other planets, link planetOne and planetTwo
                    planetOne.AddLinkTo(planetTwo);
                  }
              }
          }
    }
      internal static void nearestNeighborGraph(List<Planet> planetsForMap, ArcenSimContext Context, int maxLinksPerPlanet, int radiusForExtraConnections,
                                                int percentNearestLink, int percentSecondNearestLink, int percentThirdNearestLink, bool allowOverlappingLines)
      {
          //this is intended to recapture some more of the old Simple or Realistic maps
          //from AIWC. This will be allowed to have wormhole lines that cross
          /* Algorithm:
             every planet links to its nearest neighbor with chance percentNearestLink
             percentSecondNearestLink chance it links to the second nearest
             percentThirdNearestLink chance it links to the third nearest

             Additionally, if there are any other planets within radiusForExtraConnections of it (up to maxLinksPerPlanet)
             link those too */
          bool debug = false;
          bool veryVerboseDebug = false;
          if(debug)
              ArcenDebugging.ArcenDebugLogSingleLine("stage 1 nearest neighbor", Verbosity.DoNotShow );
          for(int i = 0; i < planetsForMap.Count; i++)
          {
              //if( planet.GetIsDirectlyLinkedTo(otherPlanet) )
              Planet thisPlanet = planetsForMap[i];
              Planet closestPlanet = null;
              Planet secondClosestPlanet = null;
              Planet thirdClosestPlanet = null;
              
              for(int j = 0; j < planetsForMap.Count; j++)
              {
                  if(veryVerboseDebug)
                      ArcenDebugging.ArcenDebugLogSingleLine(i + ", " + j, Verbosity.DoNotShow );
                  if(j == i)
                      continue;
                  bool updateClosest = false;
                  bool updateSecondClosest = false;
                  bool updateThirdClosest = false;
                  Planet otherPlanet = planetsForMap[j];
                  if(thisPlanet.GetIsDirectlyLinkedTo(otherPlanet))
                     continue;
                  int distanceBetweenPlanets = Mat.DistanceBetweenPointsImprecise(thisPlanet.GalaxyLocation, otherPlanet.GalaxyLocation);
                  otherPlanet.Mapgen_WorkingDistance = distanceBetweenPlanets;
                  if (closestPlanet == null || otherPlanet.Mapgen_WorkingDistance < closestPlanet.Mapgen_WorkingDistance) 
                      updateClosest = true;
                  if (secondClosestPlanet == null || otherPlanet.Mapgen_WorkingDistance < secondClosestPlanet.Mapgen_WorkingDistance)
                      updateSecondClosest = true;
                  if (thirdClosestPlanet == null || otherPlanet.Mapgen_WorkingDistance < thirdClosestPlanet.Mapgen_WorkingDistance)
                      updateThirdClosest = true;
                  
                  if(updateClosest)
                  {
                      thirdClosestPlanet = secondClosestPlanet;
                      secondClosestPlanet = closestPlanet;
                      closestPlanet = otherPlanet;
                  }
                  else if(updateSecondClosest)
                  {
                      thirdClosestPlanet = secondClosestPlanet;
                      secondClosestPlanet = otherPlanet;
                  }
                  else if(updateThirdClosest)
                  {
                      thirdClosestPlanet = otherPlanet;
                  }
              }
              if(Context.RandomToUse.NextWithInclusiveUpperBound(0, 100) < percentNearestLink && closestPlanet != null && closestPlanet.GetLinkedNeighborCount() < maxLinksPerPlanet)
              {
                  if(allowOverlappingLines || (!allowOverlappingLines && !wouldLinkCrossOtherPlanets(thisPlanet, closestPlanet, planetsForMap)))
                  {
                      if(debug)
                          ArcenDebugging.ArcenDebugLogSingleLine("Linking " + thisPlanet.PlanetIndex + " ("+thisPlanet.Name+") to " + closestPlanet.PlanetIndex + " ("+closestPlanet.Name+") path A", Verbosity.DoNotShow );
                      thisPlanet.AddLinkTo(closestPlanet);
                  }
                      
              }
              if(Context.RandomToUse.NextWithInclusiveUpperBound(0, 100) < percentSecondNearestLink && secondClosestPlanet != null && secondClosestPlanet.GetLinkedNeighborCount() < maxLinksPerPlanet && !wouldLinkCrossOtherPlanets(thisPlanet, secondClosestPlanet, planetsForMap))
              {
                  if(allowOverlappingLines || (!allowOverlappingLines && !wouldLinkCrossOtherPlanets(thisPlanet, secondClosestPlanet, planetsForMap)))
                  {
                      if(debug)
                          ArcenDebugging.ArcenDebugLogSingleLine("Linking " + thisPlanet.PlanetIndex + " ("+thisPlanet.Name+") to " + secondClosestPlanet.PlanetIndex + " ("+secondClosestPlanet.Name+") path B", Verbosity.DoNotShow );
                      thisPlanet.AddLinkTo(secondClosestPlanet);
                  }
              }
              if(Context.RandomToUse.NextWithInclusiveUpperBound(0, 100) < percentThirdNearestLink && thirdClosestPlanet != null && thirdClosestPlanet.GetLinkedNeighborCount() < maxLinksPerPlanet && !wouldLinkCrossOtherPlanets(thisPlanet, thirdClosestPlanet, planetsForMap))
              {
                  if(allowOverlappingLines || (!allowOverlappingLines && !wouldLinkCrossOtherPlanets(thisPlanet, thirdClosestPlanet, planetsForMap)))
                  {
                      if(debug)
                          ArcenDebugging.ArcenDebugLogSingleLine("Linking " + thisPlanet.PlanetIndex + " ("+thisPlanet.Name +") to " + thirdClosestPlanet.PlanetIndex + " ("+thirdClosestPlanet.Name+") path C", Verbosity.DoNotShow );

                      thisPlanet.AddLinkTo(thirdClosestPlanet);
                  }
              }
          }
          //Now that the three closest planets may or may not be linked, potentially add some extra links
          if(debug)
              ArcenDebugging.ArcenDebugLogSingleLine("stage 2", Verbosity.DoNotShow );
          for(int i = 0; i < planetsForMap.Count; i++)
          {
              Planet thisPlanet = planetsForMap[i];

              for(int j = 0; j < planetsForMap.Count; j++)
              {
                  if (i == j)
                      continue;
                  Planet otherPlanet = planetsForMap[j];
                  if(thisPlanet.GetLinkedNeighborCount() >= maxLinksPerPlanet || otherPlanet.GetLinkedNeighborCount() >= maxLinksPerPlanet)
                  {
                      if(debug)
                          ArcenDebugging.ArcenDebugLogSingleLine("Stage 2: planet " + thisPlanet.PlanetIndex + " ("+thisPlanet.Name+") has " + thisPlanet.GetLinkedNeighborCount() + "links " + " and " + otherPlanet.PlanetIndex + " ("+otherPlanet.Name+") has "  + otherPlanet.GetLinkedNeighborCount() +" already, so no more", Verbosity.DoNotShow );
                      break;
                  }

                  if (thisPlanet.GetIsDirectlyLinkedTo(otherPlanet))
                      continue;
                  int distanceBetweenPlanets = Mat.DistanceBetweenPointsImprecise(thisPlanet.GalaxyLocation, otherPlanet.GalaxyLocation);
                  if(distanceBetweenPlanets < radiusForExtraConnections && (allowOverlappingLines || (!allowOverlappingLines && !wouldLinkCrossOtherPlanets(thisPlanet, otherPlanet, planetsForMap))))
                  {
                      if(debug)
                          ArcenDebugging.ArcenDebugLogSingleLine("stage 2: add bonus link between " + thisPlanet.PlanetIndex + " and " + otherPlanet.PlanetIndex + " at dist " + distanceBetweenPlanets + " max dist " + radiusForExtraConnections, Verbosity.DoNotShow );
                      thisPlanet.AddLinkTo(otherPlanet);
                  }
                  else
                  {
                      // if(debug)
                      //     ArcenDebugging.ArcenDebugLogSingleLine("planet " + otherPlanet + " is too far away", Verbosity.DoNotShow );
                  }
              }
          }
      }
          
    internal static void createRNGGraph(List<Planet> planetsForMap)
      {
        //Algorithm: for each pair of nodes i and j
        //           check if any other node k is closer to both i and j than they are to eachother
        //           if no such k exists, link i and j
        for(int i = 0; i < planetsForMap.Count ; i++)
          {
            //the minus one is because the last planet in the last can't compare itself to itself
            // s = System.String.Format("Outer Loop: Planet {0} of {1}", i, planetsForMap.Count);
            // ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);
            for(int j = 0; j < planetsForMap.Count  ; j++)
              {
                if(i == j)
                  continue;
                // s = System.String.Format("  Middle Loop: Planet {0} of {1}", j, planetsForMap.Count);
                // ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);

                Planet planetOne = planetsForMap[i];
                Planet planetTwo = planetsForMap[j];
                ArcenPoint pointOne = planetOne.GalaxyLocation;
                ArcenPoint pointTwo = planetTwo.GalaxyLocation;
                int distanceBetweenPoints = Mat.DistanceBetweenPointsImprecise( pointOne, pointTwo );
                bool isThereAnotherPlanet = false;
                for(int k = 0; k < planetsForMap.Count; k++)
                  {
                    if((k == i) || (k == j))
                      continue;

                    Planet planetForCheck = planetsForMap[k];
                    int distanceFromOne = Mat.DistanceBetweenPointsImprecise(planetForCheck.GalaxyLocation, pointOne);
                    int distanceFromTwo = Mat.DistanceBetweenPointsImprecise(planetForCheck.GalaxyLocation, pointTwo);
                    if((distanceFromOne < distanceBetweenPoints) && (distanceFromTwo < distanceBetweenPoints))
                      {
                         // s = System.String.Format("    Inner Loop: Compare {0}-->{1}. Planet {2} is close enough to prevent a link", i, j, k);
                         // ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);
                        isThereAnotherPlanet = true;
                        k = planetsForMap.Count; //don't bother checking any other planets
                      }
                    }
                if(!isThereAnotherPlanet)
                  {
                    // s = System.String.Format("    Inner Loop: Putting link between {0} --> {1}", i, j);
                    // ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);

                    //if there were no other planets, link planetOne and planetTwo
                    planetOne.AddLinkTo(planetTwo);
                    // ArcenDebugging.ArcenDebugLogSingleLine("    link added sucessfully", Verbosity.DoNotShow);
                  }
              }
          }
//        ArcenDebugging.ArcenDebugLogSingleLine("Finished adding links", Verbosity.DoNotShow);
      }

    //This function will return an array of integers to make it easy
    //to divvy up a set of planets into regions
    //onlyOneOfLowestMin exists because sometimes you only want 1 of the
    //smallest group; if this is "true" then it will make sure we only
    //have at most one group of minPlanetsPerGroup
    internal static  List<int> allocatePlanetsIntoGroups(int minPlanetsPerGroup, int maxPlanetsPerGroup, int planetsToAllocate, bool onlyOneOfLowestMin, ArcenSimContext Context)
    {
        int maxPossibleGroups = planetsToAllocate/minPlanetsPerGroup;
        int planetsLeftToAllocate = planetsToAllocate;
        List<int> planetsPerGroup = new List<int>();
        
        // s = System.String.Format( "allocatePlanetsIntoGroups min {0} max {1} planetsToAllocate {2} maxPossibleGroups {3}", minPlanetsPerGroup, maxPlanetsPerGroup, planetsToAllocate, maxPlanetsPerGroup);
        // ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);

        for( int i = 0; i <= maxPossibleGroups; i++)
          {
            //Hand out batches of planets in groups until
            //we run out of planets
            // s = System.String.Format( "Iter {0} of {1}: {2} planets left", i, maxPossibleGroups, planetsLeftToAllocate);
            // ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);

            if(planetsLeftToAllocate == 0)
              {
//                ArcenDebugging.ArcenDebugLogSingleLine("No planets left; break", Verbosity.DoNotShow);
                break;
              }
            if(i == maxPossibleGroups -1 || planetsLeftToAllocate < maxPlanetsPerGroup)
              {
                //handle case for the last group, or once the number of remaining
                //planets drops low enough
  //              ArcenDebugging.ArcenDebugLogSingleLine("This is the last group", Verbosity.DoNotShow);
                planetsPerGroup.Add(planetsLeftToAllocate);
              }
            else if(planetsLeftToAllocate < minPlanetsPerGroup + maxPlanetsPerGroup)
              {
                //handle the case where we are close to the end (so we don't wind up with a really awkward
                //last case
                planetsPerGroup.Add(minPlanetsPerGroup);
              }
            else
              {
                //pick a nice friendly random number of planets
                int planetsForThisGroup = Context.RandomToUse.NextWithInclusiveUpperBound( minPlanetsPerGroup, maxPlanetsPerGroup );
                planetsPerGroup.Add(planetsForThisGroup);
                if(planetsForThisGroup == minPlanetsPerGroup && onlyOneOfLowestMin)
                  minPlanetsPerGroup++;
              }
            planetsLeftToAllocate -= planetsPerGroup[i];

            // s = System.String.Format( "Iter {0}: {1} planets left", i, planetsLeftToAllocate);
            // ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);
          }
        return planetsPerGroup;
    }
    //links currentPlanets and newPlanets
    //We will eventually have a couple styles of links (link nearest planets, link
    //nearest planet in one two nearest 2 in the other, link two different but nearby planets,
    //etc, but right now just link the two closest)
    internal static void linkPlanetLists(List<Planet>currentPlanets, List<Planet>newPlanets, ArcenPoint centerOfNewPlanets, bool combinePlanets = true)
      {
            //find the planet X in currentPlanets closest to centerOfNewPlanets,
            //then find the planet in newPlanets closest to X, then link them
            int debugStage = 0;
            try
            {
                int[] distanceFromCurrentToNew = new int[currentPlanets.Count];
                debugStage = 10;
                int[] distanceFromNewToCurrent = new int[newPlanets.Count];
                debugStage = 20;
                bool debug = false;
                if ( debug )
                {
                    string s = String.Format( "Comparing {0} planets (current) with {1} planets (new)", currentPlanets.Count, newPlanets.Count );
                    ArcenDebugging.ArcenDebugLogSingleLine( s, Verbosity.DoNotShow );
                }
                debugStage = 30;
                for ( int i = 0; i < currentPlanets.Count; i++ )
                {
                    distanceFromCurrentToNew[i] = Mat.DistanceBetweenPointsImprecise( currentPlanets[i].GalaxyLocation, centerOfNewPlanets );
                }
                debugStage = 40;
                int closestCurrentIdx = findNextValueInList( distanceFromCurrentToNew, 0, currentPlanets.Count );
                debugStage = 50;
                int secondClosestCurrentIdx = findNextValueInList( distanceFromCurrentToNew, distanceFromCurrentToNew[closestCurrentIdx] + 1, currentPlanets.Count );
                debugStage = 60;
                if ( debug )
                {
                    string s = String.Format( "current Closest planet {0}, second closest {1}", closestCurrentIdx, secondClosestCurrentIdx );
                    ArcenDebugging.ArcenDebugLogSingleLine( s, Verbosity.DoNotShow );
                }
                debugStage = 70;
                Planet closestToNewPlanets = currentPlanets[closestCurrentIdx];
                debugStage = 80;
                Planet secondClosestToNewPlanets = currentPlanets[secondClosestCurrentIdx];
                //now find the closest planet in newPlanets to closestToNewPlanets

                debugStage = 90;
                for ( int i = 0; i < newPlanets.Count; i++ )
                {
                    distanceFromNewToCurrent[i] = Mat.DistanceBetweenPointsImprecise( closestToNewPlanets.GalaxyLocation, newPlanets[i].GalaxyLocation );
                }
                debugStage = 100;
                int closestNewIdx = findNextValueInList( distanceFromNewToCurrent, 0, newPlanets.Count );
                debugStage = 110;
                int secondClosestNewIdx = findNextValueInList( distanceFromNewToCurrent, distanceFromNewToCurrent[closestNewIdx] + 1, newPlanets.Count );
                debugStage = 120;
                if ( debug )
                {
                    string s = String.Format( "new Closest planet {0}, second closest {1}", closestNewIdx, secondClosestNewIdx );
                    ArcenDebugging.ArcenDebugLogSingleLine( s, Verbosity.DoNotShow );
                }
                debugStage = 130;
                closestToNewPlanets.AddLinkTo( newPlanets[closestNewIdx] );
            }
            catch ( Exception e )
            {
                Engine_AIW2.Instance.LogErrorDuringCurrentMapGen( "linkPlanetLists error at debugStage " + debugStage + " \n" + e );
            }
      
      //        closestToNewPlanets.AddLinkTo(newPlanets[secondClosestNewIdx]);
      //secondClosestToNewPlanets.AddLinkTo(newPlanets[secondClosestNewIdx]);
      if (combinePlanets)
      {
        for (int i = 0; i < newPlanets.Count; i++)
        {
          currentPlanets.Add(newPlanets[i]);
        }
      }
      }
        //returns the index of the smallest distance that's larger than smallestDistanceSoFar
    //ie if our distances are 4, 5, 6, 7 and smallestDistanceSoFar == 5
    //then it would return 6
    internal static int findNextValueInList(int[]distanceFromCenter, int smallestDistanceSoFar, int numRegions)
      {
        int idx = -1;
        int bestFit = 9999;
        for(int i = 0; i < numRegions; i++)
          {
            //note must be >= smallestDistanceSoFar in case two regions are equidistant
            //this is allowable because we delete the entry for each match after it is made
            if(distanceFromCenter[i] >= smallestDistanceSoFar && distanceFromCenter[i] < bestFit)
              {
                idx = i;
                bestFit = distanceFromCenter[i];
              }
          }
        return idx;
      }
  }


//Graph generators work as follows:
//Select a random set of vertices (planets)
//Then for use a chosen method to link the planets

    internal class Mapgen_Graph : Mapgen_Base
  {
      private List<ArcenPoint> vertices;

      private bool gabriel;
      private bool spanning;
      private bool rng;
      private bool nearestNeighbor;
      private readonly bool debug = false;
      private int radiusForPlanetPlacement;
      //private int numPlanetsDesired;
    public override void Generate( Galaxy galaxy, ArcenSimContext Context, MapConfiguration mapConfig, MapTypeData mapType )
    {
      bool spanningRandomConnections = true;
        this.gabriel = false;
        this.spanning = false;
        this.rng = false;
        this.nearestNeighbor = false;
        int numberToSeed = mapConfig.GetClampedNumberOfPlanetsForMapType( mapType );
      //string mapName = mapType.InternalName;
      //numberToSeed =  BadgerUtilityMethods.getSettingValueInt("NumPlanets");
      //if(numberToSeed == 0)
      //  numberToSeed = 80;
      //  this.numPlanetsDesired = numberToSeed;
        int planetLayoutVal = -1;
        int realisticLinkingMethodNum = -1;
        //int maxLinks = 4;
        if(ArcenStrings.Equals(mapType.InternalName, "Simple"))
        {
            int simpleLinkingMethodNum =  BadgerUtilityMethods.getSettingValueInt_Expensive( mapConfig, mapType, "SimpleLinkMethod" );
            if( this.debug)
                ArcenDebugging.ArcenDebugLogSingleLine("Value from simpleLinkMethod was " + simpleLinkingMethodNum, Verbosity.DoNotShow);
            simpleLinkingMethodNum++;
            if ( simpleLinkingMethodNum == 1)
            {
                if( this.debug)
                {
                    string s =  String.Format( "Using a random neighborhood graph for Simple,  {0} planets", numberToSeed );
                    ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);
                }
                this.rng = true;
            }
            
            if ( simpleLinkingMethodNum == 2)
            {
                if( this.debug)
                {
                    string s =  String.Format( "Using generating a gabriel graph for Dreamcatcher,  {0} planets", numberToSeed );
                    ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);
                }
                this.gabriel = true;
            }
            if ( simpleLinkingMethodNum == 3)
            {
                if( this.debug)
                {
                    
                    string s =  String.Format( "Using a spanning tree for Constellation,  {0} planets", numberToSeed );
                    ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);
                }
                this.spanning = true;
            }
            planetLayoutVal = BadgerUtilityMethods.getSettingValueInt_Expensive( mapConfig, mapType, "SimplePointDistribution" );
        }
        else if(ArcenStrings.Equals(mapType.InternalName, "Realistic"))
        {
            realisticLinkingMethodNum = BadgerUtilityMethods.getSettingValueInt_Expensive( mapConfig, mapType, "RealisticLinkMethod" );
            realisticLinkingMethodNum++;
            this.nearestNeighbor = true;
            planetLayoutVal = BadgerUtilityMethods.getSettingValueInt_Expensive( mapConfig, mapType, "RealisticPointDistribution" );
        }
        this.vertices = new List<ArcenPoint>();

      //Set up points. Do points only first
      //because this way if I want to use a later algorithm
      //that might delete certain entries, I don't have to try
      //to remove a planet from the Galaxy because I'm not sure
      //how to do that.
        if(this.debug)
            ArcenDebugging.ArcenDebugLogSingleLine("using planet layout " + planetLayoutVal, Verbosity.DoNotShow );
        this.setUpPoints( numberToSeed, Context, planetLayoutVal);
      //Now we have matching lists of points and planets
      List<Planet> planetsForMap = BadgerUtilityMethods.convertPointsToPlanets( this.vertices, galaxy, Context);


      if( this.gabriel)
        {
          BadgerUtilityMethods.createGabrielGraph(planetsForMap);
          //remove a few links at random
          BadgerUtilityMethods.removeSomeLinksBetweenPlanets(10, planetsForMap, Context);
        }
      if( this.rng)
        {
          BadgerUtilityMethods.createRNGGraph(planetsForMap);
          //remove a few links at random
          BadgerUtilityMethods.removeSomeLinksBetweenPlanets(2, planetsForMap, Context);
        }
      if( this.nearestNeighbor)
      {
          //this is "Original"
          if(this.debug)
              ArcenDebugging.ArcenDebugLogSingleLine("Linking nearest neighbnord with method " + realisticLinkingMethodNum, Verbosity.DoNotShow );
          int maxLinksPerPlanet = 5;
          int radiusForExtraConnections = 100;
          int percentNearestLink = 100;
          int percentSecondNearestLink = 50;
          int percentThirdNearestLink = 30;
          bool allowOverlappingLines = true;
          if(realisticLinkingMethodNum == 2)
          {
              //Cyclone
              maxLinksPerPlanet = 8;
              radiusForExtraConnections = 200;
              allowOverlappingLines = false;
          }
          if(realisticLinkingMethodNum == 3)
          {
              //Amnesia
              radiusForExtraConnections = 500;
              maxLinksPerPlanet = 5;
              percentSecondNearestLink = 10;
              percentThirdNearestLink = 10;
              allowOverlappingLines = false;
          }       
          BadgerUtilityMethods.nearestNeighborGraph(planetsForMap, Context, maxLinksPerPlanet, radiusForExtraConnections,
                                                    percentNearestLink, percentSecondNearestLink, percentThirdNearestLink, allowOverlappingLines);
          BadgerUtilityMethods.limitLinksForAllPlanets(planetsForMap, Context, 4);
          //List<Planet> connectedPlanets = null;
      }
      if( this.spanning)
        {
          //create a minimal spanning tree using Prim's algorithm https://en.wikipedia.org/wiki/Prim%27s_algorithm
          BadgerUtilityMethods.createMinimumSpanningTree(planetsForMap);
          if(spanningRandomConnections)
            {
              int numRandomConnections;
              if(numberToSeed < 40)
                numRandomConnections = 2;
              else if(numberToSeed < 50)
                numRandomConnections = 3;
              else if(numberToSeed < 60)
                numRandomConnections = 4;
              else if(numberToSeed < 80)
                numRandomConnections = 5;
              else if(numberToSeed < 100)
                numRandomConnections = 6;
              else
                numRandomConnections = 7;
              int minimumHops = 3;
              if(numberToSeed < 40)
                 minimumHops = 2;
              BadgerUtilityMethods.addRandomConnections(planetsForMap, numRandomConnections, Context, minimumHops);
            }
        }
      BadgerUtilityMethods.limitLinksForAllPlanets(planetsForMap, Context, 4);
      if(this.debug)
          ArcenDebugging.ArcenDebugLogSingleLine("Making sure planets are fully connected A", Verbosity.DoNotShow );
      BadgerUtilityMethods.makeSureGalaxyIsFullyConnected(planetsForMap);

    }

    //this function is a great place for tuning the eventual map
    //There's a lot of worthwhile experimentation to do here
    public void setUpPoints(int numberToSeed, ArcenSimContext Context, int placementType)
      {
          bool circlePlacement = false;
          bool oneBigCircle = false;
          if(placementType == 0)
          {
              //distribute the points in a rectangle
              circlePlacement = false;
              oneBigCircle = false;
          }
          else if(placementType == 1)
          {
              circlePlacement = true;
          }
          else
          {
              circlePlacement = true;
              oneBigCircle = true;
          }
        //My first pass for this just steals the code from intraClusterPlanetPoints
        if( this.debug)
          ArcenDebugging.ArcenDebugLogSingleLine("Generating poitns in setUpPoints. CirclePlacement " + circlePlacement + " one big circle " + oneBigCircle, Verbosity.DoNotShow);
        int minimumDistanceBetweenPlanets = 140;
//        bool circlePlacement = true; //we can distribute in either a circle or a rectangle
        if(circlePlacement)
        {
            if(numberToSeed < 40)
                this.radiusForPlanetPlacement = 500;
            else if(numberToSeed <= 60)
                this.radiusForPlanetPlacement = 550;
            else if(numberToSeed <= 80)
                this.radiusForPlanetPlacement = 650;
            else if(numberToSeed <= 100)
                this.radiusForPlanetPlacement = 700;
            else if(numberToSeed <= 200)
                this.radiusForPlanetPlacement = 850;
            else if(numberToSeed <= 300)
                this.radiusForPlanetPlacement = 950;
            else if(numberToSeed <= 400)
                this.radiusForPlanetPlacement = 1050;
            else
                this.radiusForPlanetPlacement = 1150;

            if( this.gabriel || this.rng)
              {
                //It looks better for these maps if things are more spread out
                  this.radiusForPlanetPlacement += 100;
                  this.radiusForPlanetPlacement += numberToSeed/90 * 20;
              }
            //Here is my first pass (oneBigCircle) and a second attempt
            //where I spread things out a bit more
            if(oneBigCircle)
            {
                if( this.debug)
                    ArcenDebugging.ArcenDebugLogSingleLine("generating points in a big circle", Verbosity.DoNotShow);

                  this.radiusForPlanetPlacement += 2000;
                  ArcenPoint Center =  Engine_AIW2.Instance.GalaxyMapOnly_GalaxyCenter;
                  BadgerUtilityMethods.addPointsInCircle(numberToSeed, Context, Center, this.radiusForPlanetPlacement,
                                                         minimumDistanceBetweenPlanets, ref this.vertices);
              }
            else
              {
                if( this.debug)
                  ArcenDebugging.ArcenDebugLogSingleLine("points generated from multiple circles", Verbosity.DoNotShow);
                int xStart = 900;
                int yStart = 750;
                xStart += (numberToSeed /90) * 200;
                yStart += (numberToSeed /90) * 180;
                List<ArcenPoint> centersForCircles = new List<ArcenPoint>();
                centersForCircles.Add(ArcenPoint.Create(xStart, yStart));
                centersForCircles.Add(ArcenPoint.Create(xStart, -yStart));
                centersForCircles.Add(ArcenPoint.Create(0,0));
                centersForCircles.Add(ArcenPoint.Create(-xStart, yStart));
                centersForCircles.Add(ArcenPoint.Create(-xStart, -yStart));

                centersForCircles.Add(ArcenPoint.Create(xStart, 0));
                centersForCircles.Add(ArcenPoint.Create(-xStart, 0));
                centersForCircles.Add(ArcenPoint.Create(0, yStart));
                centersForCircles.Add(ArcenPoint.Create(0, -yStart));
                
                
                //int seedsPerCircle = numberToSeed /centersForCircles.Count;
                //int extraPoints = numberToSeed % centersForCircles.Count;
                for(int i = 0; i < centersForCircles.Count; i++)
                {
                    int seedsForThisCircle = numberToSeed/centersForCircles.Count;
                    if(i == 0)
                        seedsForThisCircle += numberToSeed % centersForCircles.Count;
                    if(this.debug)
                        ArcenDebugging.ArcenDebugLogSingleLine("Seeding " + seedsForThisCircle + " for circle " + i + " centered on " + centersForCircles[i].X + ", " + centersForCircles[i].Y, Verbosity.DoNotShow );
                    BadgerUtilityMethods.addPointsInCircle(seedsForThisCircle, Context, centersForCircles[i], this.radiusForPlanetPlacement,
                                                           minimumDistanceBetweenPlanets, ref this.vertices);
                }
              }
            }
        else
          {
              bool allowClustersInPoints = true;
              if(debug)
                  ArcenDebugging.ArcenDebugLogSingleLine("Adding points in start screen", Verbosity.DoNotShow );
              BadgerUtilityMethods.addPointsInStartScreen(numberToSeed, Context, minimumDistanceBetweenPlanets, ref this.vertices,
                                                        allowClustersInPoints );
              if(this.vertices.Count == 0)
              {
                  ArcenDebugging.ArcenDebugLogSingleLine("BUG: could not generate enough points with rectancle and clusgers", Verbosity.DoNotShow );
                                
                  allowClustersInPoints = false;
                  BadgerUtilityMethods.addPointsInStartScreen(numberToSeed, Context, minimumDistanceBetweenPlanets, ref this.vertices,
                                                        allowClustersInPoints );

              }
          }
      }
  }


  public class Mapgen_Circles : Mapgen_Base
  {

    public override void Generate( Galaxy galaxy, ArcenSimContext Context, MapConfiguration mapConfig, MapTypeData mapType )
    {
      bool linkNormally = true;
      bool linkRNG = false;
      bool linkSpanning = false;
      bool linkGabriel = false;
      int numberToSeed = mapConfig.GetClampedNumberOfPlanetsForMapType( mapType );
      //this map type is vaguely like solar systems, but it's intended to be a different
      //sort of style. The layout is
      //One central circle, surrounded by a bunch of smaller circles. Every point in the center connects to its
      //outer circle. So in a Solar System POV, the central circle are the Suns, the outer circle are its planets orbiting
      //but we have this layout (instead of the suns at the center of the orbiting planets) because it's much more readable
      //numberToSeed =  BadgerUtilityMethods.getSettingValueInt("NumPlanets");
      //if(numberToSeed == 0)
      //  numberToSeed = 80;
      //string mapName = mapType.InternalName;
      int linkingMethodNum =  BadgerUtilityMethods.getSettingValueInt_Expensive( mapConfig, mapType, "SolarSystemsLinkMethod" );
      if(linkingMethodNum == 0)
        linkingMethodNum = 1;
      if ( linkingMethodNum == 1) //the default
        linkNormally = true;
      if ( linkingMethodNum == 2)
        {
          linkNormally = false;
          linkRNG = true;
        }
      if ( linkingMethodNum == 3)
        {
          linkNormally = false;
          linkGabriel = true;
        }

      if ( linkingMethodNum == 4)
        {
          linkNormally = false;
          linkSpanning = true;
        }

      //int planetsLeftToAllocate = numberToSeed;

      int minPlanetsPerCircle = 4; //it's kinda nice if there's a single circle of 4 planets,
                                   //but more than one such is boring. Once we have
                                   // one such circle, we bump this value up
      int maxPlanetsPerCircle = 9;
      //figure out how many circles there are, and how many planets are in each circle
      List<int> planetsPerCircle = BadgerUtilityMethods.allocatePlanetsIntoGroups(minPlanetsPerCircle,
                                                                               maxPlanetsPerCircle, numberToSeed, true,
                                                                               Context);

      int numberOfCircles = planetsPerCircle.Count;   
      //Now create each circle

      int outerCircleRadius = this.getRadiusOfOuterCircles(numberOfCircles);
      int innerCircleRadius = this.getRadiusOfSmallCircle(numberOfCircles);
      List<ArcenPoint> innerCirclePlanetPoints;
      //note that this function returns the locations of the inner circle planets
      //as an out parameter (otherwise it was hard to get the center of the outer circle to be on the same
      //line as the Sun)
      List<ArcenPoint> centerOfOuterCircles = this.getCenterOfOuterCircles(galaxy, Context,
                                                                      numberOfCircles, outerCircleRadius,
                                                                      Engine_AIW2.Instance.GalaxyMapOnly_GalaxyCenter, out innerCirclePlanetPoints,
                                                                      innerCircleRadius);

      //create the inner circle (aka Suns)
      List<Planet> innerCirclePlanets = this.makeCircle(galaxy, Context, innerCirclePlanetPoints);
      if(linkNormally)
        BadgerUtilityMethods.createRNGGraph(innerCirclePlanets);
      for(int i = 0; i < centerOfOuterCircles.Count; i++)
        {
          //create all the outer planets for this circle
          List<Planet> planetsForThisCircle = this.makeCircle(galaxy, Context,
                                                                   planetsPerCircle[i], this.getRadiusOfSmallCircle(planetsPerCircle[i]),  centerOfOuterCircles[i]);
          if(linkNormally)
            {
              //link the planets of the solar system (aka outer circle)
              BadgerUtilityMethods.createRNGGraph(planetsForThisCircle);
              //link the inner planet (Sun) to the nearest member of its orbiting planet
                this.linkPlanetToNearestCircle(galaxy, innerCirclePlanets[i], planetsForThisCircle);
            }
        }
      if(linkSpanning)
        {
          BadgerUtilityMethods.createMinimumSpanningTree(galaxy.Planets);
          BadgerUtilityMethods.addRandomConnections(galaxy.Planets, 5, Context, 5);
        }
      if(linkGabriel)
        {
          BadgerUtilityMethods.createGabrielGraph(galaxy.Planets);
        }
      if(linkRNG)
        {
          BadgerUtilityMethods.createRNGGraph(galaxy.Planets);
        }

      return;
    }
    //Note that the center of the outer circle and its matching Sun
    //need to be on the same line, so we return the points on the inner circle as an out parameter
    private List<ArcenPoint> getCenterOfOuterCircles(Galaxy galaxy, ArcenSimContext Context, int outerCircles, int outerRadius, ArcenPoint circleCenter,
                                                     out List<ArcenPoint> innerCirclePoints, int innerRadius)
      {
        innerCirclePoints = new List<ArcenPoint>();
        //shamelessly stolen ;-)
        AngleDegrees angleBetweenRingPlanet = AngleDegrees.Create( (float)360 / (float)outerCircles );
        AngleDegrees ringAngle = AngleDegrees.Create( (float)Context.RandomToUse.NextWithInclusiveUpperBound( 10, 350 ) );

        List<ArcenPoint> outerCircleCenters = new List<ArcenPoint>();
        bool flipOffsetForNextRingPlanet = false;
        int offsetOuterFlip = 10;
        //We need to stagger the outer planet radii once there are enough of them
        if(outerCircles > 7)
          offsetOuterFlip = 100;
        if(outerCircles > 12)
          offsetOuterFlip = 200;

        for(int i = 0; i < outerCircles; i++)
          {
            ArcenPoint innerPoint = circleCenter.GetPointAtAngleAndDistance( ringAngle, innerRadius +  (flipOffsetForNextRingPlanet ? 15 : 30 ));
            ArcenPoint outerPoint = circleCenter.GetPointAtAngleAndDistance( ringAngle, outerRadius +  (flipOffsetForNextRingPlanet ? offsetOuterFlip : 0 ));
            outerCircleCenters.Add( outerPoint);
            innerCirclePoints.Add(innerPoint);
            flipOffsetForNextRingPlanet = !flipOffsetForNextRingPlanet;
            ringAngle = ringAngle.Add( angleBetweenRingPlanet );
          }
        return outerCircleCenters;
      }
    //maps the Sun to its corresponding planets
    private void linkPlanetToNearestCircle(Galaxy galaxy, Planet innerCirclePlanet, List<Planet> outerCircle)
    {
      //takes a planet in the inner circle and an outer circle. Link the inner planet and the closest outer planet
      int minDistanceSoFar=9999;
      int indexOfMinDistance = -1;
      for(int i = 0; i < outerCircle.Count; i++)
        {
          Planet outerPlanet = outerCircle[i];
          int distance = Mat.DistanceBetweenPointsImprecise(innerCirclePlanet.GalaxyLocation,
                                                   outerPlanet.GalaxyLocation);
          if(distance < minDistanceSoFar)
            {
              minDistanceSoFar = distance;
              indexOfMinDistance = i;
            }
        }
      innerCirclePlanet.AddLinkTo(outerCircle[indexOfMinDistance]);
    }

    //This function is overloaded; one version takes a circleCenter, finds all the planets and then
    //creates/links them
    //the other version starts knowing all the points, then only has to create the planets and link them
    private List<Planet> makeCircle(Galaxy galaxy, ArcenSimContext Context, int planetsOnCircle, int radius, ArcenPoint circleCenter)
    {
      //Generate a connected circle of planets around the circleCenter with a given radius
      PlanetType planetType = PlanetType.Normal;
      //7) Compute average angle for next step from 360/planets_left
      AngleDegrees angleBetweenRingPlanet = AngleDegrees.Create( (float)360 / (float)planetsOnCircle );

      //8) Pick Random Starting Angle from 0 to 359
      AngleDegrees ringAngle = AngleDegrees.Create( (float)Context.RandomToUse.NextWithInclusiveUpperBound( 10, 350 ) );

      List<Planet> ringPlanets = new List<Planet>();
      ArcenPoint linePoint;
      Planet newPlanetInRing;
      bool flipOffsetForNextRingPlanet = false;
      bool debug = false;
      if(debug)
        {
         string s = String.Format( "Creating Circle of {0}  planets centered on {1},{2}",//centered on ({1},{2}) at radius {3}",
                                    planetsOnCircle,  circleCenter.X, circleCenter.Y);
         ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);
        }

      for(int i = 0; i < planetsOnCircle; i++)
        {
          //-- compute point on line from origin at angle at target radius +40
          linePoint = circleCenter.GetPointAtAngleAndDistance( ringAngle, radius +  (flipOffsetForNextRingPlanet ? 15 : 30 ));

          //-- place planet there
          newPlanetInRing = galaxy.AddPlanet( planetType, linePoint, Context );

          ringPlanets.Add( newPlanetInRing );


          flipOffsetForNextRingPlanet = !flipOffsetForNextRingPlanet;
          ringAngle = ringAngle.Add( angleBetweenRingPlanet );
        }
      return ringPlanets;
    }
    //overloaded version of makeAndConnectCircle for when we already know all the points
    private List<Planet> makeCircle(Galaxy galaxy, ArcenSimContext Context, List<ArcenPoint> planetPoints)
    {
      //Generate a connected circle of planets around the circleCenter with a given radius
      PlanetType planetType = PlanetType.Normal;
      List<Planet> ringPlanets = new List<Planet>();

      for(int i = 0; i < planetPoints.Count; i++)
        {
          //-- place planet there
          Planet newPlanetInRing = galaxy.AddPlanet( planetType, planetPoints[i], Context );
          ringPlanets.Add(newPlanetInRing);
        }
      return ringPlanets;
    }

    private int getRadiusOfSmallCircle(int smallCircle)
      {
        int radius;
        if(smallCircle < 4)
          radius = 45;
        else if(smallCircle < 5)
          radius = 55;
        else if(smallCircle < 6)
          radius = 65;
        else if(smallCircle < 7)
          radius = 75;
        else
          radius = 100;
        return radius;

      }
    private int getRadiusOfOuterCircles(int numberOfSmallCircles)
    {
      int radius;
      //stolen from Wheel
      if(numberOfSmallCircles < 3)
        {
          radius = 300;
        }
      else if(numberOfSmallCircles < 4)
        radius = 310;
      else if(numberOfSmallCircles < 5)
        radius = 320;
      else if(numberOfSmallCircles < 6)
        radius = 370;
      else if(numberOfSmallCircles < 7)
        radius = 390;
      else if(numberOfSmallCircles < 8)
        radius = 400;
      else if(numberOfSmallCircles < 8)
        radius = 410;
      else if(numberOfSmallCircles < 9)
        radius = 430;
      else if(numberOfSmallCircles < 10)
        radius = 440;
      else if(numberOfSmallCircles < 11)
        radius = 460;
      else
        radius = 490;

      return radius;
    }
  }

    public class Mapgen_Tutorial : Mapgen_Base
    {
    /*This class is intended as a teaching exercise. To create a new map generator,
      you must declase a class that implements IMapGenerator. It has a "Generate" function that is
      called by the main AI War 2 code that actually creates the map. The galaxy map is laid out on a giant grid.
      The center of the galaxy is (0,0) and you can have both positive and negative coordinates.

      The input to the Generate function are as follows. The "Galaxy" object is what you populate with Planets
      to create the map for your game. The Context is used to generate random numbers (and I'm sure many other things).
      The numberToSeed is the number of planets, and the mapType is something you (the coder)
      can use if you want to have multiple map types sharing a similar codebase.
      You can look at the RootLatticeGenerator for an example of one IMapGenerator sharing
      multiple mapTypes.

    This example code generates a bunch of random planets simply connected

    One critical thing to make sure that all your planets are connected. If they are not all connected then you will get obscure bugs. 
     See Mantis bug 19086

    To have this entry appear as a selection option in the Game Start Screen, add an entry like 
     <map_type name="Tutorial" 
              display_name="ExampleForAspiringModders" <=== this will be the name that appears in Game Select
              description="~*~" <==== This doesn't do anything yet
              dll_name="AIWarExternalCode" <== must be External Code
              type_name="Arcen.AIW2.External.Mapgen_Tutorial" <=== the name of this class
  >
  </map_type>

to GameData/Configuration/MapType/YourFile_MapTypes.xml

*/
        public override void Generate( Galaxy galaxy, ArcenSimContext Context, MapConfiguration mapConfig, MapTypeData mapType )
        {
          string s; //this is used for debugging printouts later in this function
          ArcenDebugging.ArcenDebugLogSingleLine("Welcome to the test generator\n" , Verbosity.DoNotShow); //this message will go in PlayerData/ArcenDebugLog.txt
                                                                                                           //this is invaluable for debugging purposes

          //An ArcenPoint is a data structure containing (at least) an X,Y coordinate pair
          //creating a new planet requires an ArcenPoint
          //This test generator will hard code in some ArcenPoints,
          //then put planets at those points

          //The map itself is a cartesian coordinate plane centered on 0,0
          
          PlanetType planetType = PlanetType.Normal; //I think Normal is to say "not a Nomad".
                                                     //unless you know otherwise, always use PlanetType.Normal
          List<ArcenPoint> planetPoints = new List<ArcenPoint>();
          ArcenPoint originPlanetPoint = Engine_AIW2.Instance.GalaxyMapOnly_GalaxyCenter; //this is (0,0) in tha aforementioned coordinate plane
          Planet originPlanet = galaxy.AddPlanet(planetType, originPlanetPoint, Context);

          //First we create a list of points, then we will create Planets at those points
          ArcenDebugging.ArcenDebugLogSingleLine("populate PlanetPoints list\n" , Verbosity.DoNotShow);
           planetPoints.Add( ArcenPoint.Create( 0, 100)); //so this point has X=0 and Y=100
           planetPoints.Add( ArcenPoint.Create( 500, 0)); // X=500, Y=0
           planetPoints.Add( ArcenPoint.Create( 600, 100)); //etc
           planetPoints.Add( ArcenPoint.Create( -100, -100));
           planetPoints.Add( ArcenPoint.Create( 0, -600));
           planetPoints.Add( ArcenPoint.Create( -100, 0));

           int numberToSeed = planetPoints.Count;//reset numberToSeed for this example
          //int distance = Mat.DistanceBetweenPointsImprecise(planetPoints[0], planetPoints[1]); //This is how to check the distance between Points
          ArcenDebugging.ArcenDebugLogSingleLine("I have created my points, now let's make the planets\n" , Verbosity.DoNotShow);
          Planet previousPlanet = null;
          for(int i = 0; i < numberToSeed -1; i++)
            {
              //this uses a printf-style formatting string to generate a more elaborate debugging message
              s = String.Format("Adding planet {0} at location {1},{2}\n", i,
                                       planetPoints[i].X, planetPoints[i].Y);
              ArcenDebugging.ArcenDebugLogSingleLine(s , Verbosity.DoNotShow);
              //calling galaxy.AddPlanet adds a planet to the galaxy; it takes a planetType (probably "Normal"),
              //an ArcenPoint and the Context passed into the Generate functino
              Planet planet = galaxy.AddPlanet(planetType, planetPoints[i], Context);
              if(previousPlanet == null)
                planet.AddLinkTo( originPlanet); //if we have no previous planet, link this planet to the origin planet
              else
                planet.AddLinkTo(previousPlanet);
              previousPlanet = planet;

            }
          //int numLinkedToOrigin = originPlanet.GetLinkedNeighborCount(); //count how many planets are connected to originPlanet
          //bool isLinkedToOrigin = originPlanet.GetIsDirectlyLinkedTo(galaxy.Planets[2]); //checks if this is linked to origin planet
          s = String.Format("My galaxy has {0} planets. Return now\n", galaxy.Planets.Count);
          ArcenDebugging.ArcenDebugLogSingleLine(s , Verbosity.DoNotShow);
          return;
        }
    }
  
  public class Mapgen_Nebula : Mapgen_Base
  {
    /* The goal of this map type is to have a varierty of "regions" of planets,
       with a different layout of planets and a randomly chosen linking algorithm for each
       region. This gives a really organic feel to things.

       TODO: add some additional "seeding" algorithms to the initial planet placements (for example, maybe a circle?
       maybe a small grid?)
       Also add some "Link regions differently" code, and maybe consider linking adjacent regions (so it's not just
       always linked in a spanning tree, but maybe in a gabriel or something)
       Also add Spanning + random connections to the way of linking inside a region

       This galaxy type also implements ClustersMini, wherein the regions are tightly packed
    */

    bool debug = false;
    bool veryVerboseDebug = false;
    //bool checkSettings = false; //the values will be fed in from MapGeneration.cs' Mapgen_ClustersRoot for false
                                //otherwise we will check the settings directly

    public bool isAsteroid = false;
    public int numClustersHint = 2;
    public int nebulaConnectivity = 2; //tunes the connectivity algorithms for Nebula
    public bool addSomeExtraLinks = false; //for Asteroid,
                                           //which is normally linked via spanning tree

    public override List<string> LobbyGetSettingNamesForMapIn( MapConfiguration MapConfig, MapTypeData mapType )
    {
        string mapName = mapType.InternalName;
            
        List<string> names = new List<string>();
        switch ( mapName )
        {
            case "Nebula":
                //names.Add("NumPlanets");
                //names.Add("NumGolems");
                names.Add( "NumberOfNebulae" );
                names.Add( "NebulaeConnectivity" );
                // names.Add("MinPlanetsPerNebulaRegion");
                // names.Add("MaxPlanetsPerNebulaRegion"); //more add others as necessary
                // names.Add("radiusPerRegionNebula");
                // names.Add("distanceBetweenNebulaRegion");
                break;
            default:
                ArcenDebugging.ArcenDebugLog( "No sub-options defined for map type '" + mapName + "'.  If this is by design, then just have an empty case entry for it.", Verbosity.ShowAsError );
                break;
        }

        return names;
    }

    public override void Generate( Galaxy galaxy, ArcenSimContext Context, MapConfiguration mapConfig, MapTypeData mapType )
    {

      //numberToSeed =  BadgerUtilityMethods.getSettingValueInt("NumPlanets");
      //if(numberToSeed == 0)
      //  numberToSeed = 80;
        int numberToSeed = mapConfig.GetClampedNumberOfPlanetsForMapType( mapType );
        if(numberToSeed < 20)
            numberToSeed = 20;

      int percentForOneCircle = 20;
      int circleDone = -1;

      //string mapName = mapType.InternalName;
      // if( this.checkSettings)
      //   {
      //     if ( ArcenStrings.Equals( mapName, "Asteroid") )
      //         this.isAsteroid = true;
      //     else
      //         this.isAsteroid = false;
      //   }

      //These parameters are tuned based on the numClustersHint
      int minPlanetsPerRegion = 6;
      int maxPlanetsPerRegion = 17;
      int radiusPerRegion = 130;
      int distanceBetweenRegions = 360;
      int minDistanceBetweenPlanets = 60;

      //get the user requested settings
      // if( this.checkSettings)
      //     this.nebulaSettingUpdates(out this.numClustersHint, out this.nebulaConnectivity, this.isAsteroid);
      if( this.isAsteroid)
        {
          if( this.numClustersHint == 1)
            {
              //Few clusters, so each one is larger
              minPlanetsPerRegion = 7;
              maxPlanetsPerRegion = 12;
              if(numberToSeed > 120)
              {
                  minPlanetsPerRegion += 2;
                  maxPlanetsPerRegion += 2;
              }
              radiusPerRegion = 140;
              distanceBetweenRegions = 380;
            }
          if( this.numClustersHint == 2)
            {
              minPlanetsPerRegion = 5;
              maxPlanetsPerRegion = 10;
              if(numberToSeed > 120)
              {
                  minPlanetsPerRegion += 1;
                  maxPlanetsPerRegion += 1;
              }

              radiusPerRegion = 120;
              distanceBetweenRegions = 260;
            }
          if( this.numClustersHint == 3)
            {
              minPlanetsPerRegion = 4;
              maxPlanetsPerRegion = 7;
              radiusPerRegion = 110;
              distanceBetweenRegions = 240;
            }
        }
      else
        {
          /* Nebula map mode */
          if( this.numClustersHint == 1)
            {
              //Few clusters, so each one is larger
              minPlanetsPerRegion = 11;
              maxPlanetsPerRegion = 21;
              radiusPerRegion = 220;
              if(numberToSeed > 120)
              {
                  minPlanetsPerRegion += numberToSeed/80;
                  maxPlanetsPerRegion += numberToSeed/80;
                  radiusPerRegion += numberToSeed/200;
              }
              distanceBetweenRegions = 340;
            }
          if( this.numClustersHint == 2)
            {
              minPlanetsPerRegion = 6;
              maxPlanetsPerRegion = 18;
              radiusPerRegion = 210;
              if(numberToSeed > 120)
              {
                  minPlanetsPerRegion += numberToSeed/80;
                  maxPlanetsPerRegion += numberToSeed/80;
                  radiusPerRegion += numberToSeed/100;
              }
              distanceBetweenRegions = 180;
            }
          if( this.numClustersHint == 3)
            {
              minPlanetsPerRegion = 5;
              maxPlanetsPerRegion = 13;
              radiusPerRegion = 190;
              distanceBetweenRegions = 170;
            }
          if( this.numClustersHint == 4)
            {
              minPlanetsPerRegion = 16;
              maxPlanetsPerRegion = 21;
              radiusPerRegion = 220;
              distanceBetweenRegions = 170;
              if(numberToSeed > 160)
              {
                  minPlanetsPerRegion += numberToSeed/50;
                  maxPlanetsPerRegion += numberToSeed/50;
                  radiusPerRegion += numberToSeed/70;
              }
            }


        }
      // if( this.isAsteroid && this.checkSettings)
      //     this.addSomeExtraLinks = BadgerUtilityMethods.getSettingValueBool("addBonusLinksAsteroid");

      if( this.debug)
        {
          string s = String.Format("minPlanetsPerRegion: " + minPlanetsPerRegion + " maxPlanetsPerRegion " + maxPlanetsPerRegion + " radiusPerRegion " + radiusPerRegion + " distanceBetweenRegions " + distanceBetweenRegions + " isAsteroid " + isAsteroid + " connectivity " + this.nebulaConnectivity + " numClustersHint " + this.numClustersHint);
          ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);
        }
      
      bool onlyOneOfSmallestRegion = false;

      int alignmentNumber = 10; //align all points on numbers divisible by this value. It makes things look more organized
      List<int> regionsOfPlanets = BadgerUtilityMethods.allocatePlanetsIntoGroups(minPlanetsPerRegion,
                                                                                  maxPlanetsPerRegion, numberToSeed, onlyOneOfSmallestRegion,
                                                                                  Context);
      if( this.debug)
        {
          string s = String.Format("Planets divvied between {0} regions --> ", regionsOfPlanets.Count);
          for(int i = 0; i < regionsOfPlanets.Count; i++)
            {
              s += "(" +i +"="+ regionsOfPlanets[i] + ") ";
            }
          ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);
        }

      //now for each region, find a center point (chosen randomly)
      //then allocate the points
      List<ArcenPoint> regionCenters = new List<ArcenPoint>();
      bool allowClustersInPoints = false;

      BadgerUtilityMethods.addPointsInStartScreen(regionsOfPlanets.Count, Context,
                                                  distanceBetweenRegions, ref regionCenters, allowClustersInPoints,
                                                  alignmentNumber);
      if( this.veryVerboseDebug)
        {
          for(int i = 0; i < regionCenters.Count; i++)
            {
              string s = String.Format("Region Center: {0}, {1}", regionCenters[i].X, regionCenters[i].Y);
              ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);
            }
        }
      List<ArcenPoint> allPoints = new List<ArcenPoint>();
      List<List<Planet>> allPlanetsPerRegion = new List<List<Planet>>();
      List<Planet> allPlanets = new List<Planet>();

      /* Tuning parameters for how to link the various Nebulae/Asteroids */
      
      //percentages for linking within a region
      
      //settings for the Nebula
      int percentSpanningTreeInRegion;
      int percentSpanningTreeWithConnectionsInRegion;
      int percentGabrielInRegion;
      int percentRNGInRegion;
      //percentages for linking the different regions (inter-region)
      LinkMethod regionLinkMethod = LinkMethod.Gabriel;
      this.getNebulaLinkingPercentages( Context, this.isAsteroid, this.nebulaConnectivity, this.addSomeExtraLinks,
                                        out  percentSpanningTreeInRegion, out percentSpanningTreeWithConnectionsInRegion,
                                        out  percentGabrielInRegion, out  percentRNGInRegion,
                                        out  regionLinkMethod);

      

      for(int i = 0; i < regionCenters.Count; i++)
        {
          //For each region, add planets and then link the region together
          List<ArcenPoint> pointsForThisRegion;
          if( this.isAsteroid && circleDone == -1 &&
             regionsOfPlanets[i] > 4 && regionsOfPlanets[i] < 9 &&
             percentForOneCircle > Context.RandomToUse.Next(0,100)) // chance of a circle for Asteroids
            {
              if( this.debug)
                ArcenDebugging.ArcenDebugLogSingleLine("Adding a circle", Verbosity.DoNotShow);
              //sometimes we might want to just make a circle
              circleDone = i;
              List<ArcenPoint> temp = new List<ArcenPoint>();
              pointsForThisRegion = BadgerUtilityMethods.addCircularPoints(regionsOfPlanets[i], Context, regionCenters[i],
                                                      radiusPerRegion, ref temp);
            }
          else
            pointsForThisRegion = BadgerUtilityMethods.addPointsInCircleWithExclusion(regionsOfPlanets[i], Context, regionCenters[i], radiusPerRegion,
                                                                                      minDistanceBetweenPlanets, ref allPoints, regionCenters, radiusPerRegion + 20, alignmentNumber);

          List<Planet> planetsForThisRegion = BadgerUtilityMethods.convertPointsToPlanets(pointsForThisRegion, galaxy, Context);
          if( this.veryVerboseDebug)
            {
              string s = String.Format("Added planets for region {0} of {1}", i, regionCenters.Count);
              ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);
            }
          //Now pick a random method of linking these planets together

          LinkMethod method = BadgerUtilityMethods.getRandomLinkMethod(percentSpanningTreeInRegion, percentGabrielInRegion,
                                                                       percentRNGInRegion, percentSpanningTreeWithConnectionsInRegion,
                                                                       Context);
          if( this.veryVerboseDebug)
            {
                ArcenDebugging.ArcenDebugLogSingleLine("Using link method " + method, Verbosity.DoNotShow);
            }

          bool removeSomeLinks = false;
          if(method == LinkMethod.Gabriel)
            {
              BadgerUtilityMethods.createGabrielGraph(planetsForThisRegion);
              if(removeSomeLinks)
                {
                  int maxToRemove = 2;
                  if(regionsOfPlanets[i] < 8)
                    maxToRemove = 1;
                  if(circleDone == i)
                    maxToRemove = 0;
                  BadgerUtilityMethods.removeSomeLinksBetweenPlanets(maxToRemove, planetsForThisRegion, Context);
                }
            }
          else if(method == LinkMethod.RNG)
            {
              //RNG
              BadgerUtilityMethods.createRNGGraph(planetsForThisRegion);
              if(removeSomeLinks)
                {
                  int maxToRemove = 1;
                  if(regionsOfPlanets[i] < 8)
                    maxToRemove = 0;
                  if(circleDone == i)
                    maxToRemove = 0;
                  BadgerUtilityMethods.removeSomeLinksBetweenPlanets(maxToRemove, planetsForThisRegion, Context);
                }


            }
          else if(method == LinkMethod.SpanningTree)
            {
              //SpanningTree
              BadgerUtilityMethods.createMinimumSpanningTree(planetsForThisRegion);
            }
          else
            {
              //SpanningTree + random connections
                if( this.veryVerboseDebug)
                    ArcenDebugging.ArcenDebugLogSingleLine("creating minimum spanning tree", Verbosity.DoNotShow);

              BadgerUtilityMethods.createMinimumSpanningTree(planetsForThisRegion);
              if( this.veryVerboseDebug)
                  ArcenDebugging.ArcenDebugLogSingleLine("adding some random connections", Verbosity.DoNotShow);

              BadgerUtilityMethods.addRandomConnections(planetsForThisRegion, 1, Context, 2);
            }
          allPlanetsPerRegion.Add(planetsForThisRegion);
          allPlanets.AddRange(planetsForThisRegion);
          if( this.veryVerboseDebug)
            {
              string s = String.Format("Planets for region {0} of {1} are now linked", i, regionCenters.Count);
              ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);
            }
        }


      if(regionLinkMethod == LinkMethod.SpanningTree)
        {
          int[,] connectionMatrix = BadgerUtilityMethods.createMinimumSpanningTreeLinks(regionCenters);
          for(int i = 0; i < regionCenters.Count; i++)
            {
              for(int j = i + 1; j < regionCenters.Count; j++)
                {
                  if(j >= regionCenters.Count)
                    ArcenDebugging.ArcenDebugLogSingleLine("BUG! FIXME", Verbosity.DoNotShow);
                  if(connectionMatrix[i,j] == 1)
                    {
                      BadgerUtilityMethods.linkPlanetLists(allPlanetsPerRegion[i], allPlanetsPerRegion[j], regionCenters[j]);
                    }
                }
            }
        }
      else if(regionLinkMethod == LinkMethod.Gabriel)
        {
          int[,] connectionMatrix = BadgerUtilityMethods.createGabrielGraphLinks(regionCenters);
          for(int i = 0; i < regionCenters.Count; i++)
            {
              for(int j = i + 1; j < regionCenters.Count; j++)
                {
                  if(j >= regionCenters.Count)
                    ArcenDebugging.ArcenDebugLogSingleLine("BUG! FIXME", Verbosity.DoNotShow);
                  if(connectionMatrix[i,j] == 1)
                    {
                      BadgerUtilityMethods.linkPlanetLists(allPlanetsPerRegion[i], allPlanetsPerRegion[j], regionCenters[j]);
                    }
                }
            }
        }
      else if(regionLinkMethod == LinkMethod.RNG)
        {
          int[,] connectionMatrix = BadgerUtilityMethods.createRNGGraphLinks(regionCenters);
          for(int i = 0; i < regionCenters.Count; i++)
            {
              for(int j = i + 1; j < regionCenters.Count; j++)
                {
                  if(j >= regionCenters.Count)
                    ArcenDebugging.ArcenDebugLogSingleLine("BUG! FIXME", Verbosity.DoNotShow);
                  if(connectionMatrix[i,j] == 1)
                    {
                      BadgerUtilityMethods.linkPlanetLists(allPlanetsPerRegion[i], allPlanetsPerRegion[j], regionCenters[j]);
                    }
                }
            }
        }
      else if(regionLinkMethod == LinkMethod.SpanningTreeWithConnections)
        {
          int[,] connectionMatrix = BadgerUtilityMethods.createMinimumSpanningTreeLinks(regionCenters);
          for(int i = 0; i < regionCenters.Count; i++)
            {
              for(int j = i + 1; j < regionCenters.Count; j++)
                {
                  if(j >= regionCenters.Count)
                    ArcenDebugging.ArcenDebugLogSingleLine("BUG! FIXME", Verbosity.DoNotShow);
                  if(connectionMatrix[i,j] == 1)
                    {
                      BadgerUtilityMethods.linkPlanetLists(allPlanetsPerRegion[i], allPlanetsPerRegion[j], regionCenters[j]);
                    }
                }
            }
          //now let's link everything together at the end a bit better
          int minHops = numberToSeed/10;
          if(minHops > 6)
            minHops = 6;
          if( this.debug)
            {
              string s = String.Format("Adding a few random connections at the end");
              ArcenDebugging.ArcenDebugLogSingleLine(s, Verbosity.DoNotShow);
            }
          if( this.addSomeExtraLinks)
          BadgerUtilityMethods.addRandomConnections(allPlanets, 2, Context, 5);
        }
      else
        {
          ArcenDebugging.ArcenDebugLogSingleLine("BUG: linking regions with unknown algorithm", Verbosity.DoNotShow);
        }
    }

      private void getNebulaLinkingPercentages(ArcenSimContext Context, bool isAsteroid, int nebulaConnectivity, bool addSomeExtraLinks,
                                      out int percentSpanningTreeInRegion, out int percentSpanningTreeWithConnectionsInRegion,
                                      out int percentGabrielInRegion, out int percentRNGInRegion,
                                      out LinkMethod InterRegionLinkingMethod)
        {
           percentSpanningTreeInRegion = 10;
           percentSpanningTreeWithConnectionsInRegion = 10;
           percentGabrielInRegion = 40;
           percentRNGInRegion = 40;
           InterRegionLinkingMethod = LinkMethod.Gabriel;
           if(!isAsteroid )
            {
              if(nebulaConnectivity == 1)
                {
                  percentSpanningTreeInRegion = 20;
                  percentSpanningTreeWithConnectionsInRegion = 30;
                  percentGabrielInRegion = 20;
                  percentRNGInRegion = 30;
                  InterRegionLinkingMethod = LinkMethod.RNG;
                }
              if(nebulaConnectivity == 2)
                {
                  percentSpanningTreeInRegion = 10;
                  percentSpanningTreeWithConnectionsInRegion = 10;
                  percentGabrielInRegion = 40;
                  percentRNGInRegion = 40;
                  InterRegionLinkingMethod = LinkMethod.Gabriel;
                }
              if(nebulaConnectivity == 3)
                {
                  percentSpanningTreeInRegion = 5;
                  percentSpanningTreeWithConnectionsInRegion = 5;
                  percentGabrielInRegion = 45;
                  percentRNGInRegion = 45;
                  InterRegionLinkingMethod = LinkMethod.Gabriel;
               }
              if(nebulaConnectivity == 4)
                {
                  percentSpanningTreeInRegion = 0;
                  percentSpanningTreeWithConnectionsInRegion = 0;
                  percentGabrielInRegion = 90;
                  percentRNGInRegion = 10;
                  InterRegionLinkingMethod = LinkMethod.Gabriel;
               } 
            }
          if(isAsteroid)
            {
              percentSpanningTreeInRegion = 0;
              percentSpanningTreeWithConnectionsInRegion = 0;
              percentGabrielInRegion = 100;
              percentRNGInRegion = 0;
              int randomNumber = Context.RandomToUse.NextWithInclusiveUpperBound(0,2);
              if(randomNumber == 0)
                  InterRegionLinkingMethod = LinkMethod.Gabriel;
              else if(randomNumber == 1)
                  InterRegionLinkingMethod = LinkMethod.RNG;
              else
              {
                  InterRegionLinkingMethod = LinkMethod.SpanningTree;
                  if(addSomeExtraLinks)
                  {
                      InterRegionLinkingMethod = LinkMethod.SpanningTreeWithConnections;
                  }
              }
            }


        }

        private void nebulaSettingUpdates( MapConfiguration mapConfig, MapTypeData mapType, out int numClustersHint, out int nebulaConnectivity, bool isAsteroid )
        {
            numClustersHint = 2;
            if ( isAsteroid )
                numClustersHint = 1;
            nebulaConnectivity = 2;
            int settingValue;

            if ( isAsteroid )
                settingValue = BadgerUtilityMethods.getSettingValueInt_Expensive( mapConfig, mapType, "NumberOfAsteroids" );
            else
                settingValue = BadgerUtilityMethods.getSettingValueInt_Expensive( mapConfig, mapType, "NumberOfNebulae" );

            numClustersHint = settingValue;
            if ( !isAsteroid )
            {
                settingValue = BadgerUtilityMethods.getSettingValueInt_Expensive( mapConfig, mapType, "NebulaeConnectivity" );
                nebulaConnectivity = settingValue;
            }
            return;
        }

    // void nebulaSettingUpdates( out int minPlanetsPerRegion, out int maxPlanetsPerRegion,
    //                            out int radiusPerRegion, out int distanceBetweenRegions, bool isAsteroid)
    //   {

    //For this version, we passed inthe explicit region sizes. Was my original attempt
    //     //set defaults in case Settings aren't there
    //      minPlanetsPerRegion = 6;
    //      maxPlanetsPerRegion = 17;
    //      radiusPerRegion = 210;
    //      distanceBetweenRegions = 210;
    //      if(isAsteroid)
    //        {
    //          minPlanetsPerRegion = 4;
    //          maxPlanetsPerRegion = 10;
    //          radiusPerRegion = 130;
    //          distanceBetweenRegions = 360;
    //        }

    //     ArcenSetting setting;
    //     if(isAsteroid)
    //       setting = BadgerUtilityMethods.getSettingByName("MinPlanetsPerAsteroidRegion");
    //     else
    //       setting = BadgerUtilityMethods.getSettingByName("MinPlanetsPerNebulaRegion");

    //     if(setting != null && setting.TempValue_Int != 0)
    //       {
    //         minPlanetsPerRegion = setting.TempValue_Int;
    //       }
        
    //     if(isAsteroid)
    //       setting = BadgerUtilityMethods.getSettingByName("MaxPlanetsPerAsteroidRegion");
    //     else
    //       setting = BadgerUtilityMethods.getSettingByName("MaxPlanetsPerNebulaRegion");

    //     if(setting != null  && setting.TempValue_Int != 0)
    //       {
    //         maxPlanetsPerRegion = setting.TempValue_Int;
    //       }
    //     if(isAsteroid)
    //       setting = BadgerUtilityMethods.getSettingByName("radiusPerRegionAsteroid");
    //     else
    //       setting = BadgerUtilityMethods.getSettingByName("radiusPerRegionNebula");

    //     if(setting != null  && setting.TempValue_Int != 0)
    //       {
    //         radiusPerRegion = setting.TempValue_Int;
    //       }
    //     if(isAsteroid)
    //       setting = BadgerUtilityMethods.getSettingByName("distanceBetweenAsteroidRegion");
    //     else
    //       setting = BadgerUtilityMethods.getSettingByName("distanceBetweenNebulaRegion");
    //     if(setting != null  && setting.TempValue_Int != 0)
    //       {
    //         distanceBetweenRegions = setting.TempValue_Int;
    //       }
    //   }
    //returns the index of the smallest distance that's larger than smallestDistanceSoFar
    //ie if our distances are 4, 5, 6, 7 and smallestDistanceSoFar == 5
    //then it would return 6
    public int findNextValue(int[]distanceFromCenter, int smallestDistanceSoFar, int numRegions)
      {
        int idx = -1;
        int bestFit = 9999;
        for(int i = 0; i < numRegions; i++)
          {
            //note must be >= smallestDistanceSoFar in case two regions are equidistant
            //this is allowable because we delete the entry for each match after it is made
            if(distanceFromCenter[i] >= smallestDistanceSoFar && distanceFromCenter[i] < bestFit)
              {
                idx = i;
                bestFit = distanceFromCenter[i];
              }
          }
        return idx;
      }
  }

  public class Mapgen_Octopus : Mapgen_Base
  {
    /* This map type was suggested by Tadrinth on the forums. He couched it as 
       "Spiral galaxy: large cluster in the middle (Body), 8 arms coming off, each arm is a series of linked small clusters.  "
       which made me think of an octopus. So variables are named like it's an octopus

       It was initially coded by BadgerBadger, and then Tadrinth made some welcome tweaks.

       Original modification notes for Tadrinth:
       We figure out how many planets belong in each arm and how many planets go in the body.
       Planets are allocated via the "addPointsInCircle" because that's easily implemented (and because Keith
       had already written most of the pieces, so I could steal it readily).

       If you want two clusters per arm and a bit of a spiral then I suggest
       you allocate more planets per Arm (note the minPlanetsPerArm and maxPlanetsPerArm variables at the top),
       then allocate a second armCenter that's a bit further away from the body and at a slightly different angle

       You can connect gruops of planets via the linkPlanetLists function, so just call that first to link the two
       clusters in each arm

       Tadrinth update notes:
       We seed the core of the galaxy as either one big center cluster, or a ring of smaller clusters.
       Then we seed pairs of arms; each arm is made up of an middle cluster and an outer cluster.   
       Then we link everything together. 
       */

      private readonly bool debug = false;
    public override void Generate(Galaxy galaxy, ArcenSimContext Context, MapConfiguration mapConfig, MapTypeData mapType)
    { 
      int symmetryFactor = 2;
      int numberToSeed = mapConfig.GetClampedNumberOfPlanetsForMapType( mapType );

      int userSetSymmetry = BadgerUtilityMethods.getSettingValueInt_Expensive( mapConfig, mapType, "OctopusNumArms" );

      int radius = 100; // base radius for each cluster (center is twice as large)
      int distForThisArm = 105; // base distance for how far out each arm should be placed
      int minDistanceBetweenPlanets = 45; // planets will be packed more densely than this if needed.
      int alignmentNumber = 10; //align all planets on points divisible by this value. It makes things look more organized
      if (numberToSeed < 20)
      {
        radius = 70;
        distForThisArm = 80;
        symmetryFactor = 1;
      }
      else if (numberToSeed < 60)
      {
        radius = 90;
        distForThisArm = 100;

        symmetryFactor = 2;
      }
      else if (numberToSeed < 80)
      {
        radius = 100;
        distForThisArm = 120;

        symmetryFactor = Context.RandomToUse.NextWithInclusiveUpperBound(2,3);
      }
      else if(numberToSeed < 110)
      {
        radius = 130;
        distForThisArm = 145;
        symmetryFactor = Context.RandomToUse.NextWithInclusiveUpperBound(2, 4);
      }
      else if (numberToSeed < 200)
      {
        radius = 200;
        distForThisArm = 205;
        symmetryFactor = Context.RandomToUse.NextWithInclusiveUpperBound(3, 5);
      }
      else if (numberToSeed < 300)
      {
        radius = 220;
        distForThisArm = 270;
        symmetryFactor = Context.RandomToUse.NextWithInclusiveUpperBound(4, 6);
      }
      else if(numberToSeed < 400)
      {
          radius = 250;
        distForThisArm = 315;
        symmetryFactor = Context.RandomToUse.NextWithInclusiveUpperBound(8, 10);
      }
      else
      {
          radius = 350;
        distForThisArm = 415;
        symmetryFactor = Context.RandomToUse.NextWithInclusiveUpperBound(10, 12);
      }
      
      if(userSetSymmetry != 0)
        symmetryFactor = userSetSymmetry;

      // need at least symmetry three for multi-cluster method to look decent
      bool singleLargeCentralCluster = (symmetryFactor < 3) || Context.RandomToUse.NextBool();

      if( this.debug)
        ArcenDebugging.ArcenDebugLogSingleLine(string.Format("Generating a spiral galaxy with symmetry {0} and {1}", symmetryFactor, singleLargeCentralCluster ? "one large central cluster" : "a ring of small central clusters"), Verbosity.ShowAsInfo);


      ArcenPoint galacticCenter = Engine_AIW2.Instance.GalaxyMapOnly_GalaxyCenter;
            
      List<int> centerClusterSizes = new List<int>();
      List<int> innerArmClusterSizes = new List<int>();
      List<int> outerArmClusterSizes = new List<int>();
      
      // spread half the planets evenly across the clusters
      int minPlanetsPerCluster = Math.Max(numberToSeed / (symmetryFactor * 5) / 2, 2);
      for (int i = 0; i < symmetryFactor; i++)
      {
        centerClusterSizes.Add(minPlanetsPerCluster);
        innerArmClusterSizes.Add(minPlanetsPerCluster);
        innerArmClusterSizes.Add(minPlanetsPerCluster);
        outerArmClusterSizes.Add(minPlanetsPerCluster);
        outerArmClusterSizes.Add(minPlanetsPerCluster);
      }


      int planetsRemaining = numberToSeed - symmetryFactor * minPlanetsPerCluster * 5;

      // spread rest of planets randomly across the clusters
      // have to adjust ratios a bit depending on number of arms; the middle feels a little small with few arms and too big with many, otherwise
      int outerClusterRatio = 25;
      int innerClusterRatio = 30;
      if(symmetryFactor > 2)
      {
        outerClusterRatio = 35;
        innerClusterRatio = 30;
      } else if(symmetryFactor > 4)
      {
        outerClusterRatio = 50;
        innerClusterRatio = 40;
      }
      
      while (planetsRemaining > 0)
      {
        int percent = Context.RandomToUse.NextWithInclusiveUpperBound(1, 100);
        List<int> clusterSizesListToAddTo;
        if (percent > 100 - outerClusterRatio)
        {
          clusterSizesListToAddTo = outerArmClusterSizes;
        }
        else if (percent > 100 - outerClusterRatio - innerClusterRatio)
        {
          clusterSizesListToAddTo = innerArmClusterSizes;
        }
        else
        {
          clusterSizesListToAddTo = centerClusterSizes;
        }

        int i = Context.RandomToUse.Next(0, clusterSizesListToAddTo.Count);
        clusterSizesListToAddTo[i] += 1;
        planetsRemaining -= 1;
      }

      if (this.debug)
      {
        ArcenDebugging.ArcenDebugLogSingleLine("center " + String.Join(", ", centerClusterSizes), Verbosity.DoNotShow);
        ArcenDebugging.ArcenDebugLogSingleLine(" inner " + String.Join(", ", innerArmClusterSizes), Verbosity.DoNotShow);
        ArcenDebugging.ArcenDebugLogSingleLine(" outer " + String.Join(", ", outerArmClusterSizes), Verbosity.DoNotShow);
      }


      //allocate the points for the body
      List<ArcenPoint> allPoints = new List<ArcenPoint>();
      List<ArcenPoint> bodyCenters = new List<ArcenPoint>();
      List<List<Planet>> bodyPlanets = new List<List<Planet>>();

      //Figure out where to place the Arms; we split them evenly around the body
      //note that we update the armAngle for each iteration.

      AngleDegrees startingAngle = AngleDegrees.Create((float)Context.RandomToUse.NextWithInclusiveUpperBound(10, 350)); // randomly spin before we start
      AngleDegrees anglePerArm = AngleDegrees.Create((float)360 / (float)symmetryFactor); 
      AngleDegrees subAnglePerArm = AngleDegrees.Create((float)360 / (float)symmetryFactor / (float)3);
      AngleDegrees spiralizeAngle = AngleDegrees.Create((float)360 / (float)symmetryFactor / (float)6); // spin things slightly more as we go outward so it looks a little like a spiral galaxy

      AngleDegrees armAngle = startingAngle;

      List<Planet> bodyCluster = new List<Planet>();
      ArcenPoint center;

      // randomize linking method for large central cluster; usually densely connected since arms are sparse
      int percentGabriel = 80;
      int percentRNG = 10;
      int percentSpanningTree = 10;
      int percentSpanningTreeWithConnections = 0;

      LinkMethod linkingMethod = BadgerUtilityMethods.getRandomLinkMethod(percentSpanningTree, percentGabriel,
                                                                  percentRNG, percentSpanningTreeWithConnections, Context);

      if (singleLargeCentralCluster)
      {
        int totalCentralPlanets = 0;
        for(int i = 0; i < centerClusterSizes.Count; i++)
        {
          totalCentralPlanets += centerClusterSizes[i];
        }
        CreateClusterOfPlanets(bodyCluster, galaxy, Context, radius * 2, galacticCenter, minDistanceBetweenPlanets, alignmentNumber, totalCentralPlanets, ref allPoints, armAngle, linkingMethod, 0);
        if (true)
        {
          ArcenDebugging.ArcenDebugLogSingleLine("total central planets: " + totalCentralPlanets, Verbosity.DoNotShow);
          ArcenDebugging.ArcenDebugLogSingleLine("created central planets: " + bodyCluster.Count, Verbosity.DoNotShow);
        }

      }

      for (int i = 0; i < symmetryFactor; i++)
      {
        if( this.debug)
          ArcenDebugging.ArcenDebugLogSingleLine(string.Format("creating cluster {0}", i), Verbosity.DoNotShow);

        armAngle = armAngle.Add(anglePerArm);

        AngleDegrees firstArmAngle = armAngle.Add(spiralizeAngle);
        AngleDegrees secondArmAngle = firstArmAngle.Add(subAnglePerArm);
        if( this.debug)
          {
            ArcenDebugging.ArcenDebugLogSingleLine(string.Format("armAngle {0}", armAngle), Verbosity.DoNotShow);
            ArcenDebugging.ArcenDebugLogSingleLine(string.Format("first arm angle {0}", firstArmAngle), Verbosity.DoNotShow);
            ArcenDebugging.ArcenDebugLogSingleLine(string.Format("second arm angle {0}", secondArmAngle), Verbosity.DoNotShow);
          }


        //pick random method for linking clusters making up the central ring, again usually dense
        percentGabriel = 75;
        percentRNG = 15;
        percentSpanningTree = 10;
        percentSpanningTreeWithConnections = 0;
        linkingMethod = BadgerUtilityMethods.getRandomLinkMethod(percentSpanningTree, percentGabriel,
                                                                  percentRNG, percentSpanningTreeWithConnections,
                                                                  Context);
        if (!singleLargeCentralCluster)
        {
          bodyCluster = new List<Planet>();
          center = CreateClusterOfPlanets(bodyCluster, galaxy, Context, radius, galacticCenter, minDistanceBetweenPlanets, alignmentNumber, centerClusterSizes[i], ref allPoints, armAngle, linkingMethod, distForThisArm);
          bodyPlanets.Add(bodyCluster);
          bodyCenters.Add(center);
        }

        if( this.debug)
          ArcenDebugging.ArcenDebugLogSingleLine(string.Format("creating inner arm clusters {0}", i), Verbosity.DoNotShow);

        // random link method for inner parts of the arms; these can be anything.
        percentGabriel = 50;
        percentRNG = 35;
        percentSpanningTree = 10;
        percentSpanningTreeWithConnections = 5;
        linkingMethod = BadgerUtilityMethods.getRandomLinkMethod(percentSpanningTree, percentGabriel,
                                                                  percentRNG, percentSpanningTreeWithConnections,
                                                                  Context);
        List<Planet> innerArm1 = new List<Planet>();
        ArcenPoint innerArm1Center = CreateClusterOfPlanets(innerArm1, galaxy, Context, radius, galacticCenter, minDistanceBetweenPlanets+15, alignmentNumber, innerArmClusterSizes[2 * i], ref allPoints, firstArmAngle, linkingMethod, distForThisArm * 2+20);

        if( this.debug)
          ArcenDebugging.ArcenDebugLogSingleLine(string.Format("creating second inner arm clusters {0}", i), Verbosity.DoNotShow);       
        List<Planet> innerArm2 = new List<Planet>();
        ArcenPoint innerArm2Center = CreateClusterOfPlanets(innerArm2, galaxy, Context, radius, galacticCenter, minDistanceBetweenPlanets+15, alignmentNumber, innerArmClusterSizes[2 * i + 1], ref allPoints, secondArmAngle, linkingMethod, distForThisArm * 2+35);

        // random link method for outer parts of arms; prefer sparse for good defense
        percentGabriel = 15;
        percentRNG = 15;
        percentSpanningTree = 60;
        percentSpanningTreeWithConnections = 10;
        linkingMethod = BadgerUtilityMethods.getRandomLinkMethod(percentSpanningTree, percentGabriel,
                                                                  percentRNG, percentSpanningTreeWithConnections,
                                                                  Context);

        if( this.debug)
          ArcenDebugging.ArcenDebugLogSingleLine(string.Format("creating outer arm clusters {0}", i), Verbosity.DoNotShow);

        linkingMethod = BadgerUtilityMethods.getRandomLinkMethod(percentSpanningTree, percentGabriel,
                                                                  percentRNG, percentSpanningTreeWithConnections,
                                                                  Context);
        List<Planet> outerArm1 = new List<Planet>();
        ArcenPoint outerArm1Center = CreateClusterOfPlanets(outerArm1, galaxy, Context, radius + 30, galacticCenter, minDistanceBetweenPlanets + 40, alignmentNumber, outerArmClusterSizes[2 * i], ref allPoints, firstArmAngle.Add(spiralizeAngle), LinkMethod.SpanningTreeWithConnections, distForThisArm * 4);

        if( this.debug)
          {
            ArcenDebugging.ArcenDebugLogSingleLine(string.Format("linking outer arm clusters {0}", i), Verbosity.DoNotShow);
            ArcenDebugging.ArcenDebugLogSingleLine(string.Format("creating second outer arm clusters {0}", i), Verbosity.DoNotShow);
          }

        linkingMethod = BadgerUtilityMethods.getRandomLinkMethod(percentSpanningTree, percentGabriel,
                                                                  percentRNG, percentSpanningTreeWithConnections,
                                                                  Context);
        List<Planet> outerArm2 = new List<Planet>();
        ArcenPoint outerArm2Center = CreateClusterOfPlanets(outerArm2, galaxy, Context, radius+30, galacticCenter, minDistanceBetweenPlanets + 40, alignmentNumber, outerArmClusterSizes[2 * i + 1], ref allPoints, secondArmAngle.Add(spiralizeAngle), linkingMethod, distForThisArm * 4 + 30);

        // Link clusters together - inner to outer, body to inner
        BadgerUtilityMethods.linkPlanetLists(innerArm1, outerArm1, outerArm1Center, false);
        BadgerUtilityMethods.linkPlanetLists(bodyCluster, innerArm1, innerArm1Center, false);
        BadgerUtilityMethods.linkPlanetLists(innerArm2, outerArm2, outerArm2Center, false);
        BadgerUtilityMethods.linkPlanetLists(bodyCluster, innerArm2, innerArm2Center, false);
      }

      if (!singleLargeCentralCluster)
      {
        if( this.debug)
          ArcenDebugging.ArcenDebugLogSingleLine("linking central clusters together", Verbosity.DoNotShow);
        for (int i = 0; i < symmetryFactor - 1; i++)
        {
          BadgerUtilityMethods.linkPlanetLists(bodyPlanets[i], bodyPlanets[i + 1], bodyCenters[i + 1], false);

        }
        if (Context.RandomToUse.NextBool() || Context.RandomToUse.NextBool()) // occasionally skip completing the ring for spice
        {
          if (this.debug)
            ArcenDebugging.ArcenDebugLogSingleLine("linking last two central clusters together to make a ring", Verbosity.DoNotShow);
          BadgerUtilityMethods.linkPlanetLists(bodyPlanets[0], bodyPlanets[bodyPlanets.Count - 1], bodyCenters[bodyPlanets.Count - 1], false);
        }
      }
    }

    private static ArcenPoint CreateClusterOfPlanets(List<Planet> cluster, Galaxy galaxy, ArcenSimContext Context, int radius, ArcenPoint galacticCenter, int minDistanceBetweenPlanets, int alignmentNumber, int clusterSize, ref List<ArcenPoint> allPoints, AngleDegrees armAngle, LinkMethod linkingMethod, int distForThisArm)
    {
      bool debug = false;
      if(debug)
        ArcenDebugging.ArcenDebugLogSingleLine(string.Format("CreateClusterOfPlanets - creating cluster\n size: {0}\nangle: {1}\n dist: {2}", clusterSize, armAngle, distForThisArm, linkingMethod), Verbosity.DoNotShow);

      ArcenPoint bodyCenter = galacticCenter.GetPointAtAngleAndDistance(armAngle, distForThisArm);
      List<ArcenPoint> pointsForArm = BadgerUtilityMethods.addPointsInCircle(clusterSize, Context, bodyCenter, radius,
                                        minDistanceBetweenPlanets, ref allPoints, alignmentNumber);
      if(debug)
        ArcenDebugging.ArcenDebugLogSingleLine(string.Format("CreateClusterOfPlanets - converting to planets", clusterSize, armAngle, distForThisArm), Verbosity.DoNotShow);

      List<Planet> planetsForThisArm = BadgerUtilityMethods.convertPointsToPlanets(pointsForArm, galaxy, Context);
      cluster.AddRange(planetsForThisArm);
      if(debug)
        ArcenDebugging.ArcenDebugLogSingleLine(string.Format("CreateClusterOfPlanets - linking\n link: {0}", linkingMethod), Verbosity.DoNotShow);

      if (linkingMethod == LinkMethod.Gabriel)
        BadgerUtilityMethods.createGabrielGraph(planetsForThisArm);
      else if (linkingMethod == LinkMethod.RNG)
        BadgerUtilityMethods.createRNGGraph(planetsForThisArm);
      else if (linkingMethod == LinkMethod.SpanningTreeWithConnections)
      {
          BadgerUtilityMethods.createMinimumSpanningTree(planetsForThisArm);
      }
      else
      {
        BadgerUtilityMethods.createMinimumSpanningTree(planetsForThisArm);
      }

      return bodyCenter;
    }
  }
}