Download: MazeDemo.zip
- 按下Run可執行迷宮出口搜尋
- 按下Stop可停止迷宮出口搜尋
- 按下Reset可將狀態歸零
- 按下Enable可以自訂迷宮,透過滑鼠的點擊,以及托移紅色(終點)/綠色(起點)方塊來修改。
- 按下Disable可以關閉客制化,一旦開啟修改模式,修改完請手動關閉,否則無法執行迷宮搜尋。
- 程式防呆處理有限,請勿做白目舉動。
迷宮算是在程式設計裡一個很經典的設計問題,絕大數的人在用程式來解迷宮時多半都使用Recursive的形式來撰寫,但是在Flash底下我則是選擇以Stack/Array的形式來設計,一方面是受限於Flash Stack Size,而另一方面則是為了方便圖形化。
下面的迷宮演算是使用一種類似stack的形式來撰寫,這種演算是建立在已知全體地圖下才適用,如果要達到在未知地圖的自由空間裡搜尋,那個演算就會稍微複雜點。
/* SimpleMazeDemo */
package {
import flash.display.Sprite;
import flash.utils.Timer;
import flash.events.TimerEvent;
import com.xinyu.geom.Maze;
import com.xinyu.geom.Ball;
import com.xinyu.geom.Position2D;
public class MazeDemo extends Sprite {
private var pos:Position2D;
private var maze:Maze;
private var obj:Ball;
private var path:Array;
private var iPath:uint = 0;
private var timer:Timer;
private const STEP:Number = 40;
private const DIRECTION:Array = [new Position2D(0,-1), new Position2D(0,1), new Position2D(-1,0), new Position2D(1,0)];
public function MazeDemo() {
maze = new Maze(10, 10, STEP);
addChild(maze);
path = new Array(50);
for(var i:uint = 0; i<path.length;i++){
path[i] = new Position2D();
}
obj = new Ball(0xCCCCCC, 0x000000, STEP/2, 90);
addChild(obj);
obj.x = maze.start.x * STEP + STEP/2;
obj.y = maze.start.y * STEP + STEP/2;
pos = new Position2D(maze.start.x, maze.start.y);
maze.setPath(pos);
path[iPath].x = pos.x;
path[iPath].y = pos.y;
timer = new Timer(50);
timer.addEventListener(TimerEvent.TIMER, onTimer);
timer.start();
}
private function onTimer(event:TimerEvent):void {
if (pos.x == maze.end.x && pos.y == maze.end.y) {
timer.stop();
}
if(path[iPath].dir){
if (!maze.isValid(pos, DIRECTION[path[iPath].dir-1])){
moveForward(DIRECTION[path[iPath].dir-1]);
}else{
path[iPath].dir--;
}
}else{
backTrack();
}
}
private function moveForward(dir:Position2D):void {
path[iPath].dir--;
updatePos(dir);
maze.setPath(pos);
iPath++;
path[iPath].x = pos.x;
path[iPath].y = pos.y;
}
private function backTrack():void{
var dir:Position2D = new Position2D(path[iPath-1].x - pos.x, path[iPath-1].y - pos.y);
path[iPath] = new Position2D();
maze.cleanPath(pos);
--iPath;
updatePos(dir);
}
private function updatePos(dir:Position2D):void{
pos.x += dir.x;
pos.y += dir.y;
obj.x += dir.x * STEP;
obj.y += dir.y * STEP;
}
}
}
整個核心函式其實只有moveForward()跟backTrack()這兩個而已,可以說是非常簡單。而最上面的展示範例則是依造SimpleMazeDemo的基礎擴展而成。由於要實做UI的關係,所以完整程式碼篇幅就不小,所使用的class也不少,但是發佈後的swf很小(因為所有畫面上的物件都是由AS 3.0所撰寫出來的),詳細資訊請參考下載檔。