【硬核游戏攻略】1. 最小生成树的两种算法及《我的世界》中迷宫的一键生成函数 |
您所在的位置：网站首页 › 我的世界迷宫攻略 › 【硬核游戏攻略】1. 最小生成树的两种算法及《我的世界》中迷宫的一键生成函数 |
|
文章目录
1. 最小生成树算法1.1. 最小生成树的概念:1.2. Kruskal算法:1.2.1. 算法原理1.2.2. 算法适用情况
1.3. Prim算法:1.3.1. 算法原理1.3.2. 算法适用情况
2. 基于Prim算法的迷宫生成2.1. 算法原理2.1.1. 基本逻辑:2.1.2. 算法相较于Kruskal的优势:
2.2. 算法用于迷宫生成时的缺陷2.2.1. 树状图遍历脱身策略2.2.2. 部分游戏中采取的弥补措施
2.3. 算法实现:
3. 设计迷宫格子(房间)并编写房间生成的mcfunction3.1. 盔甲架,相对坐标与绝对坐标3.2. minecraft函数执行时序控制3.3. 实现:3.4. 一种可行的迷宫房间设计与mazeCellPlot:mcp**系列函数编写策略
4. 参考资料
这个系列的第一篇,虽然起名叫硬核攻略… 但我想开篇还是写点简单的,诸如Prim,Kruskal之类的MST生成算法已经烂大街了,这里重新实现一遍Prim,然后基于生成的迷宫自动创建一系列对应的mcfunction,用于在游戏中一键调用.这个系列不出意外的话应该是用Python3的,py代码没有太难理解的地方,我尽量把注释弄的详细一些,然后源码的话可能会重新整理到网盘一份(都是些不成熟的东西,不丢到GitHub上添堵了),也可能太忙(lan)不弄了.
本期需要:熟悉minecraft游戏中的function机制,会一点Python,玩过(听过)RPGMaker系列中的任何一作
1. 最小生成树算法
1.1. 最小生成树的概念:
最小生成树即一幅包含n结点的无向图中,仅选择性布置最少的边使得所有结点都能连通且这n-1条边的权重之和最短(仅针对有权图),如此布置的图将会是一个树. 可以得知最小生成树(以下简称MST)的一些基本性质: ·MST最终会保留n-1条边(否则会有环,有环就不叫树了不是么~~,参见下条性质) ·MST是单连通的(如果有环,那么删掉环上最长的那条边得到的图将仍然是连通的) 1.2. Kruskal算法: 1.2.1. 算法原理·首先将所有备选边放到一起,按权重由短到长排序.起初该算法认为在没有选择任何一条边的情况下,所有的结点都是孤立(n个结点对应n个孤立的区域,编号a,b,c,…,n或者0,1,…,n-1之类的)的. ·取备选边中最短的一条,看看这条边能否连接两个本来孤立的区域(比较该边两端结点的区域编号是否相同),如果能(区域编号不同),则在待规划的图中敲定这条边,刷新结点的区域编号,使得连通的区域内的结点编号相同. ·再取剩余边中最短的一条,看看这条边能否连接两个本来孤立的区域,如果能,同上并循环,如果不能,弃掉这条边,检查下一条直到所有的边都被检查过. 1.2.2. 算法适用情况选边的话这个图中边不能太多,否则不适用. 1.3. Prim算法: 1.3.1. 算法原理·起初该算法认为在没有选择任何一个结点的情况下,是没有图的…(我实在不知道咋说…),最开始先乱选一个点作为起点,这样待规划的图中只有这一个点是可以到达的. ·比较这个可到达的结点到剩余的结点中最短的一条边,在待规划的图中敲定这条边,然后把这条边连到的那个结点也加入到已规划结点列表. ·看看这个新的结点直接连到了哪些还没有被规划到的结点?连接的边和原来的边比较更近还是更远?已规划结点和待规划结点集合中的连接边中哪一条最短? ·选一条最短的边并开始循环直到所有的结点都被规划完毕. 1.3.2. 算法适用情况如果边太多了就用这个算法吧,应该会好一些. 2. 基于Prim算法的迷宫生成 2.1. 算法原理 2.1.1. 基本逻辑:·选择迷宫起点格子,认为这个格子是可以到达的,别的格子的墙壁都封死,也就是将其它格子都暂时标记为不可到达. ·由于没有权重一说,只要把可到达格子中胡乱选一个(要求临近至少有一个不可到达格子),胡乱打通某一堵’它和临近不可到达格子之间的’墙壁,把那个不可到达的格子分到可到达列表中. ·循环上述步骤直到所有的格子都位于可到达列表中. 2.1.2. 算法相较于Kruskal的优势:任何两个相邻格子之间的墙壁都有可能被打通,这样备选的边实在是很多(大概是格子数的二倍-横向格子数-纵向格子数+常数的样子,不考虑rouge-like类游戏中的特殊格子(房间)的情况的话). 2.2. 算法用于迷宫生成时的缺陷 2.2.1. 树状图遍历脱身策略虽然迷宫走法中没有树状图遍历中左序遍历这种说法,但熟悉迷宫的人都知道’只要捋着左手侧的墙壁一直走一定能走出迷宫’这种说法.同样的,基于Prim算法生成的迷宫(以及任何的树状迷宫)也是有这种缺陷的,可以想到的是,如果真的要玩家迷失方向,迷宫中至少应该有环,而且这个环不能被玩家绕开(如果仅仅有环则玩家也可能采取类似于左手侧’访问’(做不到遍历)之类的策略避开). 2.2.2. 部分游戏中采取的弥补措施·最常用的手法当然是直接打破一些墙壁来制造通行的路线最终围成环,但仍然有一些游戏中我们可以采取不同的策略: ·RPGMaker(MV)制作地图时可以将地图设置为’循环’,这样玩家如果仍然采取’捋着一侧墙壁走’的访问策略则极有可能陷入无限循环的深渊中. ·minecraft中可以在特定位置(非必经之路上)设置传送点,一旦侦测到附近玩家立刻传送(使用/execute @e[r=***] ~ ~ ~ /tp指令,相当于直接扩展了算法中备选的边) 2.3. 算法实现: import random import numpy #初始化迷宫格子,设置迷宫起始格子(x=0;y=0),创建可到达列表 #cellType[a,b,0:3]分别记录a,b位置格子到上下左右四个临近格子是否没有墙直接隔断(直通True 隔断False) #cellType[a,b,4]记录a,b位置的格子本身是否可以从起点到达 #acsList: 能够到达的格子下标列表(包含起点在内的,所有能从起点出发并到达的格子) #edgeList: 位于边缘的格子下标列表(当某一可到达格子的临近格子中有不可到达的,该格子才会被记录为'边缘',否则检测后会被删除) mazeWidth=int(input("请输入迷宫宽度: ")) mazeLength=int(input("请输入迷宫长度: ")) cellType=numpy.zeros((mazeLength,mazeWidth,5),dtype=numpy.bool) x=0;y=0 acsList=[(x,y)] edgeList=[(x,y)] cellType[x,y,4]=True #普利姆算法 while len(acsList)!=mazeWidth*mazeLength: #当可到达列表格子数不等于总格子数时 x,y=random.choice(edgeList) #从边缘格子列表中随便抽取一个 directionList=[];isEdge=False #初始化备选的打通方向列表,并质疑该格子是否为边缘格子 if x>0: #若格子不在最左侧 if cellType[y,x-1,4]==False: #并且该格子左侧格子不能到达 directionList.append(2) #那么可以选择打破左侧墙壁 isEdge=True #同时也证明了该格子确实位于边缘 if x0: #懒得说 if cellType[y-1,x,4]==False: directionList.append(0) isEdge=True if y |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |