fatcat

回复 8# netbenton

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

fatcat

回复 18# plp626

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

fatcat

回复 18# plp626

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

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

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

fatcat

代码逻辑框架以及搜索算法和 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
复制代码

fatcat

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