本帖最后由 fatcat 于 2012-4-17 20:42 编辑
代码逻辑框架以及搜索算法和 7 楼(改正了严重的 bug, 已提速)是一致的, 生成规则作了变化, 使迷宫通路上显得清晰.
算法特点: 以二维数组 n[x,y] 记录必要的邻居分布状态, 数值采用一个 9 位的二进制数, 最中间一位表示自身已在通路上, 其余 8 位分别表示围绕的 8 个点是否是通路上.
将 1,2,4,8 都加上 0x10, 作为 4 个搜索方向的 ID:
{1,2,4,8} -> {17,18,20,24} -> {上,左,右,下}
将一个点及周围的 8 个邻居点 位置 编号如下(位置 4 为这个点自身):
上 位可通行条件:
相对于 上 位, 012345 位置均为墙, 位序列: 876543 均置 0
n_上 & 504 == 0
下 位可通行条件:
相对于 下 位, 876543 位置均为墙, 位序列: 012345 均置 0
n_下 & 63 == 0
左 位可通行条件:
相对于 左 位, 013467 位置均为墙, 位序列: 875421 均置 0
n_左 & 438 == 0
右 位可通行条件:
相对于 右 位, 124578 位置均为墙, 位序列: 764310 均置 0
n_右 & 219 == 0
| @echo off & setlocal enabledelayedexpansion & color f0 | | set /a "wid=80,hei=40,iMax=wid*hei,cols=2*wid,row=hei+1" | | title maze !wid! col X !hei! row | | mode con cols=!cols! lines=!row! | | | | REM {1,2,4,8} -> {17,18,20,24} <-> {上,左,右,下} | | set "d17=y-=1" & set "d18=x-=1" & set "d20=x+=1" & set "d24=y+=1" | | set "maze=" | | for /l %%y in (1 1 !hei!) do for /l %%x in (1 1 !wid!) do set "maze=!maze!█" | | set /a "x=2, y=2" | | set "dirs=" & set "cells=." & set "n!x!_!y!=0" & set "dc=17" | | | | for /l %%# in () do ( | | title maze !wid! col X !hei! row -- searching !x!,!y! ... | | for %%a in (n!x!_!y!) do ( | | set /a "isBackTrack=%%a & 0x10" | | | | if !isBackTrack! equ 0x10 ( rem 回溯点 | | if !dirs:~-2! equ 0x1f ( rem 回溯点所有方向都已搜索 | | set "dirs=!dirs:~0,-2!" | | set "cells=!cells:~1!" & set "cells=!cells:*.=.!" | | if "!cells!"=="." ( | | <nul set /p "=" & title Maze generation completed, any key to exit... | | >nul pause & exit | | ) | | for /f "tokens=1-2 delims=.#" %%x in ("!cells!") do (set x=%%x&set y=%%y) | | ) else ( rem 回溯点还有未搜索的方向 | | for /f "tokens=1-2 delims=.#" %%x in ("!cells!") do (set x=%%x&set y=%%y) | | set "dir=!dirs:~-2!" | | | | set /a "visit=1, randS=!random! & 3, randE=randS|4" | | for /l %%d in (!randS! 1 !randE!) do if !visit! neq 0 ( | | set /a "dc=1<<(%%d &3), visit=dir&dc,newd=dc|dir, dc|=0x10" | | if !visit! equ 0 ( | | for %%r in (d!dc!) do set /a "!%%r!" | | set "dirs=!dirs:~0,-2!!newd!" | | ) ) ) | | ) else ( rem 待测试点 | | set /a "canPass=^!((dc-17)|(%%a&504)) | ^!((dc-24)|(%%a&63)) | ^!((dc-18)|(%%a&438)) | ^!((dc-20)|(%%a&219))" | | | | if !canPass! equ 0 ( rem 不可通行点 | | for /f "tokens=1-2 delims=.#" %%x in ("!cells!") do (set x=%%x&set y=%%y) | | ) else ( rem 可通行点 | | | | set /a "xin=x-2^x-wid,yin=y-2^y-hei,in=(xin&yin)>>31" | | if !in! equ 0 ( rem 出边界 | | for /f "tokens=1-2 delims=.#" %%x in ("!cells!") do (set x=%%x&set y=%%y) | | ) else ( rem 在边界内 | | set "cells=.!x!#!y!!cells!" | | | | set /a "ind=(x-1)+(y-1)*wid+1, lL=ind-1, lR=iMax-ind" | | for /f "tokens=1-3" %%a in ("!lL! !ind! !lR!") do (set maze=!maze:~0,%%a!·!maze:~%%b,%%c!) | | cls & <nul set /p "=!maze:·= !" | | | | set "p=1" | | for %%u in (-1 0 1) do for %%v in (-1 0 1) do ( | | set /a "xn=x+%%v, yn=y+%%u" | | set /a "n!xn!_!yn!|=p, p<<=1" | | ) | | | | set /a "dc=(1<<(!random!&3))|0x10" | | set "dirs=!dirs!!dc!" | | for %%r in (d!dc!) do set /a "!%%r!" | | ) ) ) ) ) | | exitCOPY |
|
发表于 2012-4-12 20:11
| 
发表于 2012-4-12 21:33
| 
发表于 2012-4-12 21:54
| 
发表于 2012-4-14 21:56
| 
