批处理版迷宫

neorobin · 发表于 2012-3-27 00:44:11

本帖最后由 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:23

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

wankoilz · 发表于 2012-4-6 16:16:21

没入口呢？

CrLf · 发表于 2012-4-6 18:16:28

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

gawk · 发表于 2012-4-6 18:29:44

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

BillGates · 发表于 2012-4-6 23:50:52

比较像二维码

neorobin · 发表于 2012-4-7 00:16:46

本帖最后由 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:04

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

@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:31

回复 8# netbenton

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

CrLf · 发表于 2012-4-11 21:56:54

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

本楼理解错误，删

plp626 · 发表于 2012-4-11 23:28:03

迷宫生成算法，不懂，

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

neorobin · 发表于 2012-4-11 23:42:54

回复 11# plp626

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

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

cjiabing · 发表于 2012-4-12 19:11:16

回复 7# neorobin

惨不忍睹啊~

cjiabing · 发表于 2012-4-12 19:14:23

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

netbenton · 发表于 2012-4-12 19:46:26

cjiabing 抬举我了。

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

		自动登录	找回密码
密码			注册

[新手上路]批处理新手入门导读	[视频教程]批处理基础视频教程	[视频教程]VBS基础视频教程	[批处理精品]批处理版照片整理器
[批处理精品]纯批处理备份&还原驱动	[批处理精品]CMD命令50条不能说的秘密	[在线下载]第三方命令行工具	[在线帮助]VBScript / JScript 在线参考

[其他] 批处理版迷宫

评分

评分

评分