【小白学游戏常用算法】一、随机迷宫算法

  现在的很多游戏中的地图一般采用格子的方式,虽然在表面地图上无法看到实际的格子,但是在地图的结构中专门有一个逻辑层,这个层和地图大小相等,划出很多小的格子,然后在可以通过的地方使用0表示,在有障碍的且不能通过的地方用1或者其他数字表示(如图所示)。有了这个逻辑层之后,实际上自动寻路就转换成了如何在一个二维数组中找出一条从逻辑值为0的地点移动到目标的路径。在寻路之前,我们首先要随机生成这些地图。

                             游戏中地图      二维数组逻辑层

  本质上,地图的障碍逻辑层是由一个二维数组保存的。障碍标记在二维数组中的数据值以0或者1表示,我们首先需要做的就是随机产生这样的二维数组。当然,最简单的办法就是循环这个二维数组,然后在每一个位置随机地产生0或者1,但是这种算法产生的图形比较难看,并且不一定保证图中的任意两点可以相连通。

  在随机生成的迷宫中要求任意两点,都可以找到一条路径相通,所以在图论中可以认为迷宫就是一个连通图。产生连通图的常见方法有克鲁斯卡尔和普利姆算法,这里我们以普利姆算法为例实现一下,使用普利姆算法产生的迷宫比较自然和随机。

(1)如上图所示为一个6x6的迷宫,先假设迷宫中所有的通路都是完全封闭的,黄色的格子表示可以通过,黑色的格子表示墙壁或者障碍不能通过。

  (2)随机选择一个黄色的格子作为当前正在访问的格子,同时把该格子放入一个已经访问的列表中。

  (3)循环以下操作,直到所有的格子都被访问到。

     1.得到当前访问格子的四周(上下左右)的格子,在这些格子中随机选择一个没有在访问列表中的格子,如果找到,则把该格子和当前访问的格子中间的墙打通(置为0),把该格子作为当前访问的格子,并放入访问列表。

     2.如果周围所有的格子都已经访问过,则从已访问的列表中,随机选取一个作为当前访问的格子。

   通过以上的迷宫生成算法,可以生成一个自然随机的迷宫、

  下面使用代码实现一个R行N列大小的随机迷宫,R行表示的是刚开始空白格子的行数,而格子之间还有墙壁和障碍物,所以最终产生的二维数组大小实际为2R+1 * 2N+1

 1 //产生随机迷宫
 2 primMaze:function(r,c)
 3 {
 4          //初始化数组
 5          function init(r,c)
 6          {
 7              var a = new Array(2*r+1);
 8             //全部置1
 9             for(var i=0,len=a.length;i<len;i++)
10             {
11                 var cols = 2*c+1;
12                 a[i]= new Array(cols);
13                 ArrayUtil.fillWith(a[i],1);
14             }
15             //中间格子为0
16             for(var i=0;i<r;i++)
17                 for(var j=0;j<c;j++)
18                 {
19                     a[2*i+1][2*j+1] = 0;
20                 }
21                 return a;
22         }
23          //处理数组,产生最终的数组
24          function process(arr)
25          {
26            //acc存放已访问队列,noacc存放没有访问队列
27            var acc = [],noacc = [];
28            var r = arr.length>>1,c=arr[0].length>>1;
29            var count = r*c;
30            for(var i=0;i<count;i++){noacc[i]=0;}
31            //定义空单元上下左右偏移
32            var offs=[-c,c,-1,1],offR=[-1,1,0,0],offC=[0,0,-1,1];      
33            //随机从noacc取出一个位置
34            var pos = MathUtil.randInt(count);
35            noacc[pos]=1;
36            acc.push(pos);       
37            while(acc.length<count)
38            {        
39                var ls = -1,offPos = -1;
40                offPos = -1;
41              //找出pos位置在二维数组中的坐标
42              var pr = pos/c|0,pc=pos%c,co=0,o=0;
43              //随机取上下左右四个单元
44              while(++co<5)
45              {
46                  o = MathUtil.randInt(0,5);
47                  ls =offs[o]+pos;
48                  var tpr = pr+offR[o];
49                  var tpc = pc+offC[o];           
50                  if(tpr>=0&&tpc>=0&&tpr<=r-1&&tpc<=c-1&&noacc[ls]==0){ offPos = o;break;}           
51              }                 
52              if(offPos<0)
53              {
54 
55                  pos = acc[MathUtil.randInt(acc.length)];
56              }
57              else
58              {
59                  pr = 2*pr+1;
60                  pc = 2*pc+1;
61                 //相邻空单元中间的位置置0
62                 arr[pr+offR[offPos]][pc+offC[offPos]]=0;
63                 pos = ls;  
64                 noacc[pos] = 1;
65                 acc.push(pos);
66             }        
67         }
68     }
69     var a = init(r,c);
70     process(a);
71     return a;
72 }

利用上面的算法我们就可以实现一个类似于下面的随机迷宫了。

有了随机迷宫就得开始寻路了,下一篇的博客中我们将一起学习一下最常见的A*寻路算法。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器之心

教程 | 利用TensorFlow和神经网络来处理文本分类问题

35370
来自专栏华章科技

三天速成!香港科技大学TensorFlow课件分享

该教程第一天先介绍了深度学习和机器学习的潜力与基本概念,而后便开始探讨深度学习框架 TensorFlow。首先我们将学到如何安装 TensorFlow,其实我们...

13320
来自专栏贾志刚-OpenCV学堂

使用tensorflow layers相关API快速构建卷积神经网络

tf.layers包中包含了CNN卷积神经网络的大多数层类型,当前封装支持的层包括:

18030
来自专栏机器之心

Capsule官方代码开源之后,机器之心做了份核心代码解读

440120
来自专栏mathor

matlab—影像分析进阶

在这一章里面我们要做的事情全部都围绕两个问题,一个图像当中有多少个xxx,他们的大小是多少,举个例子

28020
来自专栏null的专栏

简单易学的机器学习算法——Rosenblatt感知机的对偶解法

一、Rosenblatt感知机回顾    image.png 二、Rosenblatt感知机的对偶形式    image.png 三、算法流程 image....

39050
来自专栏数值分析与有限元编程

可视化 | MATLAB划分均匀三角形网格

划分单元网格是随心所欲的,所遵循的原则就是尽量提高计算精度。下面是一个规则区域划分均匀三角形网格的例子。 如图所示,将一个矩形平面区域划分成相同大小的直角三角形...

42040
来自专栏PaddlePaddle

【序列到序列学习】使用Scheduled Sampling改善翻译质量

生成古诗词 序列到序列学习实现两个甚至是多个不定长模型之间的映射,有着广泛的应用,包括:机器翻译、智能对话与问答、广告创意语料生成、自动编码(如金融画像编码)...

1.3K50
来自专栏AILearning

【Scikit-Learn 中文文档】使用 scikit-learn 介绍机器学习 | ApacheCN

使用 scikit-learn 介绍机器学习 | ApacheCN 内容提要 在本节中,我们介绍一些在使用 scikit-learn 过程中用到的 机器...

43590
来自专栏漫漫深度学习路

pytorch学习笔记(三):自动求导

auto gradient 本片博文主要是对http://pytorch.org/docs/notes/autograd.html的部分翻译以及自己的理解,如有...

311100

扫码关注云+社区

领取腾讯云代金券