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

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

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

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 回帖
  • 游戏

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

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

相关帖子

欢迎来到这里!

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

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

推荐标签 标签

  • React

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

    192 引用 • 291 回帖 • 384 关注
  • 深度学习

    深度学习(Deep Learning)是机器学习的分支,是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。

    53 引用 • 40 回帖
  • 链滴

    链滴是一个记录生活的地方。

    记录生活,连接点滴

    153 引用 • 3783 回帖 • 1 关注
  • Python

    Python 是一种面向对象、直译式电脑编程语言,具有近二十年的发展历史,成熟且稳定。它包含了一组完善而且容易理解的标准库,能够轻松完成很多常见的任务。它的语法简捷和清晰,尽量使用无异义的英语单词,与其它大多数程序设计语言使用大括号不一样,它使用缩进来定义语句块。

    543 引用 • 672 回帖 • 1 关注
  • Rust

    Rust 是一门赋予每个人构建可靠且高效软件能力的语言。Rust 由 Mozilla 开发,最早发布于 2014 年 9 月。

    58 引用 • 22 回帖
  • DevOps

    DevOps(Development 和 Operations 的组合词)是一组过程、方法与系统的统称,用于促进开发(应用程序/软件工程)、技术运营和质量保障(QA)部门之间的沟通、协作与整合。

    47 引用 • 25 回帖
  • Flume

    Flume 是一套分布式的、可靠的,可用于有效地收集、聚合和搬运大量日志数据的服务架构。

    9 引用 • 6 回帖 • 629 关注
  • Linux

    Linux 是一套免费使用和自由传播的类 Unix 操作系统,是一个基于 POSIX 和 Unix 的多用户、多任务、支持多线程和多 CPU 的操作系统。它能运行主要的 Unix 工具软件、应用程序和网络协议,并支持 32 位和 64 位硬件。Linux 继承了 Unix 以网络为核心的设计思想,是一个性能稳定的多用户网络操作系统。

    943 引用 • 943 回帖
  • DNSPod

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

    6 引用 • 26 回帖 • 510 关注
  • 互联网

    互联网(Internet),又称网际网络,或音译因特网、英特网。互联网始于 1969 年美国的阿帕网,是网络与网络之间所串连成的庞大网络,这些网络以一组通用的协议相连,形成逻辑上的单一巨大国际网络。

    98 引用 • 344 回帖
  • Kafka

    Kafka 是一种高吞吐量的分布式发布订阅消息系统,它可以处理消费者规模的网站中的所有动作流数据。 这种动作(网页浏览,搜索和其他用户的行动)是现代系统中许多功能的基础。 这些数据通常是由于吞吐量的要求而通过处理日志和日志聚合来解决。

    36 引用 • 35 回帖
  • InfluxDB

    InfluxDB 是一个开源的没有外部依赖的时间序列数据库。适用于记录度量,事件及实时分析。

    2 引用 • 71 关注
  • GitBook

    GitBook 使您的团队可以轻松编写和维护高质量的文档。 分享知识,提高团队的工作效率,让用户满意。

    3 引用 • 8 回帖 • 4 关注
  • IDEA

    IDEA 全称 IntelliJ IDEA,是一款 Java 语言开发的集成环境,在业界被公认为最好的 Java 开发工具之一。IDEA 是 JetBrains 公司的产品,这家公司总部位于捷克共和国的首都布拉格,开发人员以严谨著称的东欧程序员为主。

    180 引用 • 400 回帖
  • Elasticsearch

    Elasticsearch 是一个基于 Lucene 的搜索服务器。它提供了一个分布式多用户能力的全文搜索引擎,基于 RESTful 接口。Elasticsearch 是用 Java 开发的,并作为 Apache 许可条款下的开放源码发布,是当前流行的企业级搜索引擎。设计用于云计算中,能够达到实时搜索,稳定,可靠,快速,安装使用方便。

    117 引用 • 99 回帖 • 211 关注
  • 尊园地产

    昆明尊园房地产经纪有限公司,即:Kunming Zunyuan Property Agency Company Limited(简称“尊园地产”)于 2007 年 6 月开始筹备,2007 年 8 月 18 日正式成立,注册资本 200 万元,公司性质为股份经纪有限公司,主营业务为:代租、代售、代办产权过户、办理银行按揭、担保、抵押、评估等。

    1 引用 • 22 回帖 • 762 关注
  • 数据库

    据说 99% 的性能瓶颈都在数据库。

    340 引用 • 708 回帖
  • 博客

    记录并分享人生的经历。

    273 引用 • 2388 回帖
  • SVN

    SVN 是 Subversion 的简称,是一个开放源代码的版本控制系统,相较于 RCS、CVS,它采用了分支管理系统,它的设计目标就是取代 CVS。

    29 引用 • 98 回帖 • 680 关注
  • AngularJS

    AngularJS 诞生于 2009 年,由 Misko Hevery 等人创建,后为 Google 所收购。是一款优秀的前端 JS 框架,已经被用于 Google 的多款产品当中。AngularJS 有着诸多特性,最为核心的是:MVC、模块化、自动化双向数据绑定、语义化标签、依赖注入等。2.0 版本后已经改名为 Angular。

    12 引用 • 50 回帖 • 474 关注
  • 音乐

    你听到信仰的声音了么?

    60 引用 • 511 回帖
  • 前端

    前端技术一般分为前端设计和前端开发,前端设计可以理解为网站的视觉设计,前端开发则是网站的前台代码实现,包括 HTML、CSS 以及 JavaScript 等。

    247 引用 • 1348 回帖
  • Tomcat

    Tomcat 最早是由 Sun Microsystems 开发的一个 Servlet 容器,在 1999 年被捐献给 ASF(Apache Software Foundation),隶属于 Jakarta 项目,现在已经独立为一个顶级项目。Tomcat 主要实现了 JavaEE 中的 Servlet、JSP 规范,同时也提供 HTTP 服务,是市场上非常流行的 Java Web 容器。

    162 引用 • 529 回帖
  • ZooKeeper

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

    59 引用 • 29 回帖 • 5 关注
  • Ant-Design

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

    17 引用 • 23 回帖
  • 强迫症

    强迫症(OCD)属于焦虑障碍的一种类型,是一组以强迫思维和强迫行为为主要临床表现的神经精神疾病,其特点为有意识的强迫和反强迫并存,一些毫无意义、甚至违背自己意愿的想法或冲动反反复复侵入患者的日常生活。

    15 引用 • 161 回帖
  • 链书

    链书(Chainbook)是 B3log 开源社区提供的区块链纸质书交易平台,通过 B3T 实现共享激励与价值链。可将你的闲置书籍上架到链书,我们共同构建这个全新的交易平台,让闲置书籍继续发挥它的价值。

    链书社

    链书目前已经下线,也许以后还有计划重制上线。

    14 引用 • 257 回帖