AI & Games

Algorithms, heuristics and hacks

'A complex AI doesnt matter if a simple one gives the challenge and fun that you need.' - TheHappieCat July 15 2016
https://www.youtube.com/watch?v=nEnNtiumgII

Dishonored is a first person stealth role playing game in which you take control of the main character named Corvo Attano. Stealth games need to have strong AI systems to give a real feeling of immersion to the player that anything above a whisper or straying too close to an area not covered in shadow or descending from a rooftop at an unfortunate time could lead to being hunted by an entire city watch and a bloody death. The AI in dishonoured uses algorithms and heuristics as a result since the player has many options of approach, so using algorithms to patrol specific areas of the environment also being alerted if the player isn’t not behind cover or in sufficient darkness or being attracted by a gunshot or explosion as well as dead bodies.

'some problems are hard and you may not be able to get an acceptable solution in an acceptable time. In such cases you often can get a not too bad solution much faster, by applying some arbitrary choices (educated guesses): that's a heuristic.' - https://stackoverflow.com/questions/2334225/what-is-the-difference-between-a-heuristic-and-an-algorithm

Heuristics comes more into effect with the pathing since the player can climb buildings and there is often multiple ways of doing so, having non player characters struggle to give chase by getting stuck or taking ages to decide the best path up. Heuristics will alter the algorithm of the NPC to find either a better solution. Some games these days that if they can’t find a suitable solution to getting stuck or not finding a path they’ll teleport to an open space or in the vicinity of the player such games include Skyrim and GTA 5. GTA 5 for example when you drive around running either NPC’s or other players over you can park on top of them which means they can’t get up, after a specific amount of time or lack of pathing the NPC or player will teleport to a suitable area in the environment. Skyrim has a similar solution in which an NPC might get stuck on or in a table and if it can’t find a path it will also teleport.

"Cheat wherever you can. A.I.s are handicapped. They need to cheat from time to time if they're going to close the gap... Never get caught cheating. Nothing ruins the illusion of a good A.I. like seeing how they're cheating." - Jonny Ebert, lead designer of Dawn of War 2 on video game A.I http://tvtropes.org/pmwiki/pmwiki.php/Main/TheComputerIsACheatingBastard

AI hacks are often a result of poor AI design and often used as a way to increase difficulty, such as AI having resources they shouldn’t have or knowing your build order so it can instantly counter your units or actions this can be found in real time strategy games such as star craft and age of empires. Age of empires would monitor the resources and actions of the player and if it started falling behind on resource nodes such as mines for gold or stone it would cheat and give itself a resource boost.

Star craft 2 can have an AI that utilizes graphical APIs to take rapid pictures of the game and react to what it sees so it keeps track of its resource quantity and if it has enough to build a unit or building. A modder then altered the AI so it’s now capable of making 500 decisions per minute or around 2000 APM (actions per minute) in a match. The best players in the world have around 300 actions per minute.

Hardware constraints & AI Engines

'you can probably guess that games which have simplistic graphics, like Minecraft, need very little GPU performance. There are also games that look amazing when graphics quality is cranked up, and need a powerful GPU in order to do that, but which don’t need a particularly high-end CPU - Witcher 3 is a good example of that.' - William George October 15, 2015
https://www.pugetsystems.com/blog/2015/10/15/Gaming-Computers-Different-Hardware-for-Different-Genres-720/

Hardware constraints can include many things from graphics cards, memory to monitors/display outputs, for example something like the original Pokémon games and Mario on the Nintendo Gameboy where they were restricted around 160x144 and to a single colour palette of four shades of the same colour. Another example would be a the original Crysis game which would run poor or was even unplayable without borderline top spec hardware of the time (2007) This also cause some review outlets to criticise the developers for having such a steep hardware requirement, as not having sufficient hardware would result in incredibly low frame rate which means the image you see will appear like a slide show giving a janky feel or just out right crashing on launch. First person shooters are one of the genres that relies heavily on having a high but also sustained frame rate/frame timing since if either is low or out of sync the gameplay will feel off and the animations will be less fluid creating a lesser experience.

Constraints can help push innovation, experimentation and creativity. Having good AI can make the difference between a bad game and an excellent game, however this does present its own problem as systems have all different specs and performances and a game with a lot of algorithms could be a burden on the systems processor causing heat issues which is very prevalent on mobile devices (E.G. smart phones/tablets) currently as well as causing frame rate dipping again compromising the user experience.

Developer priorities

'There are few things that irritate people more than micro-transactions in games. Even so, major game studios are pushing forward with including them in as many games as possible.' - Dann Albright April 11, 2015
http://www.makeuseof.com/tag/big-game-studios-killing-video-game-industry/

Consoles, PCs, Phones

Developers have different priorities depending on the situations of the systems they are developing for such as Microsoft’s new Xbox One X, this means that the developers for this console will be aiming for the best user experience to show how well it runs and give a good impression to drive more sales of that console. An older console might aim more towards squeezing the last drop of performance out of the console which happen in the previous generation of consoles (PlayStation 3 and the Xbox 360).

Smartphone developers have a very different approach to video game design usually aiming towards the more casual gamer be they older people or the very young, and often have very simple mechanics such as clicking on buildings or the match 3 styles of games and usually have a cash shop to make progression easier or to skip entire segments of the game. Such games also are very light on AI meaning the performance impact can also be minimal. That said more AI intensive games are making their way onto App stores such as Fallout Shelter which is like a diet Xcom: enemy unknown which has quite complex AI since it’s a mixture of tactics and base building. On older phones the performance would be unbearable since a lack of performance would result in huge amounts of lag (the time it takes for your input/actions to have an effect in the game) when the screen is covered with NPC’s fighting or one of the rooms catching fire or being invaded by rad roaches.

PC developers are often have the most leeway when it comes to AI since the systems generally have a reasonable processor allowing for more complex AI though when it comes to strategy games the developers can still be lazy have the AI hack to give the impression that the AI is more complex or harder than it actually is. Although PC developers often also need a wide range of minimum and recommended specifications since there is so much variation in GPU’s, Memory, PSU’s and operating systems (Windows/MAC and Linux). Not having the minimum recommended specification results in a massively inferior experience to someone with the recommended specification especially if it’s an online multiplayer game such as call of duty or star wars battlefront since input lag could be the difference between connecting a reaction shot and killing the enemy or being killed over and over because by the time you see the enemy their superior system has transferred and displayed the relevant information while yours is still processing making the experience very frustrating. If it’s strictly a single player game the performance requirements don’t matter quite as much but you will still have a lesser experience since the game just won’t be as responsive it will feel kind of janky (unless you’re a console pleb that is used to sub 30 frames per second).

What is Boids Flocking?

'basic flocking model consists of three simple steering behaviors which describe how an individual boid maneuvers based on the positions and velocities its nearby flockmates.' - Craig Reynolds

http://www.red3d.com/cwr/boids/

Boids was a computer model of coordinated animal motion such as bird flocks and schools of fish and was based on three dimensional computational geometry which is generally used in computer animation or computer aided design. The basic simulated flocking creatures were designed boids and the standard flocking model is made up of three steering behaviours which detail how an individual boid manoeuvres based on the positions and velocities of its nearby flock mates.

Individual boids have access to whole scene geometric descriptions but the flocking requires that it reacts only to flock mates in a specific range around itself. The range is characterised by a distance (measured from the centre of the boid) and an angle, measured from the boids trajectory of flight. Flock mates outside the local range are ignored, this can be likened to a limited model of perception but is generally thought more correct as a defining region in which flock mates influence a boids steering.

It included predictive obstacle avoidance and goal seeking. Obstacle avoidance allowed the boids to fly through simulated environments while dodging static objects. For applications in computer animation, a low priority goal seeking behaviour caused the flock to follow a scripted path.

Fuzzy Logic

'There are two types of logic commonly used which are Fuzzy logic and Boolean logic, the difference between these two is that you have something like a sliding scale. Boolean logic only recognizes "false" and "true" or 0 and 1, whereas fuzzy logic will recognize any number. For example 0.4 or 0.5746 etc.' Mike Prinke, Video game technical designer - Nov 6 2016
https://www.quora.com/How-is-Fuzzy-Logic-used-in-game-development

This also applies to integers such as 1.5 or 5 which comes down to a series of discrete Boolean operations, fuzzy logic requires it to be a continuous scale.

a couple of examples include games like "Knights of the old republic and Fable" both of which use a system in which a light sided/good interaction with npcs means the majority or npcs will have a positive response to you. Whereas a dark sided/evil interaction will receive negative reactions from npcs. Of course the scale doesn't go from one end to the other instantly it’s a gradual effect that acclimates over the course of the game (basically taking a bunch of binary choices and turning them into a fuzzy value).

Another example would be where the AI evaluates not direct input but off of abstract variables so that if an npc/AI is low on ammo or health a will to fight scale (cowardice or bravery) will shift towards cowardice whereas if the AI hits the player for a critical it may gain bravery. This is often seen in AI currently in games such as "lord of the rings shadow of war" in which a horde of orcs may attack the player and if the player kills or injures the majority of the horde they will attempt to flee and regain health or find reinforcements.

Path-Finding

'The A* algorithm is the fastest graph search algorithm that finds the path that costs the least from source node to goal node. (A node can be hexagon, square or circle, etc.)' - Arpit Mishra Oct 20, 2016
https://www.quora.com/How-does-a-star-algorithm-work

A* search algorithm is one the most popular techniques for finding the shortest path between two points in an area. A* was designed to combine heuristics such as Best-First-Search (BFS) and Dijkstra's algorithm. unlike Dijkstra's and best-first-search A* doesn't randomly select a node to move to it will select what looks the most promising/cost efficient node.

f(n) = g(n) + h(n)

g(n) is the cost (distance) of the path from the starting point to another point n and h(n) is the estimated cost from point n to the goal.

Point A=7 and to move to point B costs 1 so the final cost is 8

'there are many ways to implement pathfinding, but not all of them return the shortest path, or are efficient or even reliable.' - David Gouveia/BlueRaja - Danny Pflughoeft May 27 2012
https://gamedev.stackexchange.com/questions/28041/path-finding-algorithms

Breadth First Search examines all directions which is useful for regular path finding as well as procedural map generation, flow field path-finding, distance maps and other types of map analysis.

Dijkstra's Algorithm (also called Uniform Cost Search) prioritizes which paths to explore. as opposed to exploring all possible paths, it prefers lower cost paths. It allows for assigning lower costs to encourage moving on roads and higher costs to avoid environments such as forests which could have more obstacles, using higher costs to discourage going into those areas. When movement costs vary this is used in place of Breadth First Search.

Dijkstra’s Algorithm works well to find the shortest path, but it wastes time exploring in directions that aren’t promising. Best First Search explores in promising directions but it may not find the shortest path. The A* algorithm uses both the actual distance from the start and the estimated distance to the goal.

Decision Trees, state mechanics, Tactics & strategy

'Decision trees are evaluated from root to leaf, every time. For a decision tree to work properly, the child nodes of each parent must represent all possible decisions for that node. If a node can be answered "Yes, No, Maybe", there must be three children, Yes node, No node and Maybe node. This means there's always some lower node to traverse, until reaching an end node.' - Michael House march 25 2013

https://gamedev.stackexchange.com/questions/51693/decision-tree-vs-behavior-tree

Having decision trees really helps AI feel more real by making choices similar to what a player would make such as can it see the player? yes, no or maybe? if yes then it can give chase or sound an alarm or attack. if no then it can continue on its patrol route, however if its maybe in which maybe it heard the player or say something in the shadows it may go into an alert state to check out what the disturbance was. basically starting at 0 and moving down a tree of choices. Another example is if the AI is using a ranged weapon with ammo, such as does it have enough ammo? does it need to take cover while it reloads? does it need to swap weapons so on so fourth.

Q-Learning

'Q-Learning is a special type of reinforcement learning which means learning by interacting with an environment through positive feedback or reinforcement' - Siraj Raval Jan 6, 2017
https://www.youtube.com/watch?v=A5eihauRQvo

'⟨s0,a0,r1,s1,a1,r2,s2,a2,r3,s3,a3,r4,s4...⟩, which means that the agent was in state s0 and did action a0, which resulted in it receiving reward r1 and being in state s1; then it did action a1, received reward r2, and ended up in state s2; then it did action a2, received reward r3, and ended up in state s3; and so on.' - David Poole and Alan Mackworth. 2010
http://artint.info/html/ArtInt_265.html

Q-learning is a type of algorithm that is designed to improve the AI over time or attempts, an example is if an AI was in a building and its goal is outside there would be a value for each room and its goal however each room along the way wold give a negative value until it reaches its goal. An AI with Q-learning will keep going through this process (trial and error) until it finds the optimal route/the highest reward.

Artificial Neural Network

'the biological structure of the human brain forms a massive parallel network of simple computation units that have been trained to solve these problems quickly. This network, when simulated on a computer, is called an artificial neural network or neural net for short.' - Dean Macri September 9, 2011
https://software.intel.com/en-us/articles/an-introduction-to-neural-networks-with-an-application-to-games
Artificial neural networks (ANN) are algorithmic constructs that allow machines to learn such as voice commands, managing playlists and image recognition. A general ANN is made up of thousands of artificial neurons stacked in rows called layers forming millions of connections. Often layers are only interconnected with the layers either side of them through inputs and outputs. There are usually four essential layers of neurons; Convolution, Activation, Pooling and Fully connected.

The convolution layer/s thousands of neurons act as the first filter checking everything in the image looking for any patterns and as more images get processed the neurons learn and create filters which improves accuracy. A filter for fruit as an example the filter would look at it and check is it orange? while another checks the shape or the skin, basically taking a bunch of stuff/information and arranging it into piles (apples, oranges, pineapples etc). The convolution layer breaks down images into different features.

Advantages of ANN's is that they can learn in a nonlinear way such as seeing features in images that aren't immediately obvious. Such as items in bad lighting or piles or partially obscured by other objects, the activation layer serves as a kind of highlight tool for the easily spotted and harder to see objects.

As you may of guessed all this convolution will result in a massive amount of information which can become a nightmare for machines. The Pooling layer is designed to shrink into an easier more efficient form. Max pooling edits down feature maps into a sort of average so that only some examples are featured. Basically taking our categorize and sifting through for the best average image of apples, oranges and pineapples and tossing out the rest.

A neural network designer can then gather the subsequent layered configurations and filter them to receive higher-level information. Meaning that it will then take a portion of the information and slowly build up layer upon layer and in the fully connected layer the pooled feature maps are connected to nodes on the output side and that represent the items that the ANN is learning to identify such apples, oranges and pineapples.