[其他] 批处理实现寻找迷宫最短路径

0000

(实在不知道怎么分类,就选了"其他")
其实原来有一个批处理解迷宫的解法,只是这个解法可能会生成一条非常长的路线,因为

rem 判断大方向，把最可能的方向作为首选，其余按概率排列

因此,这里修改了"批处理解迷宫"的算法,做了一个"寻找最短路径"的解法。
注意地图文件是当前目录下的map.txt

@echo off&setlocal enabledelayedexpansion

set>$&(for /f "delims==" %%a in ($) do set %%a=)&path %path%&del $
:: 不使用 for /f 直接解析命令输出，是为了避免开启新进程影响效率
:: 清洁变量环境，提升脚本效率

echo %time%

:: 一、自适应判断
(
 rem 二分回溯法判断迷宫宽度
 set /p .1=
 set "$=!.1!#"
 for %%a in (128 64 32 16 8 4 2 1) do if !$:~%%a^,1!. NEQ . set /a mx+=%%a&set $=!$:~%%a!
 rem 计算迷宫高度
 for /f %%a in (map.txt) do set /a my+=1
 for /l %%a in (2 1 !my!) do set /p .%%a=
)<map.txt

:: mx、my为迷宫宽、高，.1~.N分别记载迷宫每一行的内容

:: 获取墙对应的字符
set 墙=!.1:~0,1!
set /a xx=mx*2+1,yy=my+3

:: 二、收集基本信息
:: nx为宽度减一，用于后面的偏移，all为寻路时的总迭代上限
set /a nx=mx-1,all=10000
:: 确定出入口的位置
set "se= "
for /l %%a in (1 1 %my%) do (
 if not "!.%%a:~,1!"=="%墙%" set "se=!se!0.%%a "
 if not "!.%%a:~-1!"=="%墙%" set "se=!se!%nx%.%%a "
)
for /l %%a in (0 1 %nx%) do (
 if not "!.1:~%%a,1!"=="%墙%" set "se=!se!%%a.1 "
 if not "!.%my%:~%%a,1!"=="%墙%" set "se=!se!%%a.%my% "
)

:: 设置 se 变量中的第一个坐标为起点，最后一个坐标为终点
for %%a in (!se!) do (
 if defined start (
  set end=%%a
 ) else (
  set start=%%a
))

:: 三、开始

::反方向
set dir_←=_x+=1
set dir_↑=_y+=1
set dir_→=_x-=1
set dir_↓=_y-=1

:: 从终点开始搜索
set "ds= "
set "ds1= %end% "

for /l %%a in (1 1 %my%) do set .S%%a=!.%%a!

for /l %%a in (1 1 %all%) do (
 rem 搜索完毕，没有线路
 if "!ds1: =!"=="" goto ok
 set count=%%a
 rem use为上一层迭代的位置(不能后退)
 set use=!ds!
 set ds=!ds1!
 set "ds1= "
 for %%b in (!ds!) do (
  for /f "tokens=1-2 delims=." %%x in ("%%b") do (
   for %%c in (← → ↑ ↓) do (
    set /a _x=%%x,_y=%%y,!dir_%%c!
    for /f "tokens=1-2" %%X in ("!_x! !_y!") do (
     if defined .%%Y if %%X geq 0 (
      if not "!.%%Y:~%%X,1!"=="!墙!" if "!use!"=="!use: %%X.%%Y =!" (
       rem 标记最佳方向
       set /a _x1=%%X+1
       for %%Z in (!_x1!) do set .S%%Y=!.S%%Y:~,%%X!%%c!.S%%Y:~%%Z!
       set "use=!use!%%X.%%Y "
       rem 更新下一组搜索点
       set "ds1=!ds1!%%X.%%Y "
      )
      rem 到达起点
      if "%%x.%%y"=="%start%" goto ok
))))))
:ok

::正方向
set dir_←=_x-=1
set dir_↑=_y-=1
set dir_→=_x+=1
set dir_↓=_y+=1

for /f "tokens=1-2 delims=." %%x in ("%start%") do (
 set /a _x=%%x,_y=%%y
)

:: 根据标记来移动绘制点
for /l %%a in (1 1 !count!) do (
 for /f "tokens=1-2" %%x in ("!_x! !_y!") do (
  set _u=!.S%%y:~%%x,1!
  if defined dir_!_u! (
   for %%u in (!_u!) do (
    set /a _x1=%%x+1
    for %%z in (!_x1!) do set .%%y=!.%%y:~,%%x!%%u!.%%y:~%%z!
    rem 获取下一绘制地点
    set /a !dir_%%u!
))))
for /l %%a in (1 1 !my!) do echo(!.%%a!
echo %time%

pause
复制代码

附上原帖的迷宫样例：

█████████████████████████████
█▓▓▓▓▓▓▓█▓▓▓▓▓▓▓█▓▓▓█▓▓▓▓▓█▓▓
█▓█████▓█████▓█▓▓▓███▓▓██▓▓▓█
█▓▓▓▓▓█▓▓▓▓▓█▓███▓▓▓█▓▓▓█████
███▓█▓█▓███▓▓▓█▓▓▓█▓███▓▓▓▓▓█
█▓▓▓█████▓█████████▓▓▓█████▓█
███▓▓█▓▓▓▓▓▓▓▓▓▓█▓▓▓█▓▓▓▓▓█▓█
█▓██▓█▓██████▓█▓█▓███████▓█▓█
█▓▓▓▓▓▓▓▓▓▓▓███▓█▓▓▓█▓▓▓▓▓█▓█
█▓▓▓█▓██▓██▓▓▓█▓███▓███████▓█
█▓▓▓█▓▓▓▓▓█▓█▓█▓▓▓█▓▓▓▓▓▓▓█▓█
█▓███████▓█▓█████▓█████▓███▓█
█▓▓▓▓█▓▓█▓█▓█▓▓▓▓▓█▓▓▓█▓█▓▓▓█
████▓█▓██▓███▓███████▓█▓███▓█
█▓▓▓▓█▓▓▓▓▓█▓▓▓█▓▓▓█▓▓▓▓█▓▓▓█
██████████▓█▓███▓█▓██▓███▓███
█▓▓▓▓▓▓█▓▓▓▓▓▓▓▓▓█▓▓█▓▓▓█▓▓▓█
█▓████▓█▓█▓███████▓████▓███▓█
█▓▓▓▓█▓███▓█▓▓█▓▓▓▓▓█▓▓▓█▓▓▓█
████▓█▓▓▓█▓██▓█████▓█▓███▓███
▓▓▓▓▓█▓█▓▓▓▓█▓▓▓▓▓▓▓█▓▓▓▓▓▓▓█
█████████████████████████████
复制代码

不过虽然路径短了,体积小了,速度也慢了