java - 这个自定义的“寻路”算法有什么问题？
问题描述
（我希望这不是重复的，因为我遇到的许多问题不符合我的需要）
我正在开发一个基于 2D 网格的游戏，其中有 2 名玩家使用网格。有两个玩家：蓝色和红色，每个人在牢房里放一块石头。所以我想找到一条穿过所有具有相同颜色的单元格返回起点的路径，但前提是至少有一个单元格包含对手的石头。
从上面的截图来看：右上角的红色石头没有形成有效的路径。而那些在中心的人也没有形成一条道路，即使那应该是一条。
我能够找到一条路径，但它不知何故坏了，它没有按预期工作。
编辑： Pather 类
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;
}
}
Point.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+")";
}
}
有效路径的屏幕截图
解决方案
正如我在评论中所写，没有 mvce 很难提供详细的帮助。
根据我在代码中看到的内容，我认为您正在尝试映射板上的所有循环单色路径。
我对代码进行了一些记录在案的更改，希望（无法正确检查）它可以帮助您改进代码。
请注意，由于Stone未发布课程，因此我将板的表示更改为int[][]
import java.awt.Point;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Phather {
private static final int RED = 2, BLUE = 1;
private static final int MIN_PATH_LENGTH = 3;
public enum Neighbor{
UP_RIGHT ( 1,-1),
RIGHT ( 1, 0),
DOWN_RIGHT( 1, 1),
DOWN ( 0, 1),
DOWN_LEFT (-1, 1),
LEFT (-1, 0),
UP_LEFT (-1,-1),
UP ( 0,-1);
int x, y;
Neighbor(int x, int y){
this.x = x;
this.y = y;
}
}
public static Set<Path> findPaths(int[][] gameBoard){
//use set to prevent duplicate paths
Set<Path> paths = new HashSet<>();
for (int x = 0; x < gameBoard.length ; x++) {
for (int y = 0; y < gameBoard[0].length; y++) {
//note that array indexes are [y][x] while point arguments are x,y
if(gameBoard[y][x] != 0){
//use set to prevent duplicate elements. initialize it to allow for
//overlapping paths (paths that contain some shared points)
Set<Point> checkedPoints = new HashSet<>();
//set the origin of a potential new path
ArrayList<Point> potentialPath = new ArrayList<>();
Point origin = new Point (x,y);
if(checkedPoints.add(origin)) { //add returns false if duplicate
potentialPath.add(origin);
potentialPath = findPath(gameBoard, x, y, potentialPath, checkedPoints);
if (potentialPath != null) {
paths.add(new Path(potentialPath, gameBoard[y][x]));
}
}
}
}
}
return paths;
}
private static ArrayList<Point> findPath(int[][] gameBoard, int x, int y,
ArrayList<Point> path, Set<Point> checkedPoints){
int color = gameBoard[y][x]; //no need for color as argument. get from stone
for(Neighbor neighbor : Neighbor.values()) {
int neighborX = x + neighbor.x, neighborY = y + neighbor.y;
// avoid ArrayIndexOutOfBounds
//todo: refactor to method isValidAddress(x,y,maxX, maxY)
if((neighborX < 0) || ( neighborY < 0) || (neighborY >= gameBoard.length)
|| (neighborX >= gameBoard[0].length)) {
continue;
}
// check if there's a stone that matches the current stone, we're scanning around
if((gameBoard[neighborY][neighborX] != 0) && (gameBoard[neighborY][neighborX] == color)){
// found one
Point nextStone = new Point(neighborX,neighborY);
// is the point we just found the origin of the path ?
if(nextStone.equals(path.get(0)) && (path.size() > MIN_PATH_LENGTH)) {
path.add(nextStone); //do you want it in path twice ?
//checkedPoints.add(nextStone); //if added to path before, it is already in checkedPoints
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, neighborX, neighborY, path, checkedPoints);
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;
}
}
class Path {
private ArrayList<Point> coordinateList;
private int color;
Path(ArrayList<Point> coordinatePath, int color){
coordinateList = coordinatePath;
this.color = color;
}
int getColor() { return color; }
@Override
public String toString() {
return coordinateList.toString();
}
List<Point> getPoints() { return coordinateList; }
int size() { return coordinateList.size(); }
@Override
public boolean equals(Object p){
if (p == this) { return true; }
if (p == null) { return false;}
if (!(p instanceof Path)) {return false; }
Path path = (Path)p;
return getPoints().containsAll(path.getPoints())
&& path.getPoints().containsAll(getPoints());
}
}
推荐阅读
- mysql - MYSQL - 错误代码：1415。不允许从函数返回结果集。存储函数尝试
- python - 不同模型在超参数调整时对 RNN 模型进行增量拟合
- http - nginx sent_http 标头变量不真实
- node.js - 使用带有 symfony 的 nodeJS 服务器
- dart - Dart/WebStorm“取消 dart.async.StreamSubscription 的实例”
- speech-to-text - 如何禁用 Google Cloud Speech to Text API 的不流畅移除功能
- java - 在 Java 中创建新构造函数的问题
- perl - Custom Storable hooks for dclone-ing a light-weight object referencing a heavy-weight object
- javascript - 动态表输入值计算
- xamarin.forms - 如何创建多个初始屏幕取决于条件 xamarin 形式？