批处理解迷宫

CrLf · 发表于 2011-8-11 00:22:21

本帖最后由 CrLf 于 2012-4-15 03:58 编辑

迷宫规格不大于 64*64 ，边界上只有有效的一对出入口，通道字符统一，行进时不走斜线。
（绘制迷宫帖子链接：http://bbs.bathome.net/viewthread.php?tid=16385）

2011.08.11 首发，用 call 简单实现解迷宫，但是作为草稿的第一版兼容性差、且效率低，于是同日更新了效率更高的 for 版，不过依然没有解决兼容性的问题。
2011.08.13 更新，写出兼容性很强的优化自适应版，核心算法不变，但是能够自动判定迷宫尺寸、出入口位置，优化了各方向的寻路次序（判断大方向），并用新的路径算法实现标记回路，避免回路导致的死循环。
2011.08.15 更新，再次修正错误和优化代码之后，不再畏惧死循环。同时提升了第五版的效率，超过第四版，并且避免了在该版设计之初，剪枝过程中会舍近求远的缺陷。
2011.09.01 更新，纠正原先修改时忽略的逻辑错误，修改后的第五版效率随着迷宫复杂度的增加将明显降低，于是又不如第四版优越了（上次更新时白高兴了）...
2012.04.14 最后更新，为了与绘制迷宫一贴相呼应，以版本4为基础，加入些许自适应判断功能，以便自动区分路与墙，并自动设置窗口大小、添加方向箭头，虽然未使用新算法，但为符合时间顺序故命名为版本6

以下为第六版代码：

@echo off&setlocal enabledelayedexpansion
set>$
(for /f "delims==" %%a in ($) do set %%a=
path %path%)
rem 不使用 for /f 直接解析命令输出，是为了避免开启新进程影响效率
:::::::::::清洁变量环境，提升脚本效率:::::::::::::
rem -----------------一、自适应判断-------------------
(set /p .1=
set "$=!.1!#"
for %%a in (32 16 8 4 2 1) do (
if !$:~%%a^,1!. NEQ . set /a mx+=%%a&set $=!$:~%%a!
)
rem 二分回溯法判断迷宫宽度
for /f %%a in (迷宫.txt) do set /a my+=1
rem 计算图形高度
for /l %%a in (2 1 !my!) do (
set /p .%%a=
rem 把迷宫图形分行保存为变量
set /a #!.%%a:~,1!+=1,#!.%%a:~-1!+=1
rem 统计竖边框字符
)
for %%z in (!my!) do for /l %%a in (2 1 !mx!) do (
set /a #!.1:~%%a,1!+=1,#!.%%z:~%%a,1!+=1
rem 统计横边框字符
)
rem mx、my为迷宫宽、高，.1~.N分别记载迷宫每一行的内容
)<迷宫.txt
set /a xx=mx*2+1,yy=my+3
mode con:lines=%yy% cols=%xx%
echo %time%
rem 调整窗口大小并显示时间
set #>$
for /f "tokens=1,2 delims=#=" %%a in ($) do (
set #%%a=
if %%b==2 set 路=%%a
)
rem 获取路对应的字符
::::::::::::::::::收集基本信息::::::::::::::::::::
set /a nx=mx-1,all=mx*my
::nx 为宽度减一，用于后面的偏移，all 为寻路时的总迭代上限
set "use= "
for /l %%a in (0 1 %nx%) do (
if defined .%%a (
for /l %%b in (0 1 %nx%) do (
if "!.%%a:~%%b,1!"=="%路%" set use= %%b.%%a!use!
rem 保存可用坐标到 use 变量
)
if "!.%%a:~,1!"=="%路%" (
set se=!se! 0-%%a
set t=!t!2
)
if "!.%%a:~-1!"=="%路%" (
set se=!se! %nx%-%%a
set t=!t!1
)
)
if "!.1:~%%a,1!"=="%路%" (
set se=!se! %%a-1
set t=!t!4
)
if "!.%my%:~%%a,1!"=="%路%" (
set se=!se! %%a-%my%
set t=!t!3
)
rem 保存边界出入口位置到变量 se，保存边界入口反方向的对应值到变量 t（方向：1下2右3上4左）
)
:::::::::::::::::::进一步分析:::::::::::::::::::::
rem --------------------二、优化----------------------
for %%a in (!se!) do if defined start (set end=%%a) else set start=%%a
::设置 se 变量中的第一个坐标为起点，第二个坐标为终点
for /f "tokens=1-4 delims=-" %%a in ("%start%-%end%") do (
set /a fx=%%a-%%c,fy=%%d-%%b
if !fx:-^=! gtr !fy:-^=! (
set f= 2 3 4 1
) else set f= 3 2 1 4
if !fx! lss 0 (
set f=!f: 1= @!
set f=!f: 3= 1!
set f=!f: @= 3!
)
if !fy! lss 0 (
set f=!f: 2= @!
set f=!f: 4= 2!
set f=!f: @= 4!
)
rem 判断大方向，把最可能的方向作为首选，其余按概率排列
set /a "fs=1+%%a/%nx%*2+^!~-%%b+(%%b/%my%)*3""
set /a "fe=1+2*^!%%c+3*^!~-%%d+%%d/%my%"
rem 计算在 ff 变量中的偏移量，用于获取与出入口方向对应的方向符号
)
set "ff=@→↓←↑"
::设置出入口的方向标志
set try="%start:-= %"
set "t=%t:~,1% "
::try 保存路线坐标，t 记录要排除的方向
::::::::::::::::规划主要探测方向::::::::::::::::::
for %%a in ($ fx fy se) do set %%a=
::::::::::::::::再次清空多余变量::::::::::::::::::
rem --------------------三、计算----------------------
for /l %%a in (1 1 %all%) do (
for /f tokens^=1-3delims^=^,^"^ %%b in ("!t:~,2!!try!") do (
rem 获取当前坐标和方向
for %%e in (!f:%%b^=!) do (
rem 排除来的方向
if defined back (
set /a "cx=%%c+(2*(%%e/3)-1)*^!(%%e%%2)","cy=%%d+(2*(%%e/3)-1)*(%%e%%2)","no=(%%e+2)%%5+%%e/3"
rem 通过步进方向与当前位置计算下一个要探测的坐标
for /f "tokens=1,2" %%x in ("!cx! !cy!") do (
if "!use: %%x.%%y =!" neq "!use!" (
rem 判断此坐标是否可用
if "!try:"%%x^ %%y"=!"=="!try!" (
rem 判断此坐标是否已用
set back=
if !cx!-!cy!==%start% echo 无答案&pause&exit
if !cx!-!cy!==%end% call :end
rem 到达终点时调用输出模块（其实就不准备返回了...）
set try="!cx! !cy!",!try!
set "t=!no! !t!"
rem 如果该坐标可用，并且尚未使用过，则位移到此坐标，并阻止回退。
) else set use=!use: %%x.%%y = !
rem 若出现咬尾的情况，则标记此坐标不可用，并回退
)
)
)
rem 只要当前循环还没找到可用的去路，就按照概率依次探测三个方向上是否可用
)
if defined back (
set use=!use: %%c.%%d = !
set t=!t:~2!
set try=!try:*,=!
) else set back=1
rem 判断路线是否受阻，不畅则回退，并标记当前位置不可用
)
)
rem --------------------四、输出----------------------
:end
set f=!f:~-2!!f:~-4,2!
for %%a in (!t!) do (
for /f tokens^=1-2delims^=^,^"^ %%b in ("!try!") do (
for %%d in (!f:%%a^=!) do (
rem 排除来的方向
set /a "cx=%%b+(2*(%%d%%2)-1)*^!(%%d/3)","cy=%%c+(2*(%%d%%2)-1)*(%%d/3)","no=%%d+2*(%%d%%2)-1"
for /f "tokens=1,2" %%x in ("!cx! !cy!") do (
set try=!try:*"%%x %%y",="%%b %%c","%%x %%y",!
rem 逆序拼接结果中的相邻坐标
set new=!new!"%%b %%c",
rem 保存修正过的路径在 new 变量中
)
)
set try=!try:*,=!
)
)
for /f "tokens=1,2 delims=-" %%a in ("%end%") do set /a lx=%%a-1,ly=%%b
for %%a in ("%end:-= %" !new!) do (
if "!lx! !ly!" neq %%a for /f "tokens=1,2" %%b in ("%%~a") do (
set /a "n=%%b+1,fe=1+((%%b-lx+1&2)+(ly-%%c+2^2)),lx=%%b,ly=%%c"
if %%b-%%c==%end% set fe=%fe%
rem 计算偏移量及方向
for /f "tokens=1,2" %%e in ("!n! !fe!") do (
set .%%c=!.%%c:~,%%b!!ff:~%%f,1!!.%%c:~%%e!
)
rem 提取 try 变量，将结果对应坐标的符号转换为全角空格
)
)
::转换结果为可见图形
for /l %%d in (1 1 %my%) do echo !.%%d!
::打印结果
echo %time%
(del $ &pause&exit)>nul
::::::::::::::将结果转换为可见图形::::::::::::::::

复制代码

迷宫样本：

█████████████████████████████
█▓▓▓▓▓▓▓█▓▓▓▓▓▓▓█▓▓▓█▓▓▓▓▓█▓▓
█▓█████▓█████▓█▓▓▓███▓▓██▓▓▓█
█▓▓▓▓▓█▓▓▓▓▓█▓███▓▓▓█▓▓▓█████
███▓█▓█▓███▓▓▓█▓▓▓█▓███▓▓▓▓▓█
█▓▓▓█████▓█████████▓▓▓█████▓█
███▓▓█▓▓▓▓▓▓▓▓▓▓█▓▓▓█▓▓▓▓▓█▓█
█▓██▓█▓██████▓█▓█▓███████▓█▓█
█▓▓▓▓▓▓▓▓▓▓▓███▓█▓▓▓█▓▓▓▓▓█▓█
█▓▓▓█▓██▓██▓▓▓█▓███▓███████▓█
█▓▓▓█▓▓▓▓▓█▓█▓█▓▓▓█▓▓▓▓▓▓▓█▓█
█▓███████▓█▓█████▓█████▓███▓█
█▓▓▓▓█▓▓█▓█▓█▓▓▓▓▓█▓▓▓█▓█▓▓▓█
████▓█▓██▓███▓███████▓█▓███▓█
█▓▓▓▓█▓▓▓▓▓█▓▓▓█▓▓▓█▓▓▓▓█▓▓▓█
██████████▓█▓███▓█▓██▓███▓███
█▓▓▓▓▓▓█▓▓▓▓▓▓▓▓▓█▓▓█▓▓▓█▓▓▓█
█▓████▓█▓█▓███████▓████▓███▓█
█▓▓▓▓█▓███▓█▓▓█▓▓▓▓▓█▓▓▓█▓▓▓█
████▓█▓▓▓█▓██▓█████▓█▓███▓███
▓▓▓▓▓█▓█▓▓▓▓█▓▓▓▓▓▓▓█▓▓▓▓▓▓▓█
█████████████████████████████

复制代码

详见附件，附件包含：

【使用向导】.bat
解迷宫1 call.bat
解迷宫2 for.bat
解迷宫3 优化自适应.bat
解迷宫4 拼接相邻.bat
解迷宫5 拼接相邻2.bat
解迷宫6 拼接相邻自适应.bat
迷宫单线.txt
迷宫宽线有回路.txt
迷宫.txt

复制代码

批处理解迷宫.rar (4.95 KB)
解谜宫效果：

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

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

[游戏娱乐] 批处理解迷宫

评分