/// A-starノード.
class ANode {
enum eStatus {
None,
Open,
Closed,
}
/// ステータス
eStatus _status = eStatus.None;
/// 実コスト
int _cost = 0;
/// ヒューリスティック・コスト
int _heuristic = 0;
/// 親ノード
ANode _parent = null;
/// 座標
int _x = 0;
int _y = 0;
public int X {
get { return _x; }
}
public int Y {
get { return _y; }
}
public int Cost {
get { return _cost; }
}
/// コンストラクタ.
public ANode(int x, int y) {
_x = x;
_y = y;
}
/// スコアを計算する.
public int GetScore() {
return _cost + _heuristic;
}
/// ヒューリスティック・コストの計算.
public void CalcHeuristic(bool allowdiag, int xgoal, int ygoal) {
if(allowdiag) {
// 斜め移動あり
var dx = (int)Mathf.Abs (xgoal - X);
var dy = (int)Mathf.Abs (ygoal - Y);
// 大きい方をコストにする
_heuristic = dx > dy ? dx : dy;
}
else {
// 縦横移動のみ
var dx = Mathf.Abs (xgoal - X);
var dy = Mathf.Abs (ygoal - Y);
_heuristic = (int)(dx + dy);
}
Dump();
}
/// ステータスがNoneかどうか.
public bool IsNone() {
return _status == eStatus.None;
}
/// ステータスをOpenにする.
public void Open(ANode parent, int cost) {
Debug.Log (string.Format("Open: ({0},{1})", X, Y));
_status = eStatus.Open;
_cost = cost;
_parent = parent;
}
/// ステータスをClosedにする.
public void Close() {
Debug.Log (string.Format ("Closed: ({0},{1})", X, Y));
_status = eStatus.Closed;
}
/// パスを取得する
public void GetPath(List<Point2> pList) {
pList.Add(new Point2(X, Y));
if(_parent != null) {
_parent.GetPath(pList);
}
}
public void Dump() {
Debug.Log (string.Format("({0},{1})[{2}] cost={3} heuris={4} score={5}", X, Y, _status, _cost, _heuristic, GetScore()));
}
public void DumpRecursive() {
Dump ();
if(_parent != null) {
// 再帰的にダンプする.
_parent.DumpRecursive();
}
}
}
/// A-starノード管理.
class ANodeMgr {
/// 地形レイヤー.
Layer2D _layer;
/// 斜め移動を許可するかどうか.
bool _allowdiag = true;
/// オープンリスト.
List<ANode> _openList = null;
/// ノードインスタンス管理.
Dictionary<int,ANode> _pool = null;
/// ゴール座標.
int _xgoal = 0;
int _ygoal = 0;
public ANodeMgr(Layer2D layer, int xgoal, int ygoal, bool allowdiag=true) {
_layer = layer;
_allowdiag = allowdiag;
_openList = new List<ANode>();
_pool = new Dictionary<int, ANode>();
_xgoal = xgoal;
_ygoal = ygoal;
}
/// ノード生成する.
public ANode GetNode(int x, int y) {
var idx = _layer.ToIdx(x, y);
if(_pool.ContainsKey(idx)) {
// 既に存在しているのでプーリングから取得.
return _pool[idx];
}
// ないので新規作成.
var node = new ANode(x, y);
_pool[idx] = node;
// ヒューリスティック・コストを計算する.
node.CalcHeuristic(_allowdiag, _xgoal, _ygoal);
return node;
}
/// ノードをオープンリストに追加する.
public void AddOpenList(ANode node) {
_openList.Add(node);
}
/// ノードをオープンリストから削除する.
public void RemoveOpenList(ANode node) {
_openList.Remove(node);
}
/// 指定の座標にあるノードをオープンする.
public ANode OpenNode(int x, int y, int cost, ANode parent) {
// 座標をチェック.
if(_layer.IsOutOfRange(x, y)) {
// 領域外.
return null;
}
if(_layer.Get(x, y) > 1) {
// 通過できない.
return null;
}
// ノードを取得する.
var node = GetNode(x, y);
if(node.IsNone() == false) {
// 既にOpenしているので何もしない
return null;
}
// Openする.
node.Open(parent, cost);
AddOpenList(node);
return node;
}
/// 周りをOpenする.
public void OpenAround(ANode parent) {
var xbase = parent.X; // 基準座標(X).
var ybase = parent.Y; // 基準座標(Y).
var cost = parent.Cost; // コスト.
cost += 1; // 一歩進むので+1する.
if(_allowdiag) {
// 8方向を開く.
for(int j = 0; j < 3; j++) {
for(int i = 0; i < 3; i++) {
var x = xbase + i - 1; // -1～1
var y = ybase + j - 1; // -1～1
OpenNode(x, y, cost, parent);
}
}
}
else {
// 4方向を開く.
var x = xbase;
var y = ybase;
OpenNode (x-1, y, cost, parent); // 右.
OpenNode (x, y-1, cost, parent); // 上.
OpenNode (x+1, y, cost, parent); // 左.
OpenNode (x, y+1, cost, parent); // 下.
}
}
/// 最小スコアのノードを取得する.
public ANode SearchMinScoreNodeFromOpenList() {
// 最小スコア
int min = 9999;
// 最小実コスト
int minCost = 9999;
ANode minNode = null;
foreach(ANode node in _openList) {
int score = node.GetScore();
if(score > min) {
// スコアが大きい
continue;
}
if(score == min && node.Cost >= minCost) {
// スコアが同じときは実コストも比較する
continue;
}
// 最小値更新.
min = score;
minCost = node.Cost;
minNode = node;
}
return minNode;
}
}
最終更新：2015年04月05日 17:57
