如果被包围，则形成路径的元素无效 [英] Invalidate an element forming a path if it is surrounded
本文介绍了如果被包围，则形成路径的元素无效的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我正在构建一个由单元格组成的 2D 网格游戏，玩家必须在其中放置标记并尝试包含(包围)对手的标记.现在每个单元格可以有 3 种状态:空、包含红色标记或包含蓝色标记.
I'm building a 2D grid game composed of cells in which players have to put tokens and try to contain (encircle) the opponent's tokens. Now each cell can have 3 states: empty, contains a red token or contains a blue token.
可以形成路径"的所有单元格都在一个列表中，沿着该路径我可以绘制经过单元格中心的线(多边形).还有一个包含标记的列表，被包围的标记，
All cells that can form a "path" are in a list, and along that path I can draw lines (polygons) passing by the center of cells. Also there is a list of contained tokens, the one being encircled,
现在我想找到一种方法来无效"一个被包围的令牌，这样它就可以被路径计算忽略
Now I want to find a way to "invalidate" an encircled token so it can be ignored by path calculations
参见以下示例:
- 蓝色标记首先被包围，它们不能与任何进一步的路径计算分开.
- 这是不允许的.先遏制，先赢.
以下所有代码均来自路径类:
All codes below are from the path class:
class Path extends Stack<int[]>{
private Token[][] grid;
//a path shorter than min can not surround any cell
private static final int MIN_PATH_LEGTH = 3;
//a collection of cells that has been tested
private ArrayList<int[]>checked;
//represents the cell where the search starts from
int[] origin;
//represents the token of the origin
Token originToken;
private int rows;
private int cols;
//represents the path bounds: min/max row/col in path
private int minPathRow, maxPathRow, minPathCol, maxPathCol;
Path(Token[][] grid){
this.grid = grid;
rows = grid.length;
cols = grid[0].length;
}
//search for a path
boolean findPath(int[] origin) {
this.origin = origin;
int row = origin[0] , col = origin[1];
//represents the token of the origin
originToken = grid[row][col];
//initialize list of checked items
checked = new CellsList();
boolean found = findPath(row, col);
if(found) {
printPath();
} else {
System.out.println("No path found");
}
return found;
}
//recursive method to find path. a cell is represented by its row, col
//returns true when path was found
private boolean findPath(int row, int col) {
//check if cell has the same token as origin
if(grid[row][col] != originToken) {
return false;
}
int[] cell = new int[] {row, col};
//check if this cell was tested before to avoid checking again
if(checked.contains(cell)) {
return false;
}
//get cells neighbors
CellsList neighbors = getNeighbors(row, col);
//check if solution found. If path size > min and cell
//neighbors contain the origin it means that path was found
if((size() >= MIN_PATH_LEGTH) && neighbors.contains(origin) ) {
add(cell);
return true;
}
//add cell to checked
checked.add(cell);
//add cell to path
add(cell);
//if path was not found check cell neighbors
for(int[] neighbor : neighbors ) {
boolean found = findPath(neighbor[0],neighbor[1]);
if(found) {
return true;
}
}
//path not found
pop(); //remove last element from stack
return false;
}
//use for testing
private void printPath() {
System.out.print("Path : " );
for(int[] cell : this) {
System.out.print(Arrays.toString(cell));
}
System.out.println("");
List<int[]> containedCells = getContainedWithin();
System.out.print(containedCells.size() +" cell contained : " );
for(int[] cell : containedCells) {
System.out.print(Arrays.toString(cell));
}
System.out.println("");
}
CellsList getPath() {
CellsList cl = new CellsList();
cl.addAll(this);
return cl;
}
}
下面的代码查找单元格的邻居(path.java):
The code below finds the neighbors of a cell (path.java):
//return a list of all neighbors of cell row, col
private CellsList getNeighbors(int row, int col) {
CellsList neighbors = new CellsList();
for (int colNum = col - 1 ; colNum <= (col + 1) ; colNum +=1 ) {
for (int rowNum = row - 1 ; rowNum <= (row + 1) ; rowNum +=1 ) {
if(!((colNum == col) && (rowNum == row))) {
if(isWithinGrid (rowNum, colNum ) ) {
neighbors.add( new int[] {rowNum, colNum});
}
}
}
}
return neighbors;
}
private boolean isWithinGrid(int colNum, int rowNum) {
if((colNum < 0) || (rowNum <0) ) {
return false;
}
if((colNum >= cols) || (rowNum >= rows)) {
return false;
}
return true;
}
}
下面的代码通过路径(所有包含或包围的标记)查找所有有界单元格，并且它们的标记与路径的颜色相反:
The below code finds all bounded cell by a path (all contained or encircled tokens) and their token is of the opposite color of the path:
List<int[]> getContainedWithin() {
//find path max and min X values, max and min Y values
minPathRow = grid[0].length; //set min to the largest possible value
maxPathCol = grid.length;
maxPathRow = 0; //set max to the largest possible value
maxPathCol = 0;
//find the actual min max x y values of the path
for (int[] cell : this) {
minPathRow = Math.min(minPathRow, cell[0]);
minPathCol = Math.min(minPathCol, cell[1]);
maxPathRow = Math.max(maxPathRow, cell[0]);
maxPathCol = Math.max(maxPathCol, cell[1]);
}
List<int[]> block = new ArrayList<>(25);
int[] cell = get(0);//get an arbitrary cell in the path
Token pathToken = grid[cell[0]][cell[1]]; //keep a reference to its token
//iterate over all cells within path x, y limits
for (int col = minPathCol; col < (maxPathCol); col++) {
for (int row = minPathRow; row < (maxPathRow); row++) {
//check cell color
Token token = grid[row][col];
if ((token == pathToken) || (token == Token.VIDE)) {
continue;
}
if (isWithinLoop(row,col)) {
block.add(new int[] {row, col});
}
}
}
return block;
}
//check if row, col represent a cell within path by checking if it has a
//path-cell to its left, right, top and bottom
private boolean isWithinLoop(int row, int col) {
if( isPathCellOnLeft(row, col)
&&
isPathCellOnRight(row, col)
&&
isPathCellOnTop(row, col)
&&
isPathCellOnBottom(row, col)
) {
return true;
}
return false;
}
}
如果你需要更多元素，现在就告诉我，我会更新必要的.
If you need more elements, just let me now, I'll update with the necessary.
推荐答案
这个要求意味着之前的路径，影响当前的路径计算.
可以通过多种方式实现.在当前程序结构中，最简单的方法是在所有路径中添加包含单元格的静态集合.
请参阅allContainedWithin 及其在代码中的使用方式.
另请注意，我将 getContainedWithin() 重构为 getter，并将其功能移至新方法 findContainedWithin().所有更改对其他类没有影响.
This requirement means that previous paths, affect current path calculations.
It can be achieved in many ways. The easiest, within current program structure could be adding a static collection of contained cells in all paths.
See allContainedWithin and the way it is used in the code.
Also note that I refactored getContainedWithin() to be a getter, and moved its functionality to a new method findContainedWithin().
All changes have no effect on other classes.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
//a stack representing cells in the path
//each cell represented by [row,col]
class Path extends Stack<int[]>{
private Token[][] grid;
//a path shorter than min can not surround any cell
private static final int MIN_PATH_LEGTH = 3;
//a collection of cells that has been tested
private ArrayList<int[]>checked;
//represents the cell where the search starts from
int[] origin;
//represents the token of the origin
Token originToken;
private int rows;
private int cols;
//represents the path bounds: min/max row/col in path
private int minPathRow, maxPathRow, minPathCol, maxPathCol;
//a collection of all cells that are bounded by the path
//and their token is of the opposite color of the path
private List<int[]> containedWithin;
//a STATIC collection that holds all containedWithin cells, of
//current and previous paths
private static CellsList allContainedWithin = new CellsList();
Path(Token[][] grid){
this.grid = grid;
rows = grid.length;
cols = grid[0].length;
}
//search for a path
boolean findPath(int[] origin) {
this.origin = origin;
int row = origin[0] , col = origin[1];
//represents the token of the origin
originToken = grid[row][col];
//initialize list of checked items
checked = new CellsList();
boolean found = findPath(row, col);
if(found) {
//find bounded cells
findContainedWithin();
//update the collection all
allContainedWithin.addAll(containedWithin);
printPath();
} else {
System.out.println("No path found");
}
return found;
}
//recursive method to find path. a cell is represented by its row, col
//returns true when path was found
private boolean findPath(int row, int col) {
//check if cell has the same token as origin
if(grid[row][col] != originToken) {
return false;
}
int[] cell = new int[] {row, col};
//check if this cell was tested before to avoid checking again
if(checked.contains(cell)) {
return false;
}
//check if this cell was contained in previously calculated paths
if(allContainedWithin.contains(cell)) {
return false;
}
//get cells neighbors
CellsList neighbors = getNeighbors(row, col);
//check if solution found. If path size > min and cell
//neighbors contain the origin it means that path was found
if((size() >= MIN_PATH_LEGTH) && neighbors.contains(origin) ) {
add(cell);
return true;
}
//add cell to checked
checked.add(cell);
//add cell to path
add(cell);
//if path was not found check cell neighbors
for(int[] neighbor : neighbors ) {
boolean found = findPath(neighbor[0],neighbor[1]);
if(found) {
return true;
}
}
//path not found
pop(); //remove last element from stack
return false;
}
//return a list of all neighbors of cell row, col
private CellsList getNeighbors(int row, int col) {
CellsList neighbors = new CellsList();
for (int colNum = col - 1 ; colNum <= (col + 1) ; colNum +=1 ) {
for (int rowNum = row - 1 ; rowNum <= (row + 1) ; rowNum +=1 ) {
if(!((colNum == col) && (rowNum == row))) {
if(isWithinGrid (rowNum, colNum ) ) {
neighbors.add( new int[] {rowNum, colNum});
}
}
}
}
return neighbors;
}
private boolean isWithinGrid(int colNum, int rowNum) {
if((colNum < 0) || (rowNum <0) ) {
return false;
}
if((colNum >= cols) || (rowNum >= rows)) {
return false;
}
return true;
}
//use for testing
private void printPath() {
System.out.print("Path : " );
for(int[] cell : this) {
System.out.print(Arrays.toString(cell));
}
System.out.println("");
List<int[]> containedCells = getContainedWithin();
System.out.print(containedCells.size()+" cell contained : " );
for(int[] cell : containedCells) {
System.out.print(Arrays.toString(cell));
}
System.out.println("");
}
CellsList getPath() {
CellsList cl = new CellsList();
cl.addAll(this);
return cl;
}
//finds all cells that are bounded by the path
//and their token is of the opposite color of the path
private void findContainedWithin() {
containedWithin = new ArrayList<>();
//find path max and min X values, max and min Y values
minPathRow = grid[0].length; //set min to the largest possible value
maxPathCol = grid.length;
maxPathRow = 0; //set max to the largest possible value
maxPathCol = 0;
//find the actual min max x y values of the path
for (int[] cell : this) {
minPathRow = Math.min(minPathRow, cell[0]);
minPathCol = Math.min(minPathCol, cell[1]);
maxPathRow = Math.max(maxPathRow, cell[0]);
maxPathCol = Math.max(maxPathCol, cell[1]);
}
//todo remove after testing
System.out.println("x range: "+minPathRow + "-"
+ maxPathRow + " y range: " + minPathCol + "-" + maxPathCol);
int[] cell = get(0);//get an arbitrary cell in the path
Token pathToken = grid[cell[0]][cell[1]]; //keep a reference to its token
//iterate over all cells within path x, y limits
for (int col = minPathCol; col < (maxPathCol); col++) {
for (int row = minPathRow; row < (maxPathRow); row++) {
//check cell color
Token token = grid[row][col];
if ((token == pathToken) || (token == Token.VIDE)) {
continue;
}
if (isWithinLoop(row,col)) {
containedWithin.add(new int[] {row, col});
}
}
}
}
//returns a collection of all cells that are bounded by the path
//and their token is of the opposite color of the path
List<int[]> getContainedWithin() {
return containedWithin;
}
//check if row, col represent a cell with in path by checking if it has a
//path-cell to its left, right, top and bottom
private boolean isWithinLoop(int row, int col) {
if( isPathCellOnLeft(row, col)
&&
isPathCellOnRight(row, col)
&&
isPathCellOnTop(row, col)
&&
isPathCellOnBottom(row, col)
) {
return true;
}
return false;
}
private boolean isPathCellOnLeft(int cellRow, int cellCol) {
for ( int col = minPathCol; col < cellCol ; col++) {
if(getPath().contains(new int[] {cellRow, col})) {
return true;
}
}
return false;
}
private boolean isPathCellOnRight(int cellRow, int cellCol) {
for ( int col = cellCol; col <= maxPathCol ; col++) {
if(getPath().contains(new int[] {cellRow, col})) {
return true;
}
}
return false;
}
private boolean isPathCellOnTop(int cellRow, int cellCol) {
for ( int row =minPathRow; row < cellRow ; row++) {
if(getPath().contains(new int[] {row, cellCol})) {
return true;
}
}
return false;
}
private boolean isPathCellOnBottom(int cellRow, int cellCol) {
for ( int row = cellRow; row <= maxPathRow; row++) {
if(getPath().contains(new int[] {row, cellCol})) {
return true;
}
}
return false;
}
}
请注意，我只运行了一些基本测试，例如:
Note that I only run some basic testing like :
这篇关于如果被包围，则形成路径的元素无效的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
