本帖最后由 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!"
- ) ) ) ) )
- exit
|
发表于 2012-4-12 20:11
| 
发表于 2012-4-12 21:33
| 
发表于 2012-4-12 21:54
| 
发表于 2012-4-14 21:56
| 
