Произвольное создание блоков на плоской карте

Question

Я пытаюсь случайным образом генерировать блоки на плоской карте и делать это так, чтобы они не перекрывали друг друга. Я сделал матрицу (массив C#) размера карты (500x500), блоки имеют шкалу от 1 до 5. Код работает, но если сгенерированный блок перекрывает другой, он уничтожается и не регенерируется где-то остальное.

Только около 80 из 1000 блоков, которые я пытаюсь сгенерировать, не перекрывают другой блок.

Вот изображение карты с около 80 блоков генерируется, зеленые квадраты блоки

void generateElement(int ratio, int minScale, int maxScale, GameObject g) { 
    bool elementFound = false; 
    for (int i = 0; i < ratio * generationDefault; i++) { 
     GameObject el; 
     // Randomly generate block size and position 
     int size = Random.Range(minScale, maxScale + 1); 
     int x = Random.Range(0, mapSizex + 1 - size); 
     int y = Random.Range(0, mapSizey + 1 - size); 

     // Check if there is already an element 
     for (int j = x; j < x + size; j++) 
      for (int k = y; k < y + size; k++) 
       if (map[j][k] != null) 
        elementFound = true; 
     if (elementFound) 
      continue; 
     else { 
      el = (GameObject)Instantiate(g, new Vector3(x + (float)size/2, (float)size/2, y + (float)size/2), Quaternion.Euler(0, 0, 0)); 
      el.transform.localScale *= size; 
     } 
     // Create element on map array 
     for (int j = x; j < x + size; j++) 
      for (int k = y; k < y + size; k++) 
       if (map[j][k] == null) { 
        map[j][k] = el.GetComponent<ObjectInterface>(); 
       } 
    } 
} 

я думал, 3 возможных исправлений

• I следует установить размер блока в зависимости от места, которое он имеет.
• Я должен использовать другой алгоритм рандомизации.
• Я не делаю это правильно.

Как вы думаете, а лучше всего?

---

UPDATE

Я получил код работает гораздо лучше. Теперь я пытаюсь создать несколько блоков при необходимости (максимум 5 на данный момент), и я исправил ошибки. Если на карте уже много элементов, они не всегда будут созданы, и это то, что я хотел, я просто должен найти нужное количество раз, чтобы попытаться создать экземпляр блока.

Я попытался создать 1280 элементов на карте 500x500. Он занимает всего около 1,5 секунд, и он создавал 1278/1280 блоков (99,843%).

void generateElement(int ratio, int minScale, int maxScale, GameObject g) { 
bool elementFound = false; 
int cnt = 0; 
// Generate every block 
for (int i = 0; i < ratio * generationDefault; i++) { 
    GameObject el = null; 
    // Randomly generate block size and position 
    int size, x, y, tryCnt = 0; 

    // Try maximum 5 times to generate the block 
    do { 
     elementFound = false; 
     // Randomly set block size and position 
     size = Random.Range(minScale, maxScale + 1); 
     x = Random.Range(0, mapSizex + 1 - size); 
     y = Random.Range(0, mapSizey + 1 - size); 

     // Check if there is already an element 
     for (int j = x; j < x + size; j++) 
      for (int k = y; k < y + size; k++) 
       if (map[j][k] != null) 
        elementFound = true; 
     tryCnt++; 
    } while (elementFound && tryCnt < 5); 
    if (tryCnt >= 5 && elementFound) continue; 

    // Instantiate the block 
    el = (GameObject)Instantiate(g, new Vector3(x + (float)size/2, (float)size/2, y + (float)size/2), Quaternion.Euler(0, 0, 0)); 
    el.transform.localScale *= size; 
    // Create element on map array 
    for (int j = x; j < x + size; j++) 
     for (int k = y; k < y + size; k++) 
      if (map[j][k] == null) { 
       map[j][k] = el.GetComponent<ObjectInterface>(); 
      } 
    cnt++; 
} 
print("Instantiated " + cnt + "/" + ratio * generationDefault); 

}

Answer 1

Это невероятно трудно сделать так.

Вот быстрое решение, которое вам, возможно, понравится ... в зависимости от вашей сцены.

actualWidth = 500 //or whatever. assume here is square 
// your blocks are up to 5 size 
chunkWidth = actualWidth/5 
// it goes without saying, everything here is an int 
kChunks = chunkWidth*chunkWidth 
List<int> shuf = Enumerable.Range(1,kChunks).OrderBy(r=>Random.value).ToList(); 
howManyWanted = 1000 
shuf = shuf.Take(howManyWanted) 
foreach(i in shuf) 
    x = i % actualWidth 
    y = i/actualWidth 
    make block at x y 
    put block in list allBlocks 

ОДНАКО ............

---

...... вы увидите, что это выглядит своего рода "регулярный", так что это:

Просто беспорядочно нарушать все блоки. Помните, что программирование видеоигр - это умные трюки!

В идеале, вам нужно начинать с середины и работать своим путем; в любом случае вы не можете просто делать их в одной строке. Перетасовка в порядке. Таким образом, сделать это ..

harmonic = 3 //for example. TRY DIFFERENT VALUES 

    function rh = Random.Range(1,harmonic) (that's 1 not 0) 

    function rhPosNeg 
     n = rh 
     n = either +n or -n 
     return n 

    function onePerturbation 
    { 
    allBlocks = allBlocks.OrderBy(r => Random.value) //essential 
    foreach b in allBlocks 
     newPotentialPosition = Vector2(rhPosNeg,rhPosNeg) 
     possible = your function to check if it is possible 
      to have a block at newPotentialPosition, 
      however be careful not to check "yourself" 
     if possible, move block to newPotentialPosition 
    } 

Самый простой подход просто запустить onePerturbation, скажем, в три раза. Посмотрите на это между каждым прогоном. Также попробуйте различные значения коэффициента настройки harmonic.

Существует много способов, чтобы помешать полям разным размером блоков, выше - решение KISS, которое, мы надеемся, хорошо подходит для вашей ситуации.

---

Кодирование примечание ...

Как получить наборы уникальных случайных чисел.

Просто, чтобы объяснить эту строку кода ...

List<int> shuf = Enumerable.Range(1,kChunks).OrderBy(r=>Random.value).ToList(); 

Если вы новичок в кодировании: говорят, что вы не хотите, чтобы это сделать: «получить сто случайных чисел от 1 до миллиона, но не повторяет».

К счастью, это очень хорошо известная проблема с очень простое решение.

, как вы получите номер, без повторов, просто перетасовать все номера, а затем взять сколько вы хотите от вершины.

Например, скажем, вам нужна случайная пара чисел от 1 до 10, но без повторов.

Итак, вот цифры 1-10 перемешиваются: 3,8,6,1,2,7,10,9,4,5

Просто возьмите то, что вам нужно от фронта: так, 3, 8, 6 и т. Д.

Итак, для примера предположим, что вам нужно двенадцать чисел, никаких повторений от 1 до 75. Поэтому первая проблема заключается в том, что вы хотите список со всеми номерами до 75, но перетасовывали. На самом деле вы делаете это вот так.

List<int> shuf = Enumerable.Range(1,75).OrderBy(r=>Random.value).ToList(); 

Так что этот список насчитывает 75 наименований. Вы можете проверить это, сказав foreach(int r in shuf) Debug.Log(r);. Далее в примере вам нужно только 12 из этих чисел. К счастью, есть List вызова, который делает это:

shuf = shuf.Take(12) 

Итак, это все - теперь у вас есть 12 номеров, без повторов, все случайных между 1 и 75. Опять же вы можете проверить с foreach(int r in shuf) Debug.Log(r);

Короче говоря, если вы хотите, «п» число, не повторяется, между 1 и Максом, все, что вам нужно, так это:

List<int> shuf = Enumerable.Range(1,Max).OrderBy(r=>Random.value).ToList(); 
shuf = shuf.Take(n); 

вуаля, вы можете проверить результат с foreach(int r in shuf) Debug.Log(r);

Я просто объясняю это подробно, потому что часто задают вопрос «как получить случайные числа, которые являются уникальными».Это «вековой» программный трюк, и ответ заключается в том, что вы shuffle массив всех задействованных целых чисел.

Интересно, что если Google этот вопрос («как получить случайные числа, которые являются уникальными»), это один из тех редких случаев, когда Google не очень помогают, потому что: всякий раз, когда этот вопрос задают, вы получите множество новых программистов (которые не слышали простой трюк, чтобы сделать это правильно!), выписывая огромные сложные сложные идеи, приводящие к дальнейшим путаницам и осложнениям.

Так вот, как вы делаете случайные числа без повторов, к счастью, это тривиально.

Answer 2

if (elementFound) continue; будет пропускать этот текущей итерации цикла. Вам необходимо обернуть int x=Random..; int y=Random()..; часть в while цикла с условием будучи while(/* position x/y already occupued*/) { /* generate new valid point */}, как это, например:

void generateElement(int ratio, int minScale, int maxScale, GameObject g) { 
    for (int i = 0; i < ratio * generationDefault; i++) { 
     GameObject el; 
     // Randomly generate block size and position 

     bool elementFound = false; 
     int size, x, y; 
     do 
     { 
      elementFound = false; 
      size = Random.Range(minScale, maxScale + 1); 
      x = Random.Range(0, mapSizex + 1 - size); 
      y = Random.Range(0, mapSizey + 1 - size); 

      // Check if there is already an element 
      for (int j = x; j < x + size; j++) 
       for (int k = y; k < y + size; k++) 
        if (map[j][k] != null) 
         elementFound = true; 
     } while(elementFound); 

     el = (GameObject)Instantiate(g, new Vector3(x + (float)size/2, (float)size/2, y + (float)size/2), Quaternion.Euler(0, 0, 0)); 
     el.transform.localScale *= size; 

     // Create element on map array 
     for (int j = x; j < x + size; j++) 
      for (int k = y; k < y + size; k++) 
       if (map[j][k] == null) { 
        map[j][k] = el.GetComponent<ObjectInterface>(); 
       } 
    } 
} 

Answer 3

Вы не должны получать много столкновений.

Предполагая, что ваши блоки были ВСЕ 5 единиц в ширину, и вы пытаетесь поместить их в сетку 500 500, у вас будет минимум 100 * 100 мест для них, как минимум, что даст 10000 мест, в которые будет входить 1000 блоков.

Попробуйте играть с этим кодом:

using System; 
using System.Collections.Generic; 

namespace ConsoleApplication1 
{ 
    class Program 
    { 
     static void Main() 
     { 
      var result = PlaceNonOverlappingBlocks(1000, 5, 500, 500); 
     } 

     static List<Block> PlaceNonOverlappingBlocks(int count, int maxBlockSize, int mapX, int mapY) 
     { 
      var map = new bool[mapY, mapX]; 
      var rng = new Random(); 
      var result = new List<Block>(count); 
      int collisions = 0; 

      while (count > 0) 
      { 
       int size = rng.Next(1, maxBlockSize + 1); 
       int x = rng.Next(0, mapX - size); 
       int y = rng.Next(0, mapY - size); 

       if (fits(map, x, y, size)) 
       { 
        result.Add(new Block(x, y, size)); 
        addToMap(map, x, y, size); 
        --count; 
       } 
       else 
       { 
        if (++collisions> 100000) 
         throw new InvalidOperationException("Hell has frozen over"); 
       } 
      } 

      // This is just for diagnostics, and can be removed. 
      Console.WriteLine($"There were {collisions} collisions."); 

      return result; 
     } 

     static void addToMap(bool[,] map, int px, int py, int size) 
     { 
      for (int x = px; x < px+size; ++x) 
       for (int y = py; y < py + size; ++y) 
        map[y, x] = true; 
     } 

     static bool fits(bool[,] map, int px, int py, int size) 
     { 
      for (int x = px; x < px + size; ++x) 
       for (int y = py; y < py + size; ++y) 
        if (map[y, x]) 
         return false; 

      return true; 
     } 

     internal class Block 
     { 
      public int X { get; } 
      public int Y { get; } 
      public int Size { get; } 

      public Block(int x, int y, int size) 
      { 
       X = x; 
       Y = y; 
       Size = size; 
      } 
     } 
    } 
}