[Flash] Maze

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所撰寫出來的），詳細資訊請參考下載檔。