C＃迷宮代我自己的實現Prim算法的Bug

Question

首先讓我爲大小道歉我會盡量設法準確地建立Prim算法是怎麼說在維基百科上的我摸索出之後保持這種儘可能小

我的迷宮沒有建立起來。 所以我試圖做同樣的想法，以適應我的迷宮，但我看到一個奇怪的錯誤，

當我的遊戲開始它只是無法正常建立我的迷宮，我無法弄清楚，爲什麼 這是偶爾發生的

其他時候，它完美的作品， 所以我有一個public Dictionary<int, Dictionary<int, MazeCellState>> maze該持有迷宮，當它開始迷宮是一切的籬笆，然後我着手建造像這樣

private static void buildPath() 
     { 
      List<KeyValuePair<Misc.Cord, Misc.Cord>> ends = new List<KeyValuePair<Misc.Cord, Misc.Cord>>(); 
      ends.Add(new KeyValuePair<Misc.Cord, Misc.Cord>(new Misc.Cord() { X = 0, Y = 0 }, new Misc.Cord() { X = 0, Y = 0 })); 
      Misc.Cord currentPos = null; 

      while (ends.Count > 0) 
      { 
       int posKey = rand.Next(0, ends.Count); 
       Misc.Cord lastPos = ends[posKey].Key; 
       currentPos = ends[posKey].Value; 
       maze[currentPos.X][currentPos.Y] = MazeCellState.Path; 
       int currentCount = 0; 

       MovingState moveTo1 = (MovingState)rand.Next(0, 4); 
       MovingState moveTo2 = (MovingState)rand.Next(0, 4); 
       while (moveTo1.Equals(moveTo2)) 
       { 
        moveTo1 = (MovingState)rand.Next(0, 4); 
        moveTo2 = (MovingState)rand.Next(0, 4); 
       } 

       // check left 
       if (currentPos.X - 2 > 0 && maze[currentPos.X - 2][currentPos.Y] != MazeCellState.Path && currentCount < 2 && (moveTo1 == MovingState.Left || moveTo2 == MovingState.Left)) 
       { 
        if(!lastPos.Equals(new Misc.Cord() { X = currentPos.X - 2, Y = currentPos.Y })) 
        { 
         ends.Add(new KeyValuePair<Misc.Cord, Misc.Cord>(currentPos, new Misc.Cord() { X = currentPos.X - 2, Y = currentPos.Y })); 
         maze[currentPos.X - 1][currentPos.Y] = MazeCellState.Path; 
         currentCount++; 
        } 
       } 

       // check right 
       if (currentPos.X + 2 < maze.Count && maze[currentPos.X + 2][currentPos.Y] != MazeCellState.Path && currentCount < 2 && (moveTo1 == MovingState.Right || moveTo2 == MovingState.Right)) 
       { 
        if (!lastPos.Equals(new Misc.Cord() { X = currentPos.X + 2, Y = currentPos.Y })) 
        { 
         ends.Add(new KeyValuePair<Misc.Cord, Misc.Cord>(currentPos, new Misc.Cord() { X = currentPos.X + 2, Y = currentPos.Y })); 
         maze[currentPos.X + 1][currentPos.Y] = MazeCellState.Path; 
         currentCount++; 
        } 
       } 

       // check Up 
       if (currentPos.Y - 2 > 0 && maze[currentPos.X][currentPos.Y - 2] != MazeCellState.Path && currentCount < 2 && (moveTo1 == MovingState.Up || moveTo2 == MovingState.Up)) 
       { 
        if(!lastPos.Equals(new Misc.Cord() { X = currentPos.X, Y = currentPos.Y - 2})) 
        { 
         ends.Add(new KeyValuePair<Misc.Cord, Misc.Cord>(currentPos, new Misc.Cord() { X = currentPos.X, Y = currentPos.Y - 2 })); 
         maze[currentPos.X][currentPos.Y - 1] = MazeCellState.Path; 
         currentCount++; 
        } 
       } 

       // check Down 
       if (currentPos.Y + 2 < maze[0].Count && maze[currentPos.X][currentPos.Y + 2] != MazeCellState.Path && currentCount < 2 && (moveTo1 == MovingState.Down || moveTo2 == MovingState.Down)) 
       { 
        if(!lastPos.Equals(new Misc.Cord() { X = currentPos.X, Y = currentPos.Y + 2})) 
        { 
         ends.Add(new KeyValuePair<Misc.Cord, Misc.Cord>(currentPos, new Misc.Cord() { X = currentPos.X, Y = currentPos.Y + 2 })); 
         maze[currentPos.X][currentPos.Y + 1] = MazeCellState.Path; 
         currentCount++; 
        } 
       } 
       ends.RemoveAt(posKey); 
       ends = reorderList(ends); 
      } 

      maze[0][1] = MazeCellState.Path; 
     } 

路徑

我不知道爲什麼有時我上面結了圖片，我的理論是，它最終的向上回致力於它的自我

一些快速的筆記，MazeCellState只能是在這一點上2個選項之一，路徑或對衝基金和reorderList將重新索引任何類型的迷宮大小的列表從屏幕分辨率計算方法爲，每個單元爲64×64 PX，

  GraphicsDevice.Viewport.Width * 5/64, 
      GraphicsDevice.Viewport.Height * 5/64 

Answer 1

這是真正實現算法的硬的方式，當你的場一個網格。 Prim的網格算法可以更容易地表達。而不是研究你的代碼做錯了什麼，我會告訴你簡單的方法。

創建您的網格，並從零開始編號連續數字的所有單元格。每個單元有兩個可以破壞的邊界牆; （左/右）和（上/下）中的一個，並不重要。

現在選擇任何單元格，然後選擇其中一個牆。如果牆的另一側的單元格的數量不同（一個更高，另一個更低），則打破該牆，然後在整個迷宮中，將所有出現的較高數字重新編號到較低數字。如果你選擇一個單元格和另一面上已經有相同數字的牆，不要嘗試另一個牆，而是按順序移動到下一個單元格，重複每一行並向下（可能幾乎全部騎自行車），直到找到一個可以打破牆壁的單元格。

如果你有N個細胞，你必須重複這個破牆練習，正好N-1次，直到最後一次所有的細胞都被編號爲零（因爲每次你休息時，你從場地中刪除更高的數字），你有一個完整的迷宮。

如果你想要一個迷宮的路徑往往是左右比上下，然後偏向你隨機選擇哪個牆在這個方向打破。這也適用於3D迷宮，你可能不需要很多梯子;只是不要選擇打破這麼多的天花板/地板。

我描述了這個算法後，我的14yo兒子用Turbo-Pascal在3D中實現了它，所以我知道算法和這個描述實際上工作。這實際上是Prim算法的一個版本，除非所有的弧線具有相同的成本（或者所有的左右的弧線都是，而所有的弧線都是這樣的）。關於它的巧妙之處在於編號的工作方式是確定哪些單元已經可以從其他單元訪問。