Interesting idea. Clever use of a classic algorithm in a novel way.
Interesting idea. Clever use of a classic algorithm in a novel way.
Whereas academic planners at the time were struggling with PDDL (a symbolic declarative language for describing planning domains -- i.e. problems and actions which can appear in plans), GOAP rewrites all the actions in C++. Then, no problem for procedural preconditions and postconditions, for instance: just call C++ code to check what you have to.
-- JustForFun.
// ----------------------------------------------------------------------- // // // ROUTINE: CAIActionAttackFromNode::ValidateContextPreconditions // // PURPOSE: Return true if real-time preconditions are valid. // // ----------------------------------------------------------------------- //
bool CAIActionAttackFromNode::ValidateContextPreconditions( CAI* pAI, CAIWorldState& wsWorldStateGoal, bool bIsPlanning ) { // Intentionally do not call super::ValidateContextPreconditions(). // Firing from a node ignores range.
// AI does not have a weapon of the correct type
if (!AIWeaponUtils::HasWeaponType(pAI, GetWeaponType(), bIsPlanning)) { return false; }
// AI does not have any ammo required by this weapon type.
if ( !AIWeaponUtils::HasAmmo(pAI, GetWeaponType(), bIsPlanning ) ) { return false; }
// AI must already be at a node.
SAIWORLDSTATE_PROP* pProp = pAI->GetAIWorldState()->GetWSProp( kWSK_AtNode, pAI->m_hObject ); if( !( pProp && pProp->hWSValue ) ) { return false; } HOBJECT hNode = pProp->hWSValue;
// Node must be derived from SmartObject.
HCLASS hTest = g_pLTServer->GetClass( "AINodeSmartObject" ); HCLASS hClass = g_pLTServer->GetObjectClass( hNode ); if( !g_pLTServer->IsKindOf( hClass, hTest ) ) { return false; }
// Node must be correct type.
AINode* pNode = (AINode*)g_pLTServer->HandleToObject( pProp->hWSValue ); if( !( pNode && ( pNode->GetType() == m_pActionRecord->eNodeType ) ) ) { return false; }
// The node must be valid in terms of FOV.
if( pAI->HasTarget( kTarget_Character | kTarget_Object | kTarget_CombatOpportunity ) && pNode->IsNodeValid( pAI, pAI->GetPosition(), pAI->GetAIBlackBoard()->GetBBTargetObject(), kThreatPos_TargetPos, m_dwNodeStatus ) ) { return true; }
// Preconditions are not valid.
return false; } // ----------------------------------------------------------------------- //
It's an extension of Dijkstra's algorithm that adds a few heuristics.
@omginternets:
> dates back ... extension of ... adds a few heuristics.
Blabla, BS.
Fact is Empire Earth was one of the very first computer games to use A* algo. Age of Empires 1 used a worse faster different algo.
Fact is in the age before Wikipedia and Google, decade old papers of obscure algos were more or less lost and forgotten. They were written on paper with no digital copy readly available. So game devs often reinvented things without not knowing of previous work, it took several years until the early 2000s that this old stuff got scanned and made public viewable.
Citation? The only mention I can find about the pathfinding algorithm used by Age of Empires is this: http://artho.com/age/pathfinding.html
A* is supposed to be an optimization of Dijkstra's. I don't know why you call it CPU intensive.