项目三基于A*搜索算法迷宫游戏开发-创新互联

项目三 基于A*搜索算法迷宫游戏开发

随机生成一个迷宫,并求解迷宫
玩家可以自行求解

超过10年行业经验,技术领先,服务至上的经营模式,全靠网络和口碑获得客户,为自己降低成本,也就是为客户降低成本。到目前业务范围包括了:成都网站制作、成都网站设计,成都网站推广,成都网站优化,整体网络托管,小程序定制开发,微信开发,APP应用开发,同时也可以让客户的网站和网络营销和我们一样获得订单和生意!项目目标和主要内容

1)迷宫游戏是非常经典的游戏,在该题中要求随机生成一个迷宫,并求解迷宫;
2)要求游戏支持玩家走迷宫,和系统走迷宫路径两种模式。玩家走迷宫,通过键盘方向键控制,并在行走路径上留下痕迹;
3)系统走迷宫路径要求基于A*算法实现,输出走迷宫的最优路径并显示。
4)设计交互友好的游戏图形界面。

项目总体框架

总体框架

关键算法分析

深度优先遍历生成迷宫:

void createMaze() {//将当前格压入栈
    path.push(cur);
    while(!path.empty()) {ArrayListmNei=notVisitedNei(cur);
        if(mNei.size()==0){//如果该格子没有可访问的邻接格,则跳回上一个格子
            cur = path.pop();
            continue;
        }
        //随机选取一个邻接格(并且在地图内)
        next = mNei.get(new Random().nextInt(mNei.size()));
        int x = next.x;
        int y = next.y;
        //如果该节点被访问过,则回到上一步继续寻找
        if(visit[x][y]){cur = path.pop();
        }
        //否则将当前格压入栈,标记当前格为已访问,并且在迷宫地图上移除障碍物
        else{path.push(next);
            visit[x][y] = true;
            mMap[x][y] = road;
            //打通当前格与下一格
            //打通墙,将墙的位置改换定义为路
            mMap[(cur.x + x) / 2][(cur.y + y) / 2] = road;
            //当前格等于下一格
            cur = next;
        }
    }
    //设置入口
    mMap[start.x-1][start.y]=1;
    //设置出口
    mMap[end.x+1][end.y]=1;
}

A*搜索算法求解迷宫:

public Node findPath(Node startNode, Node endNode) {openList.add(startNode);// 把起点加入 open list

        while (openList.size() >0) {Node currentNode = findMinFNodeInOpenList();// 遍历 open list ,查找F值最小的节点,把它作为当前要处理的节点
            //如果open list为空,寻路失败,找不到到达终点的路径(也就是迷宫没有路可以到达)
            openList.remove(currentNode);// 将刚刚F最小的那个点从open list中移除
            closeList.add(currentNode);// 把这个节点移到 close list

            ArrayListneighborNodes = findNeighborNodes(currentNode);//寻找邻居节点(4个中寻找)
            for (Node node : neighborNodes) {if (exists(openList, node)) {//如果邻居节点在open列表中
                    foundPoint(currentNode, node);//更新列表中父节点和估价函数信息
                } else {notFoundPoint(currentNode, endNode, node);//如果邻居节点不在open列表中,则将该点加入open列表中
                }
            }
//如果终点加入到了open list中,此时路径已经找到,从终点开始,每个方格沿着父节点移动直至起点,这就是最优路径
            if (find(openList, endNode) != null) {//如果找到尾节点,则返回尾节点
                return find(openList, endNode);
            }
        }

        // return find(openList, endNode);
        return null;
    }
项目实现及结果分析

开始页面展示:
开始页面

游戏界面展示:
游戏界面1
游戏界面2

结束界面展示:
结束界面

无法用图片展现的功能:
玩家按下空格键可以显示A*算法求解路线

实验总结

1.利用深度优先算法生产迷宫地图
2.利用A*算法求解迷宫

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


分享标题:项目三基于A*搜索算法迷宫游戏开发-创新互联
文章源于:http://pwwzsj.com/article/djjcgj.html