Ai and computer games

One of the basic modules is an effective path-finding system — sometimes, it has to find a movement solution for hundreds of units on the map, in split seconds — and there is more to it than merely finding a path from point A to point B, as it is also important to detect collisions and handle the units in the battlefield avoid each other.

Such algorithms are typically based on the game map being represented by a rectangular grid, with its mesh representing fixed-sized elements of the area. On higher levels of the AI system's hierarchy, there are modules responsible for economy, development or, very importantly, a module to analyse the game map.

It is that module which analyses the properties of the terrain, and a settlement is built based on the assessment, e. The terrain analyser decides when cities should be built and how fortifications should be placed. Basically, in the case of most sports games, we are dealing with large-scale cheating. Take car racing games, for instance. For the needs of the AI, from the geometry of the game map, only and only the polygons belonging to the track of a computer-controlled opponent should travel on and get distinguished.

Two curves are then marked on that track: the first represents the optimal driving track, the second — the track used when overtaking opponents. The whole track gets split into appropriately small sectors and, having taken parameters of the surface into account, each element of the split track gets its length calculated.

Those fragments are then used to build a graph describing the track, and to obtain characteristics of the road in the vehicle's closest vicinity. In effect, the computer knows it should slow down because it's approaching the curve, or knows that it's approaching an intersection and can, e.

Two important attributes of Artificial Intelligence systems in such games is being able to analyse the terrain in order to detect obstacles lying on the road, and strict co-operation with the physics module. The physics module can provide information that the car is skidding, having received which the Artificial Intelligence system should react appropriately and try to get the vehicle's traction back under control.

Figure 3. The method of presentation of reality in car race segmentation and optimalisation of the track. Similar cheating can also be found in other sports games. In most cases, a computer-controlled player has its complete behaviour determined even before the beginning of the turn — that is, it will, e. Additionally, in games simulating sports with scoring by judges, the scores are generated according to the rules defined by the appropriate sports bodies. The predefined scenario of a computer-controlled player is then acted out by the character animation system.

In the following part of the article, I would like to discuss the two most popular algorithms used in programming computer games. Possessing knowledge about them, one can successfully design a simple artificial intelligence system fulfilling the needs of simple FPS or RTS games.

The first of the two is the A-Star algorithm, used in performing fast searches for the optimal path connecting two points on the map graph of a game. The other is the finite state machine, useful, e. The problem of finding a way from point A to point B on a map is a key problem in almost any computer game possibly not counting certain sports games and some other types of games which can be counted using the digits of one hand.

At the same time, algorithms from this group belong to the lower level of the games' AI, serving as a base for constructing more complicated and more intelligent types of behaviour, such as strategic planning, moving in formations or groups, and many others. The world of almost any computer game can be represented with a graph, its form depending on the kind of the game. In RTS-type games, the world is typically represented by a two-dimensional array, each of its elements corresponding to fragments of the game world's rectangular map.

Each element except boundary ones has eight neighbours. Using such a representation of the RTS world, we can construct a graph in which every element of the 2D array will be corresponded to by one vertex of the graph. The edges of the graph typically present only between the nearest neighbours illustrate the possibility or lack thereof of moving from one of the elements of the map to the neighbouring element.

In real-time strategies, we usually assign one vertex of the graph to an area the smallest unit in the game can fit into. There are a lot of algorithms for finding the optimal path in a graph. The most simple of such algorithms, commonly called fire on the prairie, works by constructing consecutive circles around the starting point, with each step of the algorithm building another, wider circle.

Consecutive circles and elements belonging to them are assigned larger and larger indices. As one can see in Figure 5, the circle with index 4 passes through our target point. Now, heading in the opposite direction and following the rule that in each step we move to the nearest map point located on the circle with a smaller index, we reach the starting point; the elements of our map we have returned through make up the shortest path between the starting point and the destination.

Examining the way this algorithm works, one can see that, in addition to its great advantage — the simplicity — it also possesses a severe drawback. The path the algorithm has found in our example consists of only five elements of the game world, even though 81 fields of the map would have to be examined in the worst-case scenario. In case of a map consisting of x fields, it might mean having to examine map elements! Many requirements are presented to optimal path-finding systems.

Optimal does not necessarily mean the shortest; the algorithm can take into account such additional factors as the type of the terrain for instance, a tank in a RTS game will pass the swamp faster going around it than traversing it , turning angle limitations, the number of enemies in the area, and many other elements depending on the particular game.

The algorithm should avoid uncrossable areas of the map or, for example, maintain distance from friendly units. The foremost requirement is that the algorithm should always be able to find the optimal path, as long as a path between the two points exists. The algorithm applied directly may turn out to be ineffective as a result of how much time operations on the structures from the priority queue the OpenList and the ClosedList can take.

Multiple programming methods exist which work around those imperfections. Optimisation issues can be approached from two ways:. In the first case, one often applies the method of dividing the whole world map into regions and splitting the algorithm into two sections: first, we search for the path by checking which regions we should go through; then for each region, we move from the entry point to the exit.

That way, we significantly limit the search area, thus decreasing the amount of resources required for calculations. Another optimisation factor is the appropriate choice of functions and parameters for heuristics, as this is what decides how much the search area spreads over the game map. Finite state machines are one of the least complicated, while at the same time, one of the most effective and most frequently used methods of programming artificial intelligence.

For each object in a computer game, it is possible to discern a number of states it is in during its life. For example: a knight can be arming himself, patrolling, attacking, or resting after a battle; a peasant can be gathering wood, building a house, or defending himself against attacks. Depending on their states, in-game objects respond in different ways to the finite set of external stimuli or, should there be none, perform different activities.

The finite state machine method lets us easily divide the implementation of each game object's behaviour into smaller fragments, which are easier to debug and extend. Rocket League is a football video game which features cars powered with rockets.

Released in , it is still one of the most played online multiplayer game. Although it looks just like any sport video game, the game AI is very powerful to handle the ball game strategy. This provides a realistic experience. The idea of clubbing the fascination of soccer and cars has turned out very well, and Rocket League is a fine example of perfecting this idea. Awarded the Game of the Year in , Minecraft is a sandbox game first designed by developer Markus Persson and later on by Mojang.

Unlike a conventional video game, Minecraft has no specific goals to achieve in the game. The players simply arrange 3D objects blocks to create a game world, making Minecraft a never-ending game. The game does offer various different modes such as adventure mode, spectator mode and so on. Although there are games similar to Minecraft, not one has come close to its creativity and the freedom it gives to the gamers.

First Encounter Assault Recon, better known as F. Released in , this game garnered a lot of attention in the gaming community for its in-game AI.

Coming to the gameplay, it is a typical tactical shooter game with a spooky storyline. As mentioned earlier, what sets it apart is the opponent AI which is extremely good and acts on even minute details. For example, in the game if a player takes cover behind a barricade, the enemy AI quickly processes and throws a grenade to eliminate the player.

The enemies talk and detail their movements according to that of the players. R has explored what AI could not achieved in the earlier years, that is, giving a human-like experience. Even today, the game is one of the greatest shooter Game AI. Last but not the least, The Last of Us is an action-adventure video game published by Sony Interactive Entertainment in The game covers the story of a duo of survivors who tread to find a cure for a plague that has infected most of the humans in US.

Gameplay offers a third-person perspective as the player goes through a host of tasks and scenarios spread across the game world. It all depends on how the players respond to the situation which involves different characters. Ubisoft tries to appeal to a more casual player these days, but at one point, Far Cry was one of the most unforgiving games ever made.

The first one was developed by Crytek, and then Ubisoft helmed the second one, and the rest of them followed. This alone made the game super hard, even for veteran gamers. The AI in StarCraft II follows the same sequence every time, which is perfect for learning and developing your first strategy against it. This creepy alien and its constant, looming presence throughout the entire game makes it a particularly interesting case for an enemy AI study. This kind of prolonged interaction between the protagonist and the antagonist is unprecedented in the world of gaming.

It probably took a lot of effort to program the complex behavior of the creature that would jump out of the most unexpected places.

Clive Gratton, technical director on Alien: Isolation , said the following about the multi-layered AI system read the full interview here :. The level is pre-processed to find interesting places for the Alien to search.

We then drop it in with a few parameters to say how fast to search, where and what size radius. It is actually traversing through the vent network. Ever heard of clear shots on or meter distances? On the other hand, you could just download and install one of the many AI mods that are freely distributed for the game.

What other games do you know of that possess a great AI? Share their titles and leave your opinions on why you think so in the comments. Hardware Graphics Cards Peripherals Components. Other Culture Indie eSports Video.