所以我正在开发这个 3x3 游戏，你会得到一个当前状态，例如：
1 5 6
3 7 乙
2 8 4
并且您希望达到以下目标状态：
乙 1 2
3 4 5
6 7 8
因此，我在下面发布的代码中编写了所有其他方法。我现在遇到的问题是我实际的 A* 搜索。我想使用两种启发式方法，一种检查有多少块在错误的位置（例如，启发式函数将显示当前状态有 H=8 块在错误的位置），另一种启发式方法将计算多远总和是（所以对于我目前的状态，第一块是 1 移动，第二块是 3 移动，等等。所有这些的总和将是我的 H 值）。所以我把我的记录gameBoard在一个字符串数组中。
所以现在我的实际问题。除了我的 A* 之外的所有东西现在都在工作，如下所示。
首先，我调用setFinalGoalState()which 生成变量finalGoalState，以便我可以将当前状态与目标状态进行比较。
然后我制作一个priorityQueue应该是ArrayLists的一个Node，其中每个节点都有一个 G 值（G 是它在树中的距离）、H 值、对父级的引用和当前状态。
所以首先我调用一个初始huesticOneHValue()值来获取我的第一个状态的 H 值。然后我为“h1”运行一个if语句（这只是我的第一个启发式方法，我说过我稍后会添加另一个）。然后它应该创建一个初始节点Root，这将是我在树中的第一个节点，并将其添加到优先级队列中。
然后它应该通过优先级队列。它将当前节点作为 中的第一个元素priorityQueue，然后将其从队列中删除。它将我的实际设置为与当前节点gameBoard相同的状态。gameBoard然后它会创建一个ArrayList可能的移动（这会调用isValidMoves()，它会检查您是否真的可以向上、向下、向左或向右移动，然后将其放入列表中）。然后我创建一个 for 循环来遍历我可能移动的大小，然后通过调用该move()方法进行实际移动（所以第一次调用int i = 0将调用 move “up”，因为你可以在我当前的状态下将 b 向上移动）然后它应该创建一个Node包含gValue我在哪里（它应该等于 1），新的 H 值（在某些情况下这可能保持不变，但它应该努力降低 H 值），它的父级（我认为应该只是currentNode？），然后的状态currentNode（板子的样子）。
然后下一个 for 循环检查它应该将它放在优先级队列中的哪个位置。具有较小g+h值的节点应该排在队列的前面，因为我们想先检查它们是否达到目标状态。所以我设置了一个初始条件，如果队列为空，则将其添加到前面，否则它检查priorityQueueatj是否大于g+h子项，如果是，则将子项添加到j（以及其他所有内容）的索引中我认为应该转移过去吗？）最后，在所有移动完成后，它会检查priorityQueue' 的前端节点的状态是否等于我们的目标状态，如果不是，它会返回到 while 循环的前面并再次运行。
我认为最终我用我的节点搞砸了一些东西。当我运行调试时，我发现每次创建一个子节点时，父节点的状态都会更新为子节点的状态，这不应该发生，因为子节点应该是父节点的某个移动（向上，向下，向左，或对）。我想我搞砸了一些东西，要么是我的节点类，要么是我创建节点并将它们添加到队列中的方式。当我尝试将我的孩子添加到priorityQueueat
else if((priorityQueue.get(j).getG()+priorityQueue.get(j).getH()) > (child.getG()+child.getH())){
我的其余代码如下：
八拼图班
public class EightPuzzle{
static String[][] gameBoard = new String[3][3];
static String[][] finalGoalState = new String[3][3];
static int[] bLocation = new int[2];
String board;
String dir;
/*public void ReadFromTxt(String file) throws FileNotFoundException, IOException {
String read;
FileReader f = new FileReader(file);
int i = 0;
int j;
BufferedReader b = new BufferedReader(f);
System.out.println("Loading puzzle from file...");
while((read = b.readLine())!=null){
if(read.length()==3){
for(j=0;j<3;j++){
board[i][j] = (int)(read.charAt(j)-48);
}
}
i++;
}
b.close();
System.out.println("Puzzle loaded!");
}*/
public void setState(String board){
gameBoard[0][0] = board.substring(0,1);
gameBoard[0][1] = board.substring(1,2);
gameBoard[0][2] = board.substring(2,3);
gameBoard[1][0] = board.substring(4,5);
gameBoard[1][1] = board.substring(5,6);
gameBoard[1][2] = board.substring(6,7);
gameBoard[2][0] = board.substring(8,9);
gameBoard[2][1] = board.substring(9,10);
gameBoard[2][2] = board.substring(10,11);
System.out.println(Arrays.deepToString(gameBoard));
}
public static void setFinalGoalState(){
finalGoalState[0][0] = "b";
finalGoalState[0][1] = "1";
finalGoalState[0][2] = "2";
finalGoalState[1][0] = "3";
finalGoalState[1][1] = "4";
finalGoalState[1][2] = "5";
finalGoalState[2][0] = "6";
finalGoalState[2][1] = "7";
finalGoalState[2][2] = "8";
}
public static void setGoalState(){
gameBoard[0][0] = "b";
gameBoard[0][1] = "1";
gameBoard[0][2] = "2";
gameBoard[1][0] = "3";
gameBoard[1][1] = "4";
gameBoard[1][2] = "5";
gameBoard[2][0] = "6";
gameBoard[2][1] = "7";
gameBoard[2][2] = "8";
bLocation[0] = 0;
bLocation[1] = 0;
}
public void randomizeState(int numMoves){
setGoalState();
for(int i=0;i<numMoves;i++){
ArrayList<String> validMoves3 = isValidMove();
Random r = new Random();
int mIndex = r.nextInt(validMoves3.size());
String choice = validMoves3.get(mIndex);
move(choice);
System.out.println(Arrays.deepToString(gameBoard));
}
}
public ArrayList<String> isValidMove(){
ArrayList<String> validMoves = new ArrayList<String>();
if(bLocation[0] != 0){
//can move up
validMoves.add("up");
}
if(bLocation[0] != 2){
//can move down
validMoves.add("down");
}
if(bLocation[1] != 0){
//can move left
validMoves.add("left");
}
if(bLocation[1] != 2){
//can move right
validMoves.add("right");
}
return validMoves;
}
public void move(String dir){
ArrayList<String> validMoves2 = isValidMove();
if(validMoves2.contains("up") && dir.equals("up")){
String temp1 = new String();
temp1 = gameBoard[bLocation[0]-1][bLocation[1]];
gameBoard[bLocation[0]][bLocation[1]] = temp1;
gameBoard[bLocation[0]-1][bLocation[1]] = "b";
bLocation[0] = bLocation[0]-1;
}
else if(validMoves2.contains("down") && dir.equals("down")){
String temp2 = new String();
temp2 = gameBoard[bLocation[0]+1][bLocation[1]];
gameBoard[bLocation[0]][bLocation[1]] = temp2;
gameBoard[bLocation[0]+1][bLocation[1]] = "b";
bLocation[0] = bLocation[0]+1;
}
else if(validMoves2.contains("left") && dir.equals("left")){
String temp3 = new String();
temp3 = gameBoard[bLocation[0]][bLocation[1]-1];
gameBoard[bLocation[0]][bLocation[1]] = temp3;
gameBoard[bLocation[0]][bLocation[1]-1] = "b";
bLocation[1] = bLocation[1]-1;
}
else if(validMoves2.contains("right") && dir.equals("right")){
String temp4 = new String();
temp4 = gameBoard[bLocation[0]][bLocation[1]+1];
gameBoard[bLocation[0]][bLocation[1]] = temp4;
gameBoard[bLocation[0]][bLocation[1]+1] = "b";
bLocation[1] = bLocation[1]+1;
}
}
public static void printState(){
System.out.println(Arrays.deepToString(gameBoard));
}
public void getbLocation(){
for(int i=0; i<gameBoard.length; i++){
for(int j=0; j<gameBoard[i].length; j++){
if(gameBoard[i][j].equals("b"))
{
bLocation[0] = i;
bLocation[1] = j;
break;
}
}
}
System.out.println(Arrays.toString(bLocation));
}
public int heuristicOneHValue(){
int hValue = 0;
if(!gameBoard[0][0].equals("b")){
hValue++;
}
if(!gameBoard[0][1].equals("1")){
hValue++;
}
if(!gameBoard[0][2].equals("2")){
hValue++;
}
if(!gameBoard[1][0].equals("3")){
hValue++;
}
if(!gameBoard[1][1].equals("4")){
hValue++;
}
if(!gameBoard[1][2].equals("5")){
hValue++;
}
if(!gameBoard[2][0].equals("6")){
hValue++;
}
if(!gameBoard[2][1].equals("7")){
hValue++;
}
if(!gameBoard[2][2].equals("8")){
hValue++;
}
return hValue;
}
public void solveAstar(String heuristic){
setFinalGoalState();
ArrayList<Node> priorityQueue = new ArrayList<Node>();
int h = heuristicOneHValue();
if(heuristic.equalsIgnoreCase("h1"))
{
Node root = new Node(0,h,null,gameBoard);
priorityQueue.add(root);
while(priorityQueue != null){
Node currentNode = priorityQueue.get(0);
priorityQueue.remove(0);
gameBoard = currentNode.state;
ArrayList<String> moves = isValidMove();
for(int i = 0; i < moves.size(); i++){
move(moves.get(i));
Node child = new Node(currentNode.getG(),heuristicOneHValue(),currentNode,currentNode.getState());
for(int j = 0; j <= priorityQueue.size(); j++){
if(priorityQueue.size() == 0){
priorityQueue.add(0, child);
}
else if((priorityQueue.get(j).getG()+priorityQueue.get(j).getH()) > (child.getG()+child.getH())){
priorityQueue.add(j, child);
}
}
}
if(priorityQueue.get(0).getState() == finalGoalState){
priorityQueue = null;
}
}
}
//h2 here
}
public static void main (String[]args){
EightPuzzle b1=new EightPuzzle();
b1.setState("156 37b 284");
b1.getbLocation();
b1.solveAstar("h1");
}
}
节点类
class Node {
public String[][] state;
public Node parent;
public int g;
public int h;
public Node(int g, int h, Node parent, String[][] state){
this.g = g;
this.h = h;
this.parent = parent;
this.state = state;
}
public String[][] getState(){
return state;
}
public int getG(){;
return g;
}
public int getH(){
return h;
}
public Node getParent(){
return parent;
}
public void setState(String[][] state){
this.state = state;
}
public void setG(int g){
this.g = g;
}
public void setH(int h){
this.h = h;
}
public void setParent(Node parent){
this.parent = parent;
}
}