Unsolvable maze generator using randomized Kruskal's algorithm

Viewed 13

I have a pathfinding game and I want to generate a maze using randomized Kruskal's algorithm. I am using a rank-based disjoint set to detect cycles. Specifically, I am using this implementation.

However, it turns out that the mazes could not be solved at all. Which leads me to believe that something is wrong with my implementation logic.

function generateKruskals(grid)
{
    grid = initWalls(grid);
    let MST = {};
    for(let i = 0; i < NUM_ROWS; i++)
    {
        for(let j = 0; j < NUM_COLS; j++)
        {
            let node = grid[i][j];

            if(!node.isStart && !node.isFinish)
            {
                let entry = makeSet();
                entry.data = node;
                MST[[i, j]] = entry;
            }
        }
    }

    while(Object.keys(MST).length > 0)
    {
        let keys = Object.keys(MST);
        let nodeKey = keys[Math.floor(Math.random() * keys.length)];
        let nodeSet = MST[nodeKey];
        let node = nodeSet.data;
    
        let neighbors = getNeighborWalls(grid, node);

        if (neighbors.length > 0){
            let neighbor = neighbors[Math.floor(Math.random() * neighbors.length)];
            let neighborNodeset = MST[[neighbor.row, neighbor.col]];
            if (neighborNodeset !== undefined)
            {
                if (find(nodeSet) !== find(neighborNodeset)) tearDownWall(neighborNodeset.data);
                union(nodeSet, neighborNodeset);
            }
        }

        delete MST[nodeKey];
    }

    return grid;
}

Here is what the unsolvable maze looks like.

enter image description here

0 Answers
Related