项目三基于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;
    }

项目实现及结果分析

开始页面展示：