滑动积木块游戏设计 ——A*算法的应用

深藏阁楼爱情的钟 2022-08-18 14:16 139阅读 0赞

滑动积木块游戏设计— —A\*算法的应用

# 主题： #

1. 滑动积木快游戏：一个盒子中有七个格子，里面放了黑色，白色两种木块，三个黑色在左边，三个白色在右边，最右边一个格子空着；

2. 游戏规则：每一个木块可以跳到相邻的空格中，也可以最多跳过相邻的两个木块到达空格，游戏中将所有白色木块跳到黑色木块左边为成功；

3. 游戏目标：求最小步数。

# 设计思路： #

1. 根据初始棋局状态，找出所有可能的下一次走步；

2. 根据游戏规则，找出最适合的下一次走步，移动木块；

3. 重复前面两步，直到游戏结束。

# 模块化  1. SIZE：设置积木块数量，默认为3，即白色和黑色的木块各有3个，盒子有7格；   如果积木块数量为4，则白色和黑色的木块各有4个，盒子有9格；   2. gn：寻找最有走法时路径耗散值，有两个规则：   a) 一个木块移入相邻空格，耗散值为1；   b) 一个木块相邻一个或两个其他木块跳入空格，耗散值为跳过的木块数；   3. hn：计算出的当前状态的评估函数，值为每个白色木块前的黑色木块的数目的和；   4. status：是一个数组，大小为2\*SIZE+1，数组的值：1：黑色木块，-1：白色木块，0：空格；   5. PrintStatus：在一行上打印当前的棋局状态，耗散值以及评估函数；   6. SetCurrentStatus：将输入的数组赋值给status；   7. SetDisspativeValue：将输入的值加到gn上；   8. SetEvaluationFunction：根据当前的status，计算得到棋局当前的评估函数，赋值给hn；   9. 两个Status构造函数，无值的默认构造Status对象，需要传值的调用前面三个函数构造Status对象；   10. main函数用于测试。  ![Center][]      11. end：根据当前状态，查找得到下一步可能的走不的空格所在位编号；   12. start：查找得到的下一步要移动的木块的位置编号。    13. Move：默认构造函数，什么也不干；  ![Center 1][]   14. CalDissipasiveValue：根据当前走步计算路径耗散值；   15. GetNextMoves：根据当前格局，寻找下一步可能的所有走步，所有走步保存在List表中；   16. GetNextStatus：根据所有走步的情况，找出所有可能的Status状态；   17. GetBestNextStatus：调用前面两个函数，找出所有可能的Status，然后比较其中fn最小的，作为当前走步，下一步计算在这步的基础上（fn = gn = hn）。  ![Center 2][]   18. 此处显示了滑动积木快游戏的Main函数，在其中实现了对初始状态的初始化，利用前面类的对象的属性和方法，找出实现滑动积木快游戏的最有走步，我们的目标完成。 #

# 结果： #

# 见下面截图： #

![Center 3][]

# 源代码： #

1. 测试主类 AppMain：

package ai.ouc.g2;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class AppMain {
    	public static void main(String args[]){
    		//首先创建一个棋局作为初始棋局
    		int[] s = {1,1,1,-1,-1,-1,0};
    		int i = 0;
    		Status firstStat = new Status(s,0);
    		Move move = new Move();		
    		List<Status> statList = new ArrayList<Status>();
    		
    		statList.add(i++,firstStat);
    		Status curStat1,curStat2,printStat;
    		
    		do {
    			curStat2 = statList.get(i-1);
    			curStat1 = move.GetBestNextStatus(curStat2);
    			statList.add(i++, curStat1);
    		}while (curStat1.hn != 0);
    		
    		System.out.println("在下面打印走步：");
    		System.out.println("	        棋局状态          		                  耗散值     	               评估函数");
    		for (int j = 0;j < statList.size();j++){
    			printStat = statList.get(j);
    			printStat.PrintStatus();
    		}
    	}
    }

2.Move类：

package ai.ouc.g2;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    public class Move {
    	public Move(){
    		
    	}
    	private List<boxMove> GetNextMoves(Status stat){
    		int empty = 0;	//记录空格的位置
    		int i,j;	//用于计数的变量
    		int counter = 0;	//计算积木块走步的数量
    		
    		List<boxMove> moveList = new ArrayList<boxMove>();
    		
    		for (i = 0;i < stat.status.length;i++){
    			if (stat.status[i] == 0)
    				empty = i;	//找到空格位置
    		}
    		
    		for (j = empty-3;j <= empty+3;j++){
    			if (j >= 0 && j < Status.SIZE*2+1 && j != empty)
    				moveList.add(counter++,new boxMove(j,empty));
    		}
    		return moveList;
    	}	//根据当前棋局状态，找到下一步可能的boxMove
    	private List<Status> GetNextStatus(List<boxMove> move,Status stat){
    		int g1,g2,temp;	//用于计算耗散值
    		g1 = stat.gn;
    		int[] s;
    		boxMove pmove = new boxMove();
    		List<Status> availableStat = new ArrayList<Status>();
    		for (int i = 0;i < move.size();i++){
    			pmove = move.get(i);
    			g2 = this.CalDissipativeValue(pmove.start, pmove.end);
    			s = Arrays.copyOf(stat.status, stat.status.length);
    			temp = s[pmove.start];
    			s[pmove.start] = s[pmove.end];
    			s[pmove.end] = temp;
    			availableStat.add(i, new Status(s,g1+g2));
    		}
    		return availableStat;
    	}
    	public Status GetBestNextStatus(Status stat){		
    		List<boxMove> moveList = new ArrayList<boxMove>();
    		List<Status> statList;
    		Status nextStat;
    		
    		moveList = this.GetNextMoves(stat);
    		statList = this.GetNextStatus(moveList, stat);
    		
    		//在此处计算下一步选择哪个状态，即选择走步
    		nextStat = statList.get(0);
    		Status pstat;
    		for (int j = 1;j < statList.size();j++){//有问题
    			pstat = statList.get(j);
    			if ((nextStat.gn + nextStat.hn) > (pstat.gn + pstat.hn)){
    				nextStat = statList.get(j);
    			}
    		}
    		return nextStat;
    	}	//根据走步boxMove的值，从中找到fn = gn +hn 最小的走步
    	private int CalDissipativeValue(int st, int en) {
    		// TODO Auto-generated method stub
    		int gn = 1;
    		if ((Math.abs(st-en) == 1) && (Math.abs(st-en) == 2))
    			gn = 1;
    		else if (Math.abs(st-en) == 3)
    			gn = 2;
    		return gn;
    	}	//CalDissipativeValue,计算路径耗散值
    	public static void main(String args[]){
    		int g = 3;
    		int[] s = {-1,1,-1,1,1,-1,0};
    		Status stat = new Status(s,g);
    		Status nextStat1,nextStat2;
    		Move mov = new Move();
    		nextStat1 = mov.GetBestNextStatus(stat);
    		nextStat2 = mov.GetBestNextStatus(nextStat1);
    		
    		System.out.println("在下面打印走步：");
    		System.out.println("	        棋局状态          		                  耗散值     	               评估函数");
    		stat.PrintStatus();
    		nextStat1.PrintStatus();
    		System.out.println("第二次走步：");
    		nextStat1.PrintStatus();
    		nextStat2.PrintStatus();
    	}
    }

3. Status类：

package ai.ouc.g2;
    
    public class Status {
    	
    	public static int SIZE = 3;		//通过修改SIZE的大小，可以实现不同规格的滑动积木块游戏
    	
    	int status[] = new int[SIZE*2+1];	//当前格局，1：黑块，-1：白块，0：空格
    	
    	int gn;		//累计路径耗散值(Dissipative value)
    	int hn;		//评价函数(Evaluation function)
    	
    	public Status(int[] s,int g){
    		if (s.length != SIZE*2+1)
    			System.out.println("Wrong input!");
    		else{
    			this.SetCurrentStatus(s);
    			this.SetDissipativeValue(g);
    			this.SetEvaluationFunction();
    		}
    	}
    	public Status(){
    		
    	}
    	private void SetCurrentStatus(int status[]){
    		this.status = status;
    	}
    	private void SetDissipativeValue(int g){
    		this.gn += g;
    	}
    	private void SetEvaluationFunction(){
    		this.hn = 0;
    		for (int i = 0;i < this.status.length;i++){
    			if (this.status[i] == -1){
    				for (int j = i;j >= 0;j--){
    					if (this.status[j] == 1)
    						this.hn++; 
    				}
    			}
    		}
    	}//评估函数的值是当前格局中每个白块前面黑块数目的和
    	
    	public void PrintStatus(){
    		for (int i = 0;i < this.status.length;i++){
    			if (this.status[i] == 1)
    				System.out.print("（黑）");
    			else if (this.status[i] == -1)
    				System.out.print("（白）");
    			else
    				System.out.print("（空）");
    		}
    		System.out.print("		" + this.gn);
    		System.out.println("		" + this.hn);		
    	}
    	public static void main(String args[]){
    		int g = 3;
    		int[] s = {1,-1,1,-1,-1,1,0};
    		Status stat = new Status(s,g);
    		
    		for (int i = 0;i < stat.status.length;i++){
    			if (stat.status[i] == 1)
    				System.out.print("（黑）");
    			else if (stat.status[i] == -1)
    				System.out.print("（白）");
    			else
    				System.out.print("（空）");
    		}
    		System.out.println();
    		System.out.println("耗散值：" + stat.gn);
    		System.out.println("评估函数：" + stat.hn);		
    		
    		//stat.ChangeStatus(3, 6);
    		for (int i = 0;i < stat.status.length;i++){
    			if (stat.status[i] == 1)
    				System.out.print("（黑）");
    			else if (stat.status[i] == -1)
    				System.out.print("（白）");
    			else
    				System.out.print("（空）");
    		}
    		System.out.println();
    		System.out.println("耗散值：" + stat.gn);
    		System.out.println("评估函数：" + stat.hn);	
    	}
    }

4.boxMove类：

package ai.ouc.g2;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class boxMove {
    	int start;
    	int end;
    	public boxMove(int st,int en){
    		this.start = st;
    		this.end = en;
    	}
    	public boxMove(){
    		
    	}
    	public static void main(String args[]){
    		List<boxMove> moveList = new ArrayList<boxMove>();
    		moveList.add(0, new boxMove(2,0));
    		moveList.add(1, new boxMove(3,0));
    		moveList.add(2, new boxMove(4,0));
    		moveList.add(3, new boxMove(5,0));
    		moveList.add(4, new boxMove(6,0));
    		
    		for (int i = 0;i < moveList.size();i++) {
    			boxMove m = moveList.get(i);
    			System.out.println(" ( " + m.start + " , " + m.end + " ) ");
    		}
    	}
    }

[Center]: https://img-blog.csdn.net/20151223194606248?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 1]: https://img-blog.csdn.net/20151223194707593?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 2]: /images/20220731/e56dff922f5d4ccb94db5f9a47f7c30c.png
[Center 3]: /images/20220731/f814ca003c15444da07c979bcae98114.png