Week Two

Iveta Stripeikaite
Jan 31, 2017
3 min read

Introduction:

This week we have dabbled into the Behavioural part of the Cognitive Modelling Hierarchy. This level of the model focuses on self-animating characters, reaction and senses which are all part of movement and path finding principles. Our lab task for this week was to run a pathfinding demo and observe the results of Dijkstra, Best-First-Search (BFS) and A* algorithms. All of the observations and conclusions will be noted at the end of the blog,

Movement:

Boids is a great example demonstrating steering behaviours (not pathfinding). When there is a single boid in the scene, it simply moves in a random direction whilst avoiding obstacles. However, what gets really interesting is when there a multiple boids in its radius. They begin to behave like a flock of birds - with a leader and its followers, all moving together in the same direction. Now, the way they work is with the help of three key rules: separation, alignment and cohesion:

Separation: avoid crowding
Alignment: steer towards average heading
Cohesion: move towards average position

Separation Alignment Cohesion

Boids use a simple sensing algorithm which looks out for anyone nearby and performs the above calculations. It produces a life-like behaviour, where each boid acts as an independent entity but which also appears to be a part of a group. Boids are great for racing games as it provides an automated steering for the car as it drives along the road. It may also be used for Real-Time Strategy games that require crowd management. For example, a large group of zombies might have the same target, but because each boid is performing individual steering calculations, it makes each one of the zombies appear as individuals.

Pathfinding:

Unlike movement, path finding computes a path to follow from the NPCs start position to the end position whilst avoiding obstacles on its way there. There are tree key algorithms which we have looked into in our lab session this week: Dijkstra, A* and Best-First-Search (BFS) algorithms. We had to run a pathfinding demo and look into the effectiveness of each algorithm. Below are the results of each:

Dijkstra A* Best-First-Search

Unlike A* and BFS, Dijkstra does not have a heuristic and so it branches out equally in each direction, resulting in a larger area covered before the algorithm finds its target. This can be slow and expensive to run in a real-time game scenario which relies on pathfinding. However, in some scenarios, the target location might be unknown. For example, a player might be walking towards a goal in a new area of a map. The game algorithm calculates the most optimized path and the player follows it even though he has not yet explored the map before. This breaks the immersion of the game. Dijkstra algorithm could be used here, which would be allow the player to walk into dead ends and make believable mistakes that are expected when exploring a new area.

As seen in the figures above, BFS produced the best results. BFS considers the direction of the target when calculating the most optomized path. However, unlike A* algorithm, ir prioritizes the shortest path rather than the cheapest/optimized path. This could be catastrophic in a resource management game as they are a scarce commodity in the game.

Coursework:

Seeing that steering algorithms are best used in racing games and crowd management games, I will not be using these approaches in my game, unless further changes are made to the game idea. After considering the pahfinding approaches it is clear that A* algorithm would result in the most sensible and optimized path in my stealth game. For this reason I will only be exploring this pathfinding algorithm in the future.