I am trying to implement a A* algorithm for solve a sliding puzzle, but I can´t make the algorithm work, I have been working on this for the last few days but honestly I don´t know what's happen now. I have been following the pseudo-code from the Wikipedia and "RedBlobGame" blogs but now I'm completely lost.
This is de A* Algorithm
ArrayList<Node> open = new ArrayList<Node>();
ArrayList<Node> closed = new ArrayList<Node>();
Node goal = new Node(myBoard.getGoalBoard());
Node start = new Node(mb);
start.setH(this.heuristic.calculate(start, goal));
start.setG(0);
start.setDepth(0);
open.add(start);
Node current = null;
while(!open.isEmpty() && !myBoard.stopAlgorithm){
current = getLowest(open);
if(current.isGoal()){
System.out.println("done");
return finalise(current.getBoard(), displaySearch, current.getDepth());
}
open.remove(current);
closed.add(current);
int depth = current.getDepth() + 1;
ArrayList<Node> succesors = current.getSuccessors(depth);
for(Node node: succesors){
node.setH(this.heuristic.calculate(node, goal));
node.setG(current.getG() + 1);
node.setParent(current);
if(!closed.contains(node)){
if(!open.contains(node)){
open.add(node);
}else{
Node openN = open.get(open.indexOf(node));
if(node.getG() < openN.getG()){
openN.setG(node.getG());
openN.setParent(node.getParent());
}
}
}
}
}
System.out.println("path not finded");
return null;
Sometimes they find the solution and other times, just keep looking and expanding more possibles states, I can't see where is the problem. Any help on this?
This is the code from the Node class http://pastie.org/10521788 and the the calculus for the heuristic (manhattan in this case) http://pastie.org/10521789
It is just a guess. It has been a while since I coded A* and I can't see how you implemented the node class. I don't think you should set G with node.setG(current.getG()+1) or set the parent to current if node is already added to the open list.
try :
int depth = current.getDepth() + 1;
ArrayList<Node> succesors = current.getSuccessors(depth);
for (Node node : succesors) {
if (!closed.contains(node) && !open.contains(node)) {
node.setH(this.heuristic.calculate(node, goal));
node.setG(current.getG() + 1);
node.setParent(current);
open.add(node);
}
}
This is a more complete version that seems to work for me (only tested with 3 x 3. Most of the code is just setting up the state. Somethings to note: For efficiency you don't want to have to search a list to see if a state is contained in it. It is better to use a HashSet but that requires implementing hashCode() and equals() consistently. Your IDE can probably generate them.
public static class BoardState {
int positions[];
private int priority;
/**
* Get the value of priority
*
* @return the value of priority
*/
public int getPriority() {
return priority;
}
/**
* Set the value of priority
*
* @param priority new value of priority
*/
public void setPriority(int priority) {
this.priority = priority;
}
private int distFromGoal;
/**
* Get the value of distFromGoal
*
* @return the value of distFromGoal
*/
public int getDistFromGoal() {
return distFromGoal;
}
/**
* Set the value of distFromGoal
*
* @param distFromGoal new value of distFromGoal
*/
public void setDistFromGoal(int distFromGoal) {
this.distFromGoal = distFromGoal;
}
private BoardState goal;
/**
* Get the value of goal
*
* @return the value of goal
*/
public BoardState getGoal() {
return goal;
}
/**
* Set the value of goal
*
* @param goal new value of goal
*/
public void setGoal(BoardState goal) {
this.goal = goal;
}
private int depth;
/**
* Get the value of depth
*
* @return the value of depth
*/
public int getDepth() {
return depth;
}
/**
* Set the value of depth
*
* @param depth new value of depth
*/
public void setDepth(int depth) {
this.depth = depth;
}
private BoardState prev;
/**
* Get the value of prev
*
* @return the value of prev
*/
public BoardState getPrev() {
return prev;
}
/**
* Set the value of prev
*
* @param prev new value of prev
*/
public void setPrev(BoardState prev) {
this.prev = prev;
}
public BoardState(BoardState other) {
this.positions = new int[9];
System.arraycopy(other.positions, 0, this.positions, 0, positions.length);
this.depth = other.depth + 1;
this.goal = other.goal;
this.prev = other;
}
private BoardState() {
}
public static BoardState goal() {
List<Integer> l = new ArrayList<Integer>();
IntStream.range(0, 9).forEach(i -> l.add(i));
BoardState r = new BoardState();
r.positions = new int[9];
Arrays.setAll(r.positions, i -> l.get(i).intValue());
return r;
}
public static BoardState random() {
List<Integer> l = new ArrayList<Integer>();
IntStream.range(0, 9).forEach(i -> l.add(i));
Collections.shuffle(l);
BoardState r = new BoardState();
r.positions = new int[9];
Arrays.setAll(r.positions, i -> l.get(i).intValue());
return r;
}
@Override
public int hashCode() {
int hash = 7;
hash = 83 * hash + Arrays.hashCode(this.positions);
return hash;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final BoardState other = (BoardState) obj;
if (!Arrays.equals(this.positions, other.positions)) {
return false;
}
return true;
}
int valueAt(int r, int c) {
int pos = r * 3 + c;
for (int i = 0; i < positions.length; i++) {
if (pos == positions[i]) {
return i;
}
}
throw new RuntimeException("invalid board or position");
}
void print() {
System.out.println("depth = " + depth);
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 3; c++) {
System.out.print(this.valueAt(r, c) + "\t");
}
System.out.println("");
}
}
int distance(BoardState other) {
int dist = 0;
for (int i = 0; i < positions.length; i++) {
int c0 = this.positions[i] % 3;
int r0 = this.positions[i] / 3;
int c1 = other.positions[i] % 3;
int r1 = other.positions[i] / 3;
dist += Math.abs(r0 - r1) + Math.abs(c0 - c1);
}
return dist;
}
public List<BoardState> moves() {
List<BoardState> newList = new ArrayList<>();
int r0 = this.positions[0] / 3;
int c0 = this.positions[0] % 3;
if (r0 > 0) {
BoardState up = new BoardState(this);
up.positions[0] = (r0 - 1) * 3 + c0;
for (int i = 1; i < 9; i++) {
if (this.positions[i] == up.positions[0]) {
up.positions[i] = this.positions[0];
break;
}
}
newList.add(up);
}
if (r0 < 2) {
BoardState down = new BoardState(this);
down.positions[0] = (r0 + 1) * 3 + c0;
for (int i = 1; i < 9; i++) {
if (this.positions[i] == down.positions[0]) {
down.positions[i] = this.positions[0];
break;
}
}
newList.add(down);
}
if (c0 > 0) {
BoardState left = new BoardState(this);
left.positions[0] = r0 * 3 + (c0 - 1);
for (int i = 1; i < 9; i++) {
if (this.positions[i] == left.positions[0]) {
left.positions[i] = this.positions[0];
break;
}
}
newList.add(left);
}
if (c0 < 2) {
BoardState right = new BoardState(this);
right.positions[0] = r0 * 3 + (c0 + 1);
for (int i = 1; i < 9; i++) {
if (this.positions[i] == right.positions[0]) {
right.positions[i] = this.positions[0];
break;
}
}
newList.add(right);
}
for (BoardState move : newList) {
move.setDistFromGoal(move.distance(goal));
move.setPriority(move.distFromGoal + move.depth);
}
return newList;
}
}
The actual A* is relatively short:
BoardState goal = BoardState.goal();
System.out.println("goal");
goal.print();
BoardState start = BoardState.random();
System.out.println("start");
start.print();
start.setGoal(goal);
start.setDistFromGoal(start.distance(goal));
start.setPriority(start.distFromGoal + start.depth);
PriorityQueue<BoardState> open = new PriorityQueue<>(Comparator.comparing(b -> b.getPriority()));
open.offer(start);
Set<BoardState> set = new HashSet<>();
set.add(start);
int round = 0;
while (!open.isEmpty()) {
BoardState cur = open.poll();
round++;
if (cur.equals(goal)) {
System.out.println("goal found after " + round + " rounds");
System.out.println("printing boards in reverse order");
do {
cur.print();
} while (null != (cur = cur.getPrev()));
break;
}
for (BoardState move : cur.moves()) {
if (!set.contains(move)) {
set.add(move);
open.offer(move);
}
}
}