批处理之家 - Powered by Discuz! Board

标题: [其他] 批处理版迷宫 [打印本页]

作者: neorobin 时间: 2012-3-27 00:44 标题: 批处理版迷宫

本帖最后由 neorobin 于 2012-4-18 11:07 编辑

批处理生成的迷宫, 如果代码未生成入口和出口, 那么在边界上任选两个可以和内部通路相连的点即可作为入口和出口.
图 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 楼 的效果, 更清晰, 算法也更显简单.

作者: batman 时间: 2012-3-27 07:50

这类东东算法是灵魂。。。

作者: wankoilz 时间: 2012-4-6 16:16

没入口呢？

作者: CrLf 时间: 2012-4-6 18:16

顶！等代码
这比解迷宫难多了，曾经也想写个，可和寒夜讨论了半天还是感觉无从下手...

作者: gawk 时间: 2012-4-6 18:29

每次生成的迷宫都不一样吗？

作者: BillGates 时间: 2012-4-6 23:50

比较像二维码

作者: neorobin 时间: 2012-4-7 00:16

本帖最后由 neorobin 于 2012-4-16 21:56 编辑

回复 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
复制代码

作者: netbenton 时间: 2012-4-11 13:44

学着也做了一个，提了点速度

@echo off&setlocal enabledelayedexpansion

::设定
set "墙=█"
set "路=∷"
set /a 行=40,列=40,屏宽=列*2+1,屏高=行+1


for /l %%a in (1,1,!列!) do set one=!one!!墙!
for /l %%a in (1,1,!行!) do set one%%a=!one!


mode con: lines=!屏高! cols=!屏宽!
cls

rem 指定起点
set one2=!one2:~,2!%路%!one2:~3!
set/a #行=2,#列=2


for /l %%a in (1,1,!行!) do echo;!one%%a!


call :活点 !#行! !#列!

rem 求一个点的四周有几个是可走的，可走的点四周最必须有三个空地

set "stos=!sto:* =!"


:lp

rem 如果有三个格说明是活的
if "!str!" equ "%墙%%墙%%墙%" (

rem echo;替换一个

  rem 替换一个位置
  set /a #列0=#列+1
  for /f "tokens=1,2" %%1 in ("!#列! !#列0!") do (
    set one%#行%=!one%#行%:~,%%1!%路%!one%#行%:~%%2!
  )

cls
for /l %%a in (1,1,!行!) do echo;!one%%a!

  for /f "tokens=1*" %%a in ("!sto!") do (
     set v=%%a
     set stos=%%b !stos!
  )
) else (

rem echo;放弃一个

  for /f "tokens=1*" %%a in ("!stos!") do (
     set v=%%a
     set stos=%%b
  )
)

     call :活点 !v:.= !

if defined stos goto :lp
pause >nul 

goto :eof



:活点 行%1 列%2
rem echo;检测 %1.%2

set/a #行=%1,#列=%2

set str=
set sto=

if %1 leq 0 goto :eof
if %2 leq 0 goto :eof
if %1 geq %行% goto :eof
if %2 geq %列% goto :eof


set/a #上=%1-1,#下=%1+1,#左=%2-1,#右=%2+1

set 上█=!#上!.%2
set 下█=!#下!.%2
set 左█=%1.!#左!
set 右█=%1.!#右!

for %%a in ("上!one%#上%:~%2,1!" "下!one%#下%:~%2,1!" "左!one%1:~%#左%,1!" "右!one%1:~%#右%,1!") do (
    if defined %%~a (
       rem 根据随机数最后一位是否大于4来定先后
       if "!random:~-1!" gtr "4" (set sto=!sto! !%%~a!) else (set sto=!%%~a! !sto!)
    set str=!str!█)
)


goto :eof
复制代码

作者: fatcat 时间: 2012-4-11 13:59

回复 8# netbenton

有空再花点时间好好读读, 看看爬和飞究竟区别在哪里

作者: CrLf 时间: 2012-4-11 21:56

本帖最后由 CrLf 于 2012-4-15 00:44 编辑

本楼理解错误，删

作者: plp626 时间: 2012-4-11 23:28

迷宫生成算法，不懂，

谁用最通俗的语言描述下。。。。

作者: neorobin 时间: 2012-4-11 23:42

回复 11# plp626

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

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

作者: cjiabing 时间: 2012-4-12 19:11

回复 7# neorobin

惨不忍睹啊~

作者: cjiabing 时间: 2012-4-12 19:14

在这个方面，楼主显然不是netbenton的对手（楼主莫介意啊！），因为我见过楼主玩过俄罗斯方块、赛车、贪吃蛇、五子棋、推箱子、扫雷等游戏，界面类似于此！~

作者: netbenton 时间: 2012-4-12 19:46

cjiabing 抬举我了。

这里没有比的意思，我只是不想大家过于认为批处理脚本的效率是那么的低。所以花了点时间研究才得出来这个代码的。希望大家一起共同学习，共同提高。其实那个代码还有BUG，并且还有可以提速度的地方，看看有兴趣的朋友再改改看。

作者: neorobin 时间: 2012-4-12 20:11

本帖最后由 neorobin 于 2012-4-12 20:17 编辑

回复 14# cjiabing
,15# netbenton

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

作者: cjiabing 时间: 2012-4-12 21:33

回复 15# netbenton

兄谦虚了！能作出这样的效果实属不易，学习了~！

作者: plp626 时间: 2012-4-12 21:54

认真看了两个net的生成的迷宫图；但我都不觉得那是生成迷宫；

那是一堆随即生成的废墟；毫无通路；

随机迷宫生成，远远没有完成。。。

作者: fatcat 时间: 2012-4-12 22:00

回复 18# plp626

在边界几乎是随意选两个地方分别作为入口和出口就可以了啊, 内部任何一个点到别处都是通的

作者: fatcat 时间: 2012-4-12 22:15

回复 18# plp626

前面 neorobin 和 netbenton 都是采用的深度优先算法, 都是生成的 perfect 型迷宫.

Maze Classification
http://www.astrolog.org/labyrnth/algrithm.htm

wikipedia 上的迷宫生成算法
http://en.wikipedia.org/wiki/Maze_generation_algorithm

作者: CrLf 时间: 2012-4-14 21:56

回复 8# netbenton

也写了一个，大致思路相同，只是实现方式不一样：
http://bbs.bathome.net/viewthread.php?tid=16385

作者: fatcat 时间: 2012-4-17 20:37

本帖最后由 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 为这个点自身):

0	1	2
3	4	5
6	7	8

上位可通行条件:
相对于上位, 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
复制代码

作者: CrLf 时间: 2012-4-17 23:14

回复 22# fatcat

我也计划改成类似这样比较规整的格式，不过思路不是判断周围八格，而是每次走两个，感觉会比较简单

作者: fatcat 时间: 2012-4-18 10:49

回复 23# CrLf
你的话启发了我

@echo off & setlocal enabledelayedexpansion & color f0
set /a "wid=60,hei=40,wid|=1,hei|=1,iMax=wid*hei,cols=2*wid,row=hei+1"
title maze !wid! col X !hei! row
mode con cols=!cols! lines=!row!

set "maze="
for /l %%y in (1 1 !hei!) do for /l %%x in (1 1 !wid!) do set "maze=!maze!█"
REM {1,2,4,8} -> {17,18,20,24} <-> {上,左,右,下}
set "d17=y-=2" & set "d18=x-=2" & set "d20=x+=2" & set "d24=y+=2" & set "d=0"
set "w17=y+=1" & set "w18=x+=1" & set "w20=x-=1" & set "w24=y-=1" & set "w=0"
set "dirs=" & set "cells=." & set /a "x=2, y=2"

for /l %%# in () do (
  if defined n!x!_!y! ( 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,dir|=dc, dc|=0x10"
        if !visit! equ 0 (
          for %%r in (d!dc!) do set /a "!%%r!"
          set "dirs=!dirs:~0,-2!!dir!"
    ) ) )
  ) 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 "n!x!_!y!=1"

      for %%r in (w!dc!) do for %%i in (1 2) do (
        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!)
        set /a "!%%r!"
      )
      for %%r in (d!dc!) do set /a "!%%r!"
      cls & <nul set /p "=!maze:·=  !"

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

作者: gawk 时间: 2012-4-18 16:49

回复 18# plp626

OUT了吧，嘿嘿。

作者: 0123456789 时间: 2012-11-8 18:13

这迷宫还是随机生成的

作者: netbenton 时间: 2022-1-7 14:28

新算法，生成的迷宫更美观。

@echo off&rem 纯批处理迷宫随机生成器
set a=!
set b=!a!
rem 变量多层嵌套初始化

set r=7
rem %r% 定义生成迷宫的属性：（0到9）值越小分支越多，值越大主线越长，分支越少。

set /a 行=40,列=40,屏宽=列*2+1,屏高=行+1,出列=列-1,出行=行-1
rem 定义迷宫大小。

set sto=1$2$上
rem 定义出口

set 出=%行%.%出列% %出行%.%出列%
rem 定义入口

title r=%r%  行=%行%，列=%列%

set/a r=r %% 10

setlocal enabledelayedexpansion

set "墙=■"
set "路=　"


for /l %%a in (1,1,!行!) do (
	set L%%a=
	for /l %%b in (1,1,!列!) do set o%%a.%%b=%墙%&set L%%a=!L%%a!!a!o%%a.%%b!a!

)



set S右=!a!#上!a!$!a!#列!a!$下 !a!#行!a!$!a!#左!a!$右 !a!#下!a!$!a!#列!a!$上 
set S左=!a!#上!a!$!a!#列!a!$下 !a!#行!a!$!a!#右!a!$左 !a!#下!a!$!a!#列!a!$上 
set S上=!a!#行!a!$!a!#左!a!$右 !a!#行!a!$!a!#右!a!$左 !a!#下!a!$!a!#列!a!$上 
set S下=!a!#行!a!$!a!#左!a!$右 !a!#行!a!$!a!#右!a!$左 !a!#上!a!$!a!#列!a!$下 



set F右=!b!o!a!#上!a!.!a!#列!a!!b!!b!o!a!#上!a!.!a!#左!a!!b!!b!o!a!#行!a!.!a!#左!a!!b!!b!o!a!#下!a!.!a!#左!a!!b!!b!o!a!#下!a!.!a!#列!a!!b!
set F左=!b!o!a!#上!a!.!a!#列!a!!b!!b!o!a!#上!a!.!a!#右!a!!b!!b!o!a!#行!a!.!a!#右!a!!b!!b!o!a!#下!a!.!a!#右!a!!b!!b!o!a!#下!a!.!a!#列!a!!b!
set F上=!b!o!a!#行!a!.!a!#左!a!!b!!b!o!a!#下!a!.!a!#左!a!!b!!b!o!a!#行!a!.!a!#右!a!!b!!b!o!a!#下!a!.!a!#右!a!!b!!b!o!a!#下!a!.!a!#列!a!!b!
set F下=!b!o!a!#行!a!.!a!#左!a!!b!!b!o!a!#上!a!.!a!#左!a!!b!!b!o!a!#行!a!.!a!#右!a!!b!!b!o!a!#上!a!.!a!#右!a!!b!!b!o!a!#上!a!.!a!#列!a!!b!


::  上
::左中右
::  下

mode con: lines=!屏高! cols=!屏宽!



for /l %%z in () do (

for /f "tokens=1*" %%x in ("!sto!") do (
	set sto=%%y

	for /f "tokens=1,2,3 delims=$" %%7 in ("%%x") do (
		set/a #行=%%7,#列=%%8,#上=#行-1,#下=#行+1,#左=#列-1,#右=#列+1

		if "!random:~-1!" gtr "4" (set s%%9=!s%%9:~12!!s%%9:~,12!) else (set s%%9=!s%%9:~24!!s%%9:~,24!)


for /f "tokens=*" %%a in ("!F%%9! !S%%9!") do for /f "tokens=1*" %%b in ("%%a") do (
	if "%%b" equ "%墙%%墙%%墙%%墙%%墙%" (
		set o!#行!.!#列!=%路%
		for %%A in (%%c) do (
			for /f "tokens=1,2,3 delims=$" %%1 in ("%%~A") do (
				set/a #行=%%1,#列=%%2,#上=#行-1,#下=#行+1,#左=#列-1,#右=#列+1
				for /f %%B in ("!F%%3!") do for /f %%C in ("%%B") do if "%%C" equ "%墙%%墙%%墙%%墙%%墙%" (

if "!random:~-1!" gtr "%r%" (set sto=!sto! %%A) else (set sto=%%A !sto!)

				)
			)
		)
	)
)





	)
)

if not defined sto call :fins

)

:fins
for %%a in (%出%) do set o%%a=入

cls&for /l %%a in (1,1,!行!) do for /f %%b in ("!L%%a!") do echo;%%b

set /p in=计算结束，回车关闭。


exit
复制代码

欢迎光临批处理之家 (http://www.bathome.net/)