(我希望这不是重复的，因为我遇到的许多问题都不符合我的需要)
我正在开发一款基于 2D 网格的游戏，其中有 2 名玩家使用网格。有两名玩家:蓝色和红色，每人在格子中放置一 block 石头。所以我想找到一条路径穿过所有颜色相同的单元格回到起点，但前提是至少有一个单元格包含对手的石头。
从上面的截图看:右上角的红色石头没有形成有效的路径。那些在中心的人也没有形成一条路径，即使那应该是一条路径。
我能找到一条路径，但不知何故它坏了，它没有按预期工作。
编辑: 父亲类
public class Pather {
private static final int MIN_PATH_LENGTH = 3;
public enum Neighbor{
UP_RIGHT(0,1,-1),
RIGHT(1,1,0),
DOWN_RIGHT(2,1,1),
DOWN(3,0,1),
DOWN_LEFT(4,-1,1),
LEFT(5,-1,0),
UP_LEFT(6,-1,-1),
UP(7,0,-1);
public int index, x, y;
Neighbor(int index, int x, int y){
this.index = index;
this.x = x;
this.y = y;
}
}
private static Neighbor[] neighbors = Neighbor.values();
public static ArrayList<Path> findPaths(Stone[][] gameBoard){
ArrayList<Path> paths = new ArrayList<>();
ArrayList<Point> checkedPoints = new ArrayList<>();
for (int i = 0; i < gameBoard.length ; i++) {
for (int j = 0; j < gameBoard[0].length; j++) {
if(gameBoard[i][j] != null){
//set the origin of a potential new path
ArrayList<Point> potentialPath = new ArrayList<>();
Point origin = new Point (i,j);
if(!checkedPoints.contains(origin)) {
potentialPath.add(origin);
checkedPoints.add(origin);
potentialPath = findPath(gameBoard, i, j, potentialPath, gameBoard[i][j].getPaint(), checkedPoints, Neighbor.RIGHT.index); //Changed from Neighbor.DOWN.index
if (potentialPath != null) {
paths.add(new Path(potentialPath, gameBoard[i][j].getPaint()));
}
}
}
}
}
return paths;
}
private static ArrayList<Point> findPath(Stone[][] gameBoard, int x, int y, ArrayList<Point> path, Paint color, ArrayList<Point> checkedPoints, int cameFrom){
int startClockwiseScanAtDirection = cameFrom + 5;
for (int i = startClockwiseScanAtDirection; i < startClockwiseScanAtDirection + 7; i++) {
// avoid ArrayIndexOutOfBounds
if(x+neighbors[i%8].x < 0 || y+neighbors[i%8].y < 0 || x+neighbors[i%8].x >= gameBoard.length || y+neighbors[i%8].y >= gameBoard[0].length)
continue;
// check if there's a stone that matches the current stone, we're scanning around
if(gameBoard[x+neighbors[i%8].x][y+neighbors[i%8].y] != null && gameBoard[x+neighbors[i%8].x][y+neighbors[i%8].y].getPaint() == color){
// found one
Point nextStone = new Point(x+neighbors[i%8].x,y+neighbors[i%8].y);
// is the point we just found the origin of the path?
if(nextStone.equals(path.get(0)) && path.size() > MIN_PATH_LENGTH) { //This seems to prevent drawing a path when we have less stone to form a path with
path.add(nextStone);
checkedPoints.add(nextStone);
return path;
}
// otherwise if it's already part of the path ignore it
if (path.contains(nextStone)) {
continue;
}
// else add it to the path and keep going
path.add(nextStone);
checkedPoints.add(nextStone);
// recurse on the next stone in the path
ArrayList<Point> newPath = findPath(gameBoard,x+neighbors[i%8].x, y+neighbors[i%8].y, path, color, checkedPoints, i%8);
if (newPath == null){
// didn't find a way to continue, so backtrack
path.remove(path.size()-1);
} else {
// we have a completed path to return
return newPath;
}
}
}
return null;
}
}
路径类
public class Path {
public Paint getColor() {
return color;
}
public void setColor(Paint color) {
this.color = color;
}
public ArrayList<Point> getCoordinateList() {
return coordinateList;
}
public void setCoordinateList(ArrayList<Point> coordinateList) {
this.coordinateList = coordinateList;
}
private ArrayList<Point> coordinateList;
private Paint color;
public Path(ArrayList<Point> coordinatePath, Paint color){
this.coordinateList = coordinatePath;
this.color = color;
}
@Override
public String toString() {
return coordinateList.toString();
}
}
这里是一些案例测试:
在 MainActivity 的 onCreate() 中调用:
@Override
public void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
gameGrid = findViewById(R.id.gameGrid);
bluePaint = new Paint(Paint.ANTI_ALIAS_FLAG);
bluePaint.setStyle(Paint.Style.FILL_AND_STROKE);
bluePaint.setColor(Color.BLUE);
redPaint = new Paint(Paint.ANTI_ALIAS_FLAG);
redPaint.setStyle(Paint.Style.FILL);
redPaint.setColor(Color.RED);
bgrBluePaint = new Paint(Paint.ANTI_ALIAS_FLAG);
bgrBluePaint.setStyle(Paint.Style.STROKE);
bgrBluePaint.setStrokeWidth(bgrStrokeWdth);
bgrBluePaint.setColor(Color.BLUE);
bgrRedPaint = new Paint(Paint.ANTI_ALIAS_FLAG);
bgrRedPaint.setStyle(Paint.Style.STROKE);
bgrRedPaint.setStrokeWidth(bgrStrokeWdth);
bgrRedPaint.setColor(Color.RED);
bluePlayer = new Stone(1,bluePaint, bgrBluePaint);
redPlayer = new Stone(2, redPaint, bgrRedPaint);
gameBoard = new Stone[100][100];
gameBoard[47][47]= redPlayer;
gameBoard[46][47]= bluePlayer;
gameBoard[44][48]= redPlayer; //REDs form a path when you place this stone in the last positioon
gameBoard[44][49]= redPlayer;
gameBoard[45][47]= redPlayer;
gameBoard[45][48]= bluePlayer;
gameBoard[45][49]= bluePlayer;
gameBoard[45][50]= redPlayer;
gameBoard[46][50]= bluePlayer;
gameBoard[46][49]= redPlayer;
gameBoard[46][48]= redPlayer;
gameBoard[47][50]= bluePlayer;
gameBoard[47][48]= bluePlayer;
gameBoard[47][49]= redPlayer;
gameBoard[48][50]= redPlayer;
gameBoard[48][49]= redPlayer;
gameBoard[48][48]= redPlayer;
gameBoard[49][50]= bluePlayer;
gameBoard[48][51]= redPlayer;
gameBoard[44][50] = bluePlayer;
ArrayList<Path> paths = Pather.findPaths(gameBoard);
gameGrid.setPaths(paths);
gameGrid.setGameBoard(gameBoard);
}
在以下位置放置石头可以清除路径:
//Adding the following deletes the path
gameBoard[43][50] = redPlayer; //Adding this one in last position clears the path
gameBoard[45][51] = redPlayer;
我需要弄清楚如何制定先检查附近的对手然后验证路径的条件。
编辑 2:
石头.java
public class Stone{
private int _player;
private Paint _paint, _bgrPaint;
public Stone(int player, Paint paint, Paint bgrPaint){
_player = player;
_paint = paint;
_bgrPaint = bgrPaint;
}
public int getPlayer() {
return _player;
}
public Paint getPaint() {
return _paint;
}
public Paint get_bgrPaint() {
return _bgrPaint;
}
}
点.java
public class Point {
int x, y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object point) {
return this.x == ((Point) point).x && this.y == ((Point) point).y;
}
@Override
public String toString() {
return "("+x+","+y+")";
}
}
有效路径的截图
最佳答案
解决此类问题的或多或少的标准方法是“扫描线”算法。为简单起见，假设我们正在寻找包裹红点的蓝色路径。 (您可以同时或在第二遍中处理包裹蓝点的红色路径，但您可以稍后解决。)
您可以搜索“扫描线算法”来查看它们在相关应用中的工作原理。 Wikipedia page还不错。
对于这个问题，扫描线是一组 y 区间。它使用最左边(最少 x)的蓝点进行初始化。它为每组垂直相邻的蓝点获得一个间隔。每个间隔代表通过潜在蓝色多边形的垂直切片。
算法的其余部分是设计当扫描线向右移动一个位置并增加 x 时更新扫描线所需的规则。这将是更新每个间隔的问题。当一个步骤找到一组断开的垂直相邻点时，将添加一个新的间隔。在某些情况下，间隔会“消失”，因为潜在的多边形边界会出现死胡同(想想 C 形)。在其他情况下，它们会“合并”，因为在相应的 x 坐标处，存在一组 1 个或多个垂直相邻的连接点。在其他情况下，多边形将成功完成最终一组 1 个或多个垂直相邻点。
细节会很繁琐，但通过案例分析不难解决。
要追踪成功的多边形，间隔可以包括两条前面的点链:多边形上边界和下边界。
最后要考虑的是一个成功闭合的多边形是否包含至少一个红点。但这很容易。如果对于任何 x 坐标，代表多边形的区间用一个红点括起来，那么答案是肯定的。这可以记录为间隔中维护的最初为假的 boolean 值，每次看到这样的红点时都设置为真。成功关闭多边形后，检查标志以查看是否应使用它。
通过使用合适的数据结构，上述所有内容都可以针对非常大的网格变得高效:例如区间树。但如果网格比较小，使用简单的列表应该没问题。无论如何，首先考虑使用扫描线列表对其进行原型(prototype)设计，然后在需要时使用更复杂的数据结构进行优化。
关于java - 这个自定义 "path finding"算法有什么问题？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/51693799/