Sign in to follow this  
Miloslav ?

Open world RPG - how to efficiently simulate the whole world?

Recommended Posts

Miloslav ?    132

I recently started programming a 2D RPG and my goal is to have an open world with hundreds of NPCs, very much like in TES games like Skyrim. The idea for the world is to be a classic 2D tile grid, about 2000 x 2000 tiles, and the NPCs should behave acoording to AI scripts that each of them will have assigned - I basically imagine each NPC having an AI script for different events, like for example "being attacked" or "ceratin amount of time has passed" etc, on which the script will be run. I naturally came to a problem of how to implement the game engine that could simulate the whole game world in real-time.

 

Problem 1: How do I design the engine to be able to run the AI scripts of all the hundreds of NPCs in the game at once? I know that some open world games, like GTA, only update the NPCs that are in the player's close area. However I cannot do this, I need my world to work independently on where the player is, the events need to be happening even when the player isn't around, like in Skyrim. So I need to run every NPCs AI script plus I need to compute all the interactions of the NPCs with their environment, such as detecting colissions, have them fighting each other etc. But I have a feeling that this would be very bad for performance - I would like to know how games like Skyrim deal with this. My guess is that they use real-time detailed simulation for NPCs that are in the player's close area and they handle all other NPCs in the world only once in a while, i.e. once every nth "game frames", plus they may use some simplifications of the "NPC - environment" interactions (like teleporting NPCs instantly instead of having them really travel step by step with colission detections etc.). These are only my guesses and I don't really know how to make the simplifications, or whether I can use them. I would love to know how this is actually done.

 

Problem 2: Do I need to have the whole world plus all the interior instances loaded in memory at once? I would like to only load one small part of the world where the player currently is in order to save memory, as having 2000 x 2000 tiles plus all the NPCs, objects and items loaded can take a lot of space. However I cannot do this, because, as I mentioned above, I need to be simulating the whole world constantly, so I am forced to have it all loaded in memory. Again, I would like to know how Skyrim does it, because it obviously cannot be all loaded at one time, at least not with all the details.

 

I've been searching for answers to these questions for a few days now and I cannot find them, so I would be very glad if any game developer or anyone who might know the solutions would give me at least the basic ideas of how these problems could be dealt with. Thank you very much :)

 

Technical details: I'm currently using Python with Pygame and Numpy, but I could switch to C++ later if performance shows to be an issue.

Share this post


Link to post
Share on other sites
Norman Barrows    7179


the events need to be happening even when the player isn't around, like in Skyrim.

 

i don't think skyrim does this.

 

can you give an example of what you mean? I'm pretty familiar with skyrim - odds are its faking what you think its doing. give me an example, and i might be able to tell you how they do it (or fake it).

Share this post


Link to post
Share on other sites
ferrous    6139

An example of abstractions might be having two factions, each with different strength amounts.  You could then spawn random battle locations across their borders, each with a timer on it.  If the player gets near one before it's resolved, then go about spawning actual units at various healths whacking away at each other.  If the player never sees it, then just resolve the battle via some basic dice off.  (str+ random >= str2+random2), and shift the strengths and borders of the two factions based on that result.  Super cheap to compute when the player isn't there, since it's just timers and some basic math, but if the player gets near, it's a cool experience for them.

 

(There are some gotchas of course, as what happens when the player leaves the area of a battle, then comes back?  Games usually either autoresolve/recompute the strength of the two sides as the player leaves, or tries to keep a couple of the battles the player has visited as nearer full sim.  Basically, the simulations end up having an LoD of sorts.)

Edited by ferrous

Share this post


Link to post
Share on other sites
Miloslav ?    132

Okay, thank you guys, I've read through your comments smile.png I've been thinking about this yesterday before I fell asleep and I think I finally came to understanding all of this as it corresponds with what you wrote here. I guess it has a lot to do with Skyrim's Radiant AI, which in my mind works like this:

 

Besides having some AI scripts written in Turing-complete language that may be slower to interpret, NPCs have some kind of "daily plan" that consists of places they visit during the day time, i.e. at 6:00 they go to work, at 12:00 they go to pub to have a lunch for 1 hour etc. Furthermore there is an active area of the world which is the player's close area, where NPCs do stuff (AI scripts plus their "daily plan") in detailed way, that means with animations, colission detection, so the player can see them actually doing things. Out of this active area, i.e. the rest of the world, the NPCs are executing their "daily plan" very simply by just having states saying "at work", "at pub", so they are kind of being teleported instantly between these places (as you said), which is very easy to do. The question is how to handle if for example the NPC is in the inactive part of the world and it wants to

travel to the active area, i.e. where the player is. This can be solved by teleporting the NPC to the border of the active area and then start the detailed simulation for it. The thing that's left is how to deal with player moving around the world, which is also easy to solve. When the player moves near the border of the active area, in Skyrim that may be the active world cell, a new active area (cell) is loaded and at the moment that happens everything is recomputed so that the NPCs in the new active area are being simulated via detailed simulation etc. Each NPC's position can be calculated as for each NPC we have the information that says "I've been on my way to point [x,y] since time T".

 

So the point for me is that not all NPC behavior is done with AI scripts in general programming language. Instead there is this "daily plan" that can be executed even without the world being loaded all at once. The AI scripts are there for NPCs that closely interact with the player. It may be a bit more complicated in Skyrim but I think this is the basic idea.

 

Plus there are the battles, as some of you mentioned, that can be resolved randomly etc. Anyway, I think I got the point, thank you all smile.png

 

First thing first, if this is your first foray into developing a game, you'e really biting off more than you can chew.  Even if it's your second, third, or fourth foray, you're still likely biting off more than you can chew.

 

I am aware that this is pretty much the seconds most difficult kind of game to develop (first being an MMORPG)... I've made a reasonably complex game already and I've been studying computer science for 5 years now, so I know it will probably never be what I imagine it could be... it's just my spare time hobby and it gives me a lot of experience smile.png

Edited by tastyfish

Share this post


Link to post
Share on other sites
conq    735

A better example of this is X3. That game simulates thousands of NPC's each with a specific job, and stay persistant until decomissioned or destroyed.

 

They accomplish it similar to how Sean described Skyrim above, and also by tricking the user into thinking what's going on is really happening. Basically it calculates schedules etc, and determines when certain occurences may happen. For example, "If this trader isn't bothered for 10 minutes he should make it to this location".

 

It then stores the sectors/areas relevant to what will happen. As the player goes around sectors, the game determines what should be happening in that sector, and starts simulating it "for real". The neat thing about X3 is you can check a galaxy map at any time, and view any point in the universe. However, when you do this, there's a delay before unit icons etc load up. That's when the game is deciding what should be happening at that time.

 

Of course, while players are out of that area, calculations are very simplified (No collision checks, weapons hit 100% of the time, only x, y calculated instead of Z as well).

Share this post


Link to post
Share on other sites
coremarq    528
Another thing i didnt notice being said already... forget the idea of doing it all at once. Split your update so that a percentage of your objects are updated. Then the next iteration of update updates the next percentage.

You could use a spatial partioning system to divy up yoir objects and have the ones closer updated more frequently and the ones further away less frequently. Aslong as eberything is based on the time passed since last update it should be quite feasable.

Your system will stay far more responsive this way and if the updates are happening readily enough, youll never notice that theyre done in stages. As others have said its about making the user believe its working.

Sometime programming is like performing magic ;)

Share this post


Link to post
Share on other sites
CC Ricers    1491

I'm making an RPG as well, and what I'm planning to do is have various friendly/neutral NPCs traveling around the overworld, some by themselves and some in groups. This will give the feel that you're not the only adventuring warrior in the world.

 

I think it's possible to make NPCs appear as if they were killed or injured from fighting some enemy even if they go out of view for a long time and were expected to join up with you in the same destination. Just simulate a "dice roll" that can say whether this NPC lost none, some or all of its health before deciding to render it. If the NPC was killed, re-spawn it by re-setting its location to some random point along its pre-determined path and store it for later use.

Share this post


Link to post
Share on other sites
markr    1692

I'm going to reply and reiterate a very old maxim - premature optimisation is the root of all evil.

 

Your goal *may* be to make the "open world RPG" with 2000 NPCs and a zillion zones, etc,

 

But you might be overestimating the amount of content that you can reasonably create. You might subsequently change the scope of the game to be a bit ... smaller.

 

So don't do anything. Make a few NPCs work in a small world, and once you're happy with that, then you can expand it as you have additional content.

 

After all, a game with 2000 NPCs and a zillion zones, is really BORING if you don't have varied, detailed content to go with it.

Share this post


Link to post
Share on other sites
SirFroweey    126

Great job using PyGame! While C++ is faster, it isn't as easy to pick up and make games as it is in Python/PyGame. That being said, I'm developing a 2D game framework on-top of PyGame that employs a bunch of optimization techniques and trips to max out performance. Furthermore, my framework comes built-in with online multiplayer networking code via Twisted. If this seems like a fit for you, you're more than welcomed to join my frameworks community at www.pydark.com

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this