AI好きな人の備忘録

ここでは経路探索に必要なものページで載せたソースコードについて簡単に解説していく。

まずはNodeクラスから。
Node.h

#pragma once
#include "NodeType.h"
class Node
{
public:
	Node() :m_iIndex(invalid_node_index){}
	Node(int idx) :m_iIndex(idx){}

	// getter
	int Index()const{ return m_iIndex; }
	
private:
	int m_iIndex;	// ノードのインデックス（ノード番号）
};

Nodeを実装する上で必要最低限の情報はノード番号を表すインデックスのみ。
クラスの内容もコンストラクタとインデックスを取得するためのGetterメソッドしかない。
しかし、このように単純な構造になったのはこれから実装していく経路探索の結果が最短経路を上にある「ノードのインデックス」で出力されるためだ。
例）最短経路：1 -> 5 -> 3 -> 4 （最短経路はノード１，ノード５，ノード３，ノード４の順番で通る経路である事を表している）
このままだと２次元空間でのゲームや３次元空間でのゲームで経路探索をさせるためには情報が足りなさすぎるので、その際は適宜２次元ベクトルクラスや３次元ベクトルクラスをNodeが持つべき情報として定義してやる必要がある。

Edge.h

#pragma once
#include "NodeType.h"
class Edge
{
public:
	Edge() :m_iFrom(invalid_node_index), m_iTo(invalid_node_index){}
	Edge(int from, int to) :m_iFrom(from), m_iTo(to){}

	// getter & setter
	int   From()const{ return m_iFrom; }
	void  SetFrom(int NewIndex){ m_iFrom = NewIndex; }
	int   To()const{ return m_iTo; }
	void  SetTo(int NewIndex){ m_iTo = NewIndex; }

private:
	int m_iFrom;	// 接続元ノードのインデックス
	int m_iTo;			// 接続先ノードのインデックス
};

EdgeクラスもNodeクラスと似たような構造になっている。
Edgeクラスが持つべき情報として「接続元ノードのインデックス」「接続先ノードのインデックス」の２つしか無い。
クラスの内容もコンストラクタと接続元ノードのインデックスを操作するためのGetterとSetter、接続先ノードのインデックスを操作するためのGetterとSetterのみ。
EdgeクラスはNodeクラスとは異なり２次元空間でも３次元空間でも保持する情報を変更する必要はない。
ただ経路探索に用いるアルゴリズムによって追加するべき情報は存在する。
後に解説するダイクストラ法やA*(エースター)では「コスト」という情報が必要になる。
場合によってはエッジの「属性(砂利道であったりぬかるみであったり)」を示す情報も必要となる。
深さ優先探索や幅優先探索においては「コスト」「属性」の情報は不必要なので今回は定義しなかった。

Graph.h

#pragma once
#include <vector>
#include <list>

#include "NodeType.h"
class Node;
class Edge;
class Graph
{
public:
	typedef std::vector<Node> NodeVector;
	typedef std::list<Edge> EdgeList;
	typedef std::vector<EdgeList> EdgeListVector;
public:
	Graph(bool digraph) :m_iNextNodeIndex(0), m_bDigraph(digraph){}

	// ノードを追加する
	int AddNode(Node node);
	// エッジを追加する
	void AddEdge(Edge edge);
	// グラフ内のノード数を返す
	int NumNodes()const{ return m_Nodes.size(); }
	// これは有向グラフであるかどうか情報を返す
	bool IsDigraph()const{ return m_bDigraph; }
	// グラフ内にノードが存在するかをチェック
	bool IsEmpty()const{ return m_Nodes.empty(); }

	// getter & setter
	EdgeListVector GetEdges()const{ return m_Edges; }
	int GetNextFreeNodeIndex()const{ return m_iNextNodeIndex; }

	// グラフクラスが持つ list配列 や vector配列 へのアクセスを容易にするイテレータクラス
	class ConstEdgeIterator
	{
	private:
		EdgeList::const_iterator curEdge;
	public:
		ConstEdgeIterator(const Graph& graph, int node);
		const Edge* begin();
		const Edge* next();
		bool end();
	private:
		const Graph& G;
		const int NodeIndex;
	};

private:
	// 引数で指定した from と to を持つエッジはグラフ内で唯一なものかをチェックする
	bool UniqueEdge(int from, int to)const;

private:
	// このグラフ内にある全ノードのインスタンス
	NodeVector m_Nodes;
	// このグラフ内にある全エッジのインスタンス
	EdgeListVector m_Edges;
	// このグラフは有向グラフであるかどうか
	bool m_bDigraph;
	// 次に追加されるノードのインデックス
	int m_iNextNodeIndex;
};

GraphクラスはNodeクラス、Edgeクラスと比べると少し実装する内容は多い。
話は逸れるがNodeクラス、Edgeクラスを直接操作するより誰か間を取り持つクラスを定義し、そちらでNodeクラス、Edgeクラスを操作出来るようにしてしまったほうがプログラムの安全性が多少は上がる（余計な操作をさせないため）。
AddNodeやAddEdgeは名前の通りノード情報を追加したり、エッジ情報を追加したりするだけだが、安全に追加するために中では少し気の利いたコードを書いたりしている。
話を戻して、Graphクラスが持つ情報は「グラフ内にある全ノードの情報」「グラフ内にある全エッジの情報」「このグラフは有向グラフであるかどうかのフラグ」「次回追加されるノードのインデックス」だ。
メソッドはノード情報を追加するメソッド、エッジ情報を追加するメソッド、グラフ内のノード数を返すメソッド等のグラフの作成、経路探索する上で便利なメソッドを備えている。