※ [本文转录自 mud 看板 #1R-xocVS ]
作者: laechan (挥泪斩马云) 看板: mud
标题: [闲聊] 随机地图产生器
时间: Mon Nov 26 17:28:02 2018
网页好读版：https://www.ptt.cc/bbs/mud_sanc/M.1543224853.A.20C.html
以前曾写过相关的东西:
┌───────────────────────────────────┐
│ 文章代码(AID): #1EjMKNIx (mud) [ptt.cc] [闲聊] 区域产生器 │
│ 文章网址: https://www.ptt.cc/bbs/mud/M.1320510743.A.4BB.html │
└───────────────────────────────────┘
以上面的做法所产生的地图，有个缺点，就是很难靠程式产生一条
明确的移动路径(注: 并非指最短路径)。
在大部份时候这其实没什么问题，但有视障玩家曾反映，在这样的
地图容易迷路。
因此直觉的想法就是，改成，先产生一条明确的移动路径，再从这
条路径上生出复数的分支，以此构成一张地图，然后将移动路径标
示在地图指令上，视障玩家只需读取移动路径那一行，就能从地图
的起点走到地图的终点。
以下就说明做法。
首先，让使用者先决定地图的范围，例如宽度 10，高度 10，则假
设地图的最左上角座标是 (0, 0)，那最右下角座标就是 (9, 9)。
(0, 0)
┌────┐
│ │
│ │
│ │
└────┘
(9, 9)
接下来假设将 (0, 0) 当成起点，然后做如下判断:
random(2)==1 ? nexts=({1,0}) : nexts=({0,1});
它的意思就是说，从 (0, 0) 开始移动，50% 的机率往右走，50%
的机率往下走。假设是往右，那一开始的路径就如下
x-x
假设是往下，那一开始的路径就如下
x
|
x
接下来持续做以下的判断:
while(nexts!=ends) // 循环持续执行，直到抵达终点
{
lasts=nexts;
switch(random(4))
{
// 往左或往右移动(y轴座标不变)
case 0: nexts=({nexts[0]+1,nexts[1]}); break;
case 1: nexts=({nexts[0]-1,nexts[1]}); break;
// 往上或往下移动(x轴座标不变)
case 2: nexts=({nexts[0],nexts[1]+1}); break;
case 3: nexts=({nexts[0],nexts[1]+1}); break;
}
}
并且设计不走回头路:
// 如果移动点=上一座标点时，就重新跑新的点
if(lasts==nexts)
{
nexts=lasts;
continue;
}
我们以范围 10 x 8 为例，展示某两次的执行结果:
█ ███████
█ █ █
█ █ █████
█ █ █
███ █
█
█ ███
█ █ █
█████ ███ █ █
█ █ █ █ █
███ ███ ███████ █ █
█ █ █ █ █
███ ███ █
█
█
移动路径：2s e 2n 3e s 2w 3s 2w s e s e n e n e s 3e s e 3n e 4s
↑
这一行就是给视障朋友看的
█
█
███ ███
█ █ █
███ █ █
█ █ █
███ █████████
█
█████
█
█
█
█████ ███
█ █ █
█████████ █
移动路径：s e s e s e 2n e 2s 4e s 2w 2s 2w s 4e n e s
↑
这一行就是给视障朋友看的
我们并不是要找“最短路径”，所以路径有很多条；地图范围越
大，可产生出的路径就越多，但相对的产生时间就会越久。
接着就以上面的图为例，我们现在有了明确的起点与终点，也有
了明确的移动路径(注: 并非指最短路径)。
然后我们希望以这张图为基础，令它产生数条分支。分支的选择
法我是采:
分支起点: 地图边界空白点 例如 (0, 7) 是空白的
分支终点: 地图上随机一个非空白点 例如 (3, 3) 不是空白
然后就可以重复上面的循环判断做法，以下是范例:
原地图 产生第一条分支后的地图
█ █ ███ █
█ █ █ █ █
███ ███ ███ ███████
█ █ █ █ █ █
███ █ █ ███████ █
█ █ █ █ █ █ █
███ █████████ █ █████ █████████
█ █ █ █ █
█████ ███ █ █████
█ █ █
█ █ █ █
█ █ █ █
█████ ███ █████ ███
█ █ █ █ █ █ █ █
█████████ █ █████████ █
移动路径：s e s e s e 2n e 2s 4e s 2w 2s 2w s 4e n e s
↑
给视障朋友看的这一行是不会变的
这个意思就是说，虽然地图上产生了一条分支，但视障朋友仍然
可以从原本的起点走原本的移动路径来抵达原本的终点，走法是
一样的，不管分支有几条，都可以照原本的走法。
以下再 demo 第二条分支:
产生第一条分支后的地图 产生第二条分支后的地图
█ ███ █ █ ███ █
█ █ █ █ █ █ █ █
███ ███████ ███ ███████
█ █ █ █ █ █
███████ █ ███████ █
█ █ █ █ █ █ █ █
█ █████ █████████ █ █████ █████████
█ █ █ █ █ █ █ █
███ █ █████ ███ █ █ █████
█ █ █ █ █ █ █ █
█ █ █ █████████████████
█ █ █ █ █ █ █ █
█████ ███ █ ███ █████ ███
█ █ █ █ █ █ █ █ █ █ █ █
█████████ █ ███ █████████ █
移动路径：s e s e s e 2n e 2s 4e s 2w 2s 2w s 4e n e s
↑
给视障朋友看的这一行仍是不会变的
右边那张图，就很像是一般的区域地图了。
以下是以 javascript 来写的话，跑出来的样子:
https://i.imgur.com/auK92fK.jpg
这支程式我日后会将它放在我的网页空间供所有人下载，对 sanc
来说，则是只需要 x-x 图，就能透过 sanc 目前已存在的程式，
将 x-x 图转成区域所需要的所有房间，如下:
001 002-003 004
| | | |
005-006 007-008-009-010
| | |
011-012-013-014 015
| | | |
016 017-018-019 020-021-022-023-024
| | | |
025-026 027 028 029-030-031
| | | | | |
032-033-034-035-036-037-038-039-040
| | | | |
041 042-043 044-045-046 047-048
| | | | | | |
049-050 051-052-053-054-055 056
上面代表这是一张大小 10x8、拥有 56 个房间的区域。
以上一点分享，待续。
[email protected]