Я использую процедурную генерацию для создания 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);
}
}