pot.java

使用启发式算法编写的推箱子游戏,有图形界面,可以自动演示最优步骤

/*
 * Author: ruanjue
 * Created: 06/08/2004 21:01:45
 * Modified: 06/08/2004 21:01:45
 */
package boxman;

import java.util.*;
import javax.swing.*;
public class Pot extends Thread
{
	ArrayList vector=null;
	int[] set=null;
	int index_set=0;
	int[] indexs;
	boolean RUNNING=false;
	public Pot(int[] dat,byte[] path){
		vector=new ArrayList();
		set=new int[multi(9)];
		Arrays.fill(set,Main.NONE_VALUE);
		indexs=copy(dat);
		Data data=new Data(indexs,path);
		vector.add(data);
		index_set=0;
		set[index_set++]=data.getNum();
	}
	public static int[] copy(int[] dat){
		int[] indexs=new int[dat.length];
		for(int i=0;i<indexs.length;i++){
			indexs[i]=dat[i];
		}
		return indexs;
	}
	public static int multi(int n){
		int t=1;
		for(int i=1;i<=n;i++){
			t*=i;
		}
		return t;
	}
	public boolean getStatus(){
		return RUNNING;
	}
	public void shutDown(){
		RUNNING=false;
		vector.clear();
	}
	public void run(){
		RUNNING=true;
		int counter=0;
		while(RUNNING){
			int size=vector.size();
			int[] score=new int[size];
			int t=Integer.MAX_VALUE;
			for(int i=0;i<size&&RUNNING;i++){
				Data dat=(Data)vector.get(i);
				int s=dat.getScore();
				score[i]=s+dat.getLayer();
				if(s==0){
					t=0;
					score[i]=0;
				}
				else if(t>score[i]){
					t=score[i];
				}
			}
			if(t==0){
				for(int i=0;i<size;i++){
					if(score[i]==0){
						Data dat=(Data)vector.get(i);
						showArray(dat.getPath());
					}
				}
				break ;
			}
			int moved=0;
			for(int i=size-1;i>=0&&RUNNING;i--){
				if(t==score[i]){
					Data dat=(Data)vector.remove(i);
					Data[] childs=dat.getChilds();
					for(int j=0;j<childs.length;j++){
						int num=childs[j].getNum();
						if(!contains(num)){
							vector.add(childs[j]);
							set[index_set++]=num;
							moved++;
						}
					}
				}
			}
			counter++;
		}
		RUNNING=false;
	}
	public static void listArray(byte[] dat){
		for(int i=0;i<dat.length;i++){
			System.out.print(dat[i]+"\t");
		}
		System.out.println();
	}
	public static void printArray(int[] dat){
		for(int i=0;i<dat.length;i++){
			if(i%3==0){
				System.out.println();
			}
			System.out.print(dat[i]+"\t");
		}
		System.out.println();
	}
	public static void showArray(byte[] path){
		for(int i=0;i<path.length-1;i++){
			int option=JOptionPane.showConfirmDialog(null,"第【"+(i+1)+"】步: move "+path[i]+"\nDo you want to continue?");
			if(option==JOptionPane.NO_OPTION){
				break;
			}
		}
	}
	public boolean contains(int num){
		for(int i=0;i<index_set;i++){
			if(num==set[i]){
				return true;
			}
		}
		return false;
	}
	public static int getNum(int[] dat){
		int t=0;
		for(int i=0;i<dat.length;i++){
			t+=dat[i]*Math.pow(10,i);
		}
		return t;
	}
	public static int[] move(int[] data,int m){
		int[] dat=copy(data);
		int zero=Main.getRealIndex(dat,0);
		/*if(!Main.check(m,zero)){
			System.err.println("Can't Move!");
			return dat;
		}*/
		int t=dat[m];
		dat[m]=dat[zero];
		dat[zero]=t;
		return dat;
	}
}