Home

Welcome to the GamesAI6 wiki!

Contents

• How to implement genetic algorithms

5. Steering Behaviours

• How the algorithm works
  • At its most fundamental level, steering behaviours output a desired velocity as a Vector which is then applied to the object to be steered.
  • All steering behaviours have 2 weights, an internal one and an external one. Every time the desired velocity is requested, beforehand the internal weight is set to 1.0, which can then be changed by the steering behaviour, making it stronger or weaker as desired. In our project it is normally used as an 'off' switch. The external weight is set to determine the importance of a steering behaviour. In collections of steering behaviours, the weights combined are used to determine the strength of each behaviour. An example of this in action is the wall avoidance behaviour. Its external weight is set to 100.0, much larger than the default of 1.0, meaning that in practice it takes precedence over all other behaviours, which is important as to ensure collisions with walls don't take place. However, if an agent is far enough away from a wall, the internal weight is set to 0, removing any effect on other steering behaviours, regardless of the external weight, which remains unchanged.
  • Complex steering behaviours such as flocking are created by combining simpler behaviours such as cohesion, seeking, separation and alignment.
• Choices you made that are specific to your project
  • Steering behaviours are added to a generic 'Legs' object, this also calculates how strong each steering behaviours should be depending on their weighting. The Legs object also controls all movement in general, so it was the logical place to deal with steering behaviours.
  • External weights are set by States in the Finite State Machine. This is important as it means that individual states can prioritise different behaviours. For example in the wandering state, a sheep may set its Flee behaviours weight to 0.0, while when in the running state it may be set to 10.0.
  • Steering behaviours are categorized as either targetable or a group member behaviour. Targetable behaviours target a certain coordinate, while group member behaviours are passed some nearby objects of a given type which can be used to control group defined behaviour such as flocking. These 2 types have been abstracted in our implementation, making it easier for new behaviours to be created. Examples of targetable behaviours are Seek, Arrive and Pathfind, while Group behaviours include Cohesion, Alignment and Separation.
• Any deviations from textbook algorithms you made, and why.
  • The textbook mentions nothing of an internal weight. This was implemented as a way for steering behaviours to tell the legs that any output they make is pointless and should be ignored, or conversely, extremely important and must have priority over other behaviours. Implementing this using only a single weight would have been difficult as the weight as set by the user should be the default, and must be saved and restored when using a single weight value.
  • The textbook when defining path following steering behaviours involves ensuring the agent is a certain distance from the path and follows a point ahead of the object. Since we're using a grid, we decided to simply make sure the agent visits each grid square along the path in order.

6. A* Pathfinding Algorithm

• How the algorithm works
  1. Initialise a map to store any A* nodes.
  2. Initialise a map of booleans as the closed set
  3. Initialise a minimum priority queue for the open set
  4. Add the current position to the open set
  5. While there is still a node in the open set
  6. Mark the node as processed in the closed set and remove it from the open set.
  7. If the current node is the target node, exit.
  8. For every neighbour of the node, skip it if it's in the closed set, otherwise if it is in the open set, update it if the current path to it is shorter than the previous one, and if not in the open set enqueue to the open set (Ordered by F-Score). Set the neighbours parent to the current node.
• I used the Manhattan distance as the heuristic because of the cityscape environment of this game. since there are only effectively 4 possible directions of movement, the Manhattan distance is the lowest possible distance between two points on the grid. Since we are looking for the smallest distance path, this is an admissible heuristic, as it will never be greater than the actual path length.
• The algorithm piggybacks off the Grid data structure used to generate the city and maze. AStarNodes are little more than references to squares of the Grid with an F-Score and parent attached.
• When I first tested my algorithm it appeared as though nothing was working, it turned out when I was converting Unity Vector3 to grid coordinates that I casted the fraction of the Vectors position relative to the grid to an int prematurely (converting it to 0), meaning when multiplied by the size of the grid it always returned 0. The first segment of the path was never showing up, it was because I was checking if its parent was null before adding it to the path in the path construction phase.
• My closed set is simply an array of bools, one for each possible grid square. This was done since the algorithm is run multiple times every second by nearly every actor, so a constant time lookup was favourable.