bfs Mainソースコード

void User::bfsGo(const int& inStartX, const int& inStartY, 
const int& EndX, const int& EndY)
{
	const int direction = FOUR;
	Pos pos{inStartX, inStartY};
	
	vector<Pos> nextPos;
	//4방면 또는 8방면 선택하는 구간 
	if (direction == 4)
	{
		nextPos = { {0,-1}, {-1,0}, {1,0}, {0,1} };
	}
	else
	{
		nextPos = { {0,-1}, {0,1}, {1,0}, {-1,0}
			,{1,1},{1,-1},{-1,-1},{-1,1} };
	}
	
	queue<Pos>q;
	q.push({ pos });

	vector<vector<bool>>checked(MaxNode, vector <bool>(MaxNode, false));
	checked[inStartX][inStartY] = true;

	map<Pos, Pos>parent;
	parent[pos] = pos;

	while (!q.empty())
	{
		Pos prePos = q.front();
		q.pop();

		//종료 처리
		if (prePos.x == EndX && prePos.y == EndY)
			break;

		for (int i = 0; i < direction; i++)
		{
			int cmpX = prePos.x + nextPos[i].x;
			int cmpY = prePos.y + nextPos[i].y;

			//지름길 만들 수 있는지 여부 확인
			if (CanGo(cmpX, cmpY) == false)
				continue;

			if (checked[cmpX][cmpY] == true)
				continue;
			
			pos.setPos(cmpX, cmpY);
			mIsoInform->SetTileState(ISOTILE_BFS_READY, pos.x, pos.y);
			vOrigin.push_back({ pos.x, pos.y });

			q.push(pos);
			parent[pos] = prePos;
			checked[cmpX][cmpY] = true;
		}
	}

	way.clear();
	pos.x = EndX;
	pos.y = EndY;

	while (true)
	{
		way.emplace_back(pos);
		mIsoInform->SetTileState(ISOTILE_BFS_GO, pos.x, pos.y);
		vOrigin.push_back({ pos.x, pos.y });
		if (pos == parent[pos])
			break;

		pos = parent[pos];
	}

	goAhead = true;
}

使用する構造体

struct Pos
{
	int x;
	int y;

	bool operator <(const Pos& other) const
	{
		if (other.x != this->x)
			return x > other.x;
		return y > other.y;
	}

	Pos operator+(Pos& other)
	{
		Pos ret;
		ret.y = y + other.y;
		ret.x = x + other.x;
		return ret;
	}

	void setPos(const int &inX, const int &inY)
	{
		x = inX;
		y = inY;
	}

	bool operator==(Pos& other)
	{
		return y == other.y && x == other.x;
	}
};