我已经研究了 2 个小时，但我一生都无法找出为什么这个方法返回无限循环。我知道这种实现在效率方面并不是最好的，任何建议也都很好:)
驱动程序.java
import java.util.Scanner;
public class Driver {
static Board b;
public static void main(String[] args){
while(init()){
init();
}
System.out.println("Thanks for testing out the A* program");
}
private static boolean init(){
System.out.println("Would you like to play? (\"y\",\"n\")");
Scanner s = new Scanner(System.in);
String input = s.nextLine();
if(!input.equals("y")){
return false;
}
b = new Board(3,3);
System.out.print(b.toString());
while(getStartValue() == false){
getStartValue();
}
while(getDestinationValue() == false){
getDestinationValue();
}
System.out.print(b.toString());
b.setHValueAllNodes();
b.createPath(b.getStartPosition());
System.out.print(b.toString());
return true;
}
private static boolean getStartValue() {
Scanner s = new Scanner(System.in);
System.out.println("Please enter a starting X position");
int startX = s.nextInt();
System.out.println("Please enter a starting Y position");
int startY = s.nextInt();
if(b.getBoard()[startX][startY].getStatus() == 'X'){
System.out.println("Please enter a position that is not an obstacle");
return false;
}
else{
b.getBoard()[startX][startY].setStatus('S');
b.setStartPosition(startX, startY);
return true;
}
}
private static boolean getDestinationValue() {
Scanner s = new Scanner(System.in);
System.out.println("Please enter an ending X position");
int endX = s.nextInt();
System.out.println("Please enter a ending Y position");
int endY = s.nextInt();
if(b.getBoard()[endX][endY].getStatus() == 'X'){
System.out.println("Please enter a position that is not an obstacle");
return false;
}
else if(b.getBoard()[endX][endY].getStatus() == 'S'){
System.out.println("Please enter a postition that is not the starting value");
return false;
}
else{
b.getBoard()[endX][endY].setStatus('E');
b.setEndPosition(endX, endY);
return true;
}
}
}
Node.java
public class Node {
private int x;
private int y;
//Controls if transversable
private char status;
//f = g+h
private int f;
private int g;
private int h;
private Node parent;
Node(char status, int x, int y){
this.status = status;
this.x = x;
this.y = y;
this.g=0;
this.h=0;
this.f=0;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
public char getStatus() {
return status;
}
public void setStatus(char status) {
this.status = status;
}
public int getF() {
return f;
}
public void setF(int f) {
this.f = f;
}
public int getG() {
return g;
}
public void setG(int g) {
this.g = g;
}
public int getH() {
return h;
}
public void setH(int h) {
this.h = h;
}
public Node getParent() {
return parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
@Override
public String toString() {
if(this.getStatus() == 'O'){
return "O (" + this.getX() + ", " + this.getY() + ", " + this.getH() + ", " + this.getG() + ", " +this.getF() + ")";
}
else if(this.getStatus() == 'S'){
return "S (" + this.getX() + ", " + this.getY() + ")";
}
else if(this.getStatus() == 'E'){
return "E (" + this.getX() + ", " + this.getY() + ")";
}
else{
return "X (" + this.getX() + ", " + this.getY() + ")";
}
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if( !(obj instanceof Node)) return false;
Node nodeObj = (Node) obj;
return (nodeObj.getX() == this.getX() && nodeObj.getY() == this.getY());
}
}
Board.java
import java.util.ArrayList;
import java.util.Random;
public class Board {
private int length;
private int width;
private Node[][] board;
private ArrayList<Node> openList = new ArrayList<>();
private ArrayList<Node> closedList = new ArrayList<>();
private Node startPosition;
private Node endPosition;
public Node[][] getBoard() {
return board;
}
public void setBoard(Node[][] board) {
this.board = board;
}
Board(int length, int width){
board = new Node[length][width];
Random rand = new Random();
for(int row=0; row < board.length; row++){
for(int col=0; col < board[row].length; col++){
int randomNum = rand.nextInt(10);
if(randomNum == 0){
board[row][col] = new Node('X',row,col);
}
else{
board[row][col] = new Node('O',row,col);
}
}
}
}
public Node getStartPosition() {
return this.startPosition;
}
public void setStartPosition(int x, int y) {
board[x][y].setStatus('S');
board[x][y].setParent(null);
startPosition = new Node('S', x, y);
}
public Node getEndPosition() {
return endPosition;
}
public void setEndPosition(int x, int y) {
board[x][y].setStatus('E');
endPosition = new Node('E', x, y);
}
public void setHValueAllNodes(){
for(int row=0; row < board.length; row++){
for(int col=0; col < board[row].length; col++){
int xDistance = Math.abs(endPosition.getX() - board[row][col].getX());
int yDistance = Math.abs(endPosition.getY() - board[row][col].getY());
board[row][col].setH(xDistance + yDistance);
}
}
}
public void createPath(Node n){
Node minimum;
System.out.println("RUNNING WITH NODE " + n.getX() + n.getY());
//1. Add the starting square to open list
if(n.getStatus() == 'S'){
openList.add(n);
}
//d1. Stop when the open list is empty
if(openList.isEmpty() ){
return;
}
//d4. Add the target square to the closed list
if(n.equals(endPosition)){
return;
}
//2a. Find lowest F score in our list
int index = 0;
int indexMin = 0;
minimum = openList.get(0);
for(Node node: openList){
if(node.getF() < minimum.getF()){
minimum = node;
indexMin = index;
}
index++;
}
//2b. Switch minimum node to closed list
//Remove node from openlist
openList.remove(indexMin);
//Add to close list
closedList.add(minimum);
//c. For each of the 8 squares adjacent to this square
addToOpenList(minimum);
createPath(minimum);
System.out.println("OUR OPEN LIST CONTAINS: ");
for(Node n1 : openList){
System.out.print("X: " + n1.getX() + "Y: " + n1.getY());
}
System.out.println("OUR CLOSED LIST CONTAINS: ");
for(Node n2 : closedList){
System.out.print("X: " + n2.getX() + "Y: " + n2.getY());
}
System.out.println();
}
private void addToOpenList(Node n) {
boolean inClosedList = false;
boolean inOpenList = false;
for(int i= -1; i < 2; i++){
for(int j = -1; j < 2; j++){
inClosedList = false;
inOpenList = false;
//c1. If it is not walkable or it is in closed list ignore it
int xPos = n.getX() + i;
int yPos = n.getY() + j;
if(xPos == -1 || yPos == -1){
System.out.println("OUR NODE IS OUT OF BOUNDS: " + "X: " + xPos + "Y: " + yPos);
}
else{
for(Node node : closedList){
if(node.equals(board[xPos][yPos])){
inClosedList = true;
System.out.println("OUR NODE IS IN THE CLOSED LIST: " + "X: " + xPos + "Y: " + yPos);
}
}
if(inClosedList == false){
//c2. If it isnt on the open list, add it to the open list. Make the current square the parent of this square. Record F, G, H of the square
System.out.println("OUR NODE IS NOTTTTTTTT IN THE CLOSED LIST: " + "X: " + xPos + "Y: " + yPos);
int gCounter = (i + j == 1)? 10 : 14;
int g = n.getG() + gCounter;
int f = g + board[xPos][yPos].getH();
for(Node node1 : openList){
System.out.println("OUR NODE IN FOR LOOP: " + "X: " + xPos + "Y: " + yPos);
if(node1.equals(board[xPos][yPos])){
System.out.println("OUR NODE IS IN THE OPEN LIST: " + "X: " + xPos + "Y: " + yPos);
inOpenList = true;
//c3.If it is in the open list already, check to see if this path to the square is better, using g cost as the measure
if(g < board[xPos][yPos].getG()){
board[xPos][yPos].setG(g);
board[xPos][yPos].setF(f);
board[xPos][yPos].setParent(n);
}
}
}
if(inOpenList == false){
System.out.println("WE ARE HERE WITH" + "X: " + xPos + "Y: " + yPos);
board[xPos][yPos].setG(g);
board[xPos][yPos].setF(f);
board[xPos][yPos].setParent(n);
openList.add(board[xPos][yPos]);
}
}
}
}
}
}
@Override
public String toString() {
String output = "";
for(int row=0; row < board.length; row++){
for(int col=0; col < board[row].length; col++){
output += board[row][col].toString() + "\t";
}
output += "\n";
}
return output;
}
}
乍一看有两个错误，我不知道我的建议在语义上是否正确。
错误：
错误：
while(init()){
init();
}
右：
while(init());
错误：
while(getStartValue() == false){
getStartValue();
}
while(getDestinationValue() == false){
getDestinationValue();
}
右：
while(!getStartValue());
while(!getDestinationValue());
问题实际上出在我的 createPath 类中......
我递归地调用 createPath，而不是执行 while 循环检查打开列表是否为空。