01.26

AI

FSM

State에서 event가 발생하면 Transition State로 전이

A Star

갈 수 있는 영역과 갈 수 없는 영역을 미리 설정

Calculate(Node parent)
{
	return parent.G + node.Cost(parent);
}

CompareCost(Node comparedNode)
{
	// comparedNode를  통해 사용된 비용 보다 이전에 계산된 비용이 더 비싼 경우
	int newCost = Calculate(comparedNode);
	if(newCost < node.G)
	{
		node.parent = comparedNode;
		node.G = newCost;
	}
}

CalculateNodeCost(Node parent)
{
	node.G = Calculate(parent);
	node.H = HeuristicsCost;
	node.F = G + H;
}
vector<Node> AStar()
{
	OpenSet, CloseSet;
	while(!openSet.empty())
	{
		Node* current = openSet.GetMinimumFCostNode();
		if(current == destination)
		{
			break;
		}
		closeSet.insert(current);

		for(auto linkedNode : linkedNodeListFromCurrentNode)
		{
			if(IsCollision(linkedNode))
			{
				continue;
			}
			else if(IsAlreadyIn(CloseSet, linkedNode))
			{
				continue;
			}
			else
			{
				if(IsAlreadyIn(OpenSet, linkedNode))
				{
					openSet.erase(linkedNode);
					linkedNode.CompareCost(current);
				}
				else
				{
					linkedNode.CalculateCost(current);
				}
				openSet.insert(linkedNode);
			}
		}
	}

	stack<Node> reverse;
	node = destination;
	while(node->parent != null)
	{
		reverse.push(node);
		node = node->parent;
	}

	vector<Node> ret;
	while(!reverse.empty())
	{
		ret.push_back(reverse.top());
		reverse.pop();
	}
	return ret;
}

Reference : https://itmining.tistory.com/66