星系地图生成器总是允许一些恒星系统接触

Question

我正在使用程序生成创建一个 List<int[]>，其中每个 int[] 都包含星系中恒星系统的 x 和 y 坐标。我使用最小距离参数来避免将恒星系统彼此靠得太近。不过，这似乎并不重要，我总能得到至少几个接触的恒星系统。

如何才能让最小距离为 2 或更大，生成的坐标永远不会接触？

using System;
using System.Collections.Generic;
using System.Linq;

/// <summary> 
/// Procedurally generates a new galaxy.
///
/// This class uses a relatively complex manner of ensuring no solar systems are
/// too close to each other. This is designed to allow slower hardware to handle
/// the generation fairly quickly. 
///
/// To achieve this, the program will break the given area of the galaxy into 
/// smaller squares. Each square will be given several solar systems that are at
/// least a user-given distance apart. Then each square will be placed within
/// the galaxy at the same user-given distance apart from each other. This 
/// ensures no solar systems are within the given distance from one another.
/// </summary>
public class GalGen
{
   /// <summary>
   /// Generates a new galaxy.
   /// 
   /// This generates a new galaxy by creating many small sections of the galaxy
   /// and combining them together.
   /// </summary>
   /// <param name="galaxyHeight"> The height of the galaxy in sections. </param>
   /// <param name="galaxyWidth"> The width of the galaxy in sections. </param>
   /// <param name="sectionSize"> The height and width of galaxy sections in tiles. </param>
   /// <param name="minStars"> The lowest possible amount of stars per section. </param>
   /// <param name="maxStars"> The highest possible amount of stars per section. </param>
   /// <param name="minDistance"> Both the minimum distance between star 
   /// systems, and the distance of each sector from it's neighbors and the
   /// borders of the galaxy. </param>
   /// <returns> A List<int[]> of (x, y) star system locations </returns>
   public static List<int[]> 
   generate(int galaxyHeight, int galaxyWidth, int sectionSize, int minStars, int maxStars, int minDistance)
   {
      Random rand = new Random();
      List<int[]> galaxy = new List<int[]>(2_500);

      for (int x = 0; x < galaxyWidth; x++)
      {
         for (int y = 0; y < galaxyHeight; y++)
         {
            // randomly determine the amount of star systems in the section
            int stars = rand.Next(minStars, maxStars + 1);
            // create the section
            List<int[]> section = createSection(sectionSize, minDistance, stars);
            // adjust the section's position according to it's placement in the galaxy
            section = adjustSystemPosition(section, sectionSize, x, y);
            // add the star system's coordinates to the galaxy
            galaxy = galaxy.Concat(section).ToList();
         }
      }

      return galaxy;
   }

   /// <summary>
   /// Adjusts the position of the star systems in a section according to their
   /// position in the galaxy, as indicated by the y and x arguments.
   /// </summary>
   /// <param name="section"> The section to modify. </param>
   /// <param name="x"> The amount of sections to the left of the section argument. </param>
   /// <param name="y"> The amount of sections above the section argument. </param>
   /// <returns> A List<int[]> of (x, y) star system coordinates. </returns>
   public static List<int[]> 
   adjustSystemPosition(List<int[]> section, int sectionSize, int x, int y)
   {
      for (int i = 0; i < section.Count; i++)
      {
         int xPos; 
         int yPos; 

         // adjust for tile size
         xPos = section[i][0] << 5; // 32
         yPos = section[i][1] << 5; // 32

         // adjust for section position
         xPos += (x * sectionSize) << 5; // 32
         yPos += (y * sectionSize) << 5; // 32

         // adjust for section borders
         xPos += x << 5; // 32
         yPos += y << 5; // 32

         section[i] = new int[] {xPos, yPos};
      }

      return section;
   }

   /// <summary>
   /// Generates a small, square, section of the galaxy. 
   /// </summary>
   /// <param name="sectionSize"> The height and width of the galaxy section. </param>
   /// <param name="minDistance"> The minimum distance between star systems. </param>
   /// <param name="stars"> The amount of stars to create. </param>
   /// <returns> A List<int[]> of (x, y) star system locations. </returns>
   private static List<int[]> 
   createSection(int sectionSize, int minDistance, int stars)
   {
      Random rand = new Random();
      List<int[]> section = new List<int[]>(stars);

      // determine the first star system's location
      int x = rand.Next(0, sectionSize + 1);
      int y = rand.Next(0, sectionSize + 1);
      int[] location = new int[] {x, y};
      section.Add(location);

      for(int i = (stars - 1); i > 0; i--)
      {
         // create new star coordinates
         x = rand.Next(0, sectionSize + 1);
         y = rand.Next(0, sectionSize + 1);
         location = new int[] {x, y};

         // avoid locations that would put it too close to other stars

         for(int j = 0; j < section.Count; j++)
         {
            if (findDistance(location, section[j]) < minDistance)
            {
               j = 0; // restart loop
               // find new potential star coordinates
               x = rand.Next(0, sectionSize);
               y = rand.Next(0, sectionSize);
               location = new int[] {x, y};
            }
         }

         section.Add(location);
      }

      return section;
   }

   /// <summary>
   /// Finds the distance between two stars.
   /// </summary>
   /// <param name="star1"> The coordinates of the first star </param>
   /// <param name="star2"> The coordinates of the second star. </param>
   /// <returns> The distance between the two stars. </returns>
   private static double findDistance(int[] star1, int[] star2)
   {
      double exponent1 = Math.Pow((star1[0] - star2[0]), 2.0);
      double exponent2 = Math.Pow((star1[1] - star2[1]), 2.0);

      return Math.Sqrt(exponent1 + exponent2);
   }
}

Answer 1

问题出在这一段：

for(int j = 0; j < section.Count; j++)
{
    if (findDistance(location, section[j]) < minDistance)

您遍历所有这些并在它们接近时重新生成。然而，它可能只会生成与前一个碰撞的坐标。

改为这样做：（用于演示目的的最小更改。适当的解决方案会有所不同。而且如果没有空间，它永远不会完成！）

for(int i = (stars - 1); i > 0; i--)
{
   do {
      bool collisionFound = false;
      // create new star coordinates
      x = rand.Next(0, sectionSize + 1);
      y = rand.Next(0, sectionSize + 1);
      location = new int[] {x, y};

      // avoid locations that would put it too close to other stars

      for(int j = 0; j < section.Count; j++)
      {
         if (findDistance(location, section[j]) < minDistance)
         {
            collisionFound = true;
            break;
         }
      }
   } while (collisionFound);
   section.Add(location);
}

星系地图生成器总是允许一些恒星系统接触

Galaxy map generator always allows some star systems to touch

c#

procedural-generation