|
|
关于随机迷宫的算法的理论,一个简单算法的详细解释和使用时的注意:
首先先抄下演示中使用的算法代码段:
复制代码
//=================Function Start======================
function RandomMZ takes integer offset returns nothing
local integer rd
local integer symbol
local integer tmp
local integer lDir
local integer direction
set udg_isVisited[offset]=true
loop
set symbol=0
if (offset>10 and udg_isVisited[offset-11]==false) then
set symbol=symbol+1
endif
if (offset-offset/11*11>0 and udg_isVisited[offset-1]==false) then
set symbol=symbol+2
endif
if (offset <110 and udg_isVisited[offset+11]==false) then
set symbol=symbol+4
endif
if (offset-offset/11*11-10<0 and udg_isVisited[offset+1]==false) then
set symbol=symbol+8
endif
exitwhen (symbol==0)
set lDir=0
set tmp=symbol
loop
exitwhen (tmp==0)
set lDir=lDir+tmp-tmp/2*2
set tmp=tmp/2
endloop
set rd=GetRandomInt(1,lDir)
set tmp=symbol-symbol/2*2
set direction=1
loop
exitwhen (tmp==1 and rd==1)
set symbol=symbol/2
if (tmp==1) then
set rd=rd-1
endif
set tmp=symbol-symbol/2*2
set direction=direction+1
endloop
if (direction==1) then
set udg_toDown[offset-11]=true
call RandomMZ(offset-11)
endif
if (direction==2) then
set udg_toRight[offset-1]=true
call RandomMZ(offset-1)
endif
if (direction==3) then
set udg_toDown[offset]=true
call RandomMZ(offset+11)
endif
if (direction==4) then
set udg_toRight[offset]=true
call RandomMZ(offset+1)
endif
endloop
endfunction
//=================Function End======================
其中使用的全局变量有:
boolean isVisited[]
boolean toDown[]
boolean toRight[]
现在解释各个变量的意义
迷宫一般由X*Y个房间构成,比如说这个6*5的迷宫(X=6,Y=5)
---------------------->X
0 1 2 3 4 5
| ┏━┳━┳━┳━┳━┳━┓
| 0┃0 ┃1 ┃2 ┃3 ┃4 ┃5 ┃
| ┣━╋━╋━╋━╋━╋━┫
| 1┃6 ┃7 ┃8 ┃9 ┃10┃11┃
| ┣━╋━╋━╋━╋━╋━┫
| 2┃12┃13┃14┃15┃16┃17┃
| ┣━╋━╋━╋━╋━╋━┫
| 3┃18┃19┃20┃21┃22┃23┃
| ┣━╋━╋━╋━╋━╋━┫
y 4┃24┃25┃26┃27┃28┃29┃
┗━┻━┻━┻━┻━┻━┛
====1====下标表示
由于JASS中只有一维数组,我们只能通过计算下标来找到每个房间储存的位置
如(0,0)下标是0,(3,4)下标是4*6+3=27,而下标是19的房间坐标为(19%6,[19/6])=(1,3)
(19%6即19/6的余数,具体算法是19-19/6*6,[19/6]即对19/6取整)
左右相邻的两个房间下标相差1,上下相邻的房间下标相差X
第1行下标=X*(Y-1),第一列下标特点是能被X整除,最后一列下标特点是加1后能被X整
除
====2====迷宫的储存
我们用toRight记录每个房间于其右边的房间是否连通,toDown记录是否与下面的房间连通
(为什么不用toLeft和toTop记录与左边和上面的房间的连通情况?原因是重复)
所以,toRight(19)和toDown(19)记录了房间(1,3)和(2,3)(1,4)的连通情况
通过一个X*Y大小的toRight和toDown的数组我们就可以记录一个X*Y的迷宫了
我们的目标就是随机算出每个房间的连通情况
====3====isVisited数组
isVisited数组保存每个房间的访问情况
对于一个随机迷宫的简单算法:
1.首先,将所有房间的连通情况设为不连通,进入某个房间
2.进入某个房间R后,如果R四周有未访问过的房间,则从未访问的房间中随机选择一个房间vR,连通R与
vR,并进入房间vR
3.如果房间R四周的房间已经全部访问过,则返回上一个房间
4.重复过程2和3,直到所有房间全部访问为止
该算法生成的迷宫任意两个房间之间有且只有一条通路
证明从略.
某些朋友可能已经知道怎么做了,从某个房间开始进行一次深度优先遍历即可
下面详细解释一下代码
1.function RandomMZ takes integer offset returns nothing
不要告诉我不知道这句话是什么意思...
offset 即为进入房间的下标,在T中的call RandomMZ(0)即进入(0,0)房间
2.变量定义
local integer rd============随机数
local integer symbol========标志
local integer tmp===========临时变量
local integer lDir==========房间四周剩余未访问的房间数量
local integer direction=====最终决定的方向 1=上 2=左 3=下 4=右
3.set udg_isVisited[offset]=true
进入一个房间首先将其设为已访问
4.set symbol=0
symbol作为标志位记录每个房间的连通情况,用2进制位记录,即为二进制的(0000)
5.
if (offset>10 and udg_isVisited[offset-11]==false) then
set symbol=symbol+1
endif
如果上方有房间并且未访问,则将Symbol的第一位置1(二进制第一位是1)
if (offset-offset/11*11>0 and udg_isVisited[offset-1]==false) then
set symbol=symbol+2
endif
如果左边有房间并且未访问,则将Symbol的第二位置1(二进制第二位是2)
if (offset <110 and udg_isVisited[offset+11]==false) then
set symbol=symbol+4
endif
如果下方有房间并且未访问,则将Symbol的第三位置1(二进制第三位是4)
if (offset-offset/11*11-10<0 and udg_isVisited[offset+1]==false) then
set symbol=symbol+8
endif
如果右边有房间并且未访问,则将Symbol的第四位置1(二进制第四位是8)
比如Symbol=13,转换为二进制是(1101),就是上,下,右的房间可以访问,左边没有房间或房间已访问
6.exitwhen (symbol==0)
如果symbol=0,也就是没有房间可访问,那么退出循环,返回上一个房间
7.
set lDir=0
set tmp=symbol
loop
exitwhen (tmp==0)
set lDir=lDir+tmp-tmp/2*2
set tmp=tmp/2
endloop
这一段代码计算四周可访问的房间的数量,并保存在lDir中
8.set rd=GetRandomInt(1,lDir)
rd从1到lDir中随机取数(因为共lDir个房间可访问),决定访问可访问房间中的第几个
9.
set tmp=symbol-symbol/2*2
set direction=1
loop
exitwhen (tmp==1 and rd==1)
set symbol=symbol/2
if (tmp==1) then
set rd=rd-1
endif
set tmp=symbol-symbol/2*2
set direction=direction+1
endloop
得到访问房间的方向.具体是用计数器实现,依次取得每一个房间的状态,如果可访问,则将rd减1
当rd=1并且当前房间可访问时停止循环,这样当前的房间即为通过rd选择的房间
PS:以上7,8,9实现了随机选择可访问的房间,如果有更好的算法说一声啊
10. if (direction==1) then
set udg_toDown[offset-11]=true
call RandomMZ(offset-11)
endif
if (direction==2) then
set udg_toRight[offset-1]=true
call RandomMZ(offset-1)
endif
if (direction==3) then
set udg_toDown[offset]=true
call RandomMZ(offset+11)
endif
if (direction==4) then
set udg_toRight[offset]=true
call RandomMZ(offset+1)
endif
更据选择的方向决定下标变化,将两个房间连通,并进入该房间
11.loop
4,5,6,7,8,9,10
endloop
之所以重复4,5,6,7,8,9,10的过程是保证每个房间四周的房间都全部访问(根据6,那时候退出循环)
不会有遗漏的房间存在
12.endfunction
......
关于使用:
实际上修改这段代码很简单
比如要生成一个30*30的迷宫,只要简单的把该函数中的"11"全改为30,"10"全改为29(=30-1),"110"改为
870(=30*(30-1))即可,剩下的过程就是根据连通情况画出图了,在演示中也有T的例子,这点不再罗嗦
PS:由于生成的迷宫任意两个房间之间有且只有一条通路,迷宫有时候回显得比较简单,这时候可以修改
一下算法,比如随机连通两个不相连的房间,以增加回路,提高迷宫的复杂性
差不多就将这些,欢迎各位指正 |
|
狗仔卡
发表于 2011-9-7 23:11:21
提升卡
变色卡
抢沙发
千斤顶
显身卡
Discuz! 代码