Simulating AI in large open world games

Development World Creation
,
1

I have been thinking how AI is simulated in large open world games. Please note I have no idea what I’m talking about, and I just want to learn about it.

In most “simple” games AI is only relevelant when you have something to kill. AI is then only reponsible for presenting challenge to you, by means of acoiding being killed. That is simple enough to understrand.

What I’m curious about how AI is approached in games where NPCs might have indirect effect on what player can see.

For example somewhere in the world there is caravan going, and if it will go unaffected it will eventually cross path with player, who stand on it’s path. But if for example caravan will be attacked by bandits, player might never meet it, because it has been already destroyed. Instead player might only find remains of it.

What is really giving me head caches on it, is not designing AI to do it (with Behavior Trees it should be easy enough to get something basic going), but how to manage world around it.

Assuming we have more than average playing area (4km x 4km), there is going to be a lot of content. From what I understrand, to have AI really affect world around we would need to have all this content loaded at all times, which not really option, it will tank performance.

Another idea that occurred to me, that we could probably store simplified presentation of world at all times (nav meshes, AI paths, etc.) and on that is loaded at all times, and we stream world as needed for player. After all AI doesn’t really care how pretty it looks.

tl;dr I’m curious what are valid approaches of simulating AI in singleplayer game, over vast open world game (Skyrim size at minimum, and that is not even that big).

2

That’s the reason why active scripted mobs are very costly. You need to decide if the caravan really must be on the way, even if no player is around. Usually you will need to decide that it must not and it will be enough when it starts spawning as soon as a player comes near to the spawn point.

A third option is to have a function in the heartbeat, just calculating the actual coordinates of the caravan without spawning anything or influencing anything or being influenced by anything (or just use some randomness to simulate if it was attacked and is not there) - and spawn the caravan if a player comes near the current position for full simulation until it despawns while nobody is watching anymore. (Transportation in MMOs, like Ships, sometimes works this way, sometimes even easier by not calculating a position but just the times when the ship would be visible at one of the ports)

Modern MMO clusters balance the AI for the zones between many servers and allocate CPU power in the way it’s needed. If you can’t reduce the required overall CPU time, you have to add more computer power to the cluster.

To give you a number, usually around 20-50% (higher especially for shooter type combat systems) of the CPU power of an MMO server cluster is used only for the AI.

3

Let’s assume we have 2 villages (A and B), our caravan is leaving from A at 08:00 am and reaches B at 04:00 pm (8 hours).

Somewhere along the road there are areas where bandits operate, we already know around what time our caravan enters those areas and it’s only at those times we run the following tasks:

  • Probability of attack
  • Probability of survival (destroyed, delayed)
  • etc …
4

A good example of this approach to AI LOD is STALKER. There’s quite a bit of info about it around.

In UE4 I’d basically just set it up so that it knows its distance, the BT can determine the LOD then select a specialize tree to run that does the reduced cost calculations (e.g., no real move to, just teleporting etc.).

5

IN today’s world we actually see meshes and behavior as actual objects. In a way they actually are. But they are only relevant when the user is in the area. If you were to take your wagon that the player sees and create a instance state, then when it leaves the area (via a box) everything else is just a matter of either using time nodes or actually running the event without the pictures, yet when the player shows up along the line he is loading its instance.

With some understanding of C++ could create a small world event system that merely ran these events when triggered. Then load them as the character gets near. However if you wanted randomly generated events things could get costly on the system depending on how many you use.

Remember in game development and design less is better no matter how advanced our hardware is.

6

This is mostly a problem of how to handle concurrency well. Unfortunately most of the better tools for this are not in C++. For example I have games running tens of thousands of ai’s concurrently on the server on fairly minimal hardware using Akka (http://www.akka.io), a java framwork that uses the java fork/join framework and the actor model.

I know from working with that, that it’s very possible to have several hundred ai’s running concurrently on the client. Server side a couple hundred ai’s all running with a 30ms ‘game tick’ consume roughly 10% of a single cpu. Those ai’s were doing basic pathfinding and movement. While they were always running in terms of being sent a game tick every X ms, in between those ticks they consume no resources whatsoever outside of around 10kb of ram.

The problem is that there just aren’t any good libraries for this that are open source in C++. People generally don’t solve this problem on the server with C++, and on the client, there just hasn’t been the demand for such a thing. I did find a couple of C++ libraries for implementing the actor model, which I do feel is the right approach for this (messaging based is the key). One was Theron, the other I forget but just google C++ actor framework.

7

Concurrency is a factor however java is a big bloated pig. Anything you can do in java I can do in C or C++ with alot less overhead. The problem with game engines that come complete with tools is that if you can’t program in its native language you tend to fail at a good option when you want more (which in game development we always want more). I have come at unreal backward (apparently) being a programmer first for many years and now I have dedicated my time to learning modeling because the tools and engine are built and I don’t have to do that… Though I will tell you I am thinking about completely re-writing the terrain editor toolset.

A concurrent timeline gets crazy when you are running that many AI agents and it is difficult to manage. However with events inheriting from base classes it should be pretty simple provided your classes are written correctly and you apply your variables and functions accordingly.

Also it is important to remember that Java is completely based on C++ but it is a middle man. It runs native to the OS you are using (sort of). In C++ we tend to be a bunch of jerky elitists. Mainly because the work we do is maddening and sometimes difficult and we don’t want to share because then we have to support it LOL…

8

Java is not a bloated pig that is pure FUD. Statements like that outside of a context are meaningless. An environment where 48 cores is the norm and you can spread a problem over multiple servers, is completely different from a PC of and end user, or a gaming console. It’s about understanding the environment you are in, the problems you are solving, and using the right tool for the job.

My point was that with the right concurrency models handling many ai’s is not that difficult. It’s difficult for many game developers because it’s just a huge context switch. If you spend all your time working in engines that are single threaded and mostly linear, you will try to apply the same approaches you use there to a concurrent problem. It’s completely natural but doomed to failure.

Even on the server where concurrency is the norm, it’s taken years for frameworks and libraries to come out with good abstractions that make it fairly simple. Erlang had it all along, but then who wants to write Erlang:)

For some specifics. Take the actor model which is what I used. Actors are just blocks of code that have a method that receives a message. You can ‘tick’ them by sending them messages every few ms. Messages are immutable data. Actors don’t share state although they can contain state. So the model here is you have a bunch of actors all running at whatever clock rate you want via special ‘tick’ messages you send them. This can be done efficiently using very little cpu. If you use the right threading model you have no more then one thread per core.

Actors effect each other by sending messages that result in an actor transforming data as a result of getting the message. Generally speaking you can handle a lot of transformations using this model with very low overhead and no lock/thread contention at all.

I coupled this model with an entity/component system where an entity is just a container for component messages. My actors are the ‘systems’ and entities are the messages sent between the systems.

Overall this is a very simple system to work with and easy to reason about. You never have to deal with concurrent data structures directly. Performance is good, you can have several hundred actors and push around 25k messages per second or so and use just a small part of a single core. Actors are also lightweight and can be anywhere from 50 to 300 bytes base size depending on language, functionality, etc…

9

Just check http://actor-framework.org/ and CAF: C++ Actor Framework · GitHub

10

I think for open world and persistent AI (i hate you GTA clones for lack of it!) best is split in two poarts: near player area AI, and global AI.

For near player use unreal engine, some added factions. eg when your caravan is near robbers they will fight. Etc. that is something we have in gta and clones. But those games lack global AI. Wonder why cars in gta disappear around corner?

For global AI (this really should be called world simulation) use one of systems described above, make sure to utilize those additional cores that are in most current desktop PCs. Make some simple logic for caravan and robbers fight etc, then update statistics so local AI has some data. Then when player is near those actors spawn them in player layer AI, freeze that global ai around player. Wait for results of player intervention, update global layer directly from player level.

So this is kind of client server just done on single PC. Because you are not making MMO where cheating is serious problem, you are quite free with moving things between “server” and “client” parts of AI. Also later on you can make standalone AI server for that game so users with multiple PCs could make their own servers. And even further down the path you can make standalone persistent world server for players to cooperate. Kind of small mmo with private servers.

11

I once heard someone say “sure EverQuest has a scripting language – it’s called English!”
Apparently, the original EverQuest was very basic. Actors could be spawned, set to patrol along a path, and given a conversation tree and aggro parameters.
An actor that heard some text being said, would stop, and enter a conversation/quest tree based on key words.
Designers then started making actors occasionally say things, which other actors might pick up if they were close enough, and then they made those characters converse with each other, making semi-scripted events occur.

The moral of this story is that AI comes in a number of shapes and forms. It doesn’t have to be expensive. It doesn’t have to have specific support from an AI subsystem, even. It all depends on what your goals are.
Simple state machines are very, very cheap to run on modern CPUs. You can have tens of thousands being updated in real time with no problem, assuming you optimize the other bits that go into that – don’t run expensive physics simulation and collision when a navigation cell system is sufficient, for example.
If a player pulls/aggros a character, the state machine may switch into a more expensive mode which knows about specific collision geometry, level features, etc – but this is not needed on a tick-by-tick basis for background actors and emergent crowds.

12

Thanks everyone, I actually learned few things :smiley:

Here is Actor model in .NET:
http://blogs.msdn.com/b/dotnet/archive/2014/04/02/available-now-preview-of-project-orleans-cloud-services-at-scale.aspx

This might be interesting, especially with recent movement from MS to open source entire .NET stack.