| cwl157 |
Sep 17th, 2007 3:48 PM |
data tree for A* algorithm
I have to make a program that can solve the 8 puzzle game using A* algorithm. I understand the algorithm and everything i just cant figure out how to make the tree. I have a class called GridNode that has all the methods for manipulating the node, mainly moving the 0 left, up right or down. I have to make a tree that can have anywhere from 0 - 4 children per node for the 4 different states, left, up right or down. Each node is a 2-d int array. I know that to have more than 2 children you just create one child and then it has siblings. Then i thought that since i know its a max 4 children, i could store them in an array. I have been trying to get this for 3 days and am not really any farther today then i was 3 days ago. I've drawn about 5 pages worth of tree pictures with the nodes and all that and children and siblings and everything and can still not make the connection. Can someone please help me figure out how to make a tree in java? Thanks. I know i'm gonna need a method that starts at the root and goes through the entire tree and im gonna need to create the children nodes and somehow keep track of where i am in the tree. Also, in the GridNode class are methods to check to make sure that to move left, up, right, or down is valid.
Here is the GridNode class that has all the methods for manipulating the 2-d array that makes up each state.
:
import java.io.*;
public class GridNode
{
private int[][] initialState = {{7, 6, 4},
{8, 5, 2},
{1, 0, 3}
};
private int[][] goalState = {{7, 2, 6},
{8, 0, 4},
{1, 5, 3}
};
private int[][] state = {{1, 0, 2},
{3, 4, 5},
{6, 7, 8}
};
public GridNode firstChild;
public GridNode nextSibling;
public GridNode(int[][] newState)
{
state = newState;
firstChild = null;
nextSibling = null;
} // end GridNode constructor
// get current state
public int[][] getState()
{
return state;
} // end getState
// get goal state
public int[][] getGoalState()
{
return goalState;
} // end getGoalState
// get initial state
public int[][] getInitialState()
{
return initialState;
} // end getInitialState
public void setFirstChild(GridNode newFirstChild)
{
firstChild = newFirstChild;
} // end setFirstChild
public void setNextSibling(GridNode newNextSibling)
{
nextSibling = newNextSibling;
} // end setNextSibling
// print the current state
public void printNode(int[][] state)
{
for(int row = 0; row < 3; row++)
{
for(int col = 0; col < 3; col++)
System.out.print(state[row][col] + " ");
System.out.println();
} // end for
} // end printNode
// check to see if current state is equal to the goal state
public boolean isEqual(int[][] state, int[][] goalState)
{
for (int row = 0; row < 3; row++)
{
for (int col = 0; col < 3; col++)
{
if (state[row][col] == goalState[row][col])
continue;
else
return false;
} // end for
} // end for
return true;
} // end isEqual
// calculates h1(n)
public int findHone(int[][] state, int[][] goalState)
{
int hOne = 0;
for (int row = 0; row < 3; row++)
{
for (int col = 0; col < 3; col++)
{
if (state[row][col] != goalState[row][col] && state[row][col] != 0)
hOne++;
else
continue;
} // end for
} // end for
return hOne;
} // end findHone
// check to see if it can move left
public boolean canMoveLeft(int[][] state)
{
int tempPos = -1;
for (int row = 0; row < 3; row++)
{
for (int col = 0; col < 3; col++)
{
if (state[row][col] == 0)
tempPos = col;
} // end for
} // end for
if (tempPos == 0)
return false;
else
return true;
} // end canMoveLeft
// check to see if it can move up
public boolean canMoveUp(int[][] state)
{
int tempPos = -1;
for (int row = 0; row < 3; row++)
{
for (int col = 0; col < 3; col++)
{
if (state[row][col] == 0)
tempPos = row;
} // end for
} // end for
if (tempPos == 0)
return false;
else
return true;
} // end canMoveUp
// check to see if it can move right
public boolean canMoveRight(int[][] state)
{
int tempPos = -1;
for (int row = 0; row < 3; row++)
{
for (int col = 0; col < 3; col++)
{
if (state[row][col] == 0)
tempPos = col;
} // end for
} // end for
if (tempPos == 2)
return false;
else
return true;
} // end canMoveRight
// check to see if it can move down
public boolean canMoveDown(int[][] state)
{
int tempPos = -1;
for (int row = 0; row < 3; row++)
{
for (int col = 0; col < 3; col++)
{
if (state[row][col] == 0)
tempPos = row;
} // end for
} // end for
if (tempPos == 2)
return false;
else
return true;
} // end canMoveDown
// move it left, the old one
public void moveLeft(int[][] state)
{
for (int row = 0; row < 3; row++)
{
for (int col = 0; col < 3; col++)
{
if (state[row][col] == 0)
{
state[row][col] = state[row][col-1];
state[row][col-1] = 0;
//printNode();
return;
} // end if
} // end for
} // end for
} // end moveLeft
// move it Up
public void moveUp(int[][] state)
{
for (int row = 0; row < 3; row++)
{
for (int col = 0; col < 3; col++)
{
if (state[row][col] == 0)
{
state[row][col] = state[row-1][col];
state[row-1][col] = 0;
// printNode(state);
return;
} // end if
} // end for
} // end for
} // end moveUp
// move it right
public void moveRight(int[][] state)
{
for (int row = 0; row < 3; row++)
{
for (int col = 0; col < 3; col++)
{
if (state[row][col] == 0)
{
state[row][col] = state[row][col+1];
state[row][col+1] = 0;
// printNode(state);
return;
} // end if
} // end for
} // end for
} // end moveRight
// move it down
public void moveDown(int[][] state)
{
//int tempPos = -1;
for (int row = 0; row < 3; row++)
{
for (int col = 0; col < 3; col++)
{
if (state[row][col] == 0)
{
state[row][col] = state[row+1][col];
state[row+1][col] = 0;
// printNode(state);
return;
} // end if
} // end for
} // end for
} // end moveDown
} // end GridNode
|
