Prim's Algorithm for mazes: Why do I have to double check if nodes are contained in my maze?

Question

I'm trying to implement Prim's Algorithm in my maze generator as described here. I've got it working as intended, but with an extra catch in my code of which I'm not sure why it's needed.

In my algorithm, I keep track of a list of cells that make up the maze in maze. I then look at the potential frontier cells (neighbouring cells to those that make up the maze), and pick one randomly. Let's call this the frontier. I then determine the neighbours of the frontier, and check which of the neighbours connect to the already existing maze. I connect the frontier node and the adjacent already in-maze node, remove the frontier node from the list of possible frontiers, add it to the maze, and finally add the newly found maze node's neighbours to the frontier list.

During this process, I make sure to only add nodes to the frontiers list that are not already contained in maze. (see the if (neighbour.Cell != null && !maze.Contains(neighbour.Cell)) statements.

However, my Algorithm seems to mess up if I don't end up double checking each chosenFrontier to see if they're not already contained in the maze. If I do not do this, the algorithm will end up thinking there's still frontier cells even in places where every adjacent tile is already part of the maze.

Why is this? Why do I need the if { ... } else { ...} statement there for my algorithm to succeed? I'm dumbstruck as to why it would be neccessary, since everywhere I add cells to my frontier lists, I already check whether they are already contained in maze. If they are, they aren't added to my frontier list. Yet somehow if I have to doublecheck my frontier list for cells that are already contained in the maze (and remove them). Where did I go wrong?

Here's my code:

private IEnumerator PrimsAlgorithm(Cell startingCell)
{
    List<Cell> maze = new List<Cell>();
    maze.Add(startingCell);
    startingCell.Visit();
        
    // Determine starting cell's frontier cells
    List<Neighbour> frontiers = new List<Neighbour>();
    foreach(Neighbour neighbour in startingCell.GetNeighbours())
    {
        if (neighbour.Cell != null && !maze.Contains(neighbour.Cell))
        {
            frontiers.Add(neighbour);
        }
    }

    yield return new WaitForSeconds(stepSize);
    startingCell.Leave();

    // While there are frontier cells,
    while (frontiers.Count > 0)
    {
        // Choose a random frontier from the list
        Neighbour chosenFrontier = frontiers[random.Next(frontiers.Count)];

        if (maze.Contains(chosenFrontier.Cell))
        {
            // ----- Why is this neccessary??? -----
            frontiers.Remove(chosenFrontier);
        }
        else
        {
            // Determine the frontier cells's possible neighbours
            // Possible neighbours are only cells that are already part of the maze.
            Neighbour[] chosenFrontierNeighbours = chosenFrontier.Cell.GetNeighbours();
            List<Neighbour> adjacentInMazeNeighbours = new List<Neighbour>();
            foreach (Neighbour chosenFrontierNeighbour in chosenFrontierNeighbours)
            {
                if (chosenFrontierNeighbour.Cell != null && maze.Contains(chosenFrontierNeighbour.Cell))
                {
                    adjacentInMazeNeighbours.Add(chosenFrontierNeighbour);
                }
            }

            // Choose a random neighbour from the possible neighbours
            if (adjacentInMazeNeighbours.Count > 0)
            {
                Neighbour chosenInMazeNeighbour = adjacentInMazeNeighbours[random.Next(adjacentInMazeNeighbours.Count)];

                // Connect the frontier cell to their new neighbour (and the other way around)
                maze.Add(chosenFrontier.Cell);
                chosenFrontier.Cell.Visit();
                chosenFrontier.Cell.AddConnection(chosenInMazeNeighbour.Dir);
                chosenInMazeNeighbour.Cell.AddConnection(GetOppositeDir(chosenInMazeNeighbour.Dir));
                // Remove the frontier from the set
                frontiers.Remove(chosenFrontier);

                // Determine the chosenFrontiers' possible neighbours and add them to the list of frontiers.
                // Possible neighbours are cells that exist and aren't yet contained in the maze.
                // These become the new frontier nodes.
                foreach (Neighbour neighbour in chosenFrontier.Cell.GetNeighbours())
                {
                    if (neighbour.Cell != null && !maze.Contains(neighbour.Cell))
                    {
                        frontiers.Add(neighbour);
                    }
                }
            }
            // Wait to show this iteration
            yield return new WaitForSeconds(stepSize);
            // Leave current cell
            chosenFrontier.Cell.Leave();
        }
    }
    yield return new WaitForSeconds(stepSize);
}

Here's a gif of my algorithm working with the above code

And here's a gif of the results if I remove the if statement

Answer 1

You make sure that you only add items to the frontier list if they aren't already in the maze, but they might already be in the frontier list.

Since the frontier list can contain multiple copies of a single cell, you need an additional check to make sure you don't add it to the maze multiple times.