Алгоритм Прима C# Unity

Question

В настоящее время я генерирую случайный лабиринт в Unity, используя алгоритм prim.

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

Это то, что я хочу, чтобы лабиринт был похож.

Разница заключается в том, что у первого касаются углов белых квадратов, а у второго всегда есть пространство между белыми квадратами.

Это код, который управляет визуальным созданием лабиринта:

void FindNext(){
    //We create an empty Transform variable
    // to store the next cell in.
    Transform next;
    //List for the current cell's adjacents
    List<Transform> curAdjacents;
    //List for an element's adjacents
    List<Transform> eleAdjacents;
    //Number variable for while loop
    int num = 1;
    //Perform this loop 
    // While:
    //  The proposed next gameObject's AdjacentsOpened
    //   is less than or equal to 2.
    //   This is to ensure the maze-like structure.
    do{
        //We'll initially assume that each sub-list of AdjSet is empty
        // and try to prove that assumption false in the for loop.
        // This boolean value will keep track.
        bool empty = true;
        //We'll also take a note of which list is the Lowest,
        // and store it in this variable.
        int lowestList = 0;
        for(int i = 0; i < 10; i++){
            //We loop through each sub-list in the AdjSet list of
            // lists, until we find one with a count of more than 0.
            // If there are more than 0 items in the sub-list,
            // it is not empty.
            //We then stop the loop by using the break keyword;
            // We've found the lowest sub-list, so there is no need
            // to continue searching.
            lowestList = i;
            if(AdjSet[i].Count > 0){
                empty = false;
                break;
            }
        }
        //There is a chance that none of the sub-lists of AdjSet will
        // have any items in them.
        //If this happens, then we have no more cells to open, and
        // are done with the maze production.
        if(empty){ 
            //If we finish, as stated and determined above,
            // display a message to the DebugConsole
            // that includes how many seconds it took to finish.
            Debug.Log("We're Done, "+Time.timeSinceLevelLoad+" seconds taken"); 
            //Then, cancel our recursive invokes of the FindNext function,
            // as we're done with the maze.
            //If we allowed the invokes to keep going, we will receive an error.
            CancelInvoke("FindNext");
            //Set.Count-1 is the index of the last element in Set,
            // or the last cell we opened.
            //This will be marked as the end of our maze, and so
            // we mark it red.
            Set[Set.Count-1].renderer.material.color = Color.red;
            //Every cell in the grid that is not in the set
            // will be moved one unit up and turned black.
            // (I changed the default color from black to clear earlier).
            // If you instantiate a FirstPersonController in the maze now,
            // you can actually try walking through it.
            // It's really hard.
            foreach(Transform cell in Grid){
                if(!Set.Contains(cell)){
                    cell.Translate(Vector3.up); 
                    cell.renderer.material.color = Color.black;
                }
            }
            return;
        }
        //If we did not finish, then:
        // 1. Use the smallest sub-list in AdjSet
        //     as found earlier with the lowestList
        //     variable.
        // 2. With that smallest sub-list, take the first
        //     element in that list, and use it as the 'next'.
        next = AdjSet[lowestList][0];
        curAdjacents = next.GetComponent<CellScript>().Adjacents;
        //Since we do not want the same cell in both AdjSet and Set,
        // remove this 'next' variable from AdjSet.
        AdjSet[lowestList].Remove(next);

        //This is code I'm trying to use to solve the issue
        //When I run it though it makes all but the first and last,
        //square white. It is supposed to NOT break if one of the current,
        //cell's adjacents cells has an adjacent cell that has already,
        //been made white. I don't know what's wrong with this code.
        //foreach(Transform element in curAdjacents){
            //eleAdjacents = element.GetComponent<CellScript>().Adjacents;
            //foreach(Transform elem in eleAdjacents){
                //if(Set.Contains(elem)){
                    //continue;
                //}
                //else{
                    //Debug.Log("BREAK!");
                    //num = 0;
                    //break;
                //}
            //}
        //}
    }while(next.GetComponent<CellScript>().AdjacentsOpened >= 2 && num == 1);
    //The 'next' transform's material color becomes white.
    next.renderer.material.color = Color.white;
    //We add this 'next' transform to the Set our function.
    AddToSet(next);
    //Recursively call this function as soon as this function
    // finishes.
    Invoke("FindNext", 0);
}

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

Answer 1

На самом деле, я предполагаю, что вы почти у цели, вам просто нужно включить искусственное пространство между узлами. Я думаю, что если вы работаете на графике, как

ooo
ooo
ooo

где o представляют узлы, фактически сгенерированные пути в лабиринте должны выглядеть

o-o-o
| | |
o-o-o
| | |
o-o-o

Это означает, что в лабиринте должно быть больше места.

Answer 2

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

Скажем, вы начинаете с лабиринта, который выглядит примерно так:

...X..
.X.X.X
X....X
X.X.X.
X.X...
...XXX

Где "." - это дорожный путь, а "X" - стены. Предполагая, что ваш начальный лабиринт является массивом, чтобы добраться до лабиринта, где вы получаете хорошее разделение, вы идете "блок за блоком" и создаете "суперблоки" и размещаете их в больший массив. В этом примере блок в верхнем левом углу будет смотреть вверх, вниз, влево и вправо, чтобы увидеть, где находился его сосед. Это тогда построить "суперблок", как:

XXX
X..
X.X

Который предполагает, что "углами" будут стены. После того, как это построено, это вставляет себя в верхнюю левую часть большего массива. Аналогично, второй блок будет создавать что-то вроде:

XXX
...
XXX

А затем вставьте его во вторую позицию слева вверху. В зависимости от того, как вы хотите, чтобы он функционировал, он может перекрывать первый блок на один пробел, чтобы сохранить растягивание вниз. В этот момент ваш больший массив будет выглядеть (где [] еще пуст / не назначен):

XXXXXX[][][][][]
X.....[][][][][]
X.XXXX[][][][][]
[][][][][][][][]
[][][][][][][][]

Это продолжается, каждый блок смотрит вокруг себя, делает суперблок и устанавливает себя в большой массив, пока не получится что-то вроде:

XXXXXXXXXXXXXXXXXX
X.......XXXXX.....
X.XXXXX.XXXXX.XXXX
XXXXXXX.XXXXX.XXXX
XXXX..........XXXX
XXXX.XXXXX.XXXXXXX
XXXX.XXXXX.XXXXXXX
XXXX.XXXXX.XXXXX.X
XXXX.XXXXX.XXXXX.X
XXXX.XXXXX.XXXXX.X 
XXXX.XXXXX.......X
XXXX.XXXXXXXXXXXXX
XXXX.XXXXXXXXXXXXX
........XXXXXXXXXX
XXXXXXXXXXXXXXXXXX