[オリジナル]as 3で作ったA*の道を探す
オリジナルスタメン
www.eb163.com,転載は出典作者:iiacm(火事ドクロ)を残してください
A*アルゴリズムのアイデアは豊富で、ゲームの中で人物の役、敵の道を探す問題を解決するのはかなり良い方法です.以前帝国时代を游んでいた时、中の兵士が道を走っているのを见て、とても奇妙で、后でやっと知って、それはA*アルゴリズムの功労です.次第に学习に従って、このアルゴリズムに対して更に比类がない慕って、一度この名词を闻いて、心の中で1筋の感心の情が油然として生まれて......そこでずっと学习の方法を探して、绝えず帖を见て、検索して、ついに、jrの达人の発表する招待状(
http://www.eb163.com/club/viewthread.php?tid=2458&highlight=%D1%B0%C2%B7)と超兄の啓発の下で、自分のA*の例を書いて、彼らの助けに感謝して、出してみんなと一緒に分かち合います.
プレゼンテーションのアドレス:
http://www.eb163.com/club/thread-11209-1-1.html
一、demoの構造
demoは3つの部分に分けられます:MainClassドキュメントクラス--2次元地図を構築し、A*ルックアップクラスルックアップを呼び出します.AStar A*ルックアップアルゴリズムクラス--すべてのルックアップ時に使用されるメソッド関数を提供します.AStarGridノードのデータクラス――道を探す過程のために中間のデータ構造を提供して、このクラスのオブジェクトを導入して地図ユニットを剥離することができて、道を探す時操作ノードのデータオブジェクトは直接地図ユニットを操作する代わりに、管理しやすいです.具体的なコード:
二、A*道を探す手順
最初はA*の道を探す文章を読んだ时、すべてとても混乱して、その原理に対して理解していないため、甚だしきに至っては見れば見るほど混乱します......しかし、その原理と彼の道を探す手順をはっきりさせた后に、とても理解することができます.jrが投稿で述べたように、道を探す流れはそれぞれ:
1、道を探す過程は地図ユニット(またはノードと呼ばれる)を検査する過程であり、アルゴリズムは周囲の地形の評価によって経路を得る.道を探す前にいくつかのものを用意して、道を探すためにデータを保存する準備をして、彼らはそれぞれ:
1)オープン・リスト:検証済みおよび検証対象のノードを格納
2)クローズド・リスト:操作されたノードが格納され、検証され、最適評価値(後述)を持つノードのみが操作されたノードであり、パスは親ノードを遍歴することによって生成されます.
3)現在の操作ノード:検証され、計算された評価値が最も優れているノード
4)評価値:すなわちjr上級者投稿で述べたf=h+gであり、評価値fの関数は、h(水平方向と垂直方向の距離の和)にg(直線方向または45度方向の移動消費)を加えたものに等しい.h、gの値は自分で約束することができて、すべて1桁のものであればよくて、しかもgの値の直線方向の消耗値は必ず45度の方向の移動の消耗より大きくて、demoの中でh=10を使って、g=10(直線)、g=14(45度の方向)
2、始点から、始点をまず閉じたリストに入れて、その親ノードをnullに設定して、始点の周囲のノードを取得して、これらの周囲のノードも開放リストを加えて、彼らの親ノードを起点にして、開放リストの中のノードに対して検査を行って、同時に彼らのf、h、g値を計算して、その中のf値が最も小さいのを次の操作ノードに選択して、次に操作するオブジェクトがあり、このノードを閉じたリストに追加します.
3、現在の操作ノードの周囲のノードを取得し、これらのノードをオープンリストに配置する.ここでは、オープンリストにすでに要素があると考えている.オープンリストに追加する「周囲ノード」に判断しなければならない.この「周囲ノード」がすでにリストに存在する場合、リストに追加する操作をキャンセルする.次に、このノードが現在の操作ノードを通過した場合のg値が元のg値より小さいかどうかを見て、小さい場合は、このより小さいg値をこの「周囲ノード」に更新し、この「周囲ノード」の親ノードを現在の操作ノードに設定する.より大きい場合は、変更せずに次の「周辺ノード」を検証し続け、検証後にこれらの「周辺ノード」からf値が最も小さいものを次の操作ノードとして選択する......と再帰呼び出しが繰り返される
4、手順3の内容を繰り返して、閉じたリストに終点があることを発見するまで、私たちが終点に着いたことを説明して、再帰呼び出しを終了して、経路遡及を開始して、つまり終点から、彼らの親ノードを追跡して、これらの親ノードはすべて道を探す過程で評価値が最も優れていることを条件に設定して、親ノードがnullのノードを見つけて、出発点に戻って、道を探す過程を完成したことを説明します.
三、まとめ
さて、demoは終わり、学習過程は苦痛ですが、成果を得たときは喜びます・・・やっているうちに、道を探す手順を理解して、一歩一歩使う機能をパッケージ化すれば、各段階がはっきりと視野にさらされます.このdemoはA*探索におけるいくつかの原理のみを示しており,障害戦略や迂回戦略などのメカニズムはまだ組み込まれておらず,今後は絶えず改善されるだろう.ちなみに私の体験では、道を探す過程で地図ユニットを通り抜けて歩くことができるので、斜線の経路が見えます.これは検査の周囲のノードと関係があります.斜線を歩かないようにすれば、周囲のノードを検査するときに斜線方向のノードを追加しないでください.ハニカム型のような不規則な地図探索を行うには,同様に周囲ノードを検査する上で修正すればよい.中間操作対象のAStarGridクラスがあるため,探索クラスは,実際の地図の形状にかかわらず,伝達された地図データがどのようなものであるかにのみ関心を持ち,探索クラスの適応性が向上する.
www.eb163.com,転載は出典作者:iiacm(火事ドクロ)を残してください
A*アルゴリズムのアイデアは豊富で、ゲームの中で人物の役、敵の道を探す問題を解決するのはかなり良い方法です.以前帝国时代を游んでいた时、中の兵士が道を走っているのを见て、とても奇妙で、后でやっと知って、それはA*アルゴリズムの功労です.次第に学习に従って、このアルゴリズムに対して更に比类がない慕って、一度この名词を闻いて、心の中で1筋の感心の情が油然として生まれて......そこでずっと学习の方法を探して、绝えず帖を见て、検索して、ついに、jrの达人の発表する招待状(
http://www.eb163.com/club/viewthread.php?tid=2458&highlight=%D1%B0%C2%B7)と超兄の啓発の下で、自分のA*の例を書いて、彼らの助けに感謝して、出してみんなと一緒に分かち合います.
プレゼンテーションのアドレス:
http://www.eb163.com/club/thread-11209-1-1.html
一、demoの構造
demoは3つの部分に分けられます:MainClassドキュメントクラス--2次元地図を構築し、A*ルックアップクラスルックアップを呼び出します.AStar A*ルックアップアルゴリズムクラス--すべてのルックアップ時に使用されるメソッド関数を提供します.AStarGridノードのデータクラス――道を探す過程のために中間のデータ構造を提供して、このクラスのオブジェクトを導入して地図ユニットを剥離することができて、道を探す時操作ノードのデータオブジェクトは直接地図ユニットを操作する代わりに、管理しやすいです.具体的なコード:
package{
/*
iiacm( )， www.eb163.com
A* demo
*/
import flash.display.Sprite;
import flash.events.MouseEvent;
import flash.geom.Point;
public class MainClass extends Sprite{
//
protected var rowNum:uint=22;
//
protected var columnNum:uint=20;
//
protected var mcWidth:uint=25;
//
protected var mcHeight:uint=20;
//
protected var mcArr:Array=new Array();
// A* ，
protected var aStar:AStar=new AStar(mcArr);
//
protected var nowPoint:Point=new Point(5,5);
//
protected var endPoint:Point;
public function MainClass(){
init();
}
// ，
protected function init(){
createMcs();
}
// ，
protected function createMcs(){
for(var i:int=0; i<columnNum; i++){
mcArr[i]=new Array();
for(var j:int=0; j<rowNum; j++){
var sprite:Sprite=drawRect();
sprite.x=j*mcWidth;
sprite.y=i*mcHeight;
sprite.name="mc_"+i+"_"+j;
mcArr[i].push(sprite);
addChild(sprite);
sprite.addEventListener(MouseEvent.CLICK, onClickSpriteHandler);
}
}
}
// ， ， alpha
protected function onClickSpriteHandler(e:MouseEvent){
for(var i=0;i<mcArr.length;i++){
for(var j=0;j<mcArr[i].length;j++){
mcArr[i][j].alpha=1;
}
}
endPoint=checkMapPos(e.currentTarget as Sprite);
aStar.findPath(nowPoint, endPoint);
nowPoint=endPoint;
}
// ，
protected function checkMapPos(mapGrid:Sprite):Point{
var point:Point;
for(var i=0;i<mcArr.length;i++){
for(var j=0;j<mcArr[i].length;j++){
if(mapGrid.name==mcArr[i][j].name){
point=new Point(i,j);
break;
}
}
}
return point;
}
//
protected function drawRect():Sprite{
var sprite:Sprite=new Sprite();
sprite.graphics.lineStyle(.25, 0x232323, 1);
sprite.graphics.beginFill(0xffffff, 0.5);
sprite.graphics.drawRect(0, 0, mcWidth, mcHeight);
sprite.graphics.endFill();
return sprite;
}
}
}
package{
/*
iiacm( )， www.eb163.com
A*
A*
*/
import flash.geom.Point;
import flash.display.DisplayObject;
public class AStar{
//
protected var _closeList:Array=new Array();
//
protected var _openList:Array=new Array();
//
protected var _mapData:Array;
//
protected var way:Array=new Array();
//
protected var _startNode:AStarGrid;
//
protected var _targetNode:AStarGrid;
//
protected var _nowNode:AStarGrid;
// ， false， true
protected var _isFind:Boolean=false;
// ， g=10， obliqueG=14
public var g:Number=10;
public var obliqueG:Number=14;
//
public var h:Number=10;
// ， 8 8 ，
//public var direct:int=8;
// ，
public function AStar(mapData:Array){
_mapData=mapData;
}
//
public function findPath(startPos:Point, targetPos:Point):Array{
// 、
_startNode=new AStarGrid(startPos.x, startPos.y, _mapData[startPos.x][startPos.y]);
_targetNode=new AStarGrid(targetPos.x, targetPos.y, _mapData[targetPos.x][targetPos.y]);
//
_startNode.mc.alpha=0;
_targetNode.mc.alpha=0;
// ，
_nowNode=_startNode;
// null
setFather(_startNode, null);
//
way=new Array();
// g, h, f
countHG(_startNode);
//
addToOpen(_startNode);
addToClose(_startNode);
//
way=getAround(_startNode);
//-----------------------
return way;
}
// ，
protected function getAround(centreNode:AStarGrid):Array{
// ，
var aroundArr:Array=new Array();
var aroundNodeArr:Array=new Array();
// 、 aroundNodeArr aroundArr ，
if(centreNode.dC+1<_mapData[0].length){
aroundArr.push(_mapData[centreNode.dR][centreNode.dC+1]);
aroundNodeArr.push(dataToGrid(centreNode.dR, centreNode.dC+1, aroundArr[0]));
}
if(centreNode.dC-1>=0){
aroundArr.push(_mapData[centreNode.dR][centreNode.dC-1]);
aroundNodeArr.push(dataToGrid(centreNode.dR, centreNode.dC-1, aroundArr[1]));
}
if(centreNode.dR+1<_mapData.length){
aroundArr.push(_mapData[centreNode.dR+1][centreNode.dC]);
aroundNodeArr.push(dataToGrid(centreNode.dR+1, centreNode.dC, aroundArr[2]));
}
if(centreNode.dR-1>=0){
aroundArr.push(_mapData[centreNode.dR-1][centreNode.dC]);
aroundNodeArr.push(dataToGrid(centreNode.dR-1, centreNode.dC, aroundArr[3]));
}
if(centreNode.dR-1>=0 && centreNode.dC-1>=0){
aroundArr.push(_mapData[centreNode.dR-1][centreNode.dC-1]);
aroundNodeArr.push(dataToGrid(centreNode.dR-1, centreNode.dC-1, aroundArr[4]));
}
if(centreNode.dR+1<_mapData.length && centreNode.dC+1<_mapData[0].length){
aroundArr.push(_mapData[centreNode.dR+1][centreNode.dC+1]);
aroundNodeArr.push(dataToGrid(centreNode.dR+1, centreNode.dC+1, aroundArr[5]));
}
if(centreNode.dR-1>=0 && centreNode.dC+1<_mapData[0].length){
aroundArr.push(_mapData[centreNode.dR-1][centreNode.dC+1]);
aroundNodeArr.push(dataToGrid(centreNode.dR-1, centreNode.dC+1, aroundArr[6]));
}
if(centreNode.dR+1<_mapData.length && centreNode.dC-1>=0){
aroundArr.push(_mapData[centreNode.dR+1][centreNode.dC-1]);
aroundNodeArr.push(dataToGrid(centreNode.dR+1, centreNode.dC-1, aroundArr[7]));
}
// AStarGrid ， aroundNodeArr f
var fMaxGrid:AStarGrid;
// aroundNodeArr ， ， g, h, f ，
for(var n:int=0; n<aroundArr.length; n++){
setFather(aroundNodeArr[n], centreNode);
countHG(aroundNodeArr[n]);
addToOpen(aroundNodeArr[n]);
}
// aroundNodeArr f ， fMaxGrid
for(var i:int=1; i<aroundNodeArr.length; i++){
for(var m:int=aroundNodeArr.length-1; m>=i; m--){
if(aroundNodeArr[m].f<aroundNodeArr[m-1].f){
var sNode:AStarGrid=aroundNodeArr[m-1];
aroundNodeArr[m-1]=aroundNodeArr[m];
aroundNodeArr[m]=sNode;
}
}
}
// f ，
_nowNode=aroundNodeArr[0];
addToClose(aroundNodeArr[0]);
// _isFind
var finishArr:Array=new Array();
if(!_isFind){
// ， ；
getAround(_nowNode);
}else{
// ，
finishArr=getPath();
}
return finishArr;
}
// ， ， null，
protected function getPath():Array{
var pathArr:Array=new Array();
// ， ，
if(_targetNode.dR==_startNode.dR && _targetNode.dC==_startNode.dC){
pathArr.push(_targetNode);
}else{
// ， 、 ，
var node:AStarGrid=_targetNode;
pathArr.push(node);
while(node.father!=null){
var f:AStarGrid=node.father;
pathArr.push(f);
_mapData[node.dR][node.dC].alpha=.4;
node=node.father;
}
}
pathArr[0].mc.alpha=0;
_isFind=false;
_closeList=new Array();
_openList=new Array();
_startNode=null;
_targetNode=null;
return pathArr;
}
//
protected function setFather(sonNode:AStarGrid, fatherNode:AStarGrid){
sonNode.father=fatherNode;
}
// g, h, f
protected function countHG(node:AStarGrid){
countH(node);
countG(node);
node.f=node.h+node.g;
}
// h
protected function countH(node:AStarGrid):uint{
var xH:uint=Math.abs(_targetNode.dR-node.dR)*h;
var yH:uint=Math.abs(_targetNode.dC-node.dC)*h;
var hValue:uint=xH+yH;
node.h=hValue;
return hValue;
}
// g
protected function countG(node:AStarGrid):uint{
var n:AStarGrid=node;
var gValue:uint=0;
if(n.father!=null){
while(n.father!=null){
var f:AStarGrid=n.father;
if(f.dR==n.dR || f.dC==n.dC){
gValue+=g;
}else{
gValue+=obliqueG;
}
n=n.father;
}
}else{
gValue=0;
}
node.g=gValue;
return gValue;
}
//
protected function addToOpen(addedNode:AStarGrid){
/*for(var i:int=0; i<_openList.length;i++){
if(_openList[i].dR==_targetNode.dR && _openList[i].dC==_targetNode.dC){
_isFind=true;
setFather(_targetNode, addedNode);
break;
}
}
*/
// ， g ， g ， ，
if(!_isFind){
for(var n:int=0; n<_openList.length; n++){
if(_openList[n].dR==addedNode.dR && _openList[n].dC==addedNode.dC){
var oldG:uint=addedNode.g;
var newG:uint;
if(_nowNode.dR==addedNode.dR || _nowNode.dC==addedNode.dC){
newG=_nowNode.g+g;
}else{
newG=_nowNode.g+obliqueG;
}
if(newG<oldG){
setFather(addedNode, _nowNode);
countHG(addedNode);
}else{
}
}else{
_openList.push(addedNode);
}
}
}else{
}
}
//
protected function addToClose(addedNode:AStarGrid){
_closeList.push(addedNode);
// ， ，
for(var i:int=0; i<_closeList.length;i++){
if(_closeList[i].dR==_targetNode.dR && _closeList[i].dC==_targetNode.dC){
_isFind=true;
setFather(_targetNode, addedNode);
break;
}
}
}
//
protected function gridToData(starGrid:AStarGrid):*{
return _mapData[starGrid.dR][starGrid.dC];
}
//
protected function dataToGrid(r:uint, c:uint, mc:DisplayObject):*{
return new AStarGrid(r, c, mc, null);
}
}
}
package{
/*
iiacm( )， www.eb163.com
A*
*/
import flash.display.DisplayObject;
public class AStarGrid{
//
public var father:AStarGrid;
//
public var dR:uint;
//
public var dC:uint;
//
public var mc:DisplayObject;
//
public var h:uint=0;
//
public var g:uint=0;
// ，
public var f:uint=0;
// ，
public function AStarGrid(dataR:uint=0, dataC:uint=0, displayObj:DisplayObject=null, father=null){
father=father;
dR=dataR;
dC=dataC;
mc=displayObj;
}
}
}
二、A*道を探す手順
最初はA*の道を探す文章を読んだ时、すべてとても混乱して、その原理に対して理解していないため、甚だしきに至っては見れば見るほど混乱します......しかし、その原理と彼の道を探す手順をはっきりさせた后に、とても理解することができます.jrが投稿で述べたように、道を探す流れはそれぞれ:
1、道を探す過程は地図ユニット(またはノードと呼ばれる)を検査する過程であり、アルゴリズムは周囲の地形の評価によって経路を得る.道を探す前にいくつかのものを用意して、道を探すためにデータを保存する準備をして、彼らはそれぞれ:
1)オープン・リスト:検証済みおよび検証対象のノードを格納
2)クローズド・リスト:操作されたノードが格納され、検証され、最適評価値(後述)を持つノードのみが操作されたノードであり、パスは親ノードを遍歴することによって生成されます.
3)現在の操作ノード:検証され、計算された評価値が最も優れているノード
4)評価値:すなわちjr上級者投稿で述べたf=h+gであり、評価値fの関数は、h(水平方向と垂直方向の距離の和)にg(直線方向または45度方向の移動消費)を加えたものに等しい.h、gの値は自分で約束することができて、すべて1桁のものであればよくて、しかもgの値の直線方向の消耗値は必ず45度の方向の移動の消耗より大きくて、demoの中でh=10を使って、g=10(直線)、g=14(45度の方向)
2、始点から、始点をまず閉じたリストに入れて、その親ノードをnullに設定して、始点の周囲のノードを取得して、これらの周囲のノードも開放リストを加えて、彼らの親ノードを起点にして、開放リストの中のノードに対して検査を行って、同時に彼らのf、h、g値を計算して、その中のf値が最も小さいのを次の操作ノードに選択して、次に操作するオブジェクトがあり、このノードを閉じたリストに追加します.
3、現在の操作ノードの周囲のノードを取得し、これらのノードをオープンリストに配置する.ここでは、オープンリストにすでに要素があると考えている.オープンリストに追加する「周囲ノード」に判断しなければならない.この「周囲ノード」がすでにリストに存在する場合、リストに追加する操作をキャンセルする.次に、このノードが現在の操作ノードを通過した場合のg値が元のg値より小さいかどうかを見て、小さい場合は、このより小さいg値をこの「周囲ノード」に更新し、この「周囲ノード」の親ノードを現在の操作ノードに設定する.より大きい場合は、変更せずに次の「周辺ノード」を検証し続け、検証後にこれらの「周辺ノード」からf値が最も小さいものを次の操作ノードとして選択する......と再帰呼び出しが繰り返される
4、手順3の内容を繰り返して、閉じたリストに終点があることを発見するまで、私たちが終点に着いたことを説明して、再帰呼び出しを終了して、経路遡及を開始して、つまり終点から、彼らの親ノードを追跡して、これらの親ノードはすべて道を探す過程で評価値が最も優れていることを条件に設定して、親ノードがnullのノードを見つけて、出発点に戻って、道を探す過程を完成したことを説明します.
三、まとめ
さて、demoは終わり、学習過程は苦痛ですが、成果を得たときは喜びます・・・やっているうちに、道を探す手順を理解して、一歩一歩使う機能をパッケージ化すれば、各段階がはっきりと視野にさらされます.このdemoはA*探索におけるいくつかの原理のみを示しており,障害戦略や迂回戦略などのメカニズムはまだ組み込まれておらず,今後は絶えず改善されるだろう.ちなみに私の体験では、道を探す過程で地図ユニットを通り抜けて歩くことができるので、斜線の経路が見えます.これは検査の周囲のノードと関係があります.斜線を歩かないようにすれば、周囲のノードを検査するときに斜線方向のノードを追加しないでください.ハニカム型のような不規則な地図探索を行うには,同様に周囲ノードを検査する上で修正すればよい.中間操作対象のAStarGridクラスがあるため,探索クラスは,実際の地図の形状にかかわらず,伝達された地図データがどのようなものであるかにのみ関心を持ち,探索クラスの適応性が向上する.