Сделать рекурсивный лабиринт Java более эффективным

Question

Обновление

Мне удалось заставить работать мой алгоритм, увеличив размер потока до нескольких гигабайт, и я смог решить лабиринт 1803x1803 за секунду или две.

---------------

Я началучу себя рекурсии вчера на яве.Я создал алгоритм, который берет фотографию лабиринта и решает его.Тем не менее, я получаю ответ переполнения стека при выполнении лабиринтов размером более 200x200 пикселей, потому что я думаю, что стеки этого алгоритма становятся слишком длинными.Как я могу улучшить этот алгоритм, чтобы я мог вводить изображения размером до 1000x1000?

Кроме того, вы можете сказать мне, какой алгоритм я сейчас использую?Я считаю, что это либо DFS, но я не уверен.

Пожалуйста, объясните, почему ваше решение более эффективно, и идею, которую оно использует.

Это основной класс для решения

public class BlackWhiteSolver {

static int[][] solutionSet = new int[203][203];
static int width, height;
static String originalImage;
static int correctX, correctY;

public static void convert() {
try {
BufferedImage original = ImageIO.read(new File(originalImage));
int red;
int threshold = 2;
width = original.getWidth();
height = original.getHeight();

    for(int i=0; i<original.getWidth(); i++) {
        for(int j=0; j<original.getHeight(); j++) {
            red = new Color(original.getRGB(i, j)).getRed();
            // 1 = white, 0 = black, 9 = tried, 5 = solved
            if(red > threshold) { solutionSet[i][j] = 1; }
            else { solutionSet[i][j] = 0; }
        }
    }

} catch (IOException e) {e.printStackTrace();}
}

public BlackWhiteSolver(int solvedX, int solvedY, String pic) {
    correctX = solvedX;
    correctY = solvedY;
    originalImage = pic;
}

public boolean solve (int row, int column) {

        boolean completed = false;


        if (validPoint(row, column)) {
            solutionSet[row][column] = 9;

            if (row == correctX && column == correctY) {
                completed = true;
            } else {
                completed = solve (row+1, column);
                if (!completed) {
                    completed = solve (row, column+1);
                }
                if (!completed) {
                    completed = solve (row-1, column);
                }
                if (!completed) {
                    completed = solve (row, column-1);
                }
            }
            if (completed) {
                solutionSet[row][column] = 5;
            }
        }

        return completed;
    }

private boolean validPoint (int row, int column) {

        boolean isValid = false;
        if (row < height-1 && column < width-1 && row >= 1 && column >= 1 ) {
            if (solutionSet[row][column] == 1) {
            isValid = true;
            }
        }

        return isValid;
    }

public static void solvedFile() {
    BufferedImage binarized = new BufferedImage(width, height,BufferedImage.TYPE_3BYTE_BGR);
    int newPixel = 0;
    int rgb = new Color(255, 0, 0).getRGB();
    for(int i=0; i<width; i++){
        for(int j=0; j<height; j++)
    {
        if (solutionSet[i][j] == 0) {
            newPixel = 0;
            newPixel = colorToRGB(1, newPixel, newPixel, newPixel);
        } else if (solutionSet[i][j] == 1 || solutionSet[i][j] == 9) {
            newPixel = 255;
            newPixel = colorToRGB(1, newPixel, newPixel, newPixel);
        } else if (solutionSet[i][j] == 5) {
            newPixel = 16711680;
        }

        binarized.setRGB(i, j, newPixel);
    }
    }

    try { ImageIO.write(binarized, "gif",new File("maze-complete") );} catch (IOException e) {e.printStackTrace();}

}

    private static int colorToRGB(int alpha, int red, int green, int blue) {
        int newPixel = 0;
        newPixel += alpha;
        newPixel = newPixel << 8;
        newPixel += red; newPixel = newPixel << 8;
        newPixel += green; newPixel = newPixel << 8;
        newPixel += blue;
        return newPixel;
    }       
}

Это класс, который запускает лабиринт

public class BlackWhiteInterface
{

    public static void main (String[] args) {

        BlackWhiteSolver puzzle = new BlackWhiteSolver(60, 202, "maze-4.gif");

        System.out.println();

        puzzle.convert();

        if (puzzle.solve(0,34)) {
            System.out.println("completed");
            puzzle.solvedFile();
        } else {
            System.out.println("not possible");
        }
    }
}

Генерирует правильный лабиринт с начальной и конечной точкой

public class MazeBuilder {

    static String start = "left";
    static String end = "down";

    public static void main(String[] args)
    {
        try
        {
            BufferedImage original = ImageIO.read(new File("mazeInput1.gif"));
            BufferedImage binarized = new BufferedImage(original.getWidth(), original.getHeight(),BufferedImage.TYPE_BYTE_BINARY);
            int red;
            int redRightPixel;
            int redUpPixel;
            int newPixel;
            int threshold = 2;

            for(int i=0; i<original.getWidth(); i++)
            {
                for(int j=0; j<original.getHeight(); j++)
                {

                    red = new Color(original.getRGB(i, j)).getRed();
                    int alpha = new Color(original.getRGB(i, j)).getAlpha();
                    if(red > threshold) { newPixel = 255; }
                    else { newPixel = 0; }

                    if (i == 0 || j == 0 || i == original.getWidth()-1 || j == original.getHeight() - 1){
                        newPixel = 0;

                        if (end == "left") {

                        } else if (end == "right") {

                        } else if (end == "up") {

                        } else if (end == "down") {

                        }


    /*if (i == 1 || j == 1 || i == original.getWidth()-2 || j == original.getHeight() - 2 && red > 2) {
        System.out.println("Start Point: (" + i + ", " + j + ")");
    }
    if (i == 0 && j > 0 && j < original.getHeight()-1) {


        redRightPixel = new Color(original.getRGB(i+1, j)).getRed();

        if (i == 0 && redRightPixel > 2) {
            System.out.println("Start Point: (" + i + ", " + j + ")");
            newPixel = 255;
        }
    }*/

    /*if (j == original.getHeight()-1 && i > 0 && i < original.getWidth()-1) {

        redUpPixel = new Color(original.getRGB(i, j-1)).getRed();

        if (redUpPixel > 2) {
            System.out.println("End Point: (" + i + ", " + j + ")");
            newPixel = 255;
        }
    }*/

                    }

                    if (start == "left") {
                        if (i == 1 && j != 0 && j != original.getHeight()-1 && red > 2) {
                            System.out.println("Start Point: (" + i + ", " + j + ")");
                        }
                    } else if (start == "right") {
                        if (i == original.getHeight()-2 && j != 0 && j != original.getHeight()-1 && red > threshold) {
                            System.out.println("Start Point: (" + i + ", " + j + ")");
                        }
                    } else if (start == "up") {
                        if (j == 1 && i != 0 && i != original.getWidth()-1 && red > threshold) {
                            System.out.println("Start Point: (" + i + ", " + j + ")");
                        }
                    } else if (start == "down") {
                        if (j == original.getHeight()-2 && i != 0 && i != original.getWidth()-1 && red > threshold) {
                            System.out.println("Start Point: (" + i + ", " + j + ")");
                        }
                    }

                    if (end == "left") {
                        if (i == 1 && j != 0 && j != original.getHeight()-1 && red > 2) {
                            System.out.println("End Point: (" + i + ", " + j + ")");
                        }
                    } else if (end == "right") {
                        if (i == original.getHeight()-2 && j != 0 && j != original.getHeight()-1 && red > threshold) {
                            System.out.println("End Point: (" + i + ", " + j + ")");
                        }
                    } else if (end == "up") {
                        if (j == 1 && i != 0 && i != original.getWidth()-1 && red > threshold) {
                            System.out.println("End Point: (" + i + ", " + j + ")");
                        }
                    } else if (end == "down") {
                        if (j == original.getHeight()-2 && i != 0 && i != original.getWidth()-1 && red > threshold) {
                            System.out.println("End Point: (" + i + ", " + j + ")");
                        }
                    }


                    newPixel = colorToRGB(alpha, newPixel, newPixel, newPixel);
                    binarized.setRGB(i, j, newPixel);
                }
            }
            ImageIO.write(binarized, "gif",new File("maze-4") );
        }
        catch (IOException e)
        {
            e.printStackTrace();
        }
    }
    private static int colorToRGB(int alpha, int red, int green, int blue) {
        int newPixel = 0;
        newPixel += alpha;
        newPixel = newPixel << 8;
        newPixel += red; newPixel = newPixel << 8;
        newPixel += green; newPixel = newPixel << 8;
        newPixel += blue;
        return newPixel;
    }

}

Пример вывода лабиринта 203 x 203

Answer 1

Один простой способ, который лишь немного эффективнее, - не сохранять путь, который вы уже прошли, в стеке с помощью рекурсии.Вместо этого сохраните путь, по которому вы пошли до сих пор, либо в java.util.BitSet (где вы храните каждый пиксель пути в элементе y*width + x BitSet), либо вы можете просто использовать красную областьизображение, которое вы раскрасили для хранения пути.

Это позволяет избежать переполнения стека.

Основной алгоритм состоит в том, чтобы начать с начальной точки и идти в одном из четырех основных направлений, если только выЯ уже побывал в этом направлении (либо пробовал и обнаруживал тупик, либо пришел с этого направления, чтобы попасть сюда).Когда вы идете в направлении, вы делаете то же самое там.Это простой нерекурсивный цикл.

Когда вы попадаете в тупик, вы выясняете, как вы попали туда изначально, проверив все четыре направления, откуда вы видите, откуда пришел путь.Вы убираете красный с места, где вы стоите, и возвращаетесь в том направлении, откуда пришли.Если в любом направлении нет красной дорожки, вы снова в начальной точке и перепробовали все, поэтому не существует решения для лабиринта.

Когда вы возвращаетесь назад, вы пробуете следующее направление, которое у вас есть.еще не пробовал в старом квадрате на пути, пока все направления не зашли в тупик.

Если вы когда-либо достигнете конечной точки, все готово.

---

Вот некоторый псевдокод, которыйобычно не может обрабатывать циклы (пути, которые идут в виде «круга»), это крайне неэффективно (например, он должен использовать BitSet вместо boolean[][]), и это, вероятно, имеет некоторые ошибки, но это даетобщая идея:

public class MazeSolver {
    private static enum Direction { UP, RIGHT, DOWN, LEFT }

    // Return array's element is true if that's part of the path
    public static boolean[][] solve(final boolean[][] mazeWallHere,
                                    int x, int y,
                                    final int endX, final int endY) {
        final int width = mazeWallHere.length;
        final int height = mazeWallHere[0].length;

        final boolean[][] path = new boolean[width][height];

        Direction nextDirection = Direction.UP;
        boolean backtrack = false;
        while (true) {
            // If this spot is a dead end in all new directions, head back
            if (backtrack) {
                backtrack = false;

                // Unmark where we are
                path[x][y] = false;

                // Find where we came from and what direction we took to get here
                // Then switch to the next direction
                // If all directions have been tried, backtrack again
                // If we can't backtrack, return null because there's no solution
                // If we went up to get here, go back down and try going right.
                if (y != 0 && path[x][y - 1]) {
                    y--;
                    nextDirection = Direction.RIGHT;
                    continue;
                }
                // If we went right to get here, go back left and try going down.
                else if (x != 0 && path[x - 1][y]) {
                    x--;
                    nextDirection = Direction.DOWN;
                    continue;
                }
                // If we went down to get here, go back up and try going left.
                else if (y < height && path[x][y + 1]) {
                    y++;
                    nextDirection = Direction.LEFT;
                    continue;
                }
                // If we went left to get here, go back right and backtrack again.
                else if (x < width && path[x + 1][y]) {
                    x++;
                    backtrack = true;
                    continue;
                }
                // If we didn't come from anywhere, we're at the starting point
                // All possible paths are dead ends
                else return null;
            }

            // Mark where we are
            path[x][y] = true;

            // If we've solved it, return the solution
            if (x == endX && y == endY) return path;
            // Move unless we:
            //   * hit the edge of the maze
            //   * it's the direction we originally got here from
            //   * hit a wall
            // If we can't go a certain direction, try the next direction
            // If we're out of directions to try, backtrack
            switch (nextDirection) {
                case UP:    if (y == height
                                    || path[x][y + 1]
                                    || mazeWallHere[x][y + 1]) {
                                nextDirection = Direction.RIGHT;
                                continue;
                            }
                            else y++;
                            break;
                case RIGHT: if (x == width
                                    || path[x + 1][y]
                                    || mazeWallHere[x + 1][y]) {
                                nextDirection = Direction.DOWN;
                                continue;
                            }
                            else x++;
                            break;
                case DOWN:  if (y == 0
                                    || path[x][y - 1]
                                    || mazeWallHere[x][y - 1]) {
                                nextDirection = Direction.LEFT;
                                continue;
                            }
                            else y--;
                            break;
                case LEFT:  if (x == 0
                                    || path[x - 1][y]
                                    || mazeWallHere[x - 1][y]) {
                                backtrack = true;
                                continue;
                            }
                            else x--;
                            break;
            }
        }
    }
}

Если вы хотите правильно обрабатывать циклы, сделайте path int[][] и сохраните номер хода вместо true, чтобы вы знали, какой путь старше.