This app (in C++ using GDI+ for the graphics) demonstrates some key game AI techniques, including:
- Finite state machines
- Steering (seek, flee, path follow)
- A* graph search for pathfinding
- Goal Oriented Action Planning, using the same A* graph search code used for pathfinding
The work was graded A- with these comments from marking tutor (and noted game AI practitioner) Adam Russell:
Highly challenging extension topic (planning). Great documentation, with UML diagrams and discussion of reference texts. Full coverage of requirements, in a manager showing great evidence of orthogonality, abstraction and asynchronicity. Steering is solid…, pathfinding is really the highlight though as an abstract graph search powers both GOAP plans and an asynchronous pathfinder! Very very nice.
Download
Executable demo - AIDemo.zip (47.4KB)
-
Advertisement
how complex are actions?
do you use blackboard \ manager architecture or embed all management in actions?
The only difference with the GOAP enabled guards is that they use their plan to drive the state transitions, so the ‘actions’ used to satisfy a plan are essentially just ‘change to state x’. Here’s an extract from the technical design document which may be of interest:
“The published approach being recreated is Jeff Orkin’s Goal Oriented Action Planning (Orkin, 2006). The key difference in this implementation is that it is not built on top of a complex game engine architecture, like F.E.A.R.’s, so instead of parameterising animation states the planner is instead used as a replacement for the normal state transitions. This has also led to some other differences, such as a rather different approach to procedural preconditions – in the demo the agent just calculates them each frame when executing a plan, and if the current world state does not match the preconditions of the action being executed it is treated as an invalidation of the action. For example, ‘attack’ has a precondition that we are not wounded. If we get wounded while attacking then the planner will invalidate the action and replan. Likewise, the effects of an action are used to determine if the action has successfully completed and it is now time to move on to the next phase of the plan.
The express purpose of Orkin’s approach was managing complexity, so a planner should be expected to look like ‘overkill’ in a simple demo like this. Although this may be considered a ‘toy problem’, it does demonstrate nicely the generic nature of graph search algorithms; the demo uses the same code for pathing and for planning. Lessons were also learned; the planning system was hard to debug, in particular it was not easy to predict what plan would be made given the preconditions/effects of the actions available. A key requirement for a production implementation would be good visualization tools so that the planning process can be investigated, and held to account for its decisions.”
thanks, its interesting