Swing写的老鼠走迷宫游戏，mvc含最佳路径算法

 

 如图：

寻找路径关键代码：堆栈实现非递归实现的最佳路径算法。

package maze;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

public class PathFinder
{
	private final Log log = LogFactory.getLog(getClass());
    private maze.GameMap map=null;
    private int[][]  array=new int[8][8];;
    public final static int LOAD_PATH=50;
    public final static int div_BEGAIN=100;
    public PathFinder(GameMap map)
    {
        this.map=map;
        //copy地图数据到自己的数组中去
        for (int i = 0; i < 8; i++) 
        {
            for (int j = 0; j < 8; j++)
            {
                array[i][j]=map.arr[i][j];
            }
        }
    }
    /**
     * 从起点出发递归涂颜色给能够到达的通道填上数值，以100为基数。
     * 比如如果被填上107就说明距离起点7最短可以到达。
     * @param x
     * @param y
     * @param div
     */
    
    public void render(int x,int y,int div)
    {
        System.out.println(x+"__"+y+"__"+div);
    	log.info("渲染坐标"+x+"__"+y+"__"+"层次"+div);
       //如果填到终点回退。
        if(x==7&&y==7)
        {
            array[y][x]=div;
            return; 
        }
            
        //没有越界就填值
        if(x>=0&&y>=0&&x<=map.arr.length-1&&y<=map.arr.length-1&&array[y][x]!=map.BLOCK)
        {
            
                array[y][x]=div;
        }
        
        // down
        if(y+1<=map.arr.length-1&&array[y+1][x]!=map.BLOCK)
        {
            if(array[y+1][x]>(div+1)||array[y+1][x]<100)
            render(x,y+1,div+1);
        }
        //left 
        if(x-1>=0&&array[y][x-1]!=map.BLOCK)
        {
            if(array[y][x-1]>(div+1)||array[y][x-1]<100)
            render(x-1,y,div+1);
        }
        //right
         if(x+1<=map.arr.length-1&&array[y][x+1]!=map.BLOCK)
        {
             if(array[y][x+1]>(div+1)||array[y][x+1]<100)
            render(x+1,y,div+1);
        }
         //up
        if(y-1>=0&&array[y-1][x]!=map.BLOCK)
        {
            if(array[y-1][x]>(div+1)||array[y-1][x]<100)
            render(x,y-1,div+1);
        }
    }
    
    /***
     * 从终点出发寻找到起点的路径，非递归实现，以堆栈作为数据结构。
     * @return
     */
    public List<Point> FindPath()
    {
    	render(0, 0, this.div_BEGAIN);
    	
    	Stack<Point> stack=new Stack<Point>();
    	List<Point> list=new ArrayList<Point>();
    	stack.add(new Point(7,7));
    	while(!stack.empty())
    	{
    		Point p=stack.pop();
    		int value=this.array[p.getY()][p.getX()];
    		//left
    		if(p.getX()-1>=0&&array[p.getY()][p.getX()-1]==(value-1))
    		{
    			stack.push(new Point(p.getX()-1,p.getY()));
    			list.add(new Point(p.getX()-1,p.getY()));
    		}
    		//right
    		if(p.getX()+1<map.arr.length&&array[p.getY()][p.getX()+1]==(value-1))
    		{
    			stack.push(new Point(p.getX()+1,p.getY()));
    			list.add(new Point(p.getX()+1,p.getY()));
    		}
    		//up
    		if(p.getY()-1>=0&&array[p.getY()-1][p.getX()]==(value-1))
    		{
    			stack.push(new Point(p.getX(),p.getY()-1));
    			list.add(new Point(p.getX(),p.getY()-1));
    		}
    		//down
    		if(p.getY()+1<map.arr.length&&array[p.getY()+1][p.getX()]==(value-1))
    		{
    			stack.push(new Point(p.getX(),p.getY()+1));
    			list.add(new Point(p.getX(),p.getY()+1));
    		}
    	}
    	return list;
    }
}

 

实习期间写的小程序，没别的意思，只是不想把代码放到发霉，欢迎拍砖。

代码在附近里面。自行加个日志jar包就可以运行。

 

 

评论

2 楼 武安y 2014-06-20  

kANKAN

1 楼 pywepe 2011-05-17  

我都用log4j