C# Maze Generation my own implementation of Prim's algorithm Bug

Question

First let me apologize for the size i will try to keep this as small as possible

after trying to build prim's algorithm exactly how it say's on wikipedia i worked out it was not going to work with the way my maze it built. So i have tried to do the same idea to suit my maze but i'm seeing a strange bug,

When my game start it's just not building my maze properly and i cant figure out why This is what occasionally happens

other times it works perfectly, so i have a public Dictionary<int, Dictionary<int, MazeCellState>> maze this holds the maze when it start the maze is all hedges i then proceed to build the path like so

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;
       }

i'm not sure why occasionally i end up with the picture above, my theory is that it end's up working back on it's self

Some quick notes, MazeCellState can only be one of 2 options at this point, path or hedge and reorderList will re-index a list of any type maze size is calulated from the screen resolution, each cell is 64x64 PX,

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

Answer 1

That's really a hard way to implement the algorithm, when your field is a grid. Prim's algorithm for a grid can be much more easily expressed. Rather than study what you did wrong with your code, I'll tell you the easy way.

Create your grid, and number all the cells with consecutive numbers from zero. Each cell has two boundary walls it can break; up and left, or down and right, or some other combination, it doesn't matter as long as you choose one of (left/right) and one of (up/down).

Now choose any cell, and choose one of its walls. If the cell on the other side of that wall has a different number (one higher and one lower), break that wall, and then throughout the maze, renumber all occurrences of the higher number to the lower one. If you choose a cell and a wall that already has the same number on the other side, don't try the other wall, instead move to the next cell in order, repeating across each row and down (perhaps cycling almost all the way around) until you find a cell with a wall that you can break.

If you have N cells, you have to repeat this wall-breaking exercise exactly N-1 times until the last time all cells are numbered zero (because each time you break, you remove the higher number from the field), and you have a complete maze.

If you want a maze whose paths are more often left-right than up-down, then bias your random choice of which wall to break in that direction. This also works for 3D mazes, where you might not want many ladders; just don't choose to break so many ceilings/floors.

After I described this algorithm, my 14yo son implemented it in Turbo-Pascal in 3D, so I know that the algorithm and this description actually work. This is actually a version of Prim's algorithm, except where all arcs have the same cost (or all left-right ones do, and all up-down ones do, etc). The neat thing about it is the way the numbering works to figure out which cells are already reachable from which others.