Introduction

In this blog I will be expanding upon the AI techniques that I have discussed in the first blog. I will be considering those techniques for use within a gaming environment and how they can be applied to my game. My game idea is a zombie shooter, where the player must defeat waves of zombies to survive. Each wave will become progressively harder as the game goes on.

Algorithms

Algorithms are anything from calculating player’s health and damage taken to an RNG (Random Number Generation) system, algorithms are used to implement these systems. A lot of games nowadays feature RNG, a system where the computer generates a random number which will result in some sort of output. These are commonly used for looting systems, for example when a boss is killed, a random number will be generated which will determine the loot that the player gets. As seen in (xOctoManx, 2016)’s video, he uses the inbuilt function within Unity called “random.range” to generate a number between 1 and 100. He then uses this number to determine loot from predetermined ‘drop tables’. This is just an example of where an algorithm is used. MMOs commonly feature this type of RNG for their looting systems, games such as World of Warcraft, Warframe or Runescape have built their looting systems heavily around it.

Algorithms are used widely in any game, as they will be in mine. Pathfinding, damage, health are all examples of where algorithms will be seen in my game. For example, player damage will use an algorithm to say that if the zombie is in attack range of the player then the zombie will attack, inflicting [x] amount of damage onto the player.

Heuristics

Heuristics are used both in the design process in a game, and are also built into the core functionality of a game, such as in pathfinding. (Brown, n.d.) explains how implementing heuristics is good practice in the development of a game because “experts report any instances where the software does not follow the heuristics”. Keeping the feel of a game is extremely important, whether it’s the theme or the core gameplay, it is what allows player to become immersed. It also keeps the game on the right tracks -preventing it from straying outside of what the game was originally designed to be. Another place that heuristics can be found is with pathfinding. Algorithms such as A* search use heuristics to plot a route from the start to end points.

In my game I will be considering heuristics both in the design of the game, through a game design document, and when I implement pathfinding. 

Pathfinding

In my previous blog post I looked at Dijkstra’s algorithm and A* search algorithm. Below I will explain how each of these could be applied to my game idea.

Dijkstra’s Algorithm

In a gaming environment, Dijkstra’s algorithm is rarely suitable. This is because it will search every node that is connected to the starting point until it reaches the end point. This is extremely inefficient and expensive on the hardware. There are all sorts of problem that can occur without heuristic-driven algorithms, an example of this is the way that Dijkstra’s algorithm will not consider the direction or heading of the agent, and could therefore draw a route which takes the agent away from the player. With that being said, Dijkstra’s algorithm can be suited to scenarios where there are very few routes it can take. For example, it would be a more suitable application to games that feature specific paths, where the developer already knows the correct path. An example of this is for tower defence games, where the AI must follow a pre-set path. I would not choose Dijkstra’s algorithm for my game as I will need a heuristic-driven algorithm.

A* Search Algorithm

A* combines cost-driven and heuristic-driven algorithms to produce an algorithm that considers both cost and distance / direction. This has the added advantage that it eliminates one of the main problems of Dijkstra’s algorithm: it will consider how far away it is from the target. A* will consider the end goal, find all the paths which the AI traverse, and uses this information to plot the most optimal route. If something along the route should change, for example a new path opens that is closer to the player, then A* will be more efficient in determining that this is the faster route.
This is the algorithm that I will be using for my game as it’s the more optimal choice. Not only will it find the route faster, but it will also provide a more suitable route. It will be used in conjunction with the ‘navigation mesh’ (NavMesh) in Unity. This NavMesh defines and calculates all the routes that are possible to traverse. It will block AI from walking through anything that is defined as a ‘static’ object such as walls, rocks, trees etc.

State Machines

State machines are designed as a thought process for AI allowing them to transition between different states based on the current conditions. State machines can be used for a variety of situations, not just for AI but also for the player. Typically, they are used to determine the action of an AI based on many parameters. An example of this can be seen in the game League of Legends, where AI will attack the minions to gather gold. However, if the number of AI outnumber the player in one of the lanes, they will become overly aggressive. Should either of them become low health, they will begin to retreat.
I plan to implement state machines into my game. One instance that I could use them is when the zombies are low on health, or whereabouts they have been shot could determine the speed at which they move.

Decision trees

Decision trees empower an AI’s ability to decide depending on factors such as the environment, health, the amount of ammo they have etc. As suggested by the name, they will make many decisions, traversing through the branches until the end of the tree is reached. Decision trees often check one conditions against another, or depend on a trigger. The fundamentality of a decision would, in basic terms read as follows: IF A > B then do Y, Else do Z. This would then branch of to another part of the tree, to which some additional conditions would be checked; this continues to run until it reaches the end of the tree.

Decision trees are seen across multiple games, from First Person Shooters to Real Time Strategy games. An example of this could be seen in the game Warframe, where enemies that have sight on the player will take cover behind barriers, even erecting there own barriers to help them close down the distance to the player.

Decision trees are something that I would like to implement in my game. For example, I could implement it in a scenario such as when the zombies are running towards the player, they could swarm between cover based on the distance between them, the player and the cover around them.

Fuzzy Logic

Fuzzy logic can be applied to any situation where there isn’t just a ‘yes or no’ answer. It is often used in conjunction with state machines / behaviour trees to determine the behaviour of an AI agent. In a shooter game, the AI could take factors into account such as health, ammo, number of teammates around it to name a few. It would then use these factors to influence the decision that it makes. A clear example of fuzzy logic is an AI’s health. States can be determined using fuzzy logic, where any value above 50% health is classed as healthy, any value between 0% and 50% is classed as unhealthy and 0% is dead. Fuzzy logic is used to make games feel more dynamic, and that there isn’t just an outcome of A or B. I could implement fuzzy logic in my game in several ways, a couple of examples would be:

1. Different fire rates of weapons. Some weapons start shooting at a rate of 0.5 bullet per second, but over the course of [x] time (for example, 2 seconds), the weapon could fire at 1.5 bullets per second.

2. The movement speed of the zombies. Their speed could be determined by how far away from the player they are.

Boids Flocking

Boids flocking is a technique which is used to simulate crowd behaviour, such as a school of fish or a flock of birds. The game Assassin’s Creed is known for the use of boids flocking methods, where there are crowds of people which have a set patrol route. Crowds will group together when walking round, but will separate to walk around other NPCs, then join up again after. This technique is also commonly found within the game Dead Rising with hordes of zombies that hunt down the player.

For my zombie shooter game, I will implement this technique to create cohesion between the zombie hordes. For example, if I spawn my zombies in waves then they could be spawned in random places, but then as they seek towards the player they could align with each other –simulating a ‘horde’.

Tactics and Strategy

In games such as Call of Duty or Half-life AI are programmed to employ strategies when attacking the player. They will rush the player, move behind cover and work together to take the player down. For example, in Call of Duty: Modern Warfare 2 when an enemy called the ‘juggernaut’ spawns (a unit that can take a lot of damage), all AI units around him will rush in and attack the player, leaving the player overwhelmed and needing to find cover. In the game Half-life, AI will move towards the player, taking cover along the way and provide cover fire for each other. These strategies are used to make the game feel more realistic, it makes you feel like the enemies are genuinely working together as a team. In situations where the player is outnumbered, it makes the player genuinely feel danger. This all adds to the immersion of a game, something that is hugely important to how much we enjoy a game.
Zombie games can feel very static. However, employing different zombies that have different tactics and strategies is important to give the game a more dynamic feel. Using the Call of Duty: zombies mode as an example of this, they have many varieties of zombies. Slow moving, fast moving, crawlers (zombies that move very slowing, but crawl along the floor so they can be hard to see). All of this can be extremely challenging when combined. I plan to add many different types of zombies to increase the complexity of the game.

Hacks

Hacks in video games refer to the AI having knowledge that shouldn’t be openly available to them, such as constantly knowing the player’s state, i.e. when they’re out of ammo, low on health etc. It ruins the feel of the game, especially if they are meant to be realistic. No one likes to feel like every move they make is being predicted. This breaks the immersion and has a negative impact on the player’s experience of the game. However, hacks aren’t always a bad feature, many games use them as a way to load a cutscene, which requires knowing the player’s position. Also in many games, allowing the game to interact with the player’s position can result in a better experience. An example of this is Minecraft, where enemies spawn in a region around the player. This spawning system will never spawn a monster in a player’s view, so enemies don’t just ‘pop up’, but it can be a useful tactic to increase the intensity of a game.

I won’t be implementing hacks in my game however as it will be unnecessary. There are very few elements of it that would be positive on gameplay.

Learning Techniques

Machine Learning

Machine learning techniques aren’t very popular in games yet due to the large strain on hardware, as well as the difficulty and complexity to implement. As described in my previous blog, games such as Forza have started to implement machine learning into their game. However, this is still in a design stage and is not yet fully complete. These techniques are implemented as a way of not only creating more realistic gameplay, but also to make AI less predictable. AI is only as intelligent as we program it to be. We must physically tell it what to do by the code we write, but machine learning allows it to learn by itself.
I will not be implementing machine learning into my game because it is not suitable as well as being too complex, to which I do not possess the skills necessary to do so.

References

xOctoManx (2016). Unity 5 Tutorial: Random Loot Table C#. [Online Video]. 5 August 2016. Available from <https://www.youtube.com/watch?v=ySN5Wnu88nE> [Accessed: 28 November 2017]

Brown, M. (n.d.). Evaluating Computer Game Usability: Developing Heuristics Based on User Experience. https://www.academia.edu/4356390/Evaluating_Computer_Game_Usability_Developing_Heuristics_Based_on_User_Experience