алгоритм для генерации сегмента лабиринте

Question

Я хочу, чтобы создать лабиринт, который выглядит следующим образом:

То есть, он состоит из путей в одном направлении, которые затем связаны. Я искал алгоритм для создания лабиринтов, подобных этому, без успеха.

В частности, я не хочу лабиринта, как это:

, потому что это не «запустить» только в одном направлении.

Также было бы неплохо, если бы решение этого лабиринта потребовало, чтобы игрок «вернулся», т. Е. Не просто двигался вверх все время.

Answer 1

1. создать случайный путь между точками А и В
2. случайным образом добавить стены, пока она не лежит на пути, пока вы не будете удовлетворены

Answer 2

Просто используйте * Поиск, чтобы сделать убедитесь, что вы всегда можете найти путь до конца, а затем для каждой строки добавить двадцать случайно расположенных стен. Если A * не может достичь конца после того, как вы поместили новую строку вниз, используйте обратную трассировку для восстановления нового набора стен до тех пор, пока он не будет работать. Возможно, это не самый эффективный метод, но я думаю, что он будет работать достаточно хорошо в большинстве случаев.

Answer 3

Вот еще один:

1. Добавить стены до границ комнаты.
2. Выберите несколько случайных пятен на границах и в середине комнаты. Для каждого места:
3. Если с этого места есть направления туда, где еще нет стены, выберите произвольное свободное направление и «вырастите» там стену. В противном случае удалите это пятно из списка.
4. Дайте 20% шанс прорастить почку, и если это да, то добавьте это пятно в список.
5. Если в списке больше пятен, выберите следующий и перейти №2. В противном случае получил №5.
6. Если вы оставили лишние места, поместите все их в список. Для каждого свободного места:
7. «Смонтируйте» стену к ближайшей стене, чтобы они встретились.

Answer 4

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

Я думаю, что простой способ, чтобы создать простую горизонтальную карту первого, выбирая одну случайную дырку в каждом слое, как это:

+--------------- + 
+    + 
+--- ------------+ 
+    + 
+-------------- -+ 
+    + 
+-------- -------+ 
+    + 
+ ---------------+ 

Вы теперь определить, где путь решения идет. Теперь просто сделайте несколько шагов: удалите случайный горизонтальный край где-нибудь, затем добавьте вертикальный край, который предотвратит его использование, на строке выше или ниже нового отверстия, случайно выбранной между отверстием и там, где идет реальное решение. (Вам нужно будет убедиться, что вы не удаляете горизонтальный край между двумя разделами пути решения.)

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

Answer 5

Ну, это было весело! В комплекте с ASCII арт вывод я представляю ...

█ ██████ █████████████████████ █ 
█ █        █ █ 
█ █        █ █ 
█ █ ██████████████████████████ █ 
█          █ 
█          █ 
██████ ██████ ███████████ ██████ 
█ █ █    █   █ █ 
█ █ █    █   █ █ 
███████████████████████████████ ██████ 
█          █ 
█          █ 
██████ █████████████████████ ██████ 
█        █   █ 
█        █   █ 
██████ ███████████ ███████████ █ 
█    █     █ █ 
█    █     █ █ 
█████████████████████ ██████ ██████ 
█   █    █    █ 
█   █    █    █ 
███████████████████████████████ ██████ 
█          █ 
█          █ 



    private struct Cell 
    { 
     public bool visited; 
     public bool right; 
     public bool top; 
    } 

    static void Main(string[] args) 
    { 
     Random Rand = new Random(); 

     int size = 8; 

     var maze = new Cell[size,size]; 

     for (int x = 0; x < size; x++) 
      for (int y = 0; y < size; y++) 
      { 
       maze[x, y] = new Cell() { right = true, top = true, visited = false }; 
      } 

     int count = size * size; 

     int positionX = Rand.Next(size); 

     // mark space below (outside matrix) 

     for (int y = 0; y < size; y++) 
     { 
      maze[positionX, y].top = false; maze[positionX, y].visited = true; 
      count--; 

      // move left or right n spaces 
      int n = Rand.Next(size);     // random left or right by an amount n 
      int direction = (Rand.Next(2) == 0) ? 1 : -1; 
      while (positionX + direction > 0 && positionX + direction < size -1 && n-- > 0) 
      { 
       // moving sideways 
       if (direction == -1) 
       { 
        positionX += direction; 
        maze[positionX, y].right = false; 
        maze[positionX, y].visited = true; 
        count--; 
       } 
       else 
       { 
        maze[positionX, y].right=false; 
        positionX += direction; 
        maze[positionX, y].visited = true; 
        count--; 
       } 
      } 
     } 


     // Now pick a random place we have visited and extend into new territory 
     while (count > 0) 
     { 
      int x = Rand.Next(size); 
      int y = Rand.Next(size); 
      if (!maze[x, y].visited) continue;  // not visited yet 

      // We are on a visited node, where can we go from here? 

      // Pick a direction to break down a wall - favor left right 
      if (Rand.Next(4) > 0) 
      { 
       if (Rand.Next(2) == 1 && x < size-1 && !maze[x+1,y].visited) 
        { maze[x,y].right = false; maze[x+1,y].visited = true; count--;} 
       else if (x > 0 && !maze[x-1,y].visited) 
        {maze[x-1,y].right = false; maze[x-1,y].visited = true; count--;} 
      } 
      else 
      { 
       if (Rand.Next(2) == 1 && y < size - 1 && !maze[x, y + 1].visited) 
        { maze[x, y].top = false; maze[x, y+1].visited = true; count--; } 
       else if (y > 0 && !maze[x, y-1].visited) 
        { maze[x, y-1].top = false; maze[x,y-1].visited = true; count--; } 
      } 
     } 

     // Dump the maze 
     for (int y = 0; y < size; y++) 
     { 
      Console.Write("█"); 
      for (int x = 0; x < size; x++) 
       Console.Write((maze[x, y].top) ? "█████" : " █"); 
      Console.WriteLine(); 

      for (int repeat = 0; repeat < 2; repeat++) 
      { 
       Console.Write("█"); 
       for (int x = 0; x < size; x++) 
       { 
        Console.Write(maze[x, y].right ? " █" : "  "); 
       } 
       Console.WriteLine(); 
      } 
     } 

Answer 6

Использование Eller's algorithm и ввести смещение в горизонтальном направлении.