{"id":52118,"date":"2019-11-01T00:00:00","date_gmt":"2019-10-31T21:00:00","guid":{"rendered":"https:\/\/prohoster.info\/blog\/blog_prohoster\/kak-sozdat-igrovoj-ii-gajd-dlya-nachinayushhih"},"modified":"2020-02-18T13:59:47","modified_gmt":"2020-02-18T10:59:47","slug":"kak-sozdat-igrovoj-ii-gajd-dlya-nachinayushhih","status":"publish","type":"post","link":"https:\/\/prohoster.info\/en\/blog\/news\/kak-sozdat-igrovoj-ii-gajd-dlya-nachinayushhih","title":{"rendered":"How to Create Gaming AI: A Beginner's Guide","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"<p><img decoding=\"async\" alt=\"How to Create Gaming AI: A Beginner&#039;s Guide\" src=\"\/wp-content\/uploads\/2019\/11\/9e57175b233a104e0df98383b374eded.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nI came across an interesting material about artificial intelligence in games. It explains the basics of AI through simple examples and includes many useful tools and methods for convenient development and design. How, where, and when to use them is also discussed.<\/p>\n<p>Most examples are written in pseudocode, so in-depth programming knowledge won\u2019t be needed. Below are 35 pages of text with pictures and GIFs, so get ready.<\/p>\n<p>UPD. I apologize, but I have already translated this article on \u0425\u0430\u0431\u0440. <noindex><a rel=\"nofollow\" href=\"https:\/\/habr.com\/users\/PatientZero\/\">PatientZero<\/a><\/noindex>. You can read his version. <noindex><a rel=\"nofollow\" href=\"https:\/\/habr.com\/post\/420219\/\">here<\/a><\/noindex>, but for some reason the article passed me by (I used the search, but something went wrong). Since I am writing in a blog dedicated to game development, I decided to leave my version of the translation for the subscribers (some points are formatted differently by me, and some are intentionally skipped at the developers' advice).<br \/>\n<noindex><a rel=\"nofollow\" name=\"habracut\"><\/a><\/noindex><\/p>\n<h2>What is AI?<\/h2>\n<p>\nGame AI focuses on what actions an object should take based on the conditions it finds itself in. This is usually referred to as the management of 'intelligent agents,' where an agent is a game character, a vehicle, a bot, or sometimes something more abstract: an entire group of entities or even a civilization. In each case, this is a thing that must perceive its environment, make decisions based on it, and act accordingly. This is known as the Sense\/Think\/Act cycle:<\/p>\n<ul>\n<li>Sense: the agent finds or receives information about things in its environment that may affect its behavior (nearby threats, items to collect, interesting places to explore).<\/li>\n<li>Think: the agent decides how to respond (considers whether it is safe enough to collect items or if it should fight\/hide first).<\/li>\n<li>Act: the agent takes actions to implement the previous decision (starts moving towards the opponent or item).<\/li>\n<li>\u2026the situation has changed due to the actions of the characters, so the cycle repeats with new data.<\/li>\n<\/ul>\n<p>\nAI typically focuses on the Sense part of the cycle. For example, autonomous cars take pictures of the road, combine them with radar and lidar data, and interpret them. This is usually done by machine learning, which processes incoming data and gives it meaning, extracting semantic information like \"there's another car 20 yards ahead of you.\" These are referred to as classification problems.<\/p>\n<p>Games do not require complex systems to extract information, as most of the data is an integral part of it. There\u2019s no need to run image recognition algorithms to determine if an enemy is ahead \u2014 the game already knows and relays that information directly in the decision-making process. Therefore, the Sense part of the cycle is often much simpler than Think and Act.<\/p>\n<h2>Limitations of Game AI<\/h2>\n<p>\nAI has several limitations that must be observed:<\/p>\n<ul>\n<li>AI does not need to be pre-trained like a machine learning algorithm. It is pointless to write a neural network during development to observe tens of thousands of players and learn the best way to play against them. Why? Because the game isn't released, and there are no players.<\/li>\n<li>The game must entertain and challenge, so agents should not find the best approach against humans.<\/li>\n<li>Agents need to appear realistic so players feel like they are playing against real people. The AlphaGo program surpassed humans, but its chosen moves were far from traditional gameplay understanding. If the game mimics a human opponent, that feeling shouldn't be present. The algorithm needs to be adjusted to make plausible decisions rather than perfect ones.<\/li>\n<li>AI must operate in real-time. This means that the algorithm cannot monopolize processor usage for an extended period while making decisions. Even 10 milliseconds for this is too long, as most games require between 16 to 33 milliseconds to complete all processing and move to the next frame of graphics.<\/li>\n<li>Ideally, at least part of the system should be managed by data so that \u2018non-coders\u2019 can make changes and adjustments happen more quickly.<\/li>\n<\/ul>\n<p>\nLet's consider AI approaches that encompass the entire Sense\/Think\/Act cycle.<\/p>\n<h3>Making basic decisions<\/h3>\n<p>\nLet's start with the simplest game - Pong. Goal: move the paddle so that the ball bounces off it instead of passing by. It's like tennis, where you lose if you don't hit the ball. In this case, the AI has a relatively easy task - to decide in which direction to move the paddle.<\/p>\n<p><img decoding=\"async\" alt=\"How to Create Gaming AI: A Beginner&#039;s Guide\" src=\"\/wp-content\/uploads\/2019\/11\/e1935d657b9f090bf60c365c21e8f92b.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<\/p>\n<h3>Conditional Statements<\/h3>\n<p>\nFor AI in Pong, the most straightforward solution is to always try to position the paddle underneath the ball.<\/p>\n<p>Here\u2019s a simple algorithm for this, written in pseudocode:<\/p>\n<p><i>every frame\/update while the game is running:<br \/>\nif the ball is to the left of the paddle:<br \/>\n move paddle left<br \/>\nelse if the ball is to the right of the paddle:<br \/>\n move paddle right<\/i><\/p>\n<p>If the paddle moves at the speed of the ball, then this is the ideal algorithm for AI in Pong. There's no need to complicate things if the data and possible actions for the agent aren't that numerous.<\/p>\n<p>This approach is so simple that the entire Sense\/Think\/Act cycle is barely noticeable. But it exists:<\/p>\n<ul>\n<li>The Sense part lies in the two if statements. The game knows where the ball is and where the paddle is, so the AI accesses it for this information. <\/li>\n<li>The Think part also consists of two if statements. They embody two decisions which in this case are mutually exclusive. As a result, one of three actions is chosen - move the paddle left, move it right, or do nothing if it's already positioned correctly.<\/li>\n<li>The Act part is found in the Move Paddle Left and Move Paddle Right statements. Depending on the game design, they can move the paddle instantly or at a certain speed. <\/li>\n<\/ul>\n<p>\nSuch approaches are called reactive - there is a simple set of rules (in this case, the if statements in the code) that react to the current state of the world and act.<\/p>\n<h3>Decision Tree<\/h3>\n<p>\nThe example with Pong is essentially equivalent to a formal AI concept known as a decision tree. The algorithm traverses it to reach a 'leaf' - a decision on what action to take.<\/p>\n<p>Let's create a flowchart for the decision tree of our paddle algorithm:<\/p>\n<p><img decoding=\"async\" alt=\"How to Create Gaming AI: A Beginner&#039;s Guide\" src=\"\/wp-content\/uploads\/2019\/11\/d3b7290ba93144967cd849416cd5eef3.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nEach part of the tree is called a node - the AI uses graph theory to describe such structures. There are two types of nodes:<\/p>\n<ul>\n<li>Decision Nodes: choosing between two alternatives based on checking some condition, where each alternative is represented as a separate node.<\/li>\n<li>Terminal Nodes: an action to perform, representing the final decision.<\/li>\n<\/ul>\n<p>\nThe algorithm starts with the first node (the \"root\" of the tree). It either decides which child node to move to or performs the action stored in the node and finishes.<\/p>\n<p>What is the advantage if a decision tree performs the same job as if-operators in the previous section? There is a common system here, where each decision has only one condition and two possible outcomes. This allows the developer to create AI from data that represents decisions in the tree, avoiding hardcoding it. Let's visualize this in a table:<\/p>\n<p><img decoding=\"async\" alt=\"How to Create Gaming AI: A Beginner&#039;s Guide\" src=\"\/wp-content\/uploads\/2019\/11\/6875293a60ff9d0efa26fb5e1aa4b21c.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nOn the code side, you will get a system to read the strings. Create a node for each of them, connect the decision-making logic based on the second column, and link child nodes based on the third and fourth columns. You still need to program the conditions and actions, but now the game structure will be more complex. You can add additional decisions and actions, and then set up the entire AI by simply editing a text file defining the tree. You then pass the file to the game designer, who can change behaviors without recompiling the game or altering the code.<\/p>\n<p>Decision trees are very useful when they are built automatically based on a large set of examples (for instance, using the ID3 algorithm). This makes them an effective and high-performance tool for classifying situations based on incoming data. However, we go beyond a simple system for agents to choose actions.<\/p>\n<h3>Scenarios<\/h3>\n<p>\nWe've examined the decision tree system, which used pre-created conditions and actions. A person designing the AI can organize the tree as they wish, but they still have to rely on the coder who programmed it all. What if we could give the designer tools to create their own conditions or actions?<\/p>\n<p>To prevent the programmer from having to write code for the conditions Is Ball Left Of Paddle and Is Ball Right Of Paddle, they can create a system where the designer records conditions to check these values. Then, the decision tree data would look like this:<\/p>\n<p><img decoding=\"async\" alt=\"How to Create Gaming AI: A Beginner&#039;s Guide\" src=\"\/wp-content\/uploads\/2019\/11\/8e77f7c3410d097e8b7d8e1209355cc6.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nEssentially, this is the same as in the first table, but the solutions have their own code, somewhat akin to the conditional part of an if statement. On the code side, this would be read in the second column for decision nodes, but instead of searching for a specific condition to execute (Is Ball Left Of Paddle), it evaluates the conditional expression and returns true or false accordingly. This is done using scripting languages like Lua or Angelscript. With these, developers can take objects in their game (ball and paddle) and create variables accessible in the script (ball.position). Moreover, the scripting language is simpler than C++. It doesn't require a full compilation stage, making it perfect for quickly adjusting game logic and allowing 'non-coders' to create the necessary functions themselves.<\/p>\n<p>In the given example, the scripting language is used only for evaluating conditional expressions, but it can also be used for actions. For instance, the data Move Paddle Right can become a script operator (ball.position.x += 10). Thus, the action can also be defined in the script without the need to program Move Paddle Right.<\/p>\n<p>You can go even further and write the decision tree entirely in the scripting language. This would be code in the form of hardcoded conditional operators, but they would reside in external script files, meaning they can be modified without recompiling the entire program. Often, the script file can be changed mid-game to quickly test different AI responses.<\/p>\n<h3>Responding to Events<\/h3>\n<p>\nThe examples above are perfect for Pong. They continuously run the Sense\/Think\/Act cycle and act based on the last state of the world. However, in more complex games, it's necessary to respond to individual events rather than evaluate everything all at once. Pong, in this case, is an inadequate example. Let's choose another one. <\/p>\n<p>Imagine a shooter where enemies remain stationary until they detect the player, after which they act depending on their 'specialization': some will rush, while others will attack from a distance. This is still a basic reactive system\u2014'if the player is seen, do something'\u2014but it can be logically divided into the event Player Seen and the reaction (choose a response and execute it).<\/p>\n<p>This brings us back to the Sense\/Think\/Act cycle. We can code the Sense part, which will check every frame \u2014 whether the AI sees the player. If not, nothing happens, but if it does, a Player Seen event is created. The code will have a separate section that states: \u2018when the Player Seen event occurs, do \u2019, where  is the response you need to invoke the Think and Act parts. This way, you will set up responses to the Player Seen event: ChargeAndAttack for a \u2018charging\u2019 character, and HideAndSnipe for a sniper. These connections can be created in a data file for quick editing without the need to recompile. Scripting language can also be used here.<\/p>\n<h2>Making complex decisions<\/h2>\n<p>\nWhile simple reactive systems are very effective, there are many situations where they are insufficient. Sometimes decisions need to be made based on what the agent is currently doing, but representing this as a condition can be cumbersome. There are often too many conditions to represent effectively in a decision tree or script. At times, it's necessary to evaluate how the situation will change before deciding on the next step. More complex approaches are needed to address these issues.<\/p>\n<h3>Finite state machine<\/h3>\n<p>\nA Finite State Machine (FSM) is a way to say that our agent is currently in one of several possible states, and that it can transition from one state to another. There is a definite number of such states \u2014 hence the name. The best real-life example is a traffic light. Different places have different sequences of lights, but the principle is the same \u2014 each state represents something (stop, go, etc.). The traffic light is in only one state at any given moment, transitioning from one to another based on simple rules.<\/p>\n<p>With NPCs in games, the story is similar. For example, let\u2019s take a guard with the following states:<\/p>\n<ul>\n<li>Patrolling.<\/li>\n<li>Attacking.<\/li>\n<li>Fleeing.<\/li>\n<\/ul>\n<p>\nAnd with these conditions for changing its state:<\/p>\n<ul>\n<li>If the guard sees an enemy, it attacks.<\/li>\n<li>If the guard is attacking but no longer sees the enemy, it returns to patrolling.<\/li>\n<li>If the guard is attacking but is severely injured, it flees.<\/li>\n<\/ul>\n<p>\nYou can also write if-operators with a guard state variable and various checks: whether there is an enemy nearby, what the NPC's health level is, etc. Let's add a few more states:<\/p>\n<ul>\n<li>Idling \u2014 between patrols.<\/li>\n<li>Searching \u2014 when a spotted enemy has hidden.<\/li>\n<li>Finding Help \u2014 when an enemy is spotted but is too strong to fight alone.<\/li>\n<\/ul>\n<p>\nThe options for each of them are limited \u2014 for instance, the guard won\u2019t go looking for a hidden enemy if he has low health.<\/p>\n<p>Ultimately, a large list of &#039;ifs&#039; can become too unwieldy, so we need to formalize a method that allows us to keep track of states and transitions between states. To do this, we will consider all states and for each state, we will list all transitions to other states, along with the conditions required for them. &lt;x \u0438 y, \u043d\u043e \u043d\u0435 z&gt;, then &lt;p&gt;&raquo;, it can become too cumbersome, so we should formalize a method that allows us to keep in mind the states and transitions between states. To achieve this, we will consider all states, and under each state, we will list all transitions to other states, along with the necessary conditions for them.<\/p>\n<p><img decoding=\"async\" alt=\"How to Create Gaming AI: A Beginner&#039;s Guide\" src=\"\/wp-content\/uploads\/2019\/11\/ba4c401aa20de3d22d2478cba5a4b1ec.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nThis is a state transition table \u2014 a comprehensive way of representing an FSM. We will draw a diagram and get a complete overview of how the NPC's behavior changes.<\/p>\n<p><img decoding=\"async\" alt=\"How to Create Gaming AI: A Beginner&#039;s Guide\" src=\"\/wp-content\/uploads\/2019\/11\/b4182359983cf573872dacc575af13dc.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nThe diagram reflects the essence of decision-making for this agent based on the current situation. Each arrow shows a transition between states if the condition next to it is true.<\/p>\n<p>With each update, we check the current state of the agent, review the list of transitions, and if the conditions for a transition are met, it takes on a new state. For example, every frame we check whether the 10-second timer has expired, and if so, the guard transitions from Idling to Patrolling. In the same way, the Attacking state checks the agent's health \u2014 if it's low, he transitions to Fleeing.<\/p>\n<p>This is the handling of transitions between states, but what about the behaviors associated with the states themselves? Regarding the implementation of actual behavior for a specific state, there are usually two types of \u2018hooks\u2019 where we assign actions to the FSM:<\/p>\n<ul>\n<li>Actions that we periodically perform for the current state.<\/li>\n<li>Actions that we take when transitioning from one state to another.<\/li>\n<\/ul>\n<p>\nExamples for the first type. The Patrolling state will move the agent along the patrol route every frame. The Attacking state will try to initiate an attack or transition into a state when it is possible, every frame.<\/p>\n<p>For the second type, let's consider the transition: 'if the enemy is visible and the enemy is too strong, then transition to the Finding Help state.' The agent must choose where to go for help and retain that information so the Finding Help state knows where to turn. Once help is found, the agent transitions back to the Attacking state. At this moment, it will want to inform an ally about the threat, which may trigger the NotifyFriendOfThreat action.<\/p>\n<p>Again, we can view this system through the lens of the Sense\/Think\/Act cycle. Sense is manifested in the data used for transition logic. Think is represented by the transitions available in each state. Act is carried out through actions performed periodically within the state or during transitions between states.<\/p>\n<p>Sometimes continuous polling of transition conditions can be costly. For example, if each agent performs complex calculations every frame to determine if it sees enemies and to understand whether it can transition from the Patrolling state to Attacking \u2014 this will consume a lot of processor time. <\/p>\n<p>Significant changes in the state of the world can be viewed as events that will be processed as they occur. Instead of the FSM checking each frame whether the condition 'can my agent see the player?' is met, a separate system can be set up to perform checks less frequently (e.g., 5 times per second). The result would output Player Seen when the check passes. <\/p>\n<p>This is passed into the FSM, which now must transition to the Player Seen event received condition and respond accordingly. The final behavior remains the same except for a nearly imperceptible delay before the response. However, performance improved as a result of separating part of the Sense into a standalone component.<\/p>\n<h3>Hierarchical finite state machine<\/h3>\n<p>\nHowever, working with large FSMs is not always convenient. If we want to expand the attack state by replacing it with separate MeleeAttacking and RangedAttacking states, we will need to modify the transitions from all other states that lead into the Attacking state (current and future).<\/p>\n<p>You have probably noticed that in our example there are many duplicated transitions. Most transitions in the Idling state are identical to those in the Patrolling state. It would be better not to repeat ourselves, especially if we add more similar states. It makes sense to group Idling and Patrolling under a common label of 'non-combat,' where there is only one common set of transitions to combat states. If we envision this label as a state, then Idling and Patrolling will become sub-states. Here\u2019s an example of using a separate transition table for the new non-combat sub-state:<\/p>\n<p><i>Primary States:<\/i><br \/>\n<img decoding=\"async\" alt=\"How to Create Gaming AI: A Beginner&#039;s Guide\" src=\"\/wp-content\/uploads\/2019\/11\/d86dd918acbe81b9bf22c2fb34aecee3.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n <br \/>\n<i>Out of Combat State:<\/i><br \/>\n<img decoding=\"async\" alt=\"How to Create Gaming AI: A Beginner&#039;s Guide\" src=\"\/wp-content\/uploads\/2019\/11\/9d5bc2053010a32c5f68d7f0192c04ed.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nAnd in diagram form:<\/p>\n<p><img decoding=\"async\" alt=\"How to Create Gaming AI: A Beginner&#039;s Guide\" src=\"\/wp-content\/uploads\/2019\/11\/0ccf95ecafa9ce2a6ea5b5b9833ddc4f.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nThis is the same system, but with a new non-combat state that includes Idling and Patrolling. Each state contains an FSM with sub-states (and these sub-states, in turn, contain their own FSM \u2014 and so on as much as needed), resulting in a Hierarchical Finite State Machine or HFSM. By grouping the non-combat state, we have eliminated a bunch of redundant transitions. We can do the same for any new states with common transitions. For example, if in the future we expand the Attacking state to include MeleeAttacking and MissileAttacking states, they will be sub-states that transition between each other based on the distance to the enemy and the availability of ammunition. Ultimately, complex behavior models and behavior sub-models can be represented with minimal duplication of transitions.<\/p>\n<h3>Behavior Tree<\/h3>\n<p>\nWith HFSM, complex combinations of behaviors are created easily. However, there is a slight difficulty, as decision-making in the form of transition rules is closely tied to the current state. And in many games, that\u2019s exactly what is needed. Careful use of the state hierarchy can reduce the amount of repetition during transitions. But sometimes rules are needed that operate independently of what state you are in or that apply to almost any state. For example, if the agent's health drops to 25%, you would want it to flee regardless of whether it was in combat, idling, or talking \u2014 you would have to add this condition to each state. And if your designer later wants to change the low health threshold from 25% to 10%, you will have to deal with that again.<\/p>\n<p>Ideally, for this situation, a system is needed in which decisions about 'what state to be in' are kept separate from the states themselves, allowing changes to be made in just one place without altering the transition conditions. This is where behavior trees come in.<\/p>\n<p>There are several ways to implement them, but the essence is roughly the same and resembles a decision tree: the algorithm starts from the 'root' node, while the tree contains nodes that represent either decisions or actions. However, there are some key differences:<\/p>\n<ul>\n<li>Now, the nodes return one of three values: Succeeded (if the task is completed), Failed (if it cannot be initiated), or Running (if it is still running and no final result is available).<\/li>\n<li>No more decision nodes to choose between two alternatives. Instead, there are Decorator nodes, which have a single child node. If they Succeed, they execute their sole child node.<\/li>\n<li>Action nodes return a Running value to indicate that actions are being carried out.<\/li>\n<\/ul>\n<p>\nThis small set of nodes can be combined to create a large number of complex behavior models. Let's visualize the HFSM guard from the previous example as a behavior tree:<\/p>\n<p><img decoding=\"async\" alt=\"How to Create Gaming AI: A Beginner&#039;s Guide\" src=\"\/wp-content\/uploads\/2019\/11\/5eaa5c725e4ada8285f16f95bb206d53.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nWith this structure, there shouldn't be an explicit transition from the Idling\/Patrolling states to the Attacking state or any others. If the enemy is visible and the character's health is low, execution will halt at the Fleeing node, regardless of what node it was previously executing \u2014 Patrolling, Idling, Attacking, or any other.<\/p>\n<p><img decoding=\"async\" alt=\"How to Create Gaming AI: A Beginner&#039;s Guide\" src=\"\/wp-content\/uploads\/2019\/11\/e1c1dcc2055174aa7cfa846364b1709a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nBehavior trees are complex \u2014 there are many ways to construct them, and finding the right combination of decorators and composite nodes can be challenging. There are also questions about how often to check the tree \u2014 should we traverse it every frame, or only when one of the conditions changes? How to store state related to nodes \u2014 how to know when we were in the Idling state for 10 seconds or track which nodes were executed last to handle sequencing correctly?<\/p>\n<p>This is why there are many implementations. For example, in some systems, decorator nodes have been replaced with built-in decorators. They reevaluate the tree when the conditions of the decorator change, help to connect nodes, and provide periodic updates.<\/p>\n<h3>Utility-based system<\/h3>\n<p>\nSome games have many different mechanics. It is preferable that they take full advantage of simple and common transition rules, but not necessarily in the form of a complete behavior tree. Rather than having a clear set of choices or a tree of possible actions, it is easier to study all actions and choose the most appropriate one at the moment.<\/p>\n<p>A utility-based system helps with this. It's a system where the agent has many actions and chooses which one to perform based on the relative utility of each. Here, utility is an arbitrary measure of how important or desirable the execution of that action is for the agent. <\/p>\n<p>Based on the calculated utility of an action given the current state and environment, the agent can check and choose the most appropriate other state at any time. This is similar to an FSM, except that transitions are determined by the evaluation of each potential state, including the current one. Note that we choose the most useful action for the transition (or stay if we have already performed it). For added variety, this may be a weighted but random selection from a small list.<\/p>\n<p>The system assigns an arbitrary range of utility values \u2014 for example, from 0 (completely undesirable) to 100 (entirely desirable). Each action has a number of parameters that influence this value's calculation. Returning to our example with the guard:<\/p>\n<p><img decoding=\"async\" alt=\"How to Create Gaming AI: A Beginner&#039;s Guide\" src=\"\/wp-content\/uploads\/2019\/11\/085fb2c197bde93d78455d18e63c9c25.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n <br \/>\nTransitions between actions are ambiguous \u2014 any state can follow any other. The priorities of actions lie in the returned utility values. If an enemy is visible, and this enemy is strong, while the character's health is low, both Fleeing and FindingHelp will return high non-zero values. However, FindingHelp will always be higher. Similarly, non-combat actions never return more than 50, so they will always be ranked lower than combat actions. This must be taken into account when creating actions and calculating their utility.<\/p>\n<p>In our example, actions return either a fixed constant value or one of two fixed values. A more realistic system suggests returning scores from a continuous range of values. For instance, the Fleeing action returns higher utility values when the agent's health is low, while the Attacking action returns lower values if the enemy is too strong. As a result, the Fleeing action takes precedence over Attacking in any situation where the agent feels it lacks sufficient health to defeat the opponent. This allows for changing action priorities based on multiple criteria, making this approach more flexible and variable than behavior trees or FSMs.<\/p>\n<p>Each action has numerous conditions for program calculations. These can be written in script language or as a series of mathematical formulas. In The Sims, which models a character's daily routine, an additional layer of calculations is added\u2014agents receive a set of \"motivations\" that affect utility scores. If a character is hungry, they will become hungrier over time, and the utility score of the EatFood action will increase until the character performs it, reducing hunger levels and bringing the EatFood value back to zero. <\/p>\n<p>The idea of choosing actions based on a scoring system is quite straightforward, which is why a utility-based system can be used as part of AI decision-making processes, rather than as a complete replacement for them. A decision tree may query the utility score of two child nodes and select the higher one. Similarly, a behavior tree may have a composite Utility node to evaluate the utility of actions to determine which child element to execute.<\/p>\n<h2>Movement and Navigation<\/h2>\n<p>\nIn the previous examples, we had a platform that we moved left or right, and a guard that was patrolling or attacking. But how exactly do we handle agent movement over a certain period? How do we set the speed, how do we avoid obstacles, and how do we plan a route if reaching the destination is more complex than simply moving in a straight line? Let's explore this.<\/p>\n<h3>Management<\/h3>\n<p>\nAt the initial stage, let's consider that each agent has a speed value, which includes how fast it moves and in what direction. This can be measured in meters per second, kilometers per hour, pixels per second, etc. Remembering the Sense\/Think\/Act cycle, we can envision that part of Think selects the speed, while part of Act applies this speed to the agent. Typically, games have a physics system that handles this task for you, determining the speed value of each object and adjusting it. Therefore, we can leave the AI with one task \u2014 to decide what speed the agent should have. If it is known where the agent should be, it must be moved in the correct direction at the set speed. A very trivial equation:<\/p>\n<p><i>desired_travel = destination_position \u2013 agent_position<\/i><\/p>\n<p>Imagine a 2D world. The agent is at point (-2,-2), the destination is somewhere to the northeast at point (30, 20), and the required path for the agent to get there is (32, 22). Let's assume these positions are measured in meters \u2014 if we take the agent's speed as 5 meters per second, we will scale our displacement vector and get a speed of approximately (4.12, 2.83). With these parameters, the agent would arrive at the destination in almost 8 seconds.<\/p>\n<p>The values can be recalculated at any time. If the agent was halfway to the target, the movement would be half the distance, but since the maximum speed of the agent is 5 m\/s (as we decided earlier), the speed will remain the same. This also works for moving targets, allowing the agent to make small adjustments as they move.<\/p>\n<p>But we want more variability \u2014 for example, to slowly increase speed to simulate a character moving from a standstill to a run. The same effect can be applied at the end before stopping. These features are known as steering behaviors, each with specific names: Seek, Flee, Arrival, etc. The idea is that acceleration forces can be applied to the agent's speed based on comparing the agent's position and current speed with the destination, allowing various ways to move toward the target.<\/p>\n<p>Each behavior has a slightly different objective. Seek and Arrival are methods for moving the agent to a destination. Obstacle Avoidance and Separation adjust the agent's movement to bypass obstacles on the way to the goal. Alignment and Cohesion keep agents moving together. Any number of different steering behaviors can be summed to produce a single path vector considering all factors. An agent utilizing Arrival, Separation, and Obstacle Avoidance behaviors keeps away from walls and other agents. This approach works well in open locations without extraneous details. <\/p>\n<p>In more challenging conditions, combining different behaviors works less effectively \u2014 for example, an agent may get stuck in a wall due to a conflict between Arrival and Obstacle Avoidance. Therefore, it is necessary to consider options that are more complex than simply adding all the values. One approach is to evaluate movement in different directions and choose the best option rather than summing the results of each behavior. <\/p>\n<p>However, in a complex environment with dead ends and choices about which direction to go, we will need something even more advanced.<\/p>\n<h3>Pathfinding<\/h3>\n<p>\nSteering behaviors are great for simple movement in open areas (like a football field or arena), where getting from A to B is a direct path with slight deviations around obstacles. For complex routes, we need pathfinding, which is a method of exploring the world and making decisions about the route through it.<\/p>\n<p>The simplest approach is to overlay a grid on each square adjacent to the agent and assess which of them allow movement. If any of them is a destination, you follow from there along the route from each square back to the previous one until you reach the start. This is the route. Otherwise, repeat the process with the closest other squares until you find the destination or run out of squares (which means there is no possible route). This is formally known as Breadth-First Search or BFS. At each step, it looks in all directions (hence breadth). The search space resembles a wave front that moves until it reaches the target area \u2014 the search area expands at each step until it encompasses the end point, after which the path back to the start can be traced.<\/p>\n<p><img decoding=\"async\" alt=\"How to Create Gaming AI: A Beginner&#039;s Guide\" src=\"\/wp-content\/uploads\/2019\/11\/d367e62bc53033b05388538649853a41.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nAs a result, you will obtain a list of squares that constitute the desired route. This is the path (hence, pathfinding) \u2014 a list of locations that the agent will visit while heading to the destination.<\/p>\n<p>Given that we know the position of each square in the world, we can use steering behaviors to move along the path \u2014 from node 1 to node 2, then from node 2 to node 3, and so on. The simplest option is to head towards the center of the next square, but an even better approach is to stop at the midpoint of the edge between the current square and the next. This allows the agent to cut corners on sharp turns.<\/p>\n<p>The BFS algorithm has drawbacks \u2014 it explores as many squares in the 'wrong' direction as it does in the 'right' direction. This is where a more sophisticated algorithm called A* (A star) comes into play. It operates similarly but instead of blindly exploring neighboring squares (then neighbors of neighbors, then neighbors of neighbors of neighbors, and so forth), it collects nodes into a list and sorts them so that the next node to be explored is always the one that will lead to the shortest route. Nodes are sorted based on heuristics that consider two factors \u2014 the 'cost' of the hypothetical route to the desired square (including any movement costs) and an estimate of how far this square is from the destination (shifting the search in the right direction).<\/p>\n<p><img decoding=\"async\" alt=\"How to Create Gaming AI: A Beginner&#039;s Guide\" src=\"\/wp-content\/uploads\/2019\/11\/1cab4f53fa5af6b31d352c7bcf453d7e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nThis example shows that the agent explores one square at a time, each time choosing the neighboring one that appears most promising. The resulting path is the same as in BFS, but fewer squares were considered in the process \u2014 which is significant for game performance.<\/p>\n<h3>Free Movement<\/h3>\n<p>\nHowever, most games are not laid out on a grid, and often it can't be done without sacrificing realism. Compromises are necessary. What size should the squares be? If they are too large, they won\u2019t be able to accurately represent small corridors or turns; if they are too small, there will be an excess of squares to search through, which will ultimately take a lot of time.<\/p>\n<p>The first thing to understand is that a grid gives us a graph of connected nodes. A* and BFS algorithms essentially operate on graphs and do not care about our grid at all. We could place nodes anywhere in the game world: as long as there are connections between any two connected nodes, including the start and end points and at least one of the nodes \u2014 the algorithm will work just as well as before. This is often referred to as a waypoint system since each node represents a significant position in the world that can be part of any number of hypothetical paths.<\/p>\n<p><img decoding=\"async\" alt=\"How to Create Gaming AI: A Beginner&#039;s Guide\" src=\"\/wp-content\/uploads\/2019\/11\/d87e9d4bb2a2fc713d32abc158506eaa.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<i>Example 1: A node in each square. The search starts from the node where the agent is located and ends at the node of the target square.<\/i><\/p>\n<p><img decoding=\"async\" alt=\"How to Create Gaming AI: A Beginner&#039;s Guide\" src=\"\/wp-content\/uploads\/2019\/11\/b535a5db805efdc427d7c5724b866982.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<i>Example 2: A smaller set of nodes (waypoints). The search starts in the square with the agent, goes through the necessary number of nodes, and then continues to the destination.<\/i><\/p>\n<p>This is quite a flexible and powerful system. However, some caution is required in decisions about where and how to place waypoints; otherwise, agents may simply not see the nearest point and be unable to start their path. It would be easier if we could automatically place waypoints based on the geometry of the world.<\/p>\n<p>This is where the navigation mesh, or navmesh, comes in. It is typically a 2D mesh of triangles imposed on the geometry of the world \u2014 everywhere the agent is allowed to walk. Each triangle in the mesh becomes a node in the graph and has up to three adjacent triangles, which become neighboring nodes in the graph. <\/p>\n<p>This image is an example from the Unity engine\u2014it analyzed the geometry in the world and created a navmesh (shown in light blue in the screenshot). Each polygon in the navmesh is an area where an agent can stand or move from one polygon to another. In this example, the polygons are smaller than the floors they are located on\u2014this is done to account for the size of the agent, which may extend beyond its nominal position.<\/p>\n<p><img decoding=\"async\" alt=\"How to Create Gaming AI: A Beginner&#039;s Guide\" src=\"\/wp-content\/uploads\/2019\/11\/845705ba7b9a9d469203aedf7942da41.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nWe can search for a route through this mesh, again using the A* algorithm. This will give us a nearly perfect route in the world that accounts for all geometry while not requiring extra nodes or creating waypoints.<\/p>\n<p>Pathfinding is too broad a topic to cover in just one section of an article. If you wish to explore it in more detail, you can visit <noindex><a rel=\"nofollow\" href=\"https:\/\/www.redblobgames.com\/pathfinding\/a-star\/introduction.html\">Amit Patel's website<\/a><\/noindex>.<\/p>\n<h2>Planning<\/h2>\n<p>\nWe have confirmed with pathfinding that sometimes it is not enough to simply choose a direction and move\u2014you need to select a route and make several turns to reach your intended destination. We can generalize this idea: achieving a goal is not just the next step, but a whole sequence, where sometimes it is necessary to look ahead several steps to know what the first one should be. This is called planning. Pathfinding can be seen as one of several components of planning. From the perspective of our Sense\/Think\/Act cycle, this is where the Think part plans several parts of Act for the future.<\/p>\n<p>Let\u2019s illustrate this with an example from the card game Magic: The Gathering. We are playing first with the following cards in hand:<\/p>\n<ul>\n<li>Swamp\u2014provides 1 black mana (land card).<\/li>\n<li>Forest\u2014provides 1 green mana (land card).<\/li>\n<li>Fugitive Wizard\u2014requires 1 blue mana to cast.<\/li>\n<li>Elvish Mystic\u2014requires 1 green mana to cast.<\/li>\n<\/ul>\n<p>\nWe will ignore the remaining three cards to simplify matters. According to the rules, a player is allowed to play 1 land card per turn, they can 'tap' that card to draw mana from it, and then use spells (including summoning creatures) based on the amount of mana. In this situation, the human player knows to play Forest, 'tap' 1 green mana, and then summon Elvish Mystic. But how can the game AI deduce this?<\/p>\n<h3>Simple planning<\/h3>\n<p>\nThe trivial approach is to try each action in turn until no suitable options remain. Looking at the cards, the AI sees that it can play a Swamp. And it plays it. Are there any other actions available for this turn? It cannot summon either the Elvish Mystic or the Fugitive Wizard, as summoning requires green and blue mana, respectively, and a Swamp only provides black mana. Furthermore, it cannot play a Forest since it has already played a Swamp. Thus, the game AI followed the rules, but did so poorly. There is room for improvement.<\/p>\n<p>Planning can identify a list of actions that lead the game to the desired state. Just as each square on the path had neighbors (in pathfinding), each action in the plan also has neighbors or successors. We can search for these actions and subsequent actions until we reach the desired state.<\/p>\n<p>In our example, the desired result is \"summon a creature if possible.\" At the start of the turn, we only see two possible actions allowed by the game rules:<\/p>\n<p><i>1. Play Swamp (result: Swamp in play)<br \/>\n2. Play Forest (result: Forest in play)<\/i><\/p>\n<p>Each accepted action can lead to further actions and block others, again depending on the game rules. Imagine we played a Swamp \u2014 this removes Swamp as the next step (having already played it), and it also removes Forest (since the rules allow for playing one land card per turn). Afterwards, the AI adds as the next step \u2014 to gain 1 black mana, because there are no other options. If it proceeds and chooses to Tap the Swamp, it will get 1 unit of black mana and will not be able to do anything with it.<\/p>\n<p><i>1. Play Swamp (result: Swamp in play)<br \/>\n 1.1 Tap the Swamp (result: Swamp tapped, +1 black mana)<br \/>\n No available actions \u2013 END<br \/>\n2. Play Forest (result: Forest in play)<\/i><\/p>\n<p>The list of actions came up short, and we hit a dead end. We repeat the process for the next action. We play Forest, opening the action \"get 1 green mana,\" which in turn will open a third action \u2014 summon Elvish Mystic.<\/p>\n<p><i>1. Play Swamp (result: Swamp in play)<br \/>\n 1.1 Tap the Swamp (result: Swamp tapped, +1 black mana)<br \/>\n No available actions \u2013 END<br \/>\n2. Play Forest (result: Forest in play)<br \/>\n 2.1 Tap the Forest (result: Forest tapped, +1 green mana)<br \/>\n 2.1.1 Summon Elvish Mystic (result: Elvish Mystic in play, -1 green mana)<br \/>\n No available actions \u2013 END<\/i><\/p>\n<p>Finally, we have explored all possible actions and found a plan to summon a creature.<\/p>\n<p>This is a very simplified example. It is advisable to choose the best possible plan, rather than just any plan that meets certain criteria. Generally, potential plans can be assessed based on the final outcome or the overall benefit of executing them. You can award yourself 1 point for playing a land card and 3 points for summoning a creature. Playing a Swamp would earn you 1 point. Meanwhile, playing a Forest \u2192 Tapping the Forest \u2192 summoning an Elvish Mystic would immediately yield 4 points. <\/p>\n<p>This is how planning works in Magic: The Gathering, but the same logic applies to other situations as well. For instance, moving a pawn to clear space for a bishop in chess. Or taking cover behind a wall to shoot safely in XCOM. In general, you understand the essence.<\/p>\n<h3>Improved Planning<\/h3>\n<p>\nSometimes there are too many potential actions to consider every possible option. Going back to the example of Magic: The Gathering: let's say that in the game you have several land and creature cards in your hand \u2014 the number of possible combinations of moves can be quite large. There are several solutions to this problem.<\/p>\n<p>The first method is backwards chaining. Instead of going through all combinations, it is better to start from the final outcome and try to find a direct route. Instead of moving from the root of the tree to a specific leaf, we move in the opposite direction \u2014 from the leaf to the root. This method is simpler and faster.<\/p>\n<p>If the opponent has 1 health point, you can find a plan \"deal 1 or more damage\". To achieve this, certain conditions must be met: <\/p>\n<p>1. The damage can be dealt by a spell \u2014 it must be in your hand.<br \/>\n2. To cast the spell \u2014 mana is required.<br \/>\n3. To gain mana \u2014 a land card must be played.<br \/>\n4. To play a land card \u2014 you need to have it in your hand.<\/p>\n<p>Another method is best-first search. Instead of going through all possible paths, we select the most suitable one. This method often provides an optimal plan without unnecessary search costs. A* is a form of best-first search \u2014 by exploring the most promising routes from the start, it can already find the best path without needing to check other options.<\/p>\n<p>An interesting and increasingly popular variant of best-first search is Monte Carlo Tree Search. Instead of guessing which plans are better than others when deciding each subsequent action, the algorithm selects random successors at each step until it reaches an end (when the plan results in a win or loss). The final result is then used to increase or decrease the 'weight' assessment of previous options. By repeating this process multiple times, the algorithm provides a good evaluation of which next step is better, even if the situation changes (if the opponent takes action to hinder the player). <\/p>\n<p>In the discussion of game planning, you can't overlook Goal-Oriented Action Planning or GOAP. This is a widely used and discussed method, but aside from a few distinctive details, it is essentially a form of backwards chaining, which we've talked about earlier. If the task is 'eliminate the player', and the player is behind cover, the plan might be: destroy with a grenade \u2192 acquire it \u2192 throw.<\/p>\n<p>Typically, there are several goals, each with its own priority. If the highest priority goal cannot be accomplished (no combination of actions creates the plan 'eliminate the player' because the player is not visible), the AI will revert to lower priority goals.<\/p>\n<h2>Training and adaptation<\/h2>\n<p>\nWe've already mentioned that game AI typically does not employ machine learning because it is not suitable for controlling agents in real-time. However, this does not mean that nothing can be borrowed from this area. We want an opponent in a shooter from whom something can be learned, for instance, about the best positions on the map. Or an opponent in a fighting game that would block commonly used player combo moves, encouraging the use of others. Thus, machine learning can be quite useful in such situations.<\/p>\n<h3>Statistics and probabilities<\/h3>\n<p>\nBefore we dive into complex examples, let's consider how far we can go by taking some simple measurements and using them to make decisions. For instance, in real-time strategy \u2014 how can we determine if a player is able to launch an attack in the first few minutes of the game and what defenses to prepare against that? We can analyze the player's past experiences to understand what their future reactions might be. Initially, we don't have such baseline data, but we can collect it \u2014 every time the AI plays against a human, it can log the time of the first attack. After a few sessions, we will obtain an average value of when the player is likely to attack in the future.<\/p>\n<p>There\u2019s an issue with average values: if a player rushes 20 times and plays slowly 20 times, the necessary values will be somewhere in the middle, which won\u2019t provide us with anything useful. One solution is to limit the input data \u2014 we can take into account the last 20 instances.<\/p>\n<p>A similar approach is used when assessing the probability of certain actions, assuming that a player's past preferences will remain the same in the future. If a player attacks us five times with a fireball, twice with lightning, and once hand-to-hand, it\u2019s clear that they prefer fireballs. We can extrapolate and see the probability of using different types of weapons: fireball = 62.5%, lightning = 25%, and hand-to-hand = 12.5%. Our gaming AI needs to prepare to defend against fire.<\/p>\n<p>Another interesting method is to use the Naive Bayes Classifier to analyze large volumes of input data and classify the situation so that the AI reacts appropriately. Bayesian classifiers are best known for their use in email spam filters. They examine words, compare them with where those words appeared before (in spam or not), and draw conclusions about incoming emails. We can do the same even with a smaller amount of input data. Based on all the useful information that the AI sees (such as what enemy units are produced, what spells they use, or what technologies they have researched), and the final outcome (war or peace, 'rush' or defend, etc.) \u2014 we will determine the appropriate behavior for the AI.<\/p>\n<p>All these learning methods are sufficient, but it is preferable to use them based on data from testing. The AI will learn to adapt to various strategies that your playtesters used. An AI that adapts to players post-release may become either too predictable or, conversely, too difficult to beat.<\/p>\n<h3>Adaptation Based on Values<\/h3>\n<p>\nConsidering the content of our game world and rules, we can change the set of values that influence decision-making, rather than simply using input data. Here\u2019s how we do it:<\/p>\n<ul>\n<li>Let the AI gather data on the state of the world and key events during gameplay (as outlined above).<\/li>\n<li>We will modify several important values based on this data.<\/li>\n<li>We will implement our decisions based on the processing or evaluation of these values.<\/li>\n<\/ul>\n<p>\nFor example, an agent has several rooms to choose from on a first-person shooter map. Each room has its own value, which determines how desirable it is to visit. The AI randomly selects which room to enter based on its value. Then the agent remembers in which room it was killed and decreases its value (the likelihood of returning there). Similarly, for the opposite scenario\u2014if the agent eliminates many opponents, the value of that room increases.<\/p>\n<h3>Markov Model<\/h3>\n<p>\nWhat if we use the collected data to make predictions? If we remember each room where we see the player over a certain period, we can anticipate which room the player might move to next. By tracking and recording the player's movements through rooms (values), we can make predictions about them.<\/p>\n<p>Let's take three rooms: red, green, and blue. Also, we have the observations we recorded while watching the gameplay session:<\/p>\n<p><img decoding=\"async\" alt=\"How to Create Gaming AI: A Beginner&#039;s Guide\" src=\"\/wp-content\/uploads\/2019\/11\/6e90a365b72a176c36c9a14213baaafc.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n <br \/>\nThe number of observations for each room is nearly equal \u2014 where to set a good ambush, we still don't know. Gathering statistics is also complicated by player respawns, which occur evenly across the map. However, data on the next room they enter after spawning on the map is already useful.<\/p>\n<p>It is clear that the green room appeals to players \u2014 most people transition from the red room to it, with 50% of them staying there thereafter. The blue room, on the other hand, is not popular; few people visit it, and if they do, they don't linger. <\/p>\n<p>But the data tells us something more important \u2014 when a player is in the blue room, the next room we are most likely to see them in will be the red room, not the green one. Despite the fact that the green room is more popular than the red, the situation changes when the player is in the blue one. The next state (i.e., the room the player will move to) depends on the previous state (i.e., the room the player is currently in). Due to the analysis of dependencies, we will make more accurate predictions than if we simply counted observations independently of one another.<\/p>\n<p>Predicting the future state based on data from the past state is called a Markov model, and such examples (with rooms) are referred to as Markov chains. Since the models represent the probabilities of changes between successive states, they are visually represented as FSMs with probabilities around each transition. Previously, we used FSMs to represent the behavioral state of the agent, but this concept extends to any state, regardless of whether it pertains to the agent or not. In this case, the states represent the room occupied by the agent:<\/p>\n<p><img decoding=\"async\" alt=\"How to Create Gaming AI: A Beginner&#039;s Guide\" src=\"\/wp-content\/uploads\/2019\/11\/edb32dff7a3298b19c3fa4d66f48e9f4.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nThis is a simple way to represent the relative probability of state changes, giving AI some ability to predict the next state. It is possible to predict several steps ahead.<\/p>\n<p>If a player is in the green room, there is a 50% chance that they will remain there in the next observation. But what is the likelihood that they will still be there afterward? There is not only a chance that the player stayed in the green room after two observations, but also a chance that they left and returned. Here is a new table considering the new data:<\/p>\n<p><img decoding=\"async\" alt=\"How to Create Gaming AI: A Beginner&#039;s Guide\" src=\"\/wp-content\/uploads\/2019\/11\/f87afff68b066a879661e37f68654ae2.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n <br \/>\nIt shows that the chance of seeing a player in the green room after two observations will be 51% \u2014 with 21% that they come from the red room, 5% of them visiting the blue room in between, and 25% that the player does not leave the green room at all.<\/p>\n<p>A table is simply a visual tool\u2014the procedure requires only multiplying probabilities at each step. This means you can look far into the future with one caveat: we assume the chance of entering a room entirely depends on the current room. This is called the Markov Property\u2014the future state depends only on the present. However, this is not 100% accurate. Players can change their decisions based on other factors: health level or amount of ammunition. Since we do not record these values, our predictions will be less accurate.<\/p>\n<h3>N-Grams<\/h3>\n<p>\nWhat about the example of fighting and predicting a player's combo moves? It's the same! But instead of a single state or event, we will explore entire sequences that make up the combo strike.<\/p>\n<p>One way to do this is to keep each input (like Kick, Punch, or Block) in a buffer and record the entire buffer as an event. So, if the player repeatedly presses Kick, Kick, Punch to execute the SuperDeathFist attack, the AI system stores all inputs in a buffer and remembers the last three used at each step.<\/p>\n<p><img decoding=\"async\" alt=\"How to Create Gaming AI: A Beginner&#039;s Guide\" src=\"\/wp-content\/uploads\/2019\/11\/9a95226ae155dca5e45a66d4440f3cd4.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n(Bold indicates the lines when the player initiates the SuperDeathFist attack.)<\/p>\n<p>The AI will see all the scenarios when the player chose Kick, followed by another Kick, and then recognizes that the next input is always Punch. This allows the agent to predict the SuperDeathFist combo and block it if possible.<\/p>\n<p>These sequences of events are called N-grams, where N is the number of stored items. In the earlier example, this was a 3-gram (trigram), which means the first two entries are used to predict the third. Accordingly, in a 5-gram, the first four entries predict the fifth, and so on.<\/p>\n<p>The developer needs to carefully choose the size of the N-grams. A smaller N requires less memory but stores less history. For instance, a 2-gram (bigram) will record Kick, Kick or Kick, Punch, but will not be able to store Kick, Kick, Punch, so the AI will not respond to the SuperDeathFist combo.<\/p>\n<p>On the other hand, larger numbers require more memory and the AI will find it more challenging to learn, as there will be many more possible options. If you had three possible inputs\u2014Kick, Punch, or Block\u2014and we used a 10-gram, it would yield about 60,000 different variations.<\/p>\n<p>The bigram model is a simple Markov chain \u2014 each pair of \"previous state\/current state\" is a bigram, and you can predict the second state based on the first. A trigram and larger N-grams can also be viewed as Markov chains, where all elements (except the last in the N-gram) together form the first state, and the last element is the second. An example with fighting shows the chance of transitioning from the Kick and Kick state to the Kick and Punch state. By considering several entries of input history as one unit, we essentially transform the input sequence into part of a whole state. This gives us the Markov property, allowing the use of Markov chains to predict the next input and guess which combo move will follow.<\/p>\n<h2>Conclusion<\/h2>\n<p>\nWe discussed the most common tools and approaches in artificial intelligence development. We also analyzed situations where they need to be applied and where they are particularly useful. <\/p>\n<p>This should be enough to understand the basics of game AI. However, of course, this is far from all the methods. Less popular, but no less effective methods include:<\/p>\n<ul>\n<li>optimization algorithms, including hill climbing, gradient descent, and genetic algorithms<\/li>\n<li>competitive search\/planning algorithms (minimax and alpha-beta pruning)<\/li>\n<li>classification methods (perceptrons, neural networks, and support vector machines)<\/li>\n<li>systems for processing perception and memory of agents<\/li>\n<li>architectural approaches to AI (hybrid systems, subsets of architectures, and other ways of layering AI systems)<\/li>\n<li>animation tools (planning and movement coordination)<\/li>\n<li>performance factors (level of detail, anytime algorithms, and time slicing)<\/li>\n<\/ul>\n<p>\nOnline resources on the topic:<\/p>\n<p>1. On GameDev.net, there is a <noindex><a rel=\"nofollow\" href=\"https:\/\/www.gamedev.net\/articles\/programming\/artificial-intelligence\/\">section with articles and tutorials on AI<\/a><\/noindex>, as well as <noindex><a rel=\"nofollow\" href=\"https:\/\/www.gamedev.net\/forums\/forum\/6-artificial-intelligence\/\">forum<\/a><\/noindex>.<br \/>\n2. <noindex><a rel=\"nofollow\" href=\"http:\/\/aigamedev.com\/\">AiGameDev.com<\/a><\/noindex> contains numerous presentations and articles on a wide range of topics related to game AI development.<br \/>\n3. <noindex><a rel=\"nofollow\" href=\"https:\/\/www.gdcvault.com\/\">The GDC Vault<\/a><\/noindex> includes topics from the GDC AI summit, many of which are available for free.<br \/>\n4. Useful materials can also be found on the site <noindex><a rel=\"nofollow\" href=\"http:\/\/gameai.com\/\">AI Game Programmers Guild<\/a><\/noindex>.<br \/>\n5. Tommy Thompson, an AI researcher and game developer, produces videos on the YouTube channel <noindex><a rel=\"nofollow\" href=\"https:\/\/www.youtube.com\/user\/tthompso\">AI and Games<\/a><\/noindex> explaining and exploring AI in commercial games.<\/p>\n<p>Books on the topic:<\/p>\n<p>1. The Game AI Pro book series consists of collections of short articles explaining how to implement specific features or solve particular problems.<\/p>\n<p><noindex><a rel=\"nofollow\" href=\"http:\/\/go.gamedev.net\/?id=13722X707581&amp;xs=1&amp;isjs=1&amp;url=https%3A%2F%2Famzn.to%2F2KGoB8n&amp;xguid=f8ad586e5984991508efff4754027dbd&amp;xuuid=305451ecead59d76ca830fded0aab276&amp;xsessid=6ccb8b9fa3f10b478b65f7ed703a447b&amp;xcreo=0&amp;xed=0&amp;sref=https%3A%2F%2Fwww.gamedev.net%2Farticles%2Fprogramming%2Fartificial-intelligence%2Fthe-total-beginners-guide-to-game-ai-r4942%2F%3Fdo%3Dedit%26d%3D1%26id%3D4942%26csrfKey%3D7015c6d2c5c643e87baa74f8e5d2c094&amp;pref=https%3A%2F%2Fwww.gamedev.net%2Farticles%2Fprogramming%2Fartificial-intelligence%2Fthe-total-beginners-guide-to-game-ai-r4942%2F&amp;xtz=420&amp;jv=13.7.1&amp;bv=2.5.1\">Game AI Pro: Collected Wisdom of Game AI Professionals<\/a><\/noindex><br \/>\n<noindex><a rel=\"nofollow\" href=\"http:\/\/go.gamedev.net\/?id=13722X707581&amp;xs=1&amp;isjs=1&amp;url=https%3A%2F%2Famzn.to%2F2KFKyoe&amp;xguid=f8ad586e5984991508efff4754027dbd&amp;xuuid=305451ecead59d76ca830fded0aab276&amp;xsessid=6ccb8b9fa3f10b478b65f7ed703a447b&amp;xcreo=0&amp;xed=0&amp;sref=https%3A%2F%2Fwww.gamedev.net%2Farticles%2Fprogramming%2Fartificial-intelligence%2Fthe-total-beginners-guide-to-game-ai-r4942%2F%3Fdo%3Dedit%26d%3D1%26id%3D4942%26csrfKey%3D7015c6d2c5c643e87baa74f8e5d2c094&amp;pref=https%3A%2F%2Fwww.gamedev.net%2Farticles%2Fprogramming%2Fartificial-intelligence%2Fthe-total-beginners-guide-to-game-ai-r4942%2F&amp;xtz=420&amp;jv=13.7.1&amp;bv=2.5.1\">Game AI Pro 2: Collected Wisdom of Game AI Professionals<\/a><\/noindex><br \/>\n<noindex><a rel=\"nofollow\" href=\"https:\/\/amzn.to\/2KF4irS\">Game AI Pro 3: Collected Wisdom of Game AI Professionals<\/a><\/noindex><\/p>\n<p>2. The AI Game Programming Wisdom series is a predecessor to the Game AI Pro series. It contains older methods, but nearly all are still relevant today.<\/p>\n<p><noindex><a rel=\"nofollow\" href=\"https:\/\/amzn.to\/2ARFhKx\">AI Game Programming Wisdom 1<\/a><\/noindex><br \/>\n<noindex><a rel=\"nofollow\" href=\"https:\/\/amzn.to\/2Mkv4eh\">AI Game Programming Wisdom 2<\/a><\/noindex><br \/>\n<noindex><a rel=\"nofollow\" href=\"https:\/\/amzn.to\/2nnuYEh\">AI Game Programming Wisdom 3<\/a><\/noindex><br \/>\n<noindex><a rel=\"nofollow\" href=\"https:\/\/amzn.to\/2ARFEEV\">AI Game Programming Wisdom 4<\/a><\/noindex><\/p>\n<p>3. <noindex><a rel=\"nofollow\" href=\"https:\/\/amzn.to\/2AWKuRh\">Artificial Intelligence: A Modern Approach<\/a><\/noindex> \u2014 is one of the foundational texts for anyone looking to understand the general field of artificial intelligence. This book is not about game development\u2014it teaches the basic principles of AI.<br \/>\n<br \/>Source: <a content=\"nofollow\" rel=\"nofollow\" href=\"https:\/\/habr.com\/ru\/company\/pixonic\/blog\/428892\/\">habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"<p>\u041d\u0430\u0442\u043a\u043d\u0443\u043b\u0441\u044f \u043d\u0430 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b\u0439 \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b \u043e\u0431 \u0438\u0441\u043a\u0443\u0441\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u043c \u0438\u043d\u0442\u0435\u043b\u043b\u0435\u043a\u0442\u0435 \u0432 \u0438\u0433\u0440\u0430\u0445. \u0421 \u043e\u0431\u044a\u044f\u0441\u043d\u0435\u043d\u0438\u0435\u043c \u0431\u0430\u0437\u043e\u0432\u044b\u0445 \u0432\u0435\u0449\u0435\u0439 \u043f\u0440\u043e \u0418\u0418 \u043d\u0430 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u043f\u0440\u0438\u043c\u0435\u0440\u0430\u0445, \u0430 \u0435\u0449\u0435 \u0432\u043d\u0443\u0442\u0440\u0438 \u043c\u043d\u043e\u0433\u043e \u043f\u043e\u043b\u0435\u0437\u043d\u044b\u0445 \u0438\u043d\u0441\u0442\u0440\u0443\u043c\u0435\u043d\u0442\u043e\u0432 \u0438 \u043c\u0435\u0442\u043e\u0434\u043e\u0432 \u0434\u043b\u044f \u0435\u0433\u043e \u0443\u0434\u043e\u0431\u043d\u043e\u0439 \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u043a\u0438 \u0438 \u043f\u0440\u043e\u0435\u043a\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f. \u041a\u0430\u043a, \u0433\u0434\u0435 \u0438 \u043a\u043e\u0433\u0434\u0430 \u0438\u0445 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u2014 \u0442\u043e\u0436\u0435 \u0435\u0441\u0442\u044c. \u0411\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u043e \u043f\u0440\u0438\u043c\u0435\u0440\u043e\u0432 \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u044b \u0432 \u043f\u0441\u0435\u0432\u0434\u043e\u043a\u043e\u0434\u0435, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0433\u043b\u0443\u0431\u043e\u043a\u0438\u0435 \u0437\u043d\u0430\u043d\u0438\u044f \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043d\u0435 \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u044e\u0442\u0441\u044f. \u041f\u043e\u0434 \u043a\u0430\u0442\u043e\u043c 35 [&hellip;]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[702],"tags":[],"class_list":["post-52118","post","type-post","status-publish","format-standard","hentry","category-news"],"aioseo_notices":[],"aioseo_head":"\n\t\t<!-- All in One SEO 5.0.2 - aioseo.com -->\n\t<meta name=\"description\" content=\"\u041d\u0430\u0442\u043a\u043d\u0443\u043b\u0441\u044f \u043d\u0430 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b\u0439 \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b \u043e\u0431.\" \/>\n\t<meta name=\"robots\" content=\"max-image-preview:large\" \/>\n\t<meta name=\"author\" content=\"Yuri Gagarin\"\/>\n\t<link rel=\"canonical\" href=\"https:\/\/prohoster.info\/en\/blog\/news\/kak-sozdat-igrovoj-ii-gajd-dlya-nachinayushhih\" \/>\n\t<meta name=\"generator\" content=\"All in One SEO (AIOSEO) 5.0.2\" \/>\n\t\t<meta property=\"og:locale\" content=\"en_US\" \/>\n\t\t<meta property=\"og:site_name\" content=\"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b\" \/>\n\t\t<meta property=\"og:type\" content=\"article\" \/>\n\t\t<meta property=\"og:title\" content=\"\ud83e\udd47\u041a\u0430\u043a \u0441\u043e\u0437\u0434\u0430\u0442\u044c \u0438\u0433\u0440\u043e\u0432\u043e\u0439 \u0418\u0418: \u0433\u0430\u0439\u0434 \u0434\u043b\u044f \u043d\u0430\u0447\u0438\u043d\u0430\u044e\u0449\u0438\u0445 | ProHoster\" \/>\n\t\t<meta property=\"og:description\" content=\"\u041d\u0430\u0442\u043a\u043d\u0443\u043b\u0441\u044f \u043d\u0430 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b\u0439 \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b \u043e\u0431.\" \/>\n\t\t<meta property=\"og:url\" content=\"https:\/\/prohoster.info\/en\/blog\/news\/kak-sozdat-igrovoj-ii-gajd-dlya-nachinayushhih\" \/>\n\t\t<meta property=\"og:image\" content=\"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg\" \/>\n\t\t<meta property=\"og:image:secure_url\" content=\"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg\" \/>\n\t\t<meta property=\"og:image:width\" content=\"350\" \/>\n\t\t<meta property=\"og:image:height\" content=\"350\" \/>\n\t\t<meta property=\"article:published_time\" content=\"2019-10-31T21:00:00+00:00\" \/>\n\t\t<meta property=\"article:modified_time\" content=\"2020-02-18T10:59:47+00:00\" \/>\n\t\t<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/prohoster\" \/>\n\t\t<meta property=\"article:author\" content=\"https:\/\/www.facebook.com\/prohoster\" \/>\n\t\t<!-- All in One SEO -->\n\n","aioseo_head_json":{"title":"\ud83e\udd47How to Create Game AI: A Beginner's Guide | ProHoster","description":"Came across an interesting piece about.","canonical_url":"https:\/\/prohoster.info\/en\/blog\/news\/kak-sozdat-igrovoj-ii-gajd-dlya-nachinayushhih","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"en_US","og:site_name":"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b","og:type":"article","og:title":"\ud83e\udd47\u041a\u0430\u043a \u0441\u043e\u0437\u0434\u0430\u0442\u044c \u0438\u0433\u0440\u043e\u0432\u043e\u0439 \u0418\u0418: \u0433\u0430\u0439\u0434 \u0434\u043b\u044f \u043d\u0430\u0447\u0438\u043d\u0430\u044e\u0449\u0438\u0445 | ProHoster","og:description":"\u041d\u0430\u0442\u043a\u043d\u0443\u043b\u0441\u044f \u043d\u0430 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b\u0439 \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b \u043e\u0431.","og:url":"https:\/\/prohoster.info\/en\/blog\/news\/kak-sozdat-igrovoj-ii-gajd-dlya-nachinayushhih","og:image":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:secure_url":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:width":350,"og:image:height":350,"article:published_time":"2019-10-31T21:00:00+00:00","article:modified_time":"2020-02-18T10:59:47+00:00","article:publisher":"https:\/\/www.facebook.com\/prohoster","article:author":"https:\/\/www.facebook.com\/prohoster"},"aioseo_meta_data":{"post_id":"52118","title":null,"description":null,"keywords":null,"keyphrases":null,"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"local_seo":null,"seo_analyzer_scan_date":"2026-01-24 02:32:21","breadcrumb_settings":null,"limit_modified_date":false,"reviewed_by":null,"ai":null,"created":"2021-02-28 20:49:49","updated":"2026-01-24 02:32:21","focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"gt_translate_keys":[{"key":"link","format":"url"}],"_links":{"self":[{"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/posts\/52118","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/comments?post=52118"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/posts\/52118\/revisions"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/media?parent=52118"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/categories?post=52118"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/tags?post=52118"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}