Racing Games AI

This genre is mostly divided into two main groups, vehicular and specialty.

The variants of vehicular games appeared early, and the split stuck. They are differentiated by their camera perspective: the first-third person racing game and an overhead view.

The specialty racing games are mostly fad driven – they involve the hot racing style sport at the time.

One last subtype is the cart racing game, which simplifies the driving portion of the game and adds obstacles, strange trucks, and other action elements.

Common AI Elements

Track AI

Where the road meets the rubber, track AI is the system needed to keep a CPU-controlled car on racetrack (or city street) at high speed within the rules of the game. This is usually a state-based system with the different vehicle states detailing the main ways that a racer can be on track. As guidelines, most games use combination of physical and optimal lines of travel (which are either data path laid down in track editor, or calculated automatically by a technique known as “finding the path of minimum curvature”, as shown in figure below) that mimic the invisible lines of travel that humans use when they race on tracks and roads.

image

 

Traffic

Some games use traffic systems that look very realistic with lane changes, cars getting over for police vehicles, proper use of traffic lights and intersections. This is mostly FSM behaviors, with a lot of message passing to ensure that accidents don’t happen and some randomness to ensure that things don’t look repetitive.

Pedestrians

A game like GTA 2 has different types of pedestrians for example, one type can stop by and steal your car, other one can pass away while you are moving. Other systems use simple flocking behavior.

Enemy and Combat

That’s about adding AI bots with weapons or something to play against the player.

Nonplayer Characters

NPCs are folks that you deal with to give you information, clean your car, etc… These characters are most probably scripted.

Other competitive behavior

Adding more interesting playing elements to the game, like having bridge fall down while you are racing with the car.

Useful AI Techniques

Finite State Machines (FSMs)
Scripted Systems
Messaging System

The traffic and pedestrians mostly use this technique to communicate and coordinate their movement.

Genetic Algorithms

A genetic algorithm is used to tune car performance parameters until it reaches best outcome to be used. Most probably that is done offline.

Areas that need improvement

Other areas of interest than crime

Not everybody’s mother wants to see her kid running over a prostitute for her wallet.

More intelligent AI enemies
Persisting world

it’d be great if the whole world simulations are computed together.

Introduction to Game AI

  • It is a common mistake to think that the more complex the AI in a game, the better the characters will look to the player. Creating good AI is all about matching the right behaviors to the right algorithms
  • Knowing when to be complex and when to stay simple is the most difficult element of the game AI programmer’s art. The best AI programmers are those who can use a very simple technique to give the illusion of complexity
  • You need to make sure that a characters’ AI matches their purpose in the game and the attention they’ll get from the player
  • Perceptions should only be what exactly AI character need not more
  • Take care of changing behaviors (2 solders conversion example – 63)
  • For in-game AI, behaviorism is the way to go. We are not interested in the nature of reality or mind; we want characters that look right. In most cases, this means starting from human behaviors and trying to work out the easiest way to implement them in software
  • Developing Game AI Could Use:

    • Hacks: ad-hoc solutions and neat effects
    • Heuristics: rules of thumb that only work in most, but not all, case
    • Algorithms (the "proper" stuff)
  • Developers rarely build a great new algorithm and then ask themselves, "So what can I do with this?" Instead, you start with a design for a character and apply the most relevant tool to get the result
  • Some if the AI doesn’t require an algorithm or a technique it only requires a simple bit of code that performs an animation at the right point
  • Human beings use heuristics all the time. We don’t try to work out all the consequences of our actions. Instead, we rely on general principles that we’ve found to work in the past (or that we have been brainwashed with, equally)
  • Problems with heuristics all the time: range units when shooting peons (65)
  • Common Heuristics:

    • Most constrained

      • For example, a group of characters come across an ambush. One of the ambushers is wearing phased force-field armor. Only the new, and rare, laser rifle can penetrate it. One character has this rifle. When they select who to attack, the most constrained heuristic comes into play: it is rare to be able to attack this enemy, so that is the action that should be taken
    • Do the most difficult first

      • For example, an army has two squads with empty slots. The computer schedules the creation of five Orc warriors and a huge Stone Troll. It wants to end up with balanced squads. How should it assign the units to squads? The Stone Troll is the hardest to assign, so it should be done first. If the Orcs were assigned first, they would be balanced between the two squads, leaving room for half a Troll in each squad, but nowhere for the Troll to go
    • Try the most promising first:
  • Hacks and heuristics will get you a long way, but relying on them solely means you’ll have to constantly reinvent the wheel. General bits of AI, such as movement, decision making, and tactical thinking, all benefit from tried and tested methods that can be endlessly reused (use algorithms here)
  • Just remember that for every situation where a complex algorithm is the best way to go, there are likely to be at least five where a simpler hack or heuristic will get the job done
  • One of the major reasons that new AI techniques don’t achieve widespread use is their processing time or memory requirements
  • Processor Issues in Game AI:

    • Complex AI that does work in games needs to be split into bite-size components that can be distributed over multiple frames. The chapter on resource management shows how to accomplish this. Applying these techniques to any AI algorithm can bring it into the realm of usability
    • SIMD:

      • Most modern CPUs have dedicated SIMD processing. SIMD (single instruction multiple data) is a parallel programming technique where a single program is applied to several items of data at the same time
      • Steering algorithms benefit from this feature
    • Multi-Core Processing and Hyper-Threading:

      • Modern processors have several execution paths active at the same time. Code is passed into the processor, dividing into several pipelines which execute in parallel. The results from each pipeline are then recombined into the final result of the original code. When the result of one pipeline depends on the result of another, this can involve backtracking and repeating a set of instructions. There is a set of algorithms on the processor that works out how and where to split the code and predicts the likely outcome of certain dependent operations; this is called branch prediction. This design of processor is called super-scalar
      • Normal threading is the process of allowing different bits of code to process at the same time. Since in a serial computer this is not possible, it is simulated by rapidly switching backward and forward between different parts of the code.
      • A multi-core processor effectively has multiple separate processing systems (each may be super-scalar in addition). Different threads can be assigned to different processor cores
    • Virtual Functions/ Indirection

      • Virtual functions add flexibility to the code but it’s very costly
  • Memory Concerns:

    • Cache:

      • If processors had to rely on the main RAM, they’d be constantly stalled waiting for data
      • All modern processors use at least one level of cache: a copy of the RAM held in the processor that can be very quickly manipulated. Cache is typically fetched in pages; a whole section of main memory is streamed to the processor. It can then be manipulated at will. When the processor has done its work, the cached memory is sent back to the main memory.
      • In my experience (author), dramatic speed ups can be achieved by making sure that all the data needed for one algorithm is kept in the same place
  • PC Constraints:

    • If the AI gets less time to work, how should it respond? It can try to perform less work. This is effectively the same as having more stupid AI and can affect the difficulty level of the game. It is probably not acceptable to your quality assurance (QA) team or publisher to have your game be dramatically easier on lower specification machines
  • Develop your AI code to be an AI Engine that could be reused
  • Try to develop tools that can generate you AI Code ( as in steering behaviors)
  • AI-Implant’s Maya module, for example, exposes complex Boolean conditions, and state machines, through graphical controls

Introduction to AI

  • What is AI?
  • Many of trivial problems ( playing Connect 4) were solved by computers but there are many things that computers aren’t good at which we find trivial: recognizing familiar faces, speaking our own language, deciding what to do next, and being creative. These are the domain of AI: trying to work out what kinds of algorithms are needed to display these properties
  • In academia, some AI researchers are motivated by philosophy: understanding the nature of thought and the nature of intelligence and building software to model how thinking might work. Some are motivated by psychology: understanding the mechanics of the human brain and mental processes. Others are motivated by engineering: building algorithms to perform human-like task. Where game developers concerns with the last motivation
  • History of Academic AI:

    • The Early Days:

      • In the early days (before computers) some questions appeared (in philosophy of mind) as:

        • What produces thought?
        • Could you give life to an inanimate object?
        • What’s the difference between cadavers (جثة) and human it previously was?
      • Pioneers of the field these days were: Alan Turing (father of AI), von-Neumann, Shannon
    • The Symbolic Era:

      • From 1950s till 1980s main thrust in AI research was in "symbolic" systems
      • A symbolic system: is one in which the algorithm is divided into two components (as Expert Systems):

        • Set of knowledge: represented as symbols such as words, numbers, sentences, or pictures
        • Reasoning algorithm: that manipulates those symbols to create new combinations of symbols that hopefully represent problem solutions or new knowledge
      • Other symbolic approaches in games: blackboard architecture, pathfinding, decision trees, state machines, steering algorithms
      • Common disadvantage of symbolic systems: when solving a problem the more knowledge you have, the less work you need to do in reasoning
      • The more knowledge you have, the less searching for an answer you need; the more search you can do (i.e., the faster you can search), the less knowledge you need
    • The Natural Era:

      • From 1980s to 1990s frustration symbolic approaches come into two categories:

        • From engineering point:

          • early success on simple problems didn’t seem to scale to more difficult problems
        • From philosophical point:

          • Symbolic approaches are not biologically plausible (i.e. You can’t understand how a human being plans a route by using a symbolic route planning algorithm)
          • The effect was a move toward natural computing: techniques inspired by biology or other natural systems (like ANN, GA and simulated annealing)
  • The no-free-lunch theorem and subsequent work has shown that, over all problems, no single approach is better than any other
  • The narrower the problem domain you focus on, the easier it will be for the algorithm to shine. Which, in a roundabout way, brings us back to the golden rule of AI: search (trying possible solutions) is the other side of the coin to knowledge (knowledge about the problem is equivalent to narrowing the number of problems your approach is applicable to)
  • Game AI:
  • Till 1990 all computer-controlled characters used FSM
  • In 1997 the new technique included was ability to see colleagues and notify them when killed
  • In mid-1990s RTS games (Warcraft II) was the first time popular game having robust pathfinding implementation
  • The AI in most modern games addresses three basic needs:

    • The ability to move characters,
    • The ability to make decisions about where to move
    • The ability to think tactically or strategically
  • Model of Game AI:

  • Movement:

    • Movement refers to algorithms that turn decisions into some kind of motion
    • Examples (49):

      • Super Mario example when attacking enemies with bullets
      • Guard that want to reach alarm example
  • Decision Making:

    • Involves character working out what to do next
    • Examples: take the decision to attack, defend, patrol…
  • Strategy:

    • To coordinate whole team you need a strategic AI
    • In the context of this book, strategy refers to an overall approach used by a group of characters
    • In this category are AI algorithms that don’t control just one character, but influence the behavior of a whole set of characters
    • Example: surrounding a player in FPS Game
  • Infrastructure:

    • These are Information Gatherer (perception) and execution management issues
  • Agent-Based-AI:

    • agent-based AI is about producing autonomous characters that take in information from the game data, determine what actions to take based on the information, and carry out those actions
  • Techniques in this book are implemented into 3 categories: Algorithms, Data Structures, Game Infrastructure
  • Key elements to know when implementing algorithms:

  • Know the problem the algorithm want to solve
  • A general description of the working mechanism of the algorithm including diagrams
  • A pseudo-code presentation of the algorithm
  • Indication to the data structure used in the algorithm
  • Particular implementation node
  • Analysis of the algorithm performance: execution speed, memory footprint and scalability
  • Weaknesses in the approach

Common AI Development Concerns

  • Designing Issues:
  • Data-Driven AI System:

    • Data-Driven primitive Levels: animations, behaviors and strategies
    • Designers could build animations themselves
    • Data-Driven system doesn’t improve AI engine but supplies its degree of organization
    • Be sure that you are not driving data for areas that are better with code solutions
    • Rule of Thumb Here:

      • Create reusable, simple primitives that allow users to build more complex objects
  • The One-Track-Mind Syndrome:

    • The problem is that AI programmer apply one AI technique on all AI problems in the game
    • Most error here: "State Machines are all you need!"
    • Every AI technique is suitable for particular input and under particular game conditions
    • You can use FSM for basic layout of the game, FuSM for main short decision layer, a simpler planner to run your pathfinding and long term decision making layer , and a scripting system to drive your animations
  • Load of Details (LOD):

    • LOD might entail (handle AI details between various levels):

      • Off-screen and faraway: characters are completely non-exist for human player
      • Off-screen and close: characters can’t be seen but the human player might still hear them
      • Very far-off: character is visible a pixel or two
      • Far-off: characters are visible as solid colors but no real details yet (you can differentiate between truck and car)
      • Medium: this distance would be your true area of sight
      • Close: anything closer than medium
      • Interaction: the character is interacting directly with the player someway
    • If characters are in off-screen faraway then we can forgot about real obstacle avoidance
    • There could be LOD systems for your engine that determines the current level of detail
    • Areas under human sight could be updated thirsty times per second and far-away area could be 3/2 times
    • Scientist example (page 647)
    • LOD in RTS Game (page 648)

      • Buildings and mining will be statistically determined (without moving peons)
  • Helper AI:

    • Some areas still benefit from AI techniques as:

      • User Interface
      • AI Advisors
      • Automated Testing Systems

        • Testing Areas:

          • Limits Testing: testing values around of system’s capabilities
          • Random Testing: uses completely random input to the system
          • Smart Testing: real-game play techniques are applied
  • General AI Thinking:

    • Determine the goals of your AI controller
    • Brainstorm about how to solve these problems
    • Talk with AI staff about each proposed solution you have got
    • Coining the solutions in a small prototype (like AIsteroids)

      • Here you have 80% of the solution the rest 20% will be discovered in the code
    • Think in fuzzy with your colleagues
  • Always differentiate between good programming and programming for sake of goodness
  • Consider novelty in your AI Engines (like MOHAA when you throw grenade on them they pick up it and throw it back)

Stupid AI could do: Rules Enemy, Bad Pathfinding, Non-Contextual Enemy, Oblivious Enemy

Steering Behaviors (SB)

  • Sometimes in games, creatures not require intelligence and you want them to behave in natural way. Here you are looking for steering behavior
  • Steering techniques tend to be low level and concerned only with which direction a character should steer (يتوجه)
  • Characters that use SB are called autonomous agents meaning that they are typically set in motion and don’t require additional help from programmer or scripted elements in order to perform within the game world
  • SB are only concerned with movement so autonomous here appears in that area only
  • Reynolds call his original creatures boids and he set up 3 simple rules that can model complex locking behavior
  • These rules are:

    • Alignment: your head should always be in the same direction with the rest of the group
    • Cohesion: force of keeping the group together; tight and focused
    • Separation:

      • Could be seen as opposite of cohesion. This gives group members "personal space bubble" so they don’t crowd each other too much and every individual has room operate
  • Emergent behaviors is something like holy grail of game programming, where combination of simple local rules lead to very complex global behaviors
  • Because every boid is behaving in local stimulus (حافز), by time this can lead to chaotic state. But negative feedback from the main controller brings the overall group back into more ordered state
  • Prediction of the next behavior is 1 minute is impossible!
  • When to combine behaviors take in account following:

    • The combination could lead to meaningless behavior
    • Some behaviors could cancel other behaviors (antagonistic behaviors)
  • Most popular combining behaviors are:

    • Simple Weighted:

      • Sum up all individuals steering forces
      • Apply a weight multiple to each force vector before adding it into running sum

        • This able you to control the effect of the steering behavior on the overall system
      • The problem here is: how to find the suitable weights that lead to balance
      • Expensive o n CPU time because this calculation is calculated every game loop
    • Prioritized Sum:

      • Behaviors are stored in prioritized list
      • When we update each one we sum the result into accumulated steering force
      • The magnitude of the incoming force is subtracted from the maximal force (set by the programmer)

        • Here when we pass the maximal amount we truncate sum and stop updating
      • Advantages:

        • Here we only update exactly the number of allowed behaviors
        • We set up the behaviors here from important (pure) to lower importance
    • Prioritized
      Dither:

      • All the given behaviors are stored in priority order
      • Each behaviors is assigned a probability value
      • When the manages goes to update behavior collection, it rolls the dice and tests against the behavior’s probability value

        • If it passes, the behavior is updated
        • If the behaviors does something (sends back a steering vector), then its ignored
      • And after that the behavior in the collection is tested
      • Advantages:

        • For accurate results a very probability will be assigned to it
  • Pros of Steering Behaviors:

    • Ease of implementation
    • Predictable
    • Inexpensive to execute on the CPU
  • Cons of Steering Behaviors:

    • Combinatorial complexity
    • Short sightedness (بعد النظر)
    • Deadlocking problems
    • Large tuning requirements
    • They look robotic is misused
    • Not great at modeling idle states
  • Extension to Paradigm:

    • Layered Steering:

      • Each steering behaviors has other system of steering
      • The layers tend to be general then specific
    • Learning Behaviors:

      • Use learning behaviors in:

        • Altering weights and probabilities of behaviors
        • Learn the agent when to use the specific behavior
      • GA was used successfully in that area
      • There are 2 papers useful in that topic:

        • Competition, Coevolution and the Game of Tag
        • Evolution of Corridor Following Behavior in a Noisy World
    • Common Steering Behaviors:

      • Approach
      • Pursuit
      • Evade
      • Arrive
      • Avoid
      • Wander
      • Purist With Offset
      • Patrol
      • Match Target Speed
      • Hide
      • Interpose
      • Orbit
      • Flow Field Following
      • Queuing
    • Data-Driven Steering Behaviors:

      • This will be grateful for game designers because with one mouse click a new behaviors will be added to your system
  • Optimizations:

    • Load Balance:

      • Update certain agents in certain loops

        • Take care here if you are using flocking groups so, all the group should be updated
      • Update agent under condition

        • Like if we have a leader and a following group, the group will not be updated only if the leader changes his state
      • Using less costly combination methods for certain percentage of time

        • In order to partially bring down CPU cost without losing all the accuracy in your game
    • Priority/Weight Adjustments:

      • Assign the highest propriety to the least expensive behaviors you have (also does work well)
      • The less cost behaviors could be checked first
  • Design Considerations:

    • Genre: preferred to be used with tactical types
    • Agent Reactivity: very reactive and able to be adjusted
    • System Realism: suitable for realism
    • Genre:

      • Genres that require emergent, organic movement from AI controlled agents
      • Genres that have groups and flocking behaviors exist
    • Development Limitations:

      • Make sure of the produced emergent behaviors by system
  • Note:

Always check that you problem is really simplified break down to the simplest behaviors you have

Distributed AI

  • The first rule of ALL game programming: Keep it Simple, Stupid
  • The purpose of the distributed method is to simplify overall AI creation and maintenance, by spreading out AI tasks into modular, as well layered systems working with each other
  • Several AI Engine Layers:

    • Perception/Event Layer: Filters incoming sense data for relevance and various other factors
    • Behavior Layer: Determines the specifics of how to perform a given action
    • Animation Layer: Determines which animation to play to fit game state
    • Motion Layer: Handling aspects like pathfinding, collisions and avoidance
    • Short-Term Decision Making Layer:

      • The narrow-view intelligence for the AI entity, primarily concerned with just the entity
    • Long-Term Decision Making Layer:

      • Handles wire-view intelligence issues, like planning or team based considerations
    • Location-Based Information Layer:

      • Includes information transmitted to the entity from influence maps, smart terrains
  • Perception and Events Layer:
  • Why to create central perception System:

    • Prevent game values being calculated several times within single game loop
    • Supports debugging and tracking the system
  • Perception systems works fine with message based systems

  • Behavior Layer:

    • This layer is a candidate for data-driven systems
    • The more content designers put in this layer, the more virtually "calculation-free" personality and intelligent your characters with exhibit
    • scripts shouldn’t contain math; it contains sense-style that characters’ behaviors requires to seem realistic
  • Animation Layer:
  • Choosing right animation to play is not a trivial task
  • Scripted systems here saves calculation time

  • Motion Layer

    • Basic movement, pathfinding and obstacle avoidance algorithms stated here
    • You can adjust this layer for every character you have:

      • Smart Character: know when to use teleport in the suitable time
      • Weak Character: let the obstacle pass first and then he passes
      • Strong Character: move the obstacle away the way!
  • Short-Term Decision Making:

    • This layer is relative to character either because of its attributes, its current perceptions or its last experience
    • A character might be almost dead so his goal now is to get health power up or run away
    • A character’s weapon is empty so, its goal now is to hide and reload the weapon and appear again
    • Most of the games develop the ST layer in state-based manner
  • Long-Term Decision Making:

    • LT are likely to be outside any one unit
    • In RTS games this layer usually developed under FuSM
    • This layer contain the planning algorithms and high strategic decisions
    • In RTS games, AI opponent can use full fuzzy system logic to "guess best" action to take under current info
  • Location-Based Information Layer:

  • This layer is like blackboard architecture for creating AI Engines
  • Uses of LBI Systems:

    • LBI can help LT in determining weak defensive area
    • In knowing military intersect area in the map
    • Discovering valuable suitable ambush areas in the map
    • Pathfinding algorithm use LBI to avoid kill zones or bad designs in the map
  • Triggers could be added to this layer to help to simplify other layer (like be careful enemy is near you!)
  • Quote: "reaching for insect intelligence first, and then go on"