[其他] 批处理版迷宫

neorobin

批处理生成的迷宫, 如果代码未生成入口和出口, 那么在边界上任选两个可以和内部通路相连的点即可作为入口和出口.
图 1


图 2


图 3


此处几个版本生成的都是 perfect 型的迷宫, 通路上任意一点都可以通向其它任意一点, 且整个通路上没有环路.
参考资料:
迷宫生成算法:  http://en.wikipedia.org/wiki/Maze_generation_algorithm
Maze Classification:  http://www.astrolog.org/labyrnth/algrithm.htm
图 1 是 7 楼 的效果图, 8 楼 netbenton 和 CrLf 的代码生成效果相同或相似;
图 2 是 22 楼 fatcat 版的效果, 通路显得更清晰.
图 3 是 24 楼 的效果, 更清晰, 算法也更显简单.

neorobin

回复 5# gawk , 4# CrLf

3# wankoilz2# batman

2012.4.16, 找出之前代码数处严重的 bug, 并将所有 goto 语句移除, 而以 for 方式循环, 再次测试未发现死循环问题, 且速度提升. 重新贴出, 前版代码不予保留

2012-3-27, 实现基本想法, 效率可以用 无法忍受 来形容, 有时刚运行时甚至会出现假死的状态, 后查明为在开始搜索特定方向时出现死循环.
代码的算法最常见的是 广度优先 和 深度优先 树搜索算法.
wikipedia 上有一些介绍. 以下代码将已经搜索过的路径点和路径点已经搜索过的方向分别存储进两个堆栈, 另有一个二维数组记录已搜索过的结点的邻居数.
邻居数以自身算 4 个.

因为算法中的搜索控制是采用了随机数, 所以每次生成的格局也是随机的, 在一个较大的规模下, 两次生成一样的格局的可能性也是极低的.
这里采取了以 (2,2) 为搜索起点(边界内任何一点都可以), 但不是必须的, 另外入口和出口是可以随意选取的, 在规模足够大的情况下, 即使入口和出口靠得很近, 也可能必须走过一个很 辗转反侧 的路径.

@echo off & setlocal enabledelayedexpansion
set /a wid=40,hei=wid,iMax=wid*hei,cols=2*wid
title maze !wid! col X !hei! row
mode con cols=!cols!
call :genMaze
exit

:setPoint Screen !x! !y! !pointStr!
  set /a "ind=(%2-1)+(%3-1)*wid+1, lenL=ind-1, lenR=iMax-ind"
  for /f "tokens=1,2,3" %%a in ("!lenL! !ind! !lenR!") do (set %1=!%1:~0,%%a!%4!%1:~%%b,%%c!)
exit /b

REM dir=dc|0x10 将方向值 1,2,4,8 构成的方向组合 [1,0xf] 统一成两位十进制数 [17,31]
:genMaze
set "d1=x+=1" & set "d2=x-=1" & set "d4=y+=1" & set "d8=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=wid/2, y=hei/2"
set /a "x=2, y=2"
set "dirs=" & set "cells=." & set /a "n!x!_!y!=0"

for /l %%# in () do (
  for %%a in (n!x!_!y!) do if !%%a! geq 4 (
    if !dirs:~-2! equ 0x1f (
      set "dirs=!dirs:~0,-2!"
      set "cells=!cells:~1!" & set "cells=!cells:*.=.!"
      if "!cells!"=="." (
        <nul set /p "=Maze GEN 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 (
      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"
        if !visit! equ 0 (
          for %%r in (d!dc!) do set /a "!%%r!"
          set "dirs=!dirs:~0,-2!!newd!"
    ) ) )
  ) else (
    if !%%a! geq 2 (
      for /f "tokens=1-2 delims=.#" %%x in ("!cells!") do (set x=%%x&set y=%%y)
    ) else (

      set /a "xin=x-2^x-wid,yin=y-2^y-hei,in=(xin&yin)>>31"
      if !in! equ 0 (
        for /f "tokens=1-2 delims=.#" %%x in ("!cells!") do (set x=%%x&set y=%%y)
      ) else (

        set "cells=.!x!#!y!!cells!"
        (call :setPoint maze x y ·)
        cls & <nul set /p=!maze:·=　!

        for %%r in ("xn+=1" "xn-=1" "yn+=1" "yn-=1") do (
          (set xn=!x!&set yn=!y!)
          set /a %%r
          set /a "n!xn!_!yn!+=1"
        )
        set /a "n!x!_!y!|=4"

        set /a "dc=1<<(!random!&3),dir=dc|0x10"
        set "dirs=!dirs!!dir!"
        for %%r in (d!dc!) do set /a "!%%r!"
) ) ) )
exit /b
复制代码

neorobin

回复 11# plp626

http://en.wikipedia.org/wiki/Maze_generation_algorithm


wikipedia 尽管不通俗, 但我用通俗的语言肯定说不到很好

neorobin

回复 14# cjiabing
,15# netbenton

嘿嘿,  我很佩服 netbenton , 我可不服输哦, 本顿, 等着我什么时候嬴你啊, 到时好好庆贺哈! (水了, 可这帖本就发在水区的啊, 版主见谅啊)