某些文件的堆栈溢出 - 查找精灵的位置

Question

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

它工作正常，但是，如果精灵至少有 4300 左右的像素，则会抛出一个 Whosebug 异常。

为了找到每个精灵的边界，首先我找到 sheet 中第一个不是背景颜色的像素。然后，我开始我的递归方法来验证每个相邻像素以查看它们是否没有背景颜色，然后在该位置调用自身，它们的位置被记录在布尔矩阵中。递归方法：

 //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;  
}

此外，如果我先加载一个 sheet 正常大小的精灵，然后加载一个巨大的精灵（4400+ 像素），它不会出现计算器错误...所以，在最后，我对到底是什么问题感到很困惑。那么，递归方法真的是解决这类问题的正确方法吗？如果是这样，我该怎么做才能解决这个问题？否则，有人能找到一种方法来确定每个人的连续精灵及其位置吗？

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());

    }
}

某些文件的堆栈溢出 - 查找精灵的位置

Stack overflow on certain file - Finding positions of sprites

java

stack-overflow

recursion