2011/05/25 Na-7
 

技術資料一覧に戻る

 

A*(エースター:最短経路探索アルゴリズム)サンプル

 

注意 この資料は、筆者が自らの経験を記録したものであり、他人に勧めるものではありません。

この資料を参考として行った行為がいかなる結果になろうとも、筆者は責任を負いませんので予めご承知おきください。

 

◎目次

◎概要
◎使用ツール
◎サンプルコード
◎実行結果
◎補足事項

 

 

◎概要

ゲームを作る際に、探索アルゴリズムを利用したくなることがある(移動処理で、目的地までの最短経路を求める場合など)。

本稿では、A*(エースター:最短経路探索アルゴリズム)のサンプルコードを掲示する。

 

 

 

◎使用ツール

ツール名 入手元
XNA3.1(XNA GameStudio 3.1:ゲーム開発用フレームワーク) http://msdn.microsoft.com/ja-jp/xna/default.aspx

 

 

◎サンプルコード

using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Audio;
using Microsoft.Xna.Framework.Content;
using Microsoft.Xna.Framework.GamerServices;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;
using Microsoft.Xna.Framework.Media;
using Microsoft.Xna.Framework.Net;
using Microsoft.Xna.Framework.Storage;
 

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;
 

        // エッジクラス
       
class Edge
       
{
           
// 接続先のノード番号
           
public int To;
           
// コスト
           
public int Cost;

            // コンストラクタ
           
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;   // ノードの座標(最短経路確認用)

            // コンストラクタ
           
public Node(int no, string name, Vector2 pos, Edge[] edges)
            {
               
this.No = no;
               
this.Name = name;
               
this.Pos = pos;
               
this.Edges = edges;

               
this.Cost = costMax;
               
this.From = -1;
            }
        }

        // ノードの宣言
       
private Node[] nodes;

        // ノードリストの宣言
       
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 であるなら探索を終了する。
                //  それ以外の場合はn をCloseリストに移す。
               
if (n == this.g)
                {
                   
break;
                }
               
else
               
{
                   
this.closeList.Add(n);

                    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) を計算する、
                    // ここでCOST(n,m) はノードn からm へ移動するときのコストである。
                    // またg*(n) はg*(n) = f*(n) - h*(n) で求めることができる。
                   
int ga = n.Cost - this.heuristic(n);
                   
int ha = this.heuristic(m);
                   
int costNM = n.Edges[i].Cost;
                   
int fm = ga + ha + costNM;

                    // 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);
                    }
                }
            }
        }

        // ヒューリスティク関数
       
private int heuristic(Node n)
        {
           
// ノードとゴールを結ぶ直線
           
Vector2 line = g.Pos - n.Pos;

            // 直線の長さを返す
           
return (int)line.Length();
        }

        // コンソールに出力する
       
private void consoleOut()
        {
           
for (int i = 0; i < this.nodes.Length; i++)
            {
               
// コンソールに出力する
               
Console.WriteLine(
                   
this.nodes[i].Name
                    +
"\tcost = " + this.nodes[i].Cost.ToString()
                    +
"\tfrom = " + this.nodes[i].From.ToString()
                    );
            }

            // 最短経路を連結する
           
int last = goal;
            string root = this.nodes[last].Name;
           
while (last != start)
            {
                last =
this.nodes[last].From;
                root = root +
" ←" + this.nodes[last].Name;
            }
           
Console.WriteLine("root:" + root + " コスト:" + g.Cost.ToString());
        }
    }
}

 

 

◎実行結果

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のコメントはそちらから転記した)。

・ノード&エッジデータは、以下の図を例題とした。

・参考

 ・ウィキペディア

 ・Kangaroo's House

 

inserted by FC2 system