X hits on this document

PDF document

Enhanced NPC Behaviour using Goal Oriented Action Planning - page 45 / 110





45 / 110

3.9 The A* machine

The A* machine is an important part of almost every game nowadays as it is used to calculate paths through terrains as part of the navigation of an agent. The A* system designed for this project was based on the generic A* machine as described by Higgins (Higgins, 2002). To allow an A* machine to be used for different purposes, an A* storage mechanism is required to store the open and closed lists, a generic A* node along with custom A* goal and A* maps are needed for the different systems using the A* machine. Discussion of how the A* algorithm works is left for the reader’s own investigation but pseudo code of the algorithm used in this project is detailed in Appendix A. There are however several important components of the A* machine that need further elaboration.

Whenever the A* machine is requested to run an A* search, the planner (whether it be navigation or GOAP) must first setup the A* map and A* goal that are to be used in the A* search. Different A* map and A* goals were required for the navigation and GOAP system. The A* map and the A* goal provide the exact same function-set to the A* machine but the navigation and GOAP system implement them differently so when they are called from the A* machine they bring about the required different functionality. However the A* machine requires a consistent A* node structure regardless of what system was used and this node structure is used to map from a generic A* node to either a GOAP action or path node.

3.9.1 A* Node

The basis of the A* search is the A* node. Each node has the same characteristics; each has an ID, an overall (f), actual (g) and heuristic (h) cost with links to its parent node, next and previous nodes which are used for maintaining the linked lists. The node ID is the most important piece of data for the A* node as it is what the A* map uses to map from the


Document info
Document views158
Page views162
Page last viewedSat Oct 22 11:50:07 UTC 2016