[AS2,算法可视化]人走迷宫算法的可视化实现.[1]fficeffice" />
By EmilMtthtew ffice:smarttags" />05/10/11
小人在迷宫中寻路是一个非常经典而有趣的算法问题，主要用到的堆栈方面的知识还有一个深度优先搜索。算法的细节可以参考我的日志上的文章:
http://blog.csdn.net/EmilMatthew/archive/2005/10/06/496068.aspx
效果的演示请访问这个站点，由于要用到外部文件，所以只能放在我自己申请空间里进行演示:
只显示最正确的搜一条路线的版本:http://free5.e-168.cn/hhucskx/walkInTheMaze.swf
显示出全部搜索过程的版本: http://free5.e-168.cn/hhucskx/walkInTheMaze2.swf
这里主要谈一下可视化的实现:
其实是相当简单的，我们用堆栈作为存储中间结果的存储体，当然，越在顶上的表示的是越靠近终点的结点。
在本来只是平白的用打印进行输出的地方采用三个数组进行存储结果的转换(依次存放x方向路径，y 方向路径 和移动的方向)，然后从数组从后往前进行解析，再对应的加载相应的动画，即可。
我们请来了QQ堂里非常Q的狸猫MM来为我们演示这个效果，大家掌声欢迎.（听说叫小倩，不我我还是喜欢叫她狸猫MM，真的很可爱,很PP的样子~~~）
另外，由于这里是采用Flash进行实现，外部文件采用了xml 文件的方式来表示地图,
1表示为墙，0表示为路.
具体的例子如下:
<?xml version="1.0" encoding="gb2312"?>
<searchedMap rowNum=’8’ colNum=’11’ startX=’1’ startY=’1’ endX=’6’ endY=’6’>
<row>1,1,1,1,1,1,1,1,1,1,1</row>
<row>1,0,1,0,0,1,1,1,0,0,1</row>
<row>1,0,0,0,0,0,1,0,0,1,1</row>
<row>1,0,1,1,1,0,0,0,1,1,1</row>
<row>1,0,0,0,1,0,1,1,0,1,1</row>
<row>1,1,0,0,1,0,1,1,0,0,1</row>
<row>1,1,1,0,0,0,0,0,0,0,1</row>
<row>1,1,1,1,1,1,1,1,1,1,1</row>
</searchedMap>
假如你了解xml文件的话，相信对我上面所表达的信息可以说是一目了然.你可以通过变换地图的形式及起终点来观看不同条件下的算法效果.
该说明的部分就到这里了，下面是这个程序的具体实现：
1首先，定义一个结点类: 其实就是对C语言的源程序进行了一个代码转换的工作,你可以在注释中清楚的看到这一点.
class SearchNode
{
/*
refraction from c struct to as2 class
enum direction{UNSEARCHED,EAST,SOUTH,WEST,NORTH,SEARCHED};

struct searchNode
{
enum direction mDir;
int visited;
};
*/
public static var UNSEARCHED:Number=0;
public static var EAST:Number=1;
public static var SOUTH:Number=2;
public static var WEST:Number=3;
public static var NORTH:Number=4;
public static var SEARCHED:Number=5;

public var mDir:Number;
public var visited:Number

public function SearchNode()
{
mDir=0;
visited=0;
}
}

2接下来，就是实现主程序段的时候了:
2.1先谈一下显示最正确的搜一条路线的版本：
function CoreResolve():Void
{
var transXml:XML=new XML();
transXml.load(_root.gFileAddress);
transXml.ignoreWhite=true;
System.useCodepage = true;

transXml.onLoad=function(success):Void
{
if(success)
{
setGlobalVar(transXml);
memApply();
parseMapInfo(transXml);//for gMapArr.
dataInit();//for gAnsArr,gSearchNode.
/*Show Map*/
showMap();
/*Core Algorithms with animation show*/
pathSearch();
}
else
{
trace3(String("load news.xml error " "this.status:" this.status " "));
}
}
}

可以看到:
setGlobalVar(transXml),
memApply(),
parseMapInfo(transXml),
dataInit(),
showMap();这几步，都是算法实现及演示前的预备工作，在这里不做过多介绍，比较简单，具体的可以查看我在最后附上的源码.
下面要实现的，是本程序最为核心的地方，当然，前半部分搜索的过程也就是我blog上C语言实现版本的AS2重写而已，对我而言工作量不算大。
最后用红色笔标出的部分，实现了算法存储体与演示效果所需要的存储体---数组间的转换，也是很Easy的，最后用一个SetInterval来实现演示效果，对于我这个还能算得上是AS的熟手而言，这样的工作可谓驾轻就熟,呵呵~~~,就是这么简单.
function pathSearch():Void
{
var curX:Number=_root.gStartX;
var curY:Number=_root.gStartY;
var tmpX:Number=0;
var tmpY:Number=0;
var tmpDir:Number=0;
var flag:Number=1;
var stackX:eStack=new eStack();
var stackY:eStack=new eStack();
var stackDir:eStack=new eStack();
//animator ulti value.
var arrX:Array=new Array();
var arrY:Array=new Array();
var arrDir:Array=new Array();
var arrLen:Number=0;

trace(_root.gEndX);
trace(_root.gEndY);
if(curX==_root.gEndX&&curY==_root.gEndY)
{
stackX.push(curX);
stackY.push(curY);
stackDir.push(_root.gSearchNodeArr[curX][curY].mDir);
}
else
{
while(!(curX==_root.gStartX&&curY==_root.gStartY&&!flag))
{
flag=0;
if(!_root.gSearchNodeArr[curX][curY].visited)
_root.gSearchNodeArr[curX][curY].visited=1;
while(_root.gSearchNodeArr[curX][curY].mDir 1!=SearchNode.SEARCHED)
{
_root.gSearchNodeArr[curX][curY].mDir ;//find next direction
//EAST,SOUTH,WEST,NORTH,SEARCHED
switch(_root.gSearchNodeArr[curX][curY].mDir)
{
case SearchNode.EAST:tmpX=0;tmpY=1;//printf("e ");
break;
case SearchNode.SOUTH:tmpX=1;tmpY=0;//printf("s ");
break;
case SearchNode.WEST:tmpX=0;tmpY=-1;//printf("w ");
break;
case SearchNode.NORTH:tmpX=-1;tmpY=0;//printf("n ");
break;
default:
trace3("error dir search ");
}
if(_root.gMapArr[curX tmpX][curY tmpY]==WALKABLE&&!_root.gSearchNodeArr[curX tmpX][curY tmpY].visited)
{
stackX.push(curX);
stackY.push(curY);
stackDir.push(_root.gSearchNodeArr[curX][curY].mDir);

curX =tmpX;
curY =tmpY;
flag=1;
break;
}
}

if(flag&&curX==_root.gEndX&&curY==_root.gEndY)
{
trace3("target founded ");
trace("target founded ");
break;
}

if(flag==0&&!(curX==_root.gStartX&&curY==_root.gStartY))
{
curX=Number(stackX.pop());
curY=Number(stackY.pop());
stackDir.pop();
}
}
}

if(flag)
{
arrLen=0;
arrX[arrLen]=_root.gEndX;//because the target was not push into the stack,have a special consult.
arrY[arrLen]=_root.gEndY;
arrDir[arrLen]=SearchNode.SOUTH;
arrLen ;
while(!stackX.isEmpty()&&!stackY.isEmpty())
{
tmpX=Number(stackX.pop());
tmpY=Number(stackY.pop());
tmpDir=Number(stackDir.pop());
arrX[arrLen]=tmpX;
arrY[arrLen]=tmpY;
arrDir[arrLen]=tmpDir;
arrLen ;
_root.gAnsArr[tmpX][tmpY]=1;
}

_root.gAnsArr[_root.gEndX][_root.gEndY]=1;//because the target node was not push into the stacks.

for(var i:Number=0;i<_root.gRowNum;i )
{
var tmpStr:String=new String();
for(var j:Number=0;j<_root.gColNum;j )
if(_root.gAnsArr[j]==1)
{
tmpStr ="o ";
trace3("o ");
}
else
{
tmpStr ="* ";
trace3("* ");
}
trace3(" ");
trace(tmpStr);
}
}
else
{
trace3("no way lead to the target node ");
trace("no way lead to the target node ");
}

_root.gIndex=arrLen-1;
_root.attachMovie("mm","newMM",_root.getNextHighestDepth());
_root.newMM._x=-80;
_root.newMM._y=-80;
_root.gIntervalID=setInterval(showAnimator,_root.gFps,arrX,arrY,arrDir);
}

function showAnimator(inArrX:Array,inArrY:Array,inArrDir:Array):Void
{
if(_root.gIndex<=-1)clearInterval(_root.gIntervalID);
else
{

eval("_root.newMM")._x=_root.gLeftX _root.gSquareLen*inArrY[_root.gIndex];//posx
eval("_root.newMM")._y=_root.gTop _root.gSquareLen*inArrX[_root.gIndex];//posy
//dir
switch(inArrDir[_root.gIndex])
{
case SearchNode.EAST:
eval("_root.newMM").gotoAndStop(2);
break;
case SearchNode.SOUTH:
eval("_root.newMM").gotoAndStop(1);
break;
case SearchNode.WEST:
eval("_root.newMM").gotoAndStop(4);
break;
case SearchNode.NORTH:
eval("_root.newMM").gotoAndStop(3);
break;
default:
trace3("error dir search ");
}
_root.gIndex--;
}
}