用Google新图形化编程语言Blockly写一类迷宫的通用解

在CB看到新闻:Blockly: Google新推出的图形化编程语言,手一贱点了链接,接着玩起了Demo中的迷宫游戏Maze。

http://blockly-demo.appspot.com/blockly/demos/maze/index.html

Maze是一个自定义类,提供向前向后移动,向左转向右转以及判断前后左右是否有墙等函数。
这里的迷宫是一个很规整的迷宫,墙都是上下左右的直线段,而且是单位长度的整倍,小人每次只能移动单位长度。
(大概从拓扑学上迷宫都可以约化成这样的规整迷宫?)

Demo中的迷宫很简单,顺序结构可以到达终点,但余想写一个通用的解法,可以解所有迷宫。
一个封闭迷宫,沿着墙的一边走,最终可以回到原点,这构成了一个环。如果目标地在这个环上,无论起始方向如何,都能到达目标地。
方向1:

方向2:

方向1中,即使途中有环,都可以避过捕捉。(1和2无本质区别)

余很快发现这个解法还是不够通用,比如下面的简单迷宫,这种解法永远无法找到目标地

因此这个程序只能对付目标和原点在同一个环的情况,或者说,程序需要依赖原点位置才能找到目标,还没足够通用

2012年6月1日 | 归档于 程序
  1. 2012年6月1日 21:30 | #1

    查了一下,maze对应的是迷路,而不是迷宫。=> Wiki 迷路園
    因此事实上实现了右手(左手)定律Orz

发表评论

XHTML: 您可以使用这些标签: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
:wink: :-| :-x :twisted: :) 8-O :( :roll: :-P :oops: :-o :mrgreen: :lol: :idea: :-D :evil: :cry: 8) :arrow: :-? :?: :!: