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

CrLf

迷宫规格不大于 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
复制代码

解谜宫效果：