启发函数suggestFunc计算所有棋子到目标位置的距离，又称为曼哈顿距离。
import java.applet.Applet;
import java.awt.*;
import java.awt.Graphics;
import java.util.Vector;
public class EightNumber extends Applet implements Runnable
{
private class State
{
int[] states = new int[9];
int size;
int steps;
public State(int [] s)
{
int i;
for(i=0;i<9;i++)
states[i] = s[i];
}
public boolean equals(State st)
{
int[] s=st.getStates();
int i;
for(i=0;i<9;i++)
if(s[i] != states[i])
return false;
return true;
}
public int judgeMove(State st)
{
int[] s=st.getStates();
int i;
for(i=0;i<9;i++)
{
if(s[i] != states[i] && s[i]!=0)
return i;
}
return -1;
}
public int[] getStates()
{
return states;
}
public int expandSize()
{
if(states[4] == 0)
size = 4;
else if(states[0]==0 || states[2]==0 || states[6]==0 || states[8]==0)
size = 2;
else
size = 3;
return size;
}
public State[] expandState()
{
State[] st;
int [] ex=new int[9];
int i,j,k;
int m=0,n=0;
int a=0,b=0;
st = new State[size];
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
k = i*3+j;
ex[k] = states[k];
if(states[k] == 0)
{
m = i;
n = j;
}
}
}
i = 0;
a = m*3+n;
if(m-1>=0)
{
b = (m-1)*3+n;
ex[a] = ex[b];
ex[b] = 0;
st[i] = new State(ex);
ex[b] = ex[a];
ex[a] = 0;
i++;
}
if(m+1<=2)
{
b = (m+1)*3+n;
ex[a] = ex[b];
ex[b] = 0;
st[i] = new State(ex);
ex[b] = ex[a];
ex[a] = 0;
i++;
}
if(n-1>=0)
{
b = m*3+(n-1);
ex[a] = ex[b];
ex[b] = 0;
st[i] = new State(ex);
ex[b] = ex[a];
ex[a] = 0;
i++;
}
if(n+1<=2)
{
b = m*3+(n+1);
ex[a] = ex[b];
ex[b] = 0;
st[i] = new State(ex);
ex[b] = ex[a];
ex[a] = 0;
i++;
}
return st;
}
}
Image[] stateImg = new Image[10];
Image[] moveImg = new Image[10];
Image stepsImg;
Vector vecClose = new Vector();//记录下已经扩展的节点
Vector vecOpen = new Vector();//记录下未扩展的节点
int[] first = {7,2,4,5,0,6,8,3,1};
int[] aim = {0,1,2,3,4,5,6,7,8};
State nowState = null;
State aimState = new State(aim);
int stepX;
int stepY;
int startX;
int startY;
int steps;
int move;
boolean start;
Thread moveTh = null;
public void init()
{
int i;
Integer tmp;
String fileName;
State st = new State(first);
st.steps = 0;
resize(200,300);
startX = 16;
startY = 19;
stepX = 55;
stepY = 55;
steps = 0;
start = false;
move = -1;
for(i=0;i<10;i++)
{
tmp = new Integer(i);
fileName = "img/";
fileName = fileName + tmp.toString()+"_1.gif";
stateImg[i] = getImage(getCodeBase(),fileName);
waitForImage(stateImg[i]);
fileName = "img/";
fileName = fileName + tmp.toString() + "_2.gif";
moveImg[i] = getImage(getCodeBase(),fileName);
waitForImage(stepsImg);
}
vecOpen.add(st);
fileName = "img/steps.gif";
stepsImg = getImage(getCodeBase(),"img/steps.gif");
waitForImage(stepsImg);
}
public void waitForImage(Image i)
{
MediaTracker tracker = new MediaTracker(this);
try
{
tracker.addImage(i,0);
tracker.waitForID(0);
}
catch(InterruptedException e) {System.err.println("Wait interrupted.");}
}
public void paint(Graphics g)
{
int i,j,k;
int[] state;
Integer tmp;
if(start == false)
return ;
state = nowState.getStates();
g.drawImage(stepsImg,startX+20,startY,this);
tmp = new Integer(steps);
g.drawString(tmp.toString(),startX+80,startY+20);
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
k = i*3+j;
if(move == k)
{
putNumber(g,state[k],i,j,false);
}
else
{
putNumber(g,state[k],i,j,true);
}
}
}
}
public void update(Graphics g)
{
paint(g);
}
private void putNumber(Graphics g,int number,int i,int j,boolean isState )
{
int x,y;
x = startX + j*stepX;
y = startY + i*stepY + stepY;
if(isState)
{
g.drawImage(stateImg[number],x,y,this);
}
else
{
g.drawImage(moveImg[number],
（本文已被浏览 次） | | |
相关评论
