CODE:

class	Node
{
	//ノードは独自のIDを持つ
	int		m_ID;

	Vec2D	m_Pos;


	//_IDの操作
	static int nextID;

public:

	Node(Vec2D	pos)
		:m_Pos(pos)
	{
		m_ID = nextID;
		++nextID;
	}


	
	int		ID()const{ return m_ID; }
	Vec2D	Pos()const{ return m_Pos; }
};

CODE:

class	Link
{
	//IDで定める
	int		m_From;
	int		m_To;

	double	m_Cost;

public:

	Link(int from, int to, int cost)
		:m_From(from),
		 m_To(to),
		 m_Cost(cost)
	{}


	int		From()const{ return m_From; }
	int		To()const{ return m_To; }
};

CODE:

class	Graph
{
	
	//すべてのノード
	std::vector	m_Nodes;

	//リンク（隣接リスト）
	std::vector
				>		m_Links;



	//ノードを4方向に展開していく
	void	SeedNode(Vec2D to, Node& ori);

	//指定された座標にノードがあるか
	bool	AnyNodeThere(Vec2D pos);

public:

	Graph(){ MakeGraph(Vec2D(320,240)); }


	void	MakeGraph(Vec2D Origin);

	void	Render();
};

CODE:

//ノード間の最小距離
const double NODE_minDist = 20.0;

//リンクを作成するにあたる最小距離の平方数
const double LINK_NODE_minDist
	= (NODE_minDist+NODE_minDist)*(NODE_minDist+NODE_minDist);

void	Graph::MakeGraph(Vec2D Origin)
{
	//Originの位置にノードを作成
	Node newNode(Origin);
	m_Nodes.push_back(newNode);

	Vec2D To;

	//ノードを敷き詰める
	To = Origin + Vec2D(-NODE_minDist, 0);
	SeedNode(To, newNode);
	To = Origin + Vec2D(+NODE_minDist, 0);
	SeedNode(To, newNode);
	To = Origin + Vec2D(0, -NODE_minDist);
	SeedNode(To, newNode);
	To = Origin + Vec2D(0, +NODE_minDist);
	SeedNode(To, newNode);

	//最小距離内にあるノードを隣接リストに追加する
	m_Links.resize(m_Nodes.size());
	for(int i = 0; i < m_Nodes.size(); ++i)
	{
		for(int k = 0; k < m_Nodes.size(); ++k)
		{
			double e = 0.0001;
			double dist = (m_Nodes[k].Pos() - m_Nodes[i].Pos()).LengthSQ();
			if( dist < LINK_NODE_minDist + e)
			{
				//間に障害物がないか調べる
				if(WallManager::Instance().
					IntersectWalls(m_Nodes[i].Pos(),
								   m_Nodes[k].Pos()))
				{
					continue;
				}

				//リンクを作成
				Link newLink(m_Nodes[i].ID(), m_Nodes[k].ID(), dist);
				m_Links[m_Nodes[i].ID()].push_back(newLink);
			}
		}
	}
}


void	Graph::SeedNode(Vec2D to, Node& ori)
{
	//ノード作成

	//置こうとしているところに、
	//すでにノードがないか確かめる
	if( AnyNodeThere(to) )
		return;

	//間に遮るものがないか確かめる
	if(WallManager::Instance().IntersectWalls(ori.Pos(), to))
	{
		return;
	}

	//ノード・リンクを作成
	Node newNode(to);
	m_Nodes.push_back(newNode);

	//拡張
	Vec2D To;
	To = to + Vec2D(-NODE_minDist, 0);
	SeedNode(To, newNode);
	To = to + Vec2D(+NODE_minDist, 0);
	SeedNode(To, newNode);
	To = to + Vec2D(0, -NODE_minDist);
	SeedNode(To, newNode);
	To = to + Vec2D(0, +NODE_minDist);
	SeedNode(To, newNode);
}


bool	Graph::AnyNodeThere(Vec2D pos)
{
	for(int i = 0; i < m_Nodes.size(); ++i)
	{
		if(m_Nodes.at(i).Pos() == pos)
			return true;
	}
	return false;
}