2011/05/25 Na-7
A*(エースター:最短経路探索アルゴリズム)サンプル
注意 | この資料は、筆者が自らの経験を記録したものであり、他人に勧めるものではありません。 この資料を参考として行った行為がいかなる結果になろうとも、筆者は責任を負いませんので予めご承知おきください。 |
◎目次
◎概要 |
◎使用ツール |
◎サンプルコード |
◎実行結果 |
◎補足事項 |
◎概要
ゲームを作る際に、探索アルゴリズムを利用したくなることがある(移動処理で、目的地までの最短経路を求める場合など)。
本稿では、A*(エースター:最短経路探索アルゴリズム)のサンプルコードを掲示する。
◎使用ツール
ツール名 | 入手元 |
XNA3.1(XNA GameStudio 3.1:ゲーム開発用フレームワーク) | http://msdn.microsoft.com/ja-jp/xna/default.aspx |
◎サンプルコード
using
System;namespace MoveCostTest04
{
///
<summary>
/// This is the main
type for your game
///
</summary>
public
class
Game1 :
Microsoft.Xna.Framework.Game
{
GraphicsDeviceManager
graphics;
SpriteBatch spriteBatch;
// スタートノード番号
private
const
int start = 0;
// ゴールノード番号
private
const
int goal = 5;
// コストの上限値
private
const
int costMax = 1000000000;
// エッジクラス
// コンストラクタ
public Edge(int
to, int cost)
{
this.To = to;
this.Cost = cost;
}
}
//
ノードクラス
class
Node
{
// このノードから伸びるエッジの情報
public
Edge[] Edges;
// エースター法のためのデータ
public
int Cost;
// このノードへの現時点で判明している最小コスト
public
int No;
// このノード番号(最短経路確認用)
public
int From;
// 親のノード番号(最短経路確認用)
public
string Name;
// ノード名称(最短経路確認用)
public
Vector2 Pos;
// ノードの座標(最短経路確認用)
// コンストラクタ
// ノードの宣言
// ノードリストの宣言
private
List<Node>
openList;
private
List<Node>
closeList;
// スタートノードの宣言
private
Node s;
// ゴールノードの宣言
private
Node g;
public Game1()
{
graphics =
new
GraphicsDeviceManager(this);
Content.RootDirectory = "Content";
}
///
<summary>
///
Allows the game to perform any initialization it needs to before starting to
run.
/// This is
where it can query for any required services and load any non-graphic
/// related
content. Calling base.Initialize will enumerate through any components
/// and
initialize them as well.
///
</summary>
protected
override
void Initialize()
{
// TODO: Add your initialization logic here
base.Initialize();
}
///
<summary>
///
LoadContent will be called once per game and is the place to load
/// all of
your content.
///
</summary>
protected
override
void LoadContent()
{
// Create a new SpriteBatch, which can be used to
draw textures.
spriteBatch = new
SpriteBatch(GraphicsDevice);
// TODO: use this.Content to load your
game content here
// コストの初期設定
this.nodes =
new
Node[]
{
new
Node(0,
"A",
new
Vector2(0, 0),
new
Edge[]
{
new
Edge(1, 1),
new
Edge(3, 2),
new
Edge(4, 3)
}),
new
Node(1,
"B",
new
Vector2(1, 0),
new
Edge[]
{
new
Edge(0, 1),
new
Edge(2, 4),
new
Edge(4, 1)
}),
new
Node(2,
"C",
new
Vector2(2, 0),new
Edge[]
{
new
Edge(1, 4),
new
Edge(4, 1),
new
Edge(5, 3)
}),
new Node(3,
"D",
new
Vector2(0, -1),new
Edge[]
{
new
Edge(0, 2),
new
Edge(4, 2)
}),
new
Node(4,
"E",
new
Vector2(1, -1),new
Edge[]
{
new
Edge(0, 3),
new
Edge(1, 1),
new
Edge(2, 1),
new
Edge(3, 2),
new
Edge(5, 3)
}),
new
Node(5,
"F",
new
Vector2(2, -1),new
Edge[]
{
new
Edge(2, 3),
new
Edge(4, 3)
}),
};
// エースター法による最短経路探索
this.searchA(goal);
// コンソールに出力する
this.consoleOut();
}
///
<summary>
///
UnloadContent will be called once per game and is the place to unload
/// all
content.
///
</summary>
protected
override
void UnloadContent()
{
// TODO: Unload any non ContentManager content
here
}
///
<summary>
///
Allows the game to run logic such as updating the world,
///
checking for collisions, gathering input, and playing audio.
///
</summary>
///
<param name="gameTime">Provides
a snapshot of timing values.</param>
protected
override
void Update(GameTime
gameTime)
{
// Allows the game to exit
if (GamePad.GetState(PlayerIndex.One).Buttons.Back
== ButtonState.Pressed)
this.Exit();
// TODO: Add your update logic here
base.Update(gameTime);
}
///
<summary>
///
This is called when the game should draw itself.
///
</summary>
///
<param name="gameTime">Provides
a snapshot of timing values.</param>
protected
override
void Draw(GameTime
gameTime)
{
GraphicsDevice.Clear(Color.CornflowerBlue);
// TODO: Add your drawing code here
base.Draw(gameTime);
}
//
エースター法による最短経路探索
private
void searchA(int
goal)
{
// 1.ゴールノード(G )とスタートノード(S )を作成する。
// また計算中のノードを格納しておくためのリスト(Openリスト)と、
// 計算済みのノードを格納しておくリスト(Closeリスト)を用意する。
this.g =
this.nodes[goal];
this.s =
this.nodes[start];
this.openList =
new
List<Node>();
this.closeList =
new
List<Node>();
// 2.スタートノードをOpenリストに追加する、
// このときg*(S)
= 0 でありf*(S) = h*(S) となる。
//
またCloseリストは空にする。
this.openList.Add(this.s);
this.s.Cost =
this.heuristic(this.s);
while (true)
{
// 3.Openリストが空なら探索は失敗とする
// (スタートからゴールにたどり着くような経路が存在しなかったことになる)。
if (this.openList.Count
== 0)
break;
// 4.Openリストに格納されているノードの内、最小のf*(n) を持つノードn
を取り出す。
int openListNo = -1;
int nodeNo = -1;
Node n =
null;
int minCost =
costMax;
for (int
i = 0; i < this.openList.Count;
i++)
{
if (this.openList[i].Cost
< minCost)
{
openListNo = i;
nodeNo = this.openList[i].No;
n = this.openList[i];
minCost = n.Cost;
}
}
// 5.n = G であるなら探索を終了する。
this.openList.Remove(n);
}
// 6.n に隣接している全てのノード(ここでは隣接ノードをm
とおく)に対して以下の操作を行う
for (int
i = 0; i < n.Edges.Length; i++)
{
Node m =
this.nodes[n.Edges[i].To];
// 6.1.f '(m) = g*(n) + h*(m) + COST(n,m) を計算する、
// 6.2.m の状態に応じて以下の操作を行う
if (this.openList.IndexOf(m)
!= -1)
{
// m がOpenリストにある場合、f '(m) < f*(m)
であるならf*(m) = f '(m) に置き換える。
// このとき記録してあるm の親をn に置き換える。
if (fm < m.Cost)
{
m.Cost = fm;
m.From = n.No;
}
}
else
if (this.closeList.IndexOf(m)
!= -1)
{
// m がCloseリストにある場合、f '(m) < f*(m)
であるならf*(m) = f '(m) としてm をOpenリストに移動する。
// また記録してある m の親をn に置き換える。
if (fm < m.Cost)
{
m.Cost = fm;
m.From = n.No;
this.openList.Add(m);
this.closeList.Remove(m);
}
}
else
{
// m がOpenリストにもCloseリストにも含まれていない場合f*(m) =
f '(m) としm をOpenリストに追加する。
// このときm の親をn として記録する。
m.Cost = fm;
m.From = n.No;
this.openList.Add(m);
}
}
}
}
// ヒューリスティク関数
// 直線の長さを返す
return (int)line.Length();
}
// コンソールに出力する
// 最短経路を連結する
◎実行結果
A cost = 2 from = -1
B cost = 2 from = 0
C cost = 4 from = 4
D cost = 4 from = 0
E cost = 3 from = 1
F cost = 5 from = 4
root:F←E←B←A コスト:5
◎補足事項
・XNAの独自機能は一切使用していないので、余分なコードを削ればC#のサンプルとして利用可能。
・本稿のコードは、ウィキペディアの「アルゴリズムの流れ」をコーディングしたものである(1〜6のコメントはそちらから転記した)。
・ノード&エッジデータは、以下の図を例題とした。
・参考