迷宫生成算法 prime,实现自动走迷宫

本贴最后更新于 1680 天前,其中的信息可能已经时过境迁

从学习迷宫生成算法开始的。程序运行起来的样子:

GitHub 地址 :GitHub

show.gif

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cstdio>
#include<bits/stdc++.h>
#include <windows.h>
#include <tchar.h>
#include <SDKDDKVer.h>
#include<conio.h>
using namespace std;
#define MAZE_MAX 1000
int mz[MAZE_MAX+2][MAZE_MAX+2];
int hs[MAZE_MAX+2][MAZE_MAX+2];
int Move[MAZE_MAX+2][MAZE_MAX+2];
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
int vis[MAZE_MAX];
int fa[MAZE_MAX];
int X = 12, Y = X;
void make_path();
struct node{
    int x,y;
};
struct node f[MAZE_MAX+2],ppk,endd;
int cnt=0;
void gotoxy(int x, int y){
    HANDLE handle = GetStdHandle(STD_OUTPUT_HANDLE);
    COORD pos;
    pos.X = x;
    pos.Y = y;
    SetConsoleCursorPosition(handle, pos);
}
void hideCursor(){
    CONSOLE_CURSOR_INFO cursor_info = { 1, 0 };
    SetConsoleCursorInfo(GetStdHandle(STD_OUTPUT_HANDLE), &cursor_info);
}
void Print_Maze()
{
    printf("使用w,s,a,d移动,Esc退出\n");
    printf("当前迷宫大小:%d\n",X );
    for(int i=0; i<=X; i++){
        for(int j=0;j<=X;j++){
            if(mz[i][j]){
                printf("%s","▉");
              }
              else  if(Move[i][j]==1){
                  printf("%s","※");
                }
              else  if(i==1&&j==1){
                  printf("%s","起");
                }
             else if(i==X-1&&j==Y-1){
                  printf("%s","终");
              }
              else if(i==ppk.x&&j==ppk.y){
                 printf("人");
             }
              else{
                  printf("%s","  ");
              }
        }
        printf("\n");
    }
}
void updata_Maze(){
    hideCursor();
    gotoxy(0, 7);
    Print_Maze();
}
void Init_Maze(){
    cnt=0;
    for(int i=0;i<=X;i++){
        for(int j=0;j<=Y;j++){
            Move[i][j]=0;
            if(i==0||j==0||j==Y||i==X)
                hs[i][j]=-2;//墙壁为1
            else
                hs[i][j]=-1;//能打通的路为-1
            if(i==0||i==X||j==0||j==Y||(i%2==0)||(j%2==0)){
                  mz[i][j]=1;//
            }
            else{
                node tp;
                tp.x=i,tp.y=j;
                hs[i][j]=cnt;
                fa[cnt]=cnt;
                f[cnt++]=tp;
            }
        }
    }
    endd=f[cnt-1];
}
int find(int x){
    while(fa[x]!=x) x=fa[x];
    return x;
}
int merge(int x,int y){
    int f1=find(x);
    int f2=find(y);
    if(f1<f2) fa[f2]=f1;
    else if(f1>f2) fa[f1]=f2;
    else return 0;
    return 1;
}
int check_wall(int x,int y){
    if(x<=0||x>=X||y>=Y||y<=0){
        return 1;
    }
    return 0;
}
int check_choke(int x,int y){//检查是否全是阻塞的
    if(mz[x+1][y]==1 && mz[x-1][y]==1 &&mz[x][y+1]==1 &&mz[x][y-1]==1){
        return 1;
    }
    return 0;
}
void make_path(){
    srand(time(NULL));
    for(int p=0;p<cnt*8;p++){
        if(find(0)==find(cnt-1)){
            return ;
        }
        int road=vis[p%cnt];
        int next=rand()%4;
        int x=f[road].x,y=f[road].y;
        if(check_choke(x,y)){
            for(int i=0;i<4;i++){
                int cx=x+dir[next][0]*2,cy=y+dir[next][1]*2;
                int next_road=hs[cx][cy];
                if(!check_wall(cx,cy)){
                merge(road,next_road);
                mz[x+dir[next][0]][y+dir[next][1]]=0;
                }
            }
        }
        else{
            int cx=x+dir[next][0]*2,cy=y+dir[next][1]*2;
            int next_road=hs[cx][cy];
            if(!check_wall(cx,cy)){
                merge(road,next_road);
                mz[x+dir[next][0]][y+dir[next][1]]=0;
            }
        }
    }
    ppk=f[0];
}
void Init_list(){
    srand(time(NULL));
    for(int i=0;i<cnt;i++){
        vis[i]=i;
    }
    for(int i=0;i<cnt;i++){
        int a=rand()%cnt,b=rand()%cnt;
        swap(vis[a],vis[b]);
    }
}
int check_rode(int x,int y){
    return mz[x][y]==0 ? 1 : 0;
}  
void p_Move(){
    int ch;ppk=f[0];
    while (1){
        if(ppk.x==f[cnt-1].x&&ppk.y==f[cnt-1].y){
            printf("你赢了!\n");
            break;
        }
        updata_Maze();
        if(_kbhit()){//如果有按键按下,则_kbhit()函数返回真
            ch = _getch();//使用_getch()函数获取按下的键值
            if (ch == 27){
                break;
            }//当按下ESC时循环,ESC键的键值时27.
            else if(ch==119){// w
                if(check_rode(ppk.x-1,ppk.y))
                ppk.x--;
            }
            else if(ch==115){//s
                if(check_rode(ppk.x+1,ppk.y))
                ppk.x++;
            }
            else if(ch==97){//a
                if(check_rode(ppk.x,ppk.y-1))
                ppk.y--;
            }
            else if(ch==100){//d
                if(check_rode(ppk.x,ppk.y+1))
                ppk.y++;
            }
        }
    }
}
node step[MAZE_MAX];
int flag=0,walked[MAZE_MAX][MAZE_MAX];
void dfs_find_path(int stp,node now){
    if(flag) return ;
    if(now.x==endd.x&&now.y==endd.y){
        flag=1;
        printf("%s\n","走到了" );
        for(int i=0;i<stp;i++){
            Move[step[i].x][step[i].y]=1;
            updata_Maze();
        }
        return ;
    }
    node next_road;
    for(int i=0;i<4;i++){
        int cx=now.x+dir[i][0],cy=now.y+dir[i][1];
        if(check_rode(cx,cy)&&!walked[cx][cy]){
            walked[cx][cy]=1;
            next_road.x=step[stp].x=cx;
            next_road.y=step[stp].y=cy;
            dfs_find_path(stp+1,next_road);
            walked[cx][cy]=0;
        }
    }
}
void Print_hello(){
    hideCursor();
    gotoxy(0, 0);
    printf("--------------------------\n");
    printf("1:生成迷宫\n");
    printf("2:自己走\n");
    printf("3:电脑走\n");
    printf("4:设置大小\n");
    printf("5:退出\n");
    printf("--------------------------\n");
}
int begintime,endtime;
void menu1(){
    system("cls");
    begintime=clock();  //计时开始
    Init_Maze();//初始化迷宫
    Init_list();//生成一个个随机数列
    make_path();//生成迷宫
    updata_Maze();
    endtime = clock();  //计时结束
    printf(" 所用时间 :%8d ms", endtime-begintime);
}
void menu2(){
    begintime=clock();  //计时开始
    p_Move();//
    endtime = clock();  //计时结束
    printf(" 所用时间 :%8d ms", endtime-begintime);
}

void menu3(){
    begintime=clock();  //计时开始
    ppk=f[0];
    flag=0;
    walked[ppk.x][ppk.y]=1;
    dfs_find_path(1,ppk);
    endtime = clock();  //计时结束
    memset(Move,0,sizeof(Move));
    memset(walked,0,sizeof(walked));
    printf(" 所用时间 :%8d ms", endtime-begintime);
}
void menu4(){
    printf("\n请输入迷大小 :    ");
    scanf("%d",&X);X%2==1 ? X++ : 1;
    Y=X;
    menu1();
}
void MENU(){
    int ch;
    while (1){
        Print_hello();
        if(_kbhit()){//如果有按键按下,则_kbhit()函数返回真
            ch = _getch();//使用_getch()函数获取按下的键值
            if(ch==49){// w
                menu1();
            }
            else if(ch==50){
                menu2();
            }
            else if(ch==51){
                menu3();
            }
            else if(ch==52){//d
                menu4();
            }
            else if(ch==53){
                break;
            }
        }
    }
}
int main(){
    system("chcp 65001");
    system("mode con cols=220 lines=100");
    system("color 9");
    MENU();
    return 0;
}

  

  • C++

    C++ 是在 C 语言的基础上开发的一种通用编程语言,应用广泛。C++ 支持多种编程范式,面向对象编程、泛型编程和过程化编程。

    107 引用 • 153 回帖 • 3 关注
  • 游戏

    沉迷游戏伤身,强撸灰飞烟灭。

    176 引用 • 815 回帖
  • 迷宫
    1 引用
  • 算法
    428 引用 • 254 回帖 • 24 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • CloudFoundry

    Cloud Foundry 是 VMware 推出的业界第一个开源 PaaS 云平台,它支持多种框架、语言、运行时环境、云平台及应用服务,使开发人员能够在几秒钟内进行应用程序的部署和扩展,无需担心任何基础架构的问题。

    5 引用 • 18 回帖 • 164 关注
  • TGIF

    Thank God It's Friday! 感谢老天,总算到星期五啦!

    287 引用 • 4484 回帖 • 667 关注
  • Hexo

    Hexo 是一款快速、简洁且高效的博客框架,使用 Node.js 编写。

    21 引用 • 140 回帖 • 4 关注
  • JetBrains

    JetBrains 是一家捷克的软件开发公司,该公司位于捷克的布拉格,并在俄国的圣彼得堡及美国麻州波士顿都设有办公室,该公司最为人所熟知的产品是 Java 编程语言开发撰写时所用的集成开发环境:IntelliJ IDEA

    18 引用 • 54 回帖 • 2 关注
  • Node.js

    Node.js 是一个基于 Chrome JavaScript 运行时建立的平台, 用于方便地搭建响应速度快、易于扩展的网络应用。Node.js 使用事件驱动, 非阻塞 I/O 模型而得以轻量和高效。

    139 引用 • 269 回帖 • 48 关注
  • Shell

    Shell 脚本与 Windows/Dos 下的批处理相似,也就是用各类命令预先放入到一个文件中,方便一次性执行的一个程序文件,主要是方便管理员进行设置或者管理用的。但是它比 Windows 下的批处理更强大,比用其他编程程序编辑的程序效率更高,因为它使用了 Linux/Unix 下的命令。

    122 引用 • 73 回帖
  • 博客

    记录并分享人生的经历。

    273 引用 • 2388 回帖
  • Spring

    Spring 是一个开源框架,是于 2003 年兴起的一个轻量级的 Java 开发框架,由 Rod Johnson 在其著作《Expert One-On-One J2EE Development and Design》中阐述的部分理念和原型衍生而来。它是为了解决企业应用开发的复杂性而创建的。框架的主要优势之一就是其分层架构,分层架构允许使用者选择使用哪一个组件,同时为 JavaEE 应用程序开发提供集成的框架。

    942 引用 • 1459 回帖 • 31 关注
  • DNSPod

    DNSPod 建立于 2006 年 3 月份,是一款免费智能 DNS 产品。 DNSPod 可以为同时有电信、网通、教育网服务器的网站提供智能的解析,让电信用户访问电信的服务器,网通的用户访问网通的服务器,教育网的用户访问教育网的服务器,达到互联互通的效果。

    6 引用 • 26 回帖 • 506 关注
  • 导航

    各种网址链接、内容导航。

    39 引用 • 170 回帖 • 5 关注
  • iOS

    iOS 是由苹果公司开发的移动操作系统,最早于 2007 年 1 月 9 日的 Macworld 大会上公布这个系统,最初是设计给 iPhone 使用的,后来陆续套用到 iPod touch、iPad 以及 Apple TV 等产品上。iOS 与苹果的 Mac OS X 操作系统一样,属于类 Unix 的商业操作系统。

    84 引用 • 139 回帖 • 2 关注
  • 职场

    找到自己的位置,萌新烦恼少。

    127 引用 • 1705 回帖
  • Ant-Design

    Ant Design 是服务于企业级产品的设计体系,基于确定和自然的设计价值观上的模块化解决方案,让设计者和开发者专注于更好的用户体验。

    17 引用 • 23 回帖
  • 程序员

    程序员是从事程序开发、程序维护的专业人员。

    565 引用 • 3532 回帖
  • Log4j

    Log4j 是 Apache 开源的一款使用广泛的 Java 日志组件。

    20 引用 • 18 回帖 • 32 关注
  • HBase

    HBase 是一个分布式的、面向列的开源数据库,该技术来源于 Fay Chang 所撰写的 Google 论文 “Bigtable:一个结构化数据的分布式存储系统”。就像 Bigtable 利用了 Google 文件系统所提供的分布式数据存储一样,HBase 在 Hadoop 之上提供了类似于 Bigtable 的能力。

    17 引用 • 6 回帖 • 70 关注
  • ZooKeeper

    ZooKeeper 是一个分布式的,开放源码的分布式应用程序协调服务,是 Google 的 Chubby 一个开源的实现,是 Hadoop 和 HBase 的重要组件。它是一个为分布式应用提供一致性服务的软件,提供的功能包括:配置维护、域名服务、分布式同步、组服务等。

    59 引用 • 29 回帖 • 3 关注
  • Windows

    Microsoft Windows 是美国微软公司研发的一套操作系统,它问世于 1985 年,起初仅仅是 Microsoft-DOS 模拟环境,后续的系统版本由于微软不断的更新升级,不但易用,也慢慢的成为家家户户人们最喜爱的操作系统。

    221 引用 • 473 回帖
  • Netty

    Netty 是一个基于 NIO 的客户端-服务器编程框架,使用 Netty 可以让你快速、简单地开发出一个可维护、高性能的网络应用,例如实现了某种协议的客户、服务端应用。

    49 引用 • 33 回帖 • 19 关注
  • 钉钉

    钉钉,专为中国企业打造的免费沟通协同多端平台, 阿里巴巴出品。

    15 引用 • 67 回帖 • 337 关注
  • Ubuntu

    Ubuntu(友帮拓、优般图、乌班图)是一个以桌面应用为主的 Linux 操作系统,其名称来自非洲南部祖鲁语或豪萨语的“ubuntu”一词,意思是“人性”、“我的存在是因为大家的存在”,是非洲传统的一种价值观,类似华人社会的“仁爱”思想。Ubuntu 的目标在于为一般用户提供一个最新的、同时又相当稳定的主要由自由软件构建而成的操作系统。

    124 引用 • 169 回帖
  • 创业

    你比 99% 的人都优秀么?

    84 引用 • 1399 回帖
  • Google

    Google(Google Inc.,NASDAQ:GOOG)是一家美国上市公司(公有股份公司),于 1998 年 9 月 7 日以私有股份公司的形式创立,设计并管理一个互联网搜索引擎。Google 公司的总部称作“Googleplex”,它位于加利福尼亚山景城。Google 目前被公认为是全球规模最大的搜索引擎,它提供了简单易用的免费服务。不作恶(Don't be evil)是谷歌公司的一项非正式的公司口号。

    49 引用 • 192 回帖 • 1 关注
  • React

    React 是 Facebook 开源的一个用于构建 UI 的 JavaScript 库。

    192 引用 • 291 回帖 • 401 关注
  • 小说

    小说是以刻画人物形象为中心,通过完整的故事情节和环境描写来反映社会生活的文学体裁。

    28 引用 • 108 回帖
  • Thymeleaf

    Thymeleaf 是一款用于渲染 XML/XHTML/HTML5 内容的模板引擎。类似 Velocity、 FreeMarker 等,它也可以轻易的与 Spring 等 Web 框架进行集成作为 Web 应用的模板引擎。与其它模板引擎相比,Thymeleaf 最大的特点是能够直接在浏览器中打开并正确显示模板页面,而不需要启动整个 Web 应用。

    11 引用 • 19 回帖 • 354 关注
  • 阿里云

    阿里云是阿里巴巴集团旗下公司,是全球领先的云计算及人工智能科技公司。提供云服务器、云数据库、云安全等云计算服务,以及大数据、人工智能服务、精准定制基于场景的行业解决方案。

    89 引用 • 345 回帖