Level.java

//      Sokoban puzzles auto generator
//      https://dxdy.ru/post1541620.html#p1541620
//      2021 dec B@R5uk

import java.util.*;

public class Level {

    private static final int NO_CELL = -1;

    private static final int
            MAZE_CELL_EMPTY        =  0,
            MAZE_CELL_WALL         = -1,
            MAZE_CELL_UNREACHABLE  = -2,
            MAZE_CELL_EMPTY_MARKED = -3,
            MAZE_CELL_EMPTY_ANGLE  = -4,
            MAZE_CELL_WALL_MARKED  = -5;

    private int mazeWidth, mazeHeight, cellsNumber;
    private int [] [] mazeMap, cellMap, neighborCells, overNeighborCells;
    private CellVector [] cellVectors;
    private char [] [] displayBilletDots, displayBilletSpcs, displayBuffer;

    public Level (String [] levelLines) {
        int k, l, m, n, minX, maxX, minY, maxY, cell;
        int [] [] tmpMap;
        char [] charBufferDots, charBufferSpcs;
        String line;
        CellVector border, newVector, vector;
        Queue <CellVector> queue = new ArrayDeque <> ();

        //      Determining map dimensions
        mazeWidth = 0;
        mazeHeight = levelLines .length;
        for (k = 0; mazeHeight > k; ++k) {
            if (mazeWidth < levelLines [k] .length ()) {
                mazeWidth = levelLines [k] .length ();
            }
        }

        //      Parsing source strings
        mazeMap = new int [mazeHeight + 2] [mazeWidth + 2];
        for (k = 0, m = 1; mazeHeight > k; ++k, ++m) {
            line = levelLines [k];
            Arrays .fill (mazeMap [m], MAZE_CELL_EMPTY);
            for (l = 0, n = 1; line .length () > l; ++l, ++n) {
                if ('#' == line .charAt (l)) {
                    mazeMap [m] [n] = MAZE_CELL_WALL;
                }
            }
        }

        //      Initializing border filling
        mazeHeight += 2;
        mazeWidth  += 2;
        border = new CellVector (mazeWidth, mazeHeight);

        for (k = 0; mazeHeight > k; ++k) {
            newVector = new CellVector (0, k);
            newVector .setCell (mazeMap, MAZE_CELL_WALL);
            queue .add (newVector);
            newVector = new CellVector (mazeWidth - 1, k);
            newVector .setCell (mazeMap, MAZE_CELL_WALL);
            queue .add (newVector);
        }

        for (k = 1; mazeWidth - 1 > k; ++k) {
            newVector = new CellVector (k, 0);
            newVector .setCell (mazeMap, MAZE_CELL_WALL);
            queue .add (newVector);
            newVector = new CellVector (k, mazeHeight - 1);
            newVector .setCell (mazeMap, MAZE_CELL_WALL);
            queue .add (newVector);
        }

        //      Filling border cells with walls
        while (!queue .isEmpty ()) {
            vector = queue .remove ();
            for (k = 0; 4 > k; ++k) {
                newVector = vector .neighbour (k);
                if (newVector .outOfBorder (border)) {
                    continue;
                }
                if (MAZE_CELL_EMPTY != newVector .getCell (mazeMap)) {
                    continue;
                }
                newVector .setCell (mazeMap, MAZE_CELL_WALL);
                queue .add (newVector);
            }
        }

        //      Looking for first inner cell (topmost, leftmost)
        newVector = null;
        outerloop:
        for (k = 1; mazeHeight - 1 > k; ++k) {
            for (l = 1; mazeWidth - 1 > l; ++l) {
                if (MAZE_CELL_EMPTY == mazeMap [k] [l]) {
                    newVector = new CellVector (l, k);
                    break outerloop;
                }
            }
        }
        if (null == newVector) {
            throw new IllegalArgumentException ("\n\nMaze is non-enclosed.\n");
        }

        //      Determining connected inner area
        queue .add (newVector);
        minX = maxX = newVector .getX ();
        minY = maxY = newVector .getY ();
        --minY;
        while (!queue .isEmpty ()) {
            vector = queue .remove ();
            for (k = 0; 4 > k; ++k) {
                newVector = vector .neighbour (k);
                switch (newVector .getCell (mazeMap)) {
                case MAZE_CELL_EMPTY:
                case MAZE_CELL_EMPTY_ANGLE:
                    newVector .setCell (mazeMap, MAZE_CELL_EMPTY_MARKED);
                    queue .add (newVector);
                    break;
                case MAZE_CELL_WALL:
                    newVector .setCell (mazeMap, MAZE_CELL_WALL_MARKED);
                case MAZE_CELL_WALL_MARKED:
                case MAZE_CELL_EMPTY_MARKED:
                    break;
                }
                if (minX > newVector .getX ()) {
                    minX = newVector .getX ();
                }
                if (maxX < newVector .getX ()) {
                    maxX = newVector .getX ();
                }
                if (maxY < newVector .getY ()) {
                    maxY = newVector .getY ();
                }
            }
            for (; 8 > k; ++k) {
                newVector = vector .neighbour (k);
                switch (newVector .getCell (mazeMap)) {
                case MAZE_CELL_EMPTY:
                    newVector .setCell (mazeMap, MAZE_CELL_EMPTY_ANGLE);
                    break;
                case MAZE_CELL_WALL:
                    newVector .setCell (mazeMap, MAZE_CELL_WALL_MARKED);
                case MAZE_CELL_WALL_MARKED:
                case MAZE_CELL_EMPTY_MARKED:
                case MAZE_CELL_EMPTY_ANGLE:
                    break;
                }
            }
        }

        //      Reworking maze map
        mazeWidth  = maxX - minX + 1;
        mazeHeight = maxY - minY + 1;
        tmpMap = mazeMap;
        mazeMap = new int [mazeHeight] [mazeWidth];
        for (k = minY, m = 0; maxY >= k; ++k, ++m) {
            for (l = minX, n = 0; maxX >= l; ++l, ++n) {
                newVector = new CellVector (n, m);
                switch (tmpMap [k] [l]) {
                case MAZE_CELL_WALL:
                case MAZE_CELL_EMPTY:
                    newVector .setCell (mazeMap, MAZE_CELL_UNREACHABLE);
                    break;
                case MAZE_CELL_WALL_MARKED:
                case MAZE_CELL_EMPTY_ANGLE:
                    newVector .setCell (mazeMap, MAZE_CELL_WALL);
                    break;
                case MAZE_CELL_EMPTY_MARKED:
                    newVector .setCell (mazeMap, MAZE_CELL_EMPTY);
                    queue .add (newVector);
                    break;
                }
            }
        }

        //      Performing indexing of cells
        cellsNumber = queue .size ();
        cellVectors = queue .toArray (new CellVector [cellsNumber]);
        cellMap = new int [mazeHeight] [mazeWidth];
        for (k = 0; mazeHeight > k; ++k) {
            Arrays .fill (cellMap [k], NO_CELL);
        }
        for (k = 0; cellsNumber > k; ++k) {
            cellVectors [k] .setCell (cellMap, k);
        }

        //      Building cell adjacency tables
        neighborCells     = new int [cellsNumber] [4];
        overNeighborCells = new int [cellsNumber] [4];
        for (k = 0; cellsNumber > k; ++k) {
            Arrays .fill (overNeighborCells [k], NO_CELL);
            vector = cellVectors [k];
            for (l = 0; 4 > l; ++l) {
                newVector = vector .neighbour (l);
                cell = newVector .getCell (cellMap);
                neighborCells [k] [l] = cell;
                if (NO_CELL == cell) {
                    continue;
                }
                newVector = newVector .neighbour (l);
                overNeighborCells [k] [l] = newVector .getCell (cellMap);
            }
        }

        //      Initializing display data
        displayBilletDots = new char [mazeHeight] [];
        displayBilletSpcs = new char [mazeHeight] [];
        displayBuffer     = new char [mazeHeight] [];
        charBufferDots = new char [mazeWidth];
        charBufferSpcs = new char [mazeWidth];
        for (k = 0; mazeHeight > k; ++k) {
            m = -1;
            for (l = 0; mazeWidth > l; ++l) {
                switch (mazeMap [k] [l]) {
                case MAZE_CELL_EMPTY:
                    charBufferDots [l] = '.';
                    charBufferSpcs [l] = ' ';
                    m = l;
                    break;
                case MAZE_CELL_WALL:
                    charBufferDots [l] = '#';
                    charBufferSpcs [l] = '#';
                    m = l;
                    break;
                default:
                    charBufferDots [l] = ' ';
                    charBufferSpcs [l] = ' ';
                    break;
                }
            }
            ++m;
            displayBilletDots [k] = Arrays .copyOf (charBufferDots, m);
            displayBilletSpcs [k] = Arrays .copyOf (charBufferSpcs, m);
            displayBuffer     [k] = new char [m];
        }
    }

    //      ================================================

    public int getCellsNumber () {
        return cellsNumber;
    }

    //      ================================================

    public StateSpace buildStateSpace (int boxesNumber) {
        int k, l, agentCell, nextCell, overCell;
        StateSpace stateSpace = new StateSpace (cellsNumber, boxesNumber);
        StateGenerator stateGenerator = new StateGenerator (boxesNumber);
        long stateId;
        int [] boxCells, newBoxCells;
        boolean [] occupiedCells;

        do {
            stateSpace .addState (stateGenerator .boxCells, stateGenerator .agentCell);
        } while (stateGenerator .hasNext ());

        boxCells    = new int [boxesNumber];
        newBoxCells = new int [boxesNumber];
        occupiedCells = new boolean [cellsNumber];

        for (k = 0; stateSpace .getStatesNumber () > k; ++k) {
            stateId = stateSpace .getStateIdByIndex (k);
            agentCell = stateSpace .unpackStateFromId (stateId, boxCells, occupiedCells);
            for (l = 0; 4 > l; ++l) {
                nextCell = neighborCells [agentCell] [l];
                if (NO_CELL == nextCell) {
                    continue;
                }
                if (!occupiedCells [nextCell]) {
                    stateSpace .linkStates (
                            k,
                            stateSpace .getStateIndexById (stateSpace .replaceAgentCell (stateId, nextCell)),
                            l);
                    continue;
                }
                overCell = overNeighborCells [agentCell] [l];
                if (NO_CELL == overCell) {
                    continue;
                }
                if (occupiedCells [overCell]) {
                    continue;
                }
                System .arraycopy (boxCells, 0, newBoxCells, 0, boxesNumber);
                newBoxCells [Arrays .binarySearch (boxCells, nextCell)] = overCell;
                stateSpace .linkStates (
                        k,
                        stateSpace .getStateIndex (newBoxCells, nextCell),
                        l);
                }
        }

        return stateSpace;
    }

    //      ================================================

    private class StateGenerator {

        int boxesNumber, agentCell, boxCell, boxIndex, counter;
        int [] boxCells;
        char [] stringBuffer;

        public StateGenerator (int argBoxesNumber) {
            boxesNumber = argBoxesNumber;
            boxCells = new int [boxesNumber];
            for (int k = 0; boxesNumber > k; ++k) {
                boxCells [k] = k;
            }
            agentCell = cellsNumber - 1;
            boxCell   = boxesNumber;
            boxIndex  = boxesNumber - 1;
            counter   = 0;
        }

        public boolean hasNext () {
            do {
                if (0 == agentCell) {
                    if (0 > boxIndex) {
                        return false;
                    }
                    nextBoxesPlacement ();
                    agentCell = cellsNumber;
                }
                --agentCell;
            } while (0 <= Arrays .binarySearch (boxCells, agentCell));
            return true;
        }

        private void nextBoxesPlacement () {
            int startIndex, limitValue;

            startIndex = boxIndex;
            limitValue = boxCell;
            do {
                boxCells [boxIndex] = boxCell;
                ++boxCell;
                ++boxIndex;
            } while (boxesNumber > boxIndex);
            if (cellsNumber > boxCell) {
                --boxIndex;
                return;
            }
            boxIndex = startIndex;
            while (true) {
                --boxIndex;
                if (0 > boxIndex) {
                    return;
                }
                --limitValue;
                boxCell = boxCells [boxIndex];
                if (boxCell < limitValue) {
                    ++boxCell;
                    return;
                }
            }
        }

        @SuppressWarnings ("unused")
        public void display () {
            System .out .println (String .format ("%6d   |%s|", counter++, toString ()));
        }

        @Override
        public String toString () {
            if (null == stringBuffer) {
                stringBuffer = new char [cellsNumber];
            }
            Arrays .fill (stringBuffer, '.');
            for (int k = 0; boxesNumber > k; ++k) {
                stringBuffer [boxCells [k]] = 'o';
            }
            stringBuffer [agentCell] = 'x';
            return new String (stringBuffer);
        }
    }

    //      ================================================

    private void fillDisplayBuffer (char [] [] displayBillet) {
        for (int k = 0; mazeHeight > k; ++k) {
            System .arraycopy (displayBillet [k], 0, displayBuffer [k], 0, displayBillet [k] .length);
        }
    }

    //      ================================================

    public void displayMaze () {
        for (int k = 0; mazeHeight > k; ++k) {
            System .out .println (new String (displayBilletDots [k]));
        }
    }

    //      ================================================

    public void displayState (int index, StateSpace stateSpace) {
        int k, agentCell, boxesNumber = stateSpace .getBoxesNumber ();
        int [] boxCells = new int [boxesNumber];
        fillDisplayBuffer (displayBilletDots);
        agentCell = stateSpace .unpackStateByIndex (index, boxCells);
        for (k = 0; boxesNumber > k; ++k) {
            cellVectors [boxCells [k]] .setCell (displayBuffer, '$');
        }
        cellVectors [agentCell] .setCell (displayBuffer, '@');
        for (k = 0; mazeHeight > k; ++k) {
            System .out .println (new String (displayBuffer [k]));
        }
    }

    public void displayPlacement (int index, StateSpace stateSpace) {
        int k, boxesNumber = stateSpace .getBoxesNumber ();
        int [] boxCells = new int [boxesNumber];
        fillDisplayBuffer (displayBilletDots);
        stateSpace .unpackStateByIndex (index, boxCells);
        for (k = 0; boxesNumber > k; ++k) {
            cellVectors [boxCells [k]] .setCell (displayBuffer, '$');
        }
        for (k = 0; mazeHeight > k; ++k) {
            System .out .println (new String (displayBuffer [k]));
        }
    }

    public void displayPuzzle (int start, int end, StateSpace stateSpace) {
        int k, cell, boxesNumber = stateSpace .getBoxesNumber ();
        int [] boxCells = new int [boxesNumber];
        fillDisplayBuffer (displayBilletSpcs);
        stateSpace .unpackStateByIndex (end, boxCells);
        for (k = 0; boxesNumber > k; ++k) {
            cellVectors [boxCells [k]] .setCell (displayBuffer, '.');
        }
        cell = stateSpace .unpackStateByIndex (start, boxCells);
        if (' ' == cellVectors [cell] .getCell (displayBuffer)) {
            cellVectors [cell] .setCell (displayBuffer, '@');
        } else {
            cellVectors [cell] .setCell (displayBuffer, '+');
        }
        for (k = 0; boxesNumber > k; ++k) {
            cell = boxCells [k];
            if (' ' == cellVectors [cell] .getCell (displayBuffer)) {
                cellVectors [cell] .setCell (displayBuffer, '$');
            } else {
                cellVectors [cell] .setCell (displayBuffer, '*');
            }
        }
        for (k = 0; mazeHeight > k; ++k) {
            System .out .println (new String (displayBuffer [k]));
        }
    }
}