Simulating a large number of game entities

Denzil

So here is my current situation. In my zombie game, I want many many many zombies (or other game entities, human AI, etc) - 1000's. At the moment I can probably have near to a 1000 in the player's immediate area, and it runs smoothly (provided that they aren't mixed too equally. Say half zombies/ half humans - that doesn't run too smoothly as there is too much interaction). So I am happy with that. Now, however, I want to go a step further.

The world is rather large and I want these entities to be all over. This is the case at the moment, but as I said previously, only entities local (in a screen or two's range) of the player is processed - the others just stand there and do nothing until the player comes close enough. This causes some issues. One would be that zombies spawn in great numbers at midnight, and during the day their numbers should die down (at the moment this is a "natural process" of their health just ticking down during the day). However, the far away zombies are not processed so when you enter a new area you may be surprised to find up to 5000 zombies. This is both impossible to play :P and laggy. (I knew this would be the case at the time of implementing it like this).

So, I wanted to implement a sort of global processing queue to process the far away entities, based on some priority system. Thinking back, this is probably still a bad idea. The world should easily contain up to 50 000 entities in this scenario, and without testing, I am guessing that the global processor would just be too inefficient (it would maybe only be able to process 500 or so entities per frame). The idea was to have it run a simulation of the other entities as closely as possible, and this would surely break that rule.

I realize that however, that the point is not to be "accurate", but to be fun, and perhaps too fool the player as far as possible. Key entities (such as an AI-survivor side-kick type character), may be simulated in a very "fake" way. Certain random events can occur (such as "DIE"), and the only place zombie entities should be spawned is in the local area around the player.

Does this last idea sound better than the first? Sorry for the horribly long post, I just thought it would be interesting to hear how other games/devs do it or would do it. There's certainly enough talent and experience lying around here :P

Elyaradine

Just some silly suggestions from someone who has no idea what he's talking about, before he leaves on holiday. :D

Similar to the graph theory stuff, I guess, but you could group the zombies in such a way that you're running the sim in increasing detail the closer you are to a zombie/group of zombies. Zombies far away would be simulated together. (i.e., run a sim once, and all the other zombies are given the same properties. They don't even need to exist; when the player comes close enough, out of view the rest of the zombies get spawned.)

Also, your zombies can be nothing but nulls/points in space until further properties are needed. So you're not rendering them, and you're not simulating any properties that you don't need, until you're close enough for them to matter.

Denzil

@Elyaradine yeah thanks. I'm thinking the way to do them at the moment is for them to not exist as you say (except for if it is like a key entity, a boss or something). It's a 2D game as well so it is much simpler for me to just not render off screen entities (there is a pretty clear boundary where the entities should be visible or not!)

you could group the zombies in such a way that you're running the sim in increasing detail the closer you are to a zombie/group of zombies

This is an interesting idea. So far I sort of "group" them together by area. But I think I can possibly do this differently. I'll keep thinking of a good way to implement this. Combined with limiting far away entities (and "fooling" the player in thinking they are actually there), this may be a great way of achieving the results I want!

Thanks a lot :D

mattbenic

Cheat! Remember, the most optimal code is code you never have to run, and there's never a reason really spawn 50000 of anything the player will probably never see and run it's update loop-even a simplified version.

So split up your world as @Elyaradine suggested and rather than bothering actually spawning and destroying them, run a simple calculation when the player enters an area. For example, if say a given number of zombies should spawn every night and a random percentage within a range of them should survive in the day, then when your player enters an area after a certain number of days you can just do something like:

int zombiesToSpawn = Math.Min(maxZombiesPerArea, (zombiesPerNight * daysSinceLastVisit)) * rand(minZombieSurvival, maxZombieSurvival);
SpawnZombies(zombiesToSpawn);

You could maybe keep areas adjacent to where your player is now actually updating "properly" in that they do a minor update on zombies in them, so if a player moves back and forth between two areas he doesn't catch on to the random spawning, but only needing to do that on the few areas he can move to directly will already drop your calcs drastically.

Denzil

@mattbenic yeah this sounds brilliant! I feel much more confident that this is the way to go :) I think I will put up a prototype soon. There is not too much yet in terms of game-play, and it's far from polished, but maybe you guys want to run away from badly drawn zombies in darkness with pixelated torch-light :)

shelton

So you said you wanted to spawn game entities. Do you have a reason to spawn entities that aren't in a position to interact with the player. What I mean is maybe you want a rival who could develop relative to you(not sure if that's applicable in a zombie game) but unlike the pokemon games(shameless namedrop) you want it to be different each time that could work. But its just zombies. Survive: kill and feed is their priority and they just have a purpose to interact with the player.
I confess I'm no expert I'm just throwing myself mentally into your world. Hope it helps

Denzil

@shelton yeah, that is my final conclusion. The main reason I wanted to spawn far away entities, was because there will be survivors in game. You will rescue them, and may leave them in your base or send them on a quest, while you, yourself, is running around elsewhere. So I wanted them to still be able to interact with zombies so they may get infected or die or whatever.

However, I have decided that the interaction itself is not so important anymore, and I can just throw random events (sorta like pulling a random card from a deck), and have that happen to the survivor. I might random a number each frame, and based on that number I may kill the survivor, etc. As long as it is off screen, and far away enough from the player, it will not truly make a difference to the player if the event actually played out or not.

shelton

@Denzil interesting I like where you headed with that situation now

P. S. Why is a random card never a joker. I remember in stats when they they taught probability a deck always has 52 cards but I know it has an additional 2 jokers. I asked the lecturer why not use the full 54 card deck with the argument that cutting the 2cards out makes it the subset. Answer is always we don't use jokers. Whatever

Goodluck with your game man

Denzil

Lol, I guess adding a joker makes the example more complex, as there isn't one for every suit (and some people in your class are struggling to follow already, so why confuse them even more :P).

Thanks, I will post an early prototype soon!

shelton

Interesting point.
Looling forward to it

Denzil

Hmm, I've given more thought to this and I'm basically at the point where I will work on implementing this. At the moment my world is divided up with an array and about 16x16 tiles. Whenever I process entities, I only process those that are in a 3x3 area around the player.

This ensures that the player will never see areas that aren't being processed. However, funny things may still happen with the AI that are off-screen. If an AI entity leaves the processable area, he will essentially freeze. This could cause some entities to pile up at the edges, or frozen entities could be attacked without having the ability to retaliate or escape (if the attacker stays in the processable region).

Is this something that you guys think I should even consider? Maybe this behaviour won't really be noticed. But I could perhaps restructure the way I process my entities, and maintain a single list of active entities (and then just keep them below a specified limit to prevent lag).

Any thoughts?

Karuji

A little hack is that when you change from processing enemies to not you move it to a random x,y in it's tile.

Rigormortis

@Denzil,

Basically anything outside the 3x3 player world essentially doesn't exist(from a player's perspective). So my suggestion is to keep a list of the number of entites you want the player to experience in his 3x3 tile world. Then as soon as an entity "falls" off of this 3x3 world you move it to somewhere inside the 3x3 world instead of destroying it and recreating another one later. This results in no entities around the map to process and an ever growing entity population in the player's proximity, simulating a growing entity population on the entire map.

Denzil

@Karuji I could do something like this, although I think I will go for Rigormortis's suggestion first. So basically I just force the simulated entities to stay inside?

I could always extend this in interesting way that may allow special entities to leave the area (and be processed by semi-randomly triggered events instead of "accurate" simulation). By special entities I mean important AI such as a boss zombie or important survivor AI.