private void buildPath()

in Minecraft/src/main/java/com/microsoft/Malmo/MissionHandlers/MazeDecoratorImplementation.java [328:430]
82 lines of code
19 McCabe index (conditional complexity)

    private void buildPath(Cell[] grid, Cell start, Cell end, boolean allowDiags)
    {
        // Initialise a vector to enable us to choose random cells:
        int[] order = new int[this.width * this.length];
        for (int i = 0; i < this.width * this.length; i++)
            order[i] = i;
        int nextRandomSlot = 0;
        
        boolean refreshPath = true; // Make sure we create the optimal path, even if we don't need to remove any blocks.

        // Iteratively remove cells from the grid, whilst ensuring a path of <= maxPathLength still exists between start and end:
        while (this.gaps > 0 || (this.gaps == 0 && refreshPath))
        {
            Cell targetCell = null; // Cell to consider removing.
            int target = -1;
            if (this.gaps > 0)  // Still need to remove some blocks.
            {
                // Choose random cell to remove:
                do
                {
                    // Get next untried cell (in random order).
                    int targetSlot = nextRandomSlot + this.pathrand.nextInt((this.width * this.length) - nextRandomSlot);
                    target = order[targetSlot];
                    order[targetSlot] = order[nextRandomSlot];
                    order[nextRandomSlot] = target;
                    nextRandomSlot++;
                    targetCell = grid[target];
                }
                while (targetCell == start || targetCell == end);   // Don't remove the start or end blocks!
    
                refreshPath |= targetCell.isOnOptimalPath;  // If cell isn't on the optimal path, we don't need to worry what effect its removal will have.
                grid[target] = null;
            }
            
            if (refreshPath)
            {
                // Now, if this cell is removed, can we still construct a valid path?
                // Perform a simple graph search to find out.
                // Initialise graph grid with neutral settings:
                for (int i = 0; i < this.width * this.length; i++)
                {
                    if (grid[i] != null)
                    {
                        grid[i].dist = this.width * this.length;
                        grid[i].isOnOptimalPath = false;
                        grid[i].predecessor = null;
                    }
                }
                start.dist = 0;
                start.isOnOptimalPath = true;
                end.isOnOptimalPath = true;
    
                // Find optimal path from start to end:
                ArrayList<Cell> queue = new ArrayList<Cell>();
                queue.add(start);
                while (!queue.isEmpty() && queue.get(0) != end)
                {
                    Cell home = queue.remove(0);
                    Cell[] neighbours = new Cell[8];
                    int x = home.x;
                    int z = home.z;
                    populateNeighbours(grid, neighbours, x, z, allowDiags);
                    
                    for (int n = 0; n < 8; n++)
                    {
                        if (neighbours[n] != null && neighbours[n].dist > home.dist + 1)
                        {
                            queue.add(neighbours[n]);
                            neighbours[n].dist = home.dist + 1;
                            neighbours[n].predecessor = home;
                        }
                    }
                }
                int pathLength = end.dist + 1;  // +1 for the start block.
    
                if (pathLength <= this.maxPathLength)
                {
                    // We have a valid path.
                    // Walk backwards to build it.
                    Cell c = end;
                    while (c != start)
                    {
                        c.isOnOptimalPath = true;
                        c = c.predecessor;
                    }
                    // All good, so mark as successful and keep going.
                    this.gaps--;
                    refreshPath = false;    // No need to recalculate until next time we remove a block on the critical path.
                }
                else if (this.gaps > 0)
                {
                    // Can't remove this cell!
                    // Put it back:
                    grid[target] = targetCell;
                }
            }
            else
            {
                // Didn't need to recalculate anything.
                this.gaps--;
            }
        }
    }