Board logo

标题: [游戏娱乐] 批处理解迷宫 [打印本页]

作者: CrLf    时间: 2011-8-11 00:22     标题: 批处理解迷宫

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

以下为第六版代码:
  1. @echo off&setlocal enabledelayedexpansion
  2. set>$
  3. (for /f "delims==" %%a in ($) do set %%a=
  4. path %path%)
  5. rem 不使用 for /f 直接解析命令输出,是为了避免开启新进程影响效率
  6. :::::::::::清洁变量环境,提升脚本效率:::::::::::::
  7. rem -----------------一、自适应判断-------------------
  8. (set /p .1=
  9. set "$=!.1!#"
  10. for %%a in (32 16 8 4 2 1) do (
  11. if !$:~%%a^,1!. NEQ . set /a mx+=%%a&set $=!$:~%%a!
  12. )
  13. rem 二分回溯法判断迷宫宽度
  14. for /f %%a in (迷宫.txt) do set /a my+=1
  15. rem 计算图形高度
  16. for /l %%a in (2 1 !my!) do (
  17. set /p .%%a=
  18. rem 把迷宫图形分行保存为变量
  19. set /a #!.%%a:~,1!+=1,#!.%%a:~-1!+=1
  20. rem 统计竖边框字符
  21. )
  22. for %%z in (!my!) do for /l %%a in (2 1 !mx!) do (
  23. set /a #!.1:~%%a,1!+=1,#!.%%z:~%%a,1!+=1
  24. rem 统计横边框字符
  25. )
  26. rem mx、my为迷宫宽、高,.1~.N分别记载迷宫每一行的内容
  27. )<迷宫.txt
  28. set /a xx=mx*2+1,yy=my+3
  29. mode con:lines=%yy% cols=%xx%
  30. echo %time%
  31. rem 调整窗口大小并显示时间
  32. set #>$
  33. for /f "tokens=1,2 delims=#=" %%a in ($) do (
  34. set #%%a=
  35. if %%b==2 set 路=%%a
  36. )
  37. rem 获取路对应的字符
  38. ::::::::::::::::::收集基本信息::::::::::::::::::::
  39. set /a nx=mx-1,all=mx*my
  40. ::nx 为宽度减一,用于后面的偏移,all 为寻路时的总迭代上限
  41. set "use= "
  42. for /l %%a in (0 1 %nx%) do (
  43. if defined .%%a (
  44. for /l %%b in (0 1 %nx%) do (
  45. if "!.%%a:~%%b,1!"=="%路%" set use= %%b.%%a!use!
  46. rem 保存可用坐标到 use 变量
  47. )
  48. if "!.%%a:~,1!"=="%路%" (
  49. set se=!se! 0-%%a
  50. set t=!t!2
  51. )
  52. if "!.%%a:~-1!"=="%路%" (
  53. set se=!se! %nx%-%%a
  54. set t=!t!1
  55. )
  56. )
  57. if "!.1:~%%a,1!"=="%路%" (
  58. set se=!se! %%a-1
  59. set t=!t!4
  60. )
  61. if "!.%my%:~%%a,1!"=="%路%" (
  62. set se=!se! %%a-%my%
  63. set t=!t!3
  64. )
  65. rem 保存边界出入口位置到变量 se,保存边界入口反方向的对应值到变量 t(方向:1下2右3上4左)
  66. )
  67. :::::::::::::::::::进一步分析:::::::::::::::::::::
  68. rem --------------------二、优化----------------------
  69. for %%a in (!se!) do if defined start (set end=%%a) else set start=%%a
  70. ::设置 se 变量中的第一个坐标为起点,第二个坐标为终点
  71. for /f "tokens=1-4 delims=-" %%a in ("%start%-%end%") do (
  72. set /a fx=%%a-%%c,fy=%%d-%%b
  73. if !fx:-^=! gtr !fy:-^=! (
  74. set f= 2 3 4 1
  75. ) else set f= 3 2 1 4
  76. if !fx! lss 0 (
  77. set f=!f: 1= @!
  78. set f=!f: 3= 1!
  79. set f=!f: @= 3!
  80. )
  81. if !fy! lss 0 (
  82. set f=!f: 2= @!
  83. set f=!f: 4= 2!
  84. set f=!f: @= 4!
  85. )
  86. rem 判断大方向,把最可能的方向作为首选,其余按概率排列
  87. set /a "fs=1+%%a/%nx%*2+^!~-%%b+(%%b/%my%)*3""
  88. set /a "fe=1+2*^!%%c+3*^!~-%%d+%%d/%my%"
  89. rem 计算在 ff 变量中的偏移量,用于获取与出入口方向对应的方向符号
  90. )
  91. set "ff=@→↓←↑"
  92. ::设置出入口的方向标志
  93. set try="%start:-= %"
  94. set "t=%t:~,1% "
  95. ::try 保存路线坐标,t 记录要排除的方向
  96. ::::::::::::::::规划主要探测方向::::::::::::::::::
  97. for %%a in ($ fx fy se) do set %%a=
  98. ::::::::::::::::再次清空多余变量::::::::::::::::::
  99. rem --------------------三、计算----------------------
  100. for /l %%a in (1 1 %all%) do (
  101. for /f tokens^=1-3delims^=^,^"^  %%b in ("!t:~,2!!try!") do (
  102. rem 获取当前坐标和方向
  103. for %%e in (!f:%%b^=!) do (
  104. rem 排除来的方向
  105. if defined back (
  106. set /a "cx=%%c+(2*(%%e/3)-1)*^!(%%e%%2)","cy=%%d+(2*(%%e/3)-1)*(%%e%%2)","no=(%%e+2)%%5+%%e/3"
  107. rem 通过步进方向与当前位置计算下一个要探测的坐标
  108. for /f "tokens=1,2" %%x in ("!cx! !cy!") do (
  109. if "!use: %%x.%%y =!" neq "!use!" (
  110. rem 判断此坐标是否可用
  111. if "!try:"%%x^ %%y"=!"=="!try!" (
  112. rem 判断此坐标是否已用
  113. set back=
  114. if !cx!-!cy!==%start% echo 无答案&pause&exit
  115. if !cx!-!cy!==%end% call :end
  116. rem 到达终点时调用输出模块(其实就不准备返回了...)
  117. set try="!cx! !cy!",!try!
  118. set "t=!no! !t!"
  119. rem 如果该坐标可用,并且尚未使用过,则位移到此坐标,并阻止回退。
  120. ) else set use=!use: %%x.%%y = !
  121. rem 若出现咬尾的情况,则标记此坐标不可用,并回退
  122. )
  123. )
  124. )
  125. rem 只要当前循环还没找到可用的去路,就按照概率依次探测三个方向上是否可用
  126. )
  127. if defined back (
  128. set use=!use: %%c.%%d = !
  129. set t=!t:~2!
  130. set try=!try:*,=!
  131. ) else set back=1
  132. rem 判断路线是否受阻,不畅则回退,并标记当前位置不可用
  133. )
  134. )
  135. rem --------------------四、输出----------------------
  136. :end
  137. set f=!f:~-2!!f:~-4,2!
  138. for %%a in (!t!) do (
  139. for /f tokens^=1-2delims^=^,^"^  %%b in ("!try!") do (
  140. for %%d in (!f:%%a^=!) do (
  141. rem 排除来的方向
  142. set /a "cx=%%b+(2*(%%d%%2)-1)*^!(%%d/3)","cy=%%c+(2*(%%d%%2)-1)*(%%d/3)","no=%%d+2*(%%d%%2)-1"
  143. for /f "tokens=1,2" %%x in ("!cx! !cy!") do (
  144. set try=!try:*"%%x %%y",="%%b %%c","%%x %%y",!
  145. rem 逆序拼接结果中的相邻坐标
  146. set new=!new!"%%b %%c",
  147. rem 保存修正过的路径在 new 变量中
  148. )
  149. )
  150. set try=!try:*,=!
  151. )
  152. )
  153. for /f "tokens=1,2 delims=-" %%a in ("%end%") do set /a lx=%%a-1,ly=%%b
  154. for %%a in ("%end:-= %" !new!) do (
  155. if "!lx! !ly!" neq %%a for /f "tokens=1,2" %%b in ("%%~a") do (
  156. set /a "n=%%b+1,fe=1+((%%b-lx+1&2)+(ly-%%c+2^2)),lx=%%b,ly=%%c"
  157. if %%b-%%c==%end% set fe=%fe%
  158. rem 计算偏移量及方向
  159. for /f "tokens=1,2" %%e in ("!n! !fe!") do (
  160. set .%%c=!.%%c:~,%%b!!ff:~%%f,1!!.%%c:~%%e!
  161. )
  162. rem 提取 try 变量,将结果对应坐标的符号转换为全角空格
  163. )
  164. )
  165. ::转换结果为可见图形
  166. for /l %%d in (1 1 %my%) do echo !.%%d!
  167. ::打印结果
  168. echo %time%
  169. (del $ &pause&exit)>nul
  170. ::::::::::::::将结果转换为可见图形::::::::::::::::
复制代码
迷宫样本:
  1. █████████████████████████████
  2. █▓▓▓▓▓▓▓█▓▓▓▓▓▓▓█▓▓▓█▓▓▓▓▓█▓▓
  3. █▓█████▓█████▓█▓▓▓███▓▓██▓▓▓█
  4. █▓▓▓▓▓█▓▓▓▓▓█▓███▓▓▓█▓▓▓█████
  5. ███▓█▓█▓███▓▓▓█▓▓▓█▓███▓▓▓▓▓█
  6. █▓▓▓█████▓█████████▓▓▓█████▓█
  7. ███▓▓█▓▓▓▓▓▓▓▓▓▓█▓▓▓█▓▓▓▓▓█▓█
  8. █▓██▓█▓██████▓█▓█▓███████▓█▓█
  9. █▓▓▓▓▓▓▓▓▓▓▓███▓█▓▓▓█▓▓▓▓▓█▓█
  10. █▓▓▓█▓██▓██▓▓▓█▓███▓███████▓█
  11. █▓▓▓█▓▓▓▓▓█▓█▓█▓▓▓█▓▓▓▓▓▓▓█▓█
  12. █▓███████▓█▓█████▓█████▓███▓█
  13. █▓▓▓▓█▓▓█▓█▓█▓▓▓▓▓█▓▓▓█▓█▓▓▓█
  14. ████▓█▓██▓███▓███████▓█▓███▓█
  15. █▓▓▓▓█▓▓▓▓▓█▓▓▓█▓▓▓█▓▓▓▓█▓▓▓█
  16. ██████████▓█▓███▓█▓██▓███▓███
  17. █▓▓▓▓▓▓█▓▓▓▓▓▓▓▓▓█▓▓█▓▓▓█▓▓▓█
  18. █▓████▓█▓█▓███████▓████▓███▓█
  19. █▓▓▓▓█▓███▓█▓▓█▓▓▓▓▓█▓▓▓█▓▓▓█
  20. ████▓█▓▓▓█▓██▓█████▓█▓███▓███
  21. ▓▓▓▓▓█▓█▓▓▓▓█▓▓▓▓▓▓▓█▓▓▓▓▓▓▓█
  22. █████████████████████████████
复制代码
详见附件,附件包含:
  1. 【使用向导】.bat
  2. 解迷宫1 call.bat
  3. 解迷宫2 for.bat
  4. 解迷宫3 优化自适应.bat
  5. 解迷宫4 拼接相邻.bat
  6. 解迷宫5 拼接相邻2.bat
  7. 解迷宫6 拼接相邻 自适应.bat
  8. 迷宫 单线.txt
  9. 迷宫 宽线有回路.txt
  10. 迷宫.txt
复制代码
[attach]5149[/attach]
解谜宫效果:
[attach]5150[/attach]




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