X hits on this document

PDF document

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





50 / 110

During the pathfinding A* search, the A* map performs the same functions as the planning A* map. When the path nodes are being created by the path node container class, each path node is given a unique ID just like the actions. When the navigation A* map requires a path node it requests the path node container class to find the node with the same ID as the A* node. The navigation A* map must also find the neighbours of an A* node. For a given A* node, the A* map just obtains the path node that matches the A* node’s ID and builds up a list of neighbours by looking around this path node and eliminating unwalkable nodes.

3.9.4 A* Goal

The A* goal was designed to determine what the heuristic and actual costs are between A* nodes, to test if the A* search has finished and to check if the current plan is valid. If forms an integral part of the planning process for the GOAP system as all the world state changes take place within the A* goal.

The navigation A* goal design was quite simple. When determining the A* node cost (i.e. the g value) the A* goal just returns the cost to go from one path node to another. The heuristic cost between nodes is the distance between them ‘as the crow flies’. The A* goal can recognise if the A* search has finished by checking if the current A* node being analysed is the same node as the goal node.

The planning A* goal is a little more complex. As can be seen from the pseudo-code for the A* search in Appendix A, when examining a given neighbour of the current node, the value for g or the actual cost is first calculated followed by the calculation of the heuristic cost, h. These values are then combined to obtain the overall cost, f, for the neighbour node which determines where on the open list the neighbour is placed.


Document info
Document views359
Page views363
Page last viewedWed Jan 18 05:53:27 UTC 2017