java - 某些文件上的堆栈溢出 - 查找 Sprite 的位置

Question

首先，抱歉我的英语不好，尤其是编程方面，英语不是我的母语。 因此，我编写了一个软件来检测图像上的所有连续 Sprite 并列出它们的调色板。 该软件的完整说明在这里:https://www.vg-resource.com/thread-33373.html

它工作正常，但是，如果 Sprite 至少有 4300 左右像素，则会抛出 stackoverflow 异常。

为了找到每个 Sprite 的边界，首先我找到工作表中不是背景颜色的第一个像素。然后，我开始递归方法，验证每个相邻像素以查看它们是否没有背景颜色，然后在该位置调用自身，将它们的位置记录在 boolean 矩阵中。 递归方法:

 //pixelPosition > the position found of the current sprite, posX/posY > position of the current pixel being examined
public boolean[][] moveToNextPixel(boolean[][] pixelPosition, int posX, int posY)
{
    pixelPosition[posX][posY] = true;
    //If the next position isnt outside of the boundaries of the image AND if it hasnt already been recorded
    // AND if it isnt the color of the background, move to that position.
    if(posX + 1 < pixelPosition.length)
    {
        if(!pixelPosition[posX+1][posY] && !panBackgroundColor.isColorPresentInPalette(workingImage.getRGB(posX+1,posY)) )
        {
           moveToNextPixel(pixelPosition,posX+1,posY);
        }
    }
    if(posX - 1 >= 0)
    {
        if(!pixelPosition[posX-1][posY] &&  !panBackgroundColor.isColorPresentInPalette(workingImage.getRGB(posX-1,posY)))
        {
            moveToNextPixel(pixelPosition,posX-1,posY);
        }
    }
    if(posY + 1 < pixelPosition[0].length)
    {
        if(!pixelPosition[posX][posY+1] &&  !panBackgroundColor.isColorPresentInPalette(workingImage.getRGB(posX,posY+1)))
        {
            moveToNextPixel(pixelPosition,posX,posY+1);
        }
    }
    if(posY - 1 >= 0)
    {
        if(!pixelPosition[posX][posY-1] && !panBackgroundColor.isColorPresentInPalette(workingImage.getRGB(posX,posY-1)))
        {
            moveToNextPixel(pixelPosition,posX,posY-1);
        }
    }
    return pixelPosition;
}


//the method isColorPresentInPalette(int) check if the color in entry is in the background colors
public boolean isColorPresentInPalette( int colorRgb)
{
    boolean result = false;
    for( int i =0; i< backgroundPalette.length && !result;i++)
    {
        if(backgroundPalette[i] != null)
        {
            if(backgroundPalette[i].getRGB() == colorRgb)
            {
                result = true;    
            }
        }
    }
    return result;  
}

此外，如果我先加载一张包含正常大小 Sprite 的工作表，然后加载一个带有巨大 Sprite (4400+像素)的工作表，它不会出现 stackoverflow 错误...所以，最后，我很困惑到底是什么问题。 那么，递归方法真的适合解决这类问题吗？如果是这样我可以做什么来解决这个问题？否则，有人能找到一种方法来确定每个人的连续 Sprite 及其位置吗？

Answer 1

编辑:最初我发布了一个递归解决方案，但没有意识到你正在这样做。我认为在更仔细地阅读之后，似乎递归可能不是最好的，因为您将在给定 4300 像素的情况下添加如此多的调用。

在这种情况下，我只会在内存中进行 DFS。或者，您可以尝试 BFS(将从中心向外搜索)。

内存中 DFS 的示例。这基本上与上面的递归执行相同的操作，只不过不是将内容存储在缓冲区大小有限的调用堆栈上，而是存储内存:

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.Stack;

public class FindNeedleInHaystack {

    String[][] haystack;

    class Coordinate {
        int x;
        int y;

        public Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Coordinate that = (Coordinate) o;
            return x == that.x &&
                    y == that.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }

    public FindNeedleInHaystack() {
        this.haystack = new String[10][10];
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                this.haystack[i][j] = "";
            }
        }
    }

    public void addNeedle(int a_x, int a_y) {
        this.haystack[a_y][a_x] = "needle";
    }

    public boolean hasNeedle() {
        boolean[][] visited = new boolean[10][10];
        return hasNeedleHelper(0, 0);

    }

    private List<Coordinate> neighbors(Coordinate coord, boolean[][] visited) {
        List<Coordinate> neighbors = new ArrayList<>();
        int x = coord.x;
        int y = coord.y;
        if (y + 1 < 10 && !visited[y+1][x]) neighbors.add(new Coordinate(x, y+1));
        if (y - 1 >= 0 && !visited[y-1][x]) neighbors.add(new Coordinate(x, y-1));
        if (x + 1 < 10 && !visited[y][x+1]) neighbors.add(new Coordinate(x + 1, y));
        if (x - 1 >= 0 && !visited[y][x-1]) neighbors.add(new Coordinate(x - 1, y));
        return neighbors;
    }

    private boolean hasNeedleHelper(int x, int y) {
        Stack<Coordinate> fringe = new Stack<>();
        boolean[][] visited = new boolean[10][10];

        fringe.push(new Coordinate(x, y));
        while(!fringe.isEmpty()) {
            Coordinate toVisit = fringe.pop();
            if (this.haystack[toVisit.y][toVisit.x].equals("needle")) {
                return true;
            } else {
                visited[toVisit.y][toVisit.x] = true;
                for(Coordinate coord : this.neighbors(toVisit, visited)) {
                    fringe.push(coord);
                }
            }
        }
        return false;
    }


    public static void main(String...args) {
        FindNeedleInHaystack hasNeedle = new FindNeedleInHaystack();
        hasNeedle.addNeedle(3, 4);
        System.out.println("Has a needle?: " + hasNeedle.hasNeedle());

        FindNeedleInHaystack doesntHaveNeedle = new FindNeedleInHaystack();
        System.out.println("Has a needle?: " + doesntHaveNeedle.hasNeedle());

    }
}