Board logo

标题: [其他] 批处理实现寻找迷宫最短路径 [打印本页]

作者: 0000    时间: 2017-10-22 14:06     标题: 批处理实现寻找迷宫最短路径

本帖最后由 0000 于 2017-10-22 14:20 编辑

(实在不知道怎么分类,就选了"其他")
其实原来有一个批处理解迷宫的解法,只是这个解法可能会生成一条非常长的路线,因为
rem 判断大方向,把最可能的方向作为首选,其余按概率排列


因此,这里修改了"批处理解迷宫"的算法,做了一个"寻找最短路径"的解法。
注意地图文件是当前目录下的map.txt
  1. @echo off&setlocal enabledelayedexpansion
  2. set>$&(for /f "delims==" %%a in ($) do set %%a=)&path %path%&del $
  3. :: 不使用 for /f 直接解析命令输出,是为了避免开启新进程影响效率
  4. :: 清洁变量环境,提升脚本效率
  5. echo %time%
  6. :: 一、自适应判断
  7. (
  8. rem 二分回溯法判断迷宫宽度
  9. set /p .1=
  10. set "$=!.1!#"
  11. for %%a in (128 64 32 16 8 4 2 1) do if !$:~%%a^,1!. NEQ . set /a mx+=%%a&set $=!$:~%%a!
  12. rem 计算迷宫高度
  13. for /f %%a in (map.txt) do set /a my+=1
  14. for /l %%a in (2 1 !my!) do set /p .%%a=
  15. )<map.txt
  16. :: mx、my为迷宫宽、高,.1~.N分别记载迷宫每一行的内容
  17. :: 获取墙对应的字符
  18. set 墙=!.1:~0,1!
  19. set /a xx=mx*2+1,yy=my+3
  20. :: 二、收集基本信息
  21. :: nx为宽度减一,用于后面的偏移,all为寻路时的总迭代上限
  22. set /a nx=mx-1,all=10000
  23. :: 确定出入口的位置
  24. set "se= "
  25. for /l %%a in (1 1 %my%) do (
  26. if not "!.%%a:~,1!"=="%墙%" set "se=!se!0.%%a "
  27. if not "!.%%a:~-1!"=="%墙%" set "se=!se!%nx%.%%a "
  28. )
  29. for /l %%a in (0 1 %nx%) do (
  30. if not "!.1:~%%a,1!"=="%墙%" set "se=!se!%%a.1 "
  31. if not "!.%my%:~%%a,1!"=="%墙%" set "se=!se!%%a.%my% "
  32. )
  33. :: 设置 se 变量中的第一个坐标为起点,最后一个坐标为终点
  34. for %%a in (!se!) do (
  35. if defined start (
  36.   set end=%%a
  37. ) else (
  38.   set start=%%a
  39. ))
  40. :: 三、开始
  41. ::反方向
  42. set dir_←=_x+=1
  43. set dir_↑=_y+=1
  44. set dir_→=_x-=1
  45. set dir_↓=_y-=1
  46. :: 从终点开始搜索
  47. set "ds= "
  48. set "ds1= %end% "
  49. for /l %%a in (1 1 %my%) do set .S%%a=!.%%a!
  50. for /l %%a in (1 1 %all%) do (
  51. rem 搜索完毕,没有线路
  52. if "!ds1: =!"=="" goto ok
  53. set count=%%a
  54. rem use为上一层迭代的位置(不能后退)
  55. set use=!ds!
  56. set ds=!ds1!
  57. set "ds1= "
  58. for %%b in (!ds!) do (
  59.   for /f "tokens=1-2 delims=." %%x in ("%%b") do (
  60.    for %%c in (← → ↑ ↓) do (
  61.     set /a _x=%%x,_y=%%y,!dir_%%c!
  62.     for /f "tokens=1-2" %%X in ("!_x! !_y!") do (
  63.      if defined .%%Y if %%X geq 0 (
  64.       if not "!.%%Y:~%%X,1!"=="!墙!" if "!use!"=="!use: %%X.%%Y =!" (
  65.        rem 标记最佳方向
  66.        set /a _x1=%%X+1
  67.        for %%Z in (!_x1!) do set .S%%Y=!.S%%Y:~,%%X!%%c!.S%%Y:~%%Z!
  68.        set "use=!use!%%X.%%Y "
  69.        rem 更新下一组搜索点
  70.        set "ds1=!ds1!%%X.%%Y "
  71.       )
  72.       rem 到达起点
  73.       if "%%x.%%y"=="%start%" goto ok
  74. ))))))
  75. :ok
  76. ::正方向
  77. set dir_←=_x-=1
  78. set dir_↑=_y-=1
  79. set dir_→=_x+=1
  80. set dir_↓=_y+=1
  81. for /f "tokens=1-2 delims=." %%x in ("%start%") do (
  82. set /a _x=%%x,_y=%%y
  83. )
  84. :: 根据标记来移动绘制点
  85. for /l %%a in (1 1 !count!) do (
  86. for /f "tokens=1-2" %%x in ("!_x! !_y!") do (
  87.   set _u=!.S%%y:~%%x,1!
  88.   if defined dir_!_u! (
  89.    for %%u in (!_u!) do (
  90.     set /a _x1=%%x+1
  91.     for %%z in (!_x1!) do set .%%y=!.%%y:~,%%x!%%u!.%%y:~%%z!
  92.     rem 获取下一绘制地点
  93.     set /a !dir_%%u!
  94. ))))
  95. for /l %%a in (1 1 !my!) do echo(!.%%a!
  96. echo %time%
  97. pause
复制代码
附上原帖的迷宫样例:
  1. █████████████████████████████
  2. █▓▓▓▓▓▓▓█▓▓▓▓▓▓▓█▓▓▓█▓▓▓▓▓█▓▓
  3. █▓█████▓█████▓█▓▓▓███▓▓██▓▓▓█
  4. █▓▓▓▓▓█▓▓▓▓▓█▓███▓▓▓█▓▓▓█████
  5. ███▓█▓█▓███▓▓▓█▓▓▓█▓███▓▓▓▓▓█
  6. █▓▓▓█████▓█████████▓▓▓█████▓█
  7. ███▓▓█▓▓▓▓▓▓▓▓▓▓█▓▓▓█▓▓▓▓▓█▓█
  8. █▓██▓█▓██████▓█▓█▓███████▓█▓█
  9. █▓▓▓▓▓▓▓▓▓▓▓███▓█▓▓▓█▓▓▓▓▓█▓█
  10. █▓▓▓█▓██▓██▓▓▓█▓███▓███████▓█
  11. █▓▓▓█▓▓▓▓▓█▓█▓█▓▓▓█▓▓▓▓▓▓▓█▓█
  12. █▓███████▓█▓█████▓█████▓███▓█
  13. █▓▓▓▓█▓▓█▓█▓█▓▓▓▓▓█▓▓▓█▓█▓▓▓█
  14. ████▓█▓██▓███▓███████▓█▓███▓█
  15. █▓▓▓▓█▓▓▓▓▓█▓▓▓█▓▓▓█▓▓▓▓█▓▓▓█
  16. ██████████▓█▓███▓█▓██▓███▓███
  17. █▓▓▓▓▓▓█▓▓▓▓▓▓▓▓▓█▓▓█▓▓▓█▓▓▓█
  18. █▓████▓█▓█▓███████▓████▓███▓█
  19. █▓▓▓▓█▓███▓█▓▓█▓▓▓▓▓█▓▓▓█▓▓▓█
  20. ████▓█▓▓▓█▓██▓█████▓█▓███▓███
  21. ▓▓▓▓▓█▓█▓▓▓▓█▓▓▓▓▓▓▓█▓▓▓▓▓▓▓█
  22. █████████████████████████████
复制代码
不过虽然路径短了,体积小了,速度也慢了




欢迎光临 批处理之家 (http://bbs.bathome.net/) Powered by Discuz! 7.2