How do AI agents access information about their environment?

Question

This might be kind of a trivial question, but I am having trouble understanding this. Would very much appreciate your help.

In game development using object oriented design, I want to understand how AI-agents access the information they need from the game world in order to perform their actions.

As we all know, in games very often AI agents need to 'perceive their environment' and act according to what is happening around them. For example, an agent might be programmed to chase the player if he/she gets close enough, avoid obstacles while moving (using the Obstacle Avoidance steering behavior), etc.

My problem is I'm not sure how to do that. How can an AI agent access the information it needs about the game world?

One possible approach is that the agents simply request the information they need directly from the game world.

There's a class called GameWorld. It handles important game logic (game loop, collision detection, etc), and also holds references to all of the entities in the game.

I could make this class a Singleton. When an agent needs information from the game world, it simply gets it directly from the GameWorld instance.

For example, an agent might be programmed to Seek the player when he/she is close. In order to do this the agent has to get the player's position. So it can simply request it directly: GameWorld.instance().getPlayerPosition().

An agent could also just get the list of all the entities in the game, and analyze it for it's needs (to figure out what entities are close by , or anything else): GameWorld.instance().getEntityList()

This is the simplest approach: agents contact the GameWorld class directly and get the information they need. However, this is the only approach I know. is there a better one?

How would an experienced game developer design this? Is the "get a list of all the entities and look for whatever you need" approach naive? What approaches and mechanisms are there to allow AI agents to access the information they need in order to perform their actions?

Answer 1

What you describe is a classic "pull" model of querying the world. Most of the time, this works pretty well, especially for games with basic AI (which is most). However, there are a couple of points you should consider that might be downsides:

• You probably want to double buffer. See game programming patterns on the subject. By always requesting the data directly from the world, you can get weird race conditions in which the outcome is dependent on which order the AI is called. Whether this is important to your game is for you to determine. One possible outcome is that it biases the game to whoever goes "first" or "last," making multiplayer unfair.

• It can often be much more efficient to batch requests, especially to certain data structures. Here you might make every AI agent that wants to search for obstacles create a "query object" and register that with a central obstacle singleton. Then, before the main AI loop, all queries are run against the data structure, which keeps the obstacle data structure more in cache. Then during the AI part, each agent processes it's query results, but isn't allowed to make any more directly. At the end of the frame, the AI objects update the queries with their new location, or add or remove them. This is similar to data oriented design.

  Note that this basically does double buffering by storing the result of the queries in a buffer. It also requires you to anticipate whether you need to do a query the frame before. This is a "push" model, because the agents declare what kind of updates they are interested in (by making a corresponding query object), and these updates are pushed to them. Note you can also have the query object contain a callback, rather than storing all the results for a frame.

• Finally, you probably want to use interfaces or components for your searchable objects rather than inheritance, which is well documented elsewhere. Iterating over a list of Entities checking instanceOf is probably a recipe for pretty fragile code, the minute you want both StaticObject and MovingObject to be Healable. (unless instanceOf works for interfaces in your language of choice.)

Answer 2

AI being costly, performance is often the driving factor in architecture.

To ease your concerns around data access models, let's consider a few different AI examples both in- and outside of the games industry, working from that which is furthest from human navigation to that which is most familiar to us.

(Each example assumes a single, global logic update.)

• A* shortest path Each AI calculates the state of the map for pathfinding purposes. A* requires that each AI already know the entire (local) environment in which it must pathfind, so we must hand it information about map obstacles and space (often a 2D boolean array). A* is a specialised form of Dijkstra's Algorithm, a shortest path open graph search algorithm; such approaches return lists representing the path, and on each step, the AI simply selects the next node in this list to step to, till it reaches its goal or recalculation is required (e.g. due to a map obstacle change). Without this knowledge, no realistic shortest path may be found. A* is why AIs in RTS games always know how to get from point A to point B -- if a path does exist. It will recalculate shortest path for every individual AI, because path validity is based on the position of those AIs that have moved (and potentially blocked certain paths) previously. The iterative process by which A* calculates cell values during pathfinding is one of mathematical convergence. One could say the end result resembles a sense of smell mixed with a sense of sight, but in all it is somewhat alien to our mindset.

• Collaborative diffusion Also found in games, this is most closely resembled by a sense of smell, based on diffusion of gases and particulates. CD solves the problem of costly re-processing found in A*: Instead, a single map state is stored, processed once per update for all AIs, and the results are then accessed by each AI in turn, for it to make its respective move. No longer is a single path (list of cells) returned by a search algorithm; rather, each AI will inspect the map after it has been processed, and move to whichever adjacent cell has the highest value. This is called hill-climbing. Nevertheless, the map processing phase must already have prior access to the map information, which here also contains the locations of all AI bodies. Hence, map references AIs, and then AIs reference the map.

• Computer vision and raycasting + shortest path In rover & drone robotics, this is becoming the norm to determine the extent of spaces which the robot navigates. This allows robots to construct a full volumetric model of their environment, just as we would by sight or even sound or touch (for the blind or deaf), which the robot may then reduce to a minimal topographical graph (a bit like a waypoint graph used in games with A*), upon which shortest-path algorithms may then be applied. In this instance, while "vision" may provide a clue to the immediate environment, it still results in a graph search that ultimately provides the path-to-goal. This is close to human thought: In order to reach the kitchen from the bedroom, I must pass through the living room. The fact that I have already seen them and know their spaces and their portals, is what enables this calculated move. This is a graph topology, to which a shortest path algorithm is applied, albeit embedded in soft protein rather than hard silicon.

So you can see that the first two are reliant on already knowing the environment in it's entirety. This, for reasons of the cost of evaluating an environment from scratch, is common in games. Clearly, the last is most powerful. A robot equipped this way (or for example, a game AI that reads the depth buffer each frame) could navigate sufficiently in any environment without prior knowledge of it. As you probably guessed, it is also by far the most costly of the above three approaches, and in games we typically cannot afford to do this on a per-AI basis. Of course, it is far less costly in 2D than 3D.

Architectural points

It becomes clear above that we can't assume just one correct data access pattern for AI; the choice depends on what you're trying to achieve. Accessing the GameWorld class directly is absolutely standard: it simply provides you with world information. Essentially it is your data model, and that's what data models are for. Singleton is fine for this.

"get a list of all the entities and look for whatever you need"

Nothing naive about that, at all. The only thing that might be naive is performing more list iterations than you need to. In collision detection, we avoid this by using e.g. quadtrees to reduce the search space. Similar mechanisms can apply to AI. And if you can share the same loop to do multiple things, do so, because branches are costly.

Answer 3

Basically I'd have 2 ways of querying info.

1. when the AIState changes because you detected a collision or whatever cache a reference to whatever object is important. That way you know what reference you need. When have other systems having to run large searches every frame i'd recommend piggy backing off them so you don't have to perform multiple searches. So 'collision' detected with the zone that makes an enemy 'alert' send him a message / event that registers him with that object if he isn't already and change the game state to one that has him do his business based on being in that gamestate. You need an event of some type that tells you to make changes, I'd just pass a reference into whatever callback you use to give that information. This is more extensible then just having to deal with the player. Maybe you want an enemy to pursue another enemy or some other object. This way you only need to change whatever tag you identify it by.

2. With that information you will then perform a query to a path finding system that uses A* or some other algorithm to give you a path or you can use it with some steering behaviour. Maybe a combination of both or whatever. Basically with the transform of both you should be able to query your node system or navmesh and have it give you a path. Your gameworld likely has many things other then pathfinding. I'd submit your query to pathfinding only. Also batching these things is probably best if you have many queries because this can get pretty intensive and batching will help performance.

   Transform* targetTransform = nullptr;
   EnemyAIState  AIState = EnemyAIState::Idle;
   void OnTriggerEnter(GameObject* go)
   {
      if(go->hasTag(TAG_PLAYER))
      {
      //Cache important information that will be needed during pursuit
      targetTransform = go->getComponent<Transform>();
      AIState = EnemyAIState::Pursue;
      }
   }
   
   void Update()
   {
      switch(AIState)
      {
         case EnemyAIState::Pursue:
          //Find position to move to
          Vector3 nextNode = PathSystem::Seek(
                             transform->position,targetTransform->position);
          /*Update the position towards the target by whatever speed the unit moves
            Depending on how robust your path system is you might want to raycast
            against obstacles it can't take into account or might clip the path.*/
           transform->Move((nextNode - transform->position).unitVector()*speed*Time::deltaTime());
           break;
       }
    }