利用不相交集类制作迷宫游戏(数据结构课程设计——迷宫老鼠)

  1. 云栖社区>
  2. 博客>
  3. 正文

利用不相交集类制作迷宫游戏(数据结构课程设计——迷宫老鼠)

mingchaosun 2015-04-19 11:25:00 浏览1084
展开阅读全文

之前大一的时候有几天闲来无事,为了学习做了一个可以自动生成迷宫,可以寻找最短路径的小游戏,现在整理分享一下

这里写图片描述

简单介绍:

利用不相交集类考虑一个迷宫的生成,一个简单算法就是从各处的墙壁开始(除入口和出口之外)。此时,不断地随机选择一面墙,如果被该墙分割的单元彼此不联通,那么就把这面墙拆掉。重复这个过程直到开始单元和终止单元联通,那么就得到一个迷宫。实际上不断的拆掉墙壁直到每个单元都可以从其他单元到达更好(这会使迷宫产生更多误导的路径)。

整理一下迷宫的生成算法就是:

(1)将迷宫初始时看成一个一个的Box,每个Box在都是只有一个元素的等价类;

(2)不断的随机选择一面墙,如果被该墙分割的单元彼此不通(不是一个等价类),那么拆掉该墙,
将墙两边的 等价类合并成一个等价类;

(3)如果左上角和右下角的方块属于同一个等价类,那么迷宫完成。

这里用于判断不同单元是否在同一集合的数据结构即为不相交集类。

等价类基本知识:

即我们要建立多个等价类,联通的元素放在同一个等价类里面。

对应的,需要两个操作:

  1. 将两个元素放到一个等价类里的话,采用union操作。

  2. 查找某个元素在哪个等价类里,采用find操作。根据find的返回值可以判断两个元素是否在一个等价类里。

可以用数组来记录,或者是vector。

举个例子看可能比较清楚:

假设元素ID刚开始为 0 1 2 3 4 5 6 7 8 9

建立相同大小的数组s,数组初始化值均为-1。

最直观的处理,比如union(4,5)即使s[5] = 4。(约定union(x,y)使得s[y]=x,效果是相同的)。

find(4)会直接返回4本身,因为s[4]<0。

而find(5)则递归调用,实际上为:find(5) = find(s[5]) = 4,因此判断出4,5属于同一个等价类(我觉得可以理解为4这个结点即为等价类的代表)。

find最坏情形运行时间为O(N),因为对N个元素,有可能建立一个深度为N-1的树。

因此对union和find操作都进行了改进。

另外:

为了控制树的深度,可以重写union的方式,比如unionBySize,unionByHeight,这里就不说了。此时find运行时间为O(N)。

对于find巧妙的改进是路径压缩,即当find(x)调用时,修改递归找到的结点直接指向等价类的代表结点,使得路径上的结点移近根结点,这样下次调用时就很快了。

这种数据结构实现起来很简单,每个例程只需要几行代码,而且可以使用一个简单的数组。

实现代码 :

迷宫生成以及寻找最短路径的算法部分:

package com.sdu.embeddedLab.MingchaoSun.pac_man.mapBuilder;


import java.util.Random;
import java.util.Stack;
public class Maze {
    private final static int dirUp = 0;
    private final static int dirRight = 1;
    private final static int dirDown = 2;
    private final static int dirLeft = 3;

    public  final  int gridWall = 1;
    public final  int gridEmpty = 0;
    public final  int gridBlind = -1;
    public final  int gridPath = 2;

    private int width;
    private int height;
    private MazePoint[][] matrix;
    public  int[][] maze;

    /*
     * constructor, initial width, height and matrix
     */
    public Maze(int width, int height) {
        this.width = width;
        this.height = height;
        this.matrix = new MazePoint[height][width];
        for (int i=0; i<height; i++)
            for (int j=0; j<width; j++)
                matrix[i][j] = new MazePoint();
        this.maze = new int[2*height+1][2*width+1];
    }

    /*
     * check if the target neighbor can be visited
     * if the target point is out of bounds, treat it as already visited
     */
    public boolean isNeighborOK(int x, int y, int dir) {
        boolean isNeighborVisited = false;
        switch ( dir ) {
        case dirUp:
            if ( x <= 0 )
                isNeighborVisited = true;
            else
                isNeighborVisited = matrix[x-1][y].isVisited();
            break;
        case dirRight:
            if ( y >= width - 1 )
                isNeighborVisited = true;
            else
                isNeighborVisited = matrix[x][y+1].isVisited();
            break;
        case dirDown:
            if ( x >= height - 1 )
                isNeighborVisited = true;
            else
                isNeighborVisited = matrix[x+1][y].isVisited();
            break;
        case dirLeft:
            if ( y <= 0 )
                isNeighborVisited = true;
            else
                isNeighborVisited = matrix[x][y-1].isVisited();
            break;
        }
        return !isNeighborVisited;
    }

    /*
     * check if the neighbors have at least one non-visited point
     */
    public boolean isNeighborOK(int x, int y) {
        return (this.isNeighborOK(x, y, dirUp) || this.isNeighborOK(x, y, dirRight) ||
                this.isNeighborOK(x, y, dirDown) || this.isNeighborOK(x, y, dirLeft));
    }

    /*
     * pick up a random traversal direction
     * loop until find a correct one
     */
    public int getRandomDir(int x, int y) {
        int dir = -1;
        Random rand = new Random();
        if ( isNeighborOK(x, y) ) {
            do {
                dir = rand.nextInt(4);
            } while ( !isNeighborOK(x, y, dir) );
        }
        return dir;
    }

    /*
     * push down the wall between the adjacent two points
     */
    public void pushWall(int x, int y, int dir) {
        switch ( dir ) {
        case dirUp:
            matrix[x][y].setWallUp(false);
            matrix[x-1][y].setWallDown(false);
            break;
        case dirRight:
            matrix[x][y].setWallRight(false);
            matrix[x][y+1].setWallLeft(false);
            break;
        case dirDown:
            matrix[x][y].setWallDown(false);
            matrix[x+1][y].setWallUp(false);
            break;
        case dirLeft:
            matrix[x][y].setWallLeft(false);
            matrix[x][y-1].setWallRight(false);
            break;
        }
    }

    /*
     * depth first search traversal
     */
    public void traversal() {
        int x = 0;
        int y = 0;
        Stack<Integer> stackX = new Stack<Integer>();
        Stack<Integer> stackY = new Stack<Integer>();
        do {
            MazePoint p = matrix[x][y];
            if ( !p.isVisited() ) {
                p.setVisited(true);
            }
            if ( isNeighborOK(x, y) ) {
                int dir = this.getRandomDir(x, y);
                this.pushWall(x, y, dir);
                stackX.add(x);
                stackY.add(y);
                switch ( dir ) {
                case dirUp:
                    x--;
                    break;
                case dirRight:
                    y++;
                    break;
                case dirDown:
                    x++;
                    break;
                case dirLeft:
                    y--;
                    break;
                }
            }
            else {
                x = stackX.pop();
                y = stackY.pop();
            }
        } while ( !stackX.isEmpty() );
    }

    /*
     * create the maze by the point matrix
     * only use the right wall and down wall of every point
     */
    public void create() {
        for (int j=0; j<2*width+1; j++)
            maze[0][j] = gridWall;
        for (int i=0; i<height; i++) {
            maze[2*i+1][0] = gridWall;
            for (int j=0; j<width; j++) {
                maze[2*i+1][2*j+1] = gridEmpty;
                if ( matrix[i][j].isWallRight() )
                    maze[2*i+1][2*j+2] = gridWall;
                else
                    maze[2*i+1][2*j+2] = gridEmpty;
            }
            maze[2*i+2][0] = 1;
            for (int j=0; j<width; j++) {
                if ( matrix[i][j].isWallDown() )
                    maze[2*i+2][2*j+1] = gridWall;
                else
                    maze[2*i+2][2*j+1] = gridEmpty;
                maze[2*i+2][2*j+2] = gridWall;
            }
        }
    }

    /*
     * print the matrix
     */
    public void print() {
        for (int i=0; i<2*height+1; i++) {
            for (int j=0; j<2*width+1; j++)
                if ( maze[i][j] == gridWall )
                    System.out.print("A");
                else if ( maze[i][j] == gridPath )
                    System.out.print(".");
                else
                    System.out.print(" ");
            System.out.println();
        }
    }

    /*
     * in the maze array, try to find a break out direction
     */
    public int getBreakOutDir(int x, int y) {
        int dir = -1;
        if ( maze[x][y+1] == 0 )
            dir = dirRight;
        else if ( maze[x+1][y] == 0 )
            dir = dirDown;
        else if ( maze[x][y-1] == 0 )
            dir = dirLeft;
        else if ( maze[x-1][y] == 0 )
            dir = dirUp;
        return dir;
    }

    /*
     * find the path from (1, 1) to (2*height-1, 2*width-1)
     */
    public void findPath() {
        int x = 1;
        int y = 1;
        Stack<Integer> stackX = new Stack<Integer>();
        Stack<Integer> stackY = new Stack<Integer>();
        do {
            int dir = this.getBreakOutDir(x, y);
            if ( dir == -1 ) {
                maze[x][y] = gridBlind;
                x = stackX.pop();
                y = stackY.pop();
            }
            else {
                maze[x][y] = gridPath;
                stackX.add(x);
                stackY.add(y);
                switch ( dir ) {
                case dirUp:
                    x--;
                    break;
                case dirRight:
                    y++;
                    break;
                case dirDown:
                    x++;
                    break;
                case dirLeft:
                    y--;
                    break;
                }
            }
        } while ( !(x == 2*height-1 && y == 2*width-1) );
        maze[x][y] = gridPath;
    }

    /*
     * remove all foot print in the maze
     */
    public void reset() {
        for (int i=0; i<2*height+1; i++)
            for (int j=0; j<2*width+1; j++)
                if ( maze[i][j] != gridWall )
                    maze[i][j] = gridEmpty;
    }

    /**
     * 迷宫测试
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Maze maze = new Maze(25, 25);
        maze.traversal();
        maze.create();
        System.out.println("Create a new map");
        maze.print();
        maze.findPath();
        System.out.println("Find path");
        maze.print();
        maze.reset();
        System.out.println("Reset the map");
        maze.print();
    }
}

package com.sdu.embeddedLab.MingchaoSun.pac_man.mapBuilder;


public class MazePoint {
    private boolean isVisited = false;
    private boolean wallUp = true;
    private boolean wallRight = true;
    private boolean wallDown = true;
    private boolean wallLeft = true;

    public boolean isVisited() {
        return isVisited;
    }
    public void setVisited(boolean isVisited) {
        this.isVisited = isVisited;
    }
    public boolean isWallUp() {
        return wallUp;
    }
    public void setWallUp(boolean wallUp) {
        this.wallUp = wallUp;
    }
    public boolean isWallRight() {
        return wallRight;
    }
    public void setWallRight(boolean wallRight) {
        this.wallRight = wallRight;
    }
    public boolean isWallDown() {
        return wallDown;
    }
    public void setWallDown(boolean wallDown) {
        this.wallDown = wallDown;
    }
    public boolean isWallLeft() {
        return wallLeft;
    }
    public void setWallLeft(boolean wallLeft) {
        this.wallLeft = wallLeft;
    }
}

java界面部分就不多说了,完整的代码下载地址:
http://download.csdn.net/detail/sunmc1204953974/8609239

原创文章,手写代码,转载请注明来源
http://blog.csdn.net/sunmc1204953974

网友评论

登录后评论
0/500
评论
mingchaosun
+ 关注