AI好きな人の備忘録

経路探索において必要なクラスをここでは解説していく。
ページ後半に記述しているソースは「実例で学ぶゲームAIプログラミング」の経路探索の章を参考にした。
しかしこれから実装をしていくクラスは深さ優先探索を実装していく上で必要最低限のインターフェースしか備えていない。
今後紹介していく幅優先探索、ダイクストラ法、A*(エースター)を実装する際に必要なメソッドやメンバ変数があればここで解説するクラスを拡張していく形とする。

経路探索に必要なオブジェクトは３つある。
１つ目はノードオブジェクト、２つ目はエッジオブジェクト、３つ目はノードオブジェクトとエッジオブジェクトを包含するグラフオブジェクト。

それぞれのオブジェクトを図で表してみる


ノード０はノード１とノード２に繋がり、ノード１はノード０とノード４と繋がっている。
上記の図は無向グラフと言われており、ノード間を繋ぐエッジに向きの情報が無い。
すなわち、ノード間の相互移動が可能である事を示している。

無向グラフの他に有向グラフという物もある。
有向グラフの場合は下の図のようになる。

無向グラフと異なる点はエッジに向きを表す矢印が付いただけだ。
無向グラフの場合だとノード０とノード１では相互移動が可能であった。しかし、有向グラフの場合ノード１はノード０へと移動することが可能だがノード０からノード１への移動は不可能である。

グラフ自体の説明はこれくらいで十分だと思う。（足りなければコメントでその旨を書いてくれると嬉しい）
では、実際のソースコードを載せる。

NodeType.h

#pragma once
enum
{
	invalid_node_index = -1
};

Node.h

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

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

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){}

	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;	// 接続先ノードのインデックス
};

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.cpp

#include <cassert>
#include <string>
#include <iostream>

#include "Graph.h"
#include "Node.h"
#include "Edge.h"

// ノードを追加する
int Graph::AddNode(Node node)
{
	if (node.Index() < (int)m_Nodes.size())
	{
		assert(m_Nodes[node.Index()].Index() == invalid_node_index && "<Graph::AddNode>: 無効なインデックスです");
		m_Nodes[node.Index()] = node;
		return m_iNextNodeIndex;
	}
	else
	{
		assert(node.Index() == m_iNextNodeIndex && "<Graph::AddNode>: 無効なインデックスです");
		m_Nodes.push_back(node);
		m_Edges.push_back(EdgeList());
		return m_iNextNodeIndex++;
	}
}
// エッジを追加する
void Graph::AddEdge(Edge edge)
{
	// 引数のエッジが持つ接続元IDと接続先IDのインデックスが無効な値かチェック
	if ((m_Nodes[edge.To()].Index() != invalid_node_index) &&
		(m_Nodes[edge.From()].Index() != invalid_node_index))
	{
		// グラフ内に同様のインデックスを持つエッジが存在するかチェック
		if (UniqueEdge(edge.From(), edge.To()))
			m_Edges[edge.From()].push_back(edge);

		// このグラフは有向グラフであるかどうかチェック
		if (!m_bDigraph)
		{
			// グラフ内に同様のインデックスを持つエッジが存在するかチェック
			if (UniqueEdge(edge.To(), edge.From()))
			{
				// 新しいエッジを作成（このエッジは上記でpush_backしたエッジと対になるエッジである）
				Edge NewEdge = edge;
				NewEdge.SetTo(edge.From());
				NewEdge.SetFrom(edge.To());
				m_Edges[edge.To()].push_back(NewEdge);
			}
		}
	}
}

// 引数で指定した from と to を持つエッジはグラフ内で唯一なものかをチェックする
bool Graph::UniqueEdge(int from, int to)const
{
	for (EdgeList::const_iterator curEdge = m_Edges[from].begin();
		curEdge != m_Edges[from].end();
		++curEdge)
	{
		if (curEdge->To() == to)
			return false;
	}
	return true;
}


Graph::ConstEdgeIterator::ConstEdgeIterator(const Graph& graph, int node)
: G(graph)
, NodeIndex(node)
{
	curEdge = G.m_Edges[NodeIndex].begin();
}

const Edge* Graph::ConstEdgeIterator::begin()
{
	curEdge = G.m_Edges[NodeIndex].begin();
	return &(*curEdge);
}

const Edge* Graph::ConstEdgeIterator::next()
{
	++curEdge;
	if (end())
		return NULL;
	else
		return &(*curEdge);
}

bool Graph::ConstEdgeIterator::end()
{
	return (curEdge == G.m_Edges[NodeIndex].end());
}

以上がグラフを構成するのに必要なクラスである。
冒頭で言ったようにこのクラス構成は深さ優先探索を実装する上で必要最低限のものしか実装していない。
他のアルゴリズムを実装する上で必要なメソッドやメンバ変数が増えればこのクラス構成を元に追記していく形とする。