Monday, 6 November 2017

AI Techniques, Tactics & Strategy and Hacks

AI Techniques

Boids Flocking

Boids flocking is a technique which used to create crowd behaviour, such as a school of fish. In (mick maus, 2015)’s video titled “How do Boids Work? A Flocking Simulator” he explains the three guidelines that the boids follow. These are “alignment” which is a rule to determine the direction at which the boids are travelling. They all follow a common heading. If one boid changes direction, then all the other boids which change their alignment based on that. The second rule is “cohesion”, a rule that is applied to the area around the boids. Each boids will search the area around it, in its “radius” and will move to the middle. This helps to keep all the boids closer together, even if they are told not to crowd with each other. This leads me onto the third rule “crowding”, which basically keeps the boids together, hence the term ‘flocking’ (which refers to a flock of birds).
The application of boids flocking can be used to form units of agents, allowing them to travel as one unit. Let’s imagine a scenario where the player has just set of an alarm, and reinforcements are inbound. Enemies might form a group, a ‘flock’, when running in towards the player. There behaviour could be linked, such a not spacing out too far from each other.
(Reynolds, 2001) explains another rule of boids called “Separation”. This rule allows each entity to "steer to avoid crowding local flock mates”. This is a rule could be applied to games that have many area of effect weapons such as rocket launchers and grenades etc., where grouping would merely make the game too easy for the player.

Tactics and Strategy

The best AI from games that we know and love are employed by tactic and strategy. I’m not just talking from an in-game aspect, but also from a design aspect. There are certain strategies that are used to make a good AI system that seem realistic enough that we also forget that it isn’t human. In (Mark Brown, 2017)’s video titled “What Makes Good AI?” he highlights some of the aspects of what makes a good AI such as how AI “Lets the player cheat.” He explains that in the game FarCry there is a limit on the number of enemies that can be shooting at the player at any given time. This means that the player won’t die too quickly, especially if swarmed by many enemies. This is just one of the ways that AI cooperate with each other behind the scenes -in a way that most of us players wouldn’t even realise was a factor.
Swarms of dangerous mobs (unlike the real-world term, the gaming term for mob refers to just one entity) can make the player feel danger. But what makes a truly good AI are those that interact with them and the environment around them. (Champandard, 2007) outlines a couple of “behaviours” that I believe are necessary to AI, these are:

1.       “Assuming a intermediate position to search for cover, e.g. like dropping down on one knee.
2.       Playing a short animation while looking for cover, and signaling the threat to team mates.”

When these actions are performed by AI it can appear, even if they have their own thought process, that they are moving as a unit.  In the video that I outlined earlier, (Mark Brown, 2017) explains that the body language of an AI is important to us as players. These act as cues that we can use to know what our actions mean to them, and how we can interact with the environment. For example, if an AI hears footsteps, the agent might turn around and walk towards where the sound came from. This was a principle that was used in the franchise Metal Gear Solid. In (YongYea, 2014)’s video, he demonstrates the effect that the player character can have by throwing magazines and knocking on walls. This makes the AI appear intelligent, even if implementing something like this is a basic technique.

Behaviour trees and FSMs can play a part in how AI behaves. (Tangness, 2014) explains in his online article about the game Splinter Cell: Blacklist how AI agents behave using states. He claims that there is are four states, these being: “Normal patrol”, “Normal Investigate”, “Heightened Mode” and “Combat Mode”. He explains how the AI moves through these different states based on different factors such as whether the player has made a sound (which they are extremely sensitive to), or has been detected. These behavioural trees make the guards seems intelligent AI agents, and allow for a more immersive experience.

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. It makes the player feel like the AI is in some way cheating; this is because it basically is. (tvtropes, n.d.) outlines the problem of what he calls an “All Seeing AI”, he explains that “Stealth is useless, no surprises are possible, and it will (almost) never miss a shot. Consequently, players should not bother with misdirection, flanking, or other forms of deception and psychological warfare that would work wonderfully against actual humans.” When we play games, we want to feel that we are smarter than who we are up against, it’s part of the reason that makes computer games so competitive. It is however, a terrible position to put the player in when you are leaving them with no power over the flow of information that the AI receives. It’s frustrating when the AI lands every shot without fail. All of this breaks the immersion of the game itself. How are we meant to feel like the game is pulling us in when it’s constantly undermining the aspects of reality?

Hacks aren’t all bad though, they can be used to determine when a cutscene will occur -something that is often appreciated by the player. The game can use the player’s location to open the world up or spawn a boss.

AI Techniques and Decision Making Concepts

AI Techniques and Decision-Making Concepts

Artificial intelligence in games needs to feel real. The best games we know and love, past or present, are immersive -they make you feel like you’re actually there, not just sitting on your sofa with a controller / mouse in your hand. Time passes by and before you know it hours have flown by and you haven’t even felt it. AI plays a major part in that immersion, through the concepts and techniques they are given. These I will cover below:

 

State Machines & Behaviour / Decision Trees

Figure 6. Finite-State Machines: Theory and Implementation 
(Bevilacqua, 2013)
State machines, also known as finite state machines (FSM), are a “model of computation based on a hypothetical machine made of one or more states.” (Bevilacqua, 2013). These machines are designed to function as a thought process for AI, making them more intelligent. However, this can leave them feeling very rigid and static. This is due to the fact that each state specifies that of the next. Furthermore, states can’t be defined dynamically - it can’t query what it’s being asked and therefore it’ll always react in the same way. [Fig. 6] shows an example of a FSM, where “find aid”, “evade”, “wander” and “attack” are all of the states. The biggest problem with FSMs, as pointed out by (Estrada, 2014) “FSMs are great because they are so simple and intuitive. When they get big, however, they become so complicated. It got to a point where I’m afraid to change the configuration of the FSM because the working AI easily breaks.” For state machines that are extremely complex, this might require fixing multiple states in order to get the AI working. The bottom line is that if the AI in a game is intended to be simple, then FSMs are the correct option, but for anything complex, behaviour trees are much more appropriate.


Behaviour trees provide a way of defining a given state depending on the feedback from other states, known as children. In the diagram below [fig. 7] (Simpson, 2014) explains that “The most obvious usage of sequences is to define a sequence of tasks that must be completed in entirety, and where failure of one means further processing of that sequence of tasks becomes redundant.” In other words, the door cannot be walked through if it hasn’t been opened. All of the checks that are being made on the door are children of the “sequence” node, with this node being the parent.
These children are the leaves of the tree, and the sequence node is the branch.

Figure 7. Behaviour trees for AI: How they work 
(Simpson, 2014)
These trees give the AI more control, making them able to make decisions based on their current state adds to immersion. It can make the AI feel more human and not just a robot. Some games such as PacMan have contained the simplest of AI, but partly the reason that this game was so successful was due to the AI being able to make decisions by themselves. (Kehoe, 2015) describes AI decision making as a “core concept”. Without this capability, AI can feel very scripted and rigid. The type of decision that an AI will make will be based upon the genre of game it is, but the fundamentals stay the same.

The decision making in PacMan was extremely basic, as (Kehoe, 2015) explains “Four ghosts plagued the player. Each ghost followed a simple rule set. One ghost was always to turn left, another was always to turn right, one turned in a random direction, and the last turned toward the player.” More complex decision making involves using larger trees, which provide a platform for when an AI decides.

Fuzzy Logic

Fuzzy logic, as (Rouse, fuzzy logic, 2016) describes is “an approach to computing based on "degrees of truth" rather than the usual "true or false" (1 or 0) Boolean logic on which the modern computer is based.” 

These models can be used as a platform to make decisions to determine an AIs state to give states to an AI. In older games, such as PacMan there were only two states: alive and dead. The player would be alive until they bumped into an AI, and at that point it was all over, and they were dead. The application of fuzzy logic is expanding this linear system by introducing new waypoints between 0 and 1. In the game League of Legends, AI will become aggressive when their health bars are full or near full. Upon reaching a certain percentage of health they will start to retreat towards their base. These are states determined by fuzzy logic which, when the AI drop below a certain percentage of their maximum health, tells them that they are in some sort of unhealthy state, and must retreat. This is as shown in [fig. 6], the player is attacking back, it’s health gets low, so the AI chooses to retreat.

Pathfinding, A* Search and Dijkstra Algorithm

Pathfinding

There is a well-known pathfinding problem called the Travelling Salesmen Problem (TSP), a problem which has confused mathematicians for years. (Freiberger, 2012) defines the problem with the following analogy: “Get cash from the cash point, go to the supermarket, pick up kids from school and prescription from doctor. In what order should you do these things so that the distance you've got to drive is as short as possible?”  This is something we do in our day-to-day lives – we perform multiple tasks, but the heuristics don’t seem to bother us that much. We think about things in a logical way naturally, but we only do things in a way that seems naturally logical. When we are telling a machine to compute the fastest route, we need to involve factors that will produce the fastest route. As outlined by Freiberger, getting to all those places might not be challenging. However, if you add in hundreds or even thousands of nodes then the problem becomes computationally harder.



Dijkstra’s Algorithm

Dijkstra’s algorithm, also known as Dijkstra’s shortest path, is one of the most commonly used algorithms. It uses a best-search function which prioritises routes with the shortest cost first. This algorithm attempts to solve the TSP but there is just one major flaw with it: it’s too greedy.

Figure 3: Greedy Algorithms (Moore & Ross, 2017)
Greedy is a term that is used to describe the optimality of an algorithm. All routes have a cost associated with them. Let’s look at the above image [fig. 3]. This shows two different paths, but the aim is to find the largest sum. Greedy algorithms don’t analyse the route, but rather individual nodes. This means that the path found would be [A > C > G] instead of the correct path which would be [A > B > D]. [A > B > D] has a total sum of 109, while [A > C > G] has a total sum of 25. This algorithm is appropriate to use in situations only where one solution should exist, or used as a baseline to be expanded upon. This is because it “makes decisions based only on the information it has at any one step, and without regard to the overall problem” (Moore & Ross, 2017).
In a gaming environment, Dijkstra’s algorithm can be applied to pathfinding for AI, but there may be instances where the route chosen could appear as strange and unnatural. This is because the algorithm itself does not account for heuristics, only cost. To illustrate, (Computerphile, 2017) provides the analogy of using roads (see [fig. 4]).
Figure 4. Dijkstra’s Algorithm – Computerphile
(Computerphile, 2017)
He states that he is starting at [S] and travelling to [E]. He must travel through [A], and all the nodes below it contains traffic jams (increasing the route cost). Because of this it will search all the nodes above [A] before realising there are no through routes to get to [E]. Even if there was, at this point it could end up making the route longer. Pathfinding in games should be as optimised as possible, therefore unnecessary route finding should be kept to a minimal. The application of Dijkstra is more suitable for a linear graph, where nodes commonly have one or two connections.

A* Algorithm

This is where the A* algorithm (also known as A* search algorithm) is applied. A* algorithm is an adaptation of the Dijkstra’s 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. (Computerphile, 2017) explains the problem with Dijkstra’s algorithm using this example [fig. 5]. [S] is the node which the agent would start at, and [E] is the goal. The highlighted nodes are the areas which Dijkstra would search in before reaching the goal. A* would take the most optimal path, which would head straight down all of the nodes, to the right once, and then to [E].
However, this can have a considerable drain on the CPU and its application would not be applicable for games that feature very simple map designs.

On the other hand, maps with a complex design that have many possible routes to reach the target would be more suitable for the application of the A* algorithm. (Dennis, 2008) explains how he took on a programming challenge: “The object was to find the lowest cost route between 10 cities encoded in a map of integers. Each integer represented the cost to get from that any adjacent location to that spot. This is a classic case of a graph navigation algorithm.” In this case he found that the A* algorithm was the most suited to his task. This considerably cut down the time to reach his goal but added to the build time.


Figure 5. A* (A Star) Search Algorithm – Computerphile 
(Computerphile, 2017)
In summary, I believe that for more linear paths, Dijkstra’s algorithm is more suited. Dijkstra is much better at analysing paths when there aren’t multiple variables that can affect the cost routes of each path, and if they aren’t constantly changing. The A* algorithm is much better for these larger grid search calculations, such as in satellite navigation, where the route can change based on multiple factors.

References

References Bevilacqua, F. (2013, October 24). Finite-State Machines: Theory and Implementation . Retrieved from: https://gamedevelopmen...