10,000 Simultaneous Enemies

[+Gemintronic]

A friend desired a method to handle over 7000+ NPCs simultaneously on a PC. Here is my idea:

 

NPCs within a 3 screen radius get full runs of their AI.

NPCs over 5 screens away get their individual stats stored and their actions are now computed in groups.

Groups out of range get computed into regions.

Regions get generalized into world health.

 

Basically, as the NPCs get farther from the players perception they get further generalized.

As they re-enter the players perception their stats are reintegrated.

The amount of change when NPCs are reintegrated depends on how much time has passed since they got direct attention.

 

In essence 4 controllers are active at one time:

1. Screen range

2. Area range

3. Region range

4. World

 

The NPCs are brought from one level to another based on their distance to player.

 

Does this sound sane? One major concern is determining migration. Path-finding a horde is not a per pixel affair but it has to seem like it.

[Rybags]

That's not such a big number for modern machines.

 

It could be done equally easily and without sacrificing stats by timeslicing. Use a similar region scheme to you already have.

 

Then e.g. update onscreen stuff 50 times/second. Near neighbour stuff 5 times/sec, further away = more seldom. So you might have 5,000 "far away" characters but only be dealing with 25-50 per iteration.

[SeaGtGruff]

I don't think even Skyrim and the other Elder Scrolls games keep track of all NPCs at all times, just the ones that are within range of your character or are "active" for some other reason. There's no need to. The ones that are "out of range"-- however you want to define that-- can be inactive, and whenever you get within range and they need to become active, just use some logic to determine where they are and what they're doing, such as based on the time of day. If you've already interacted with them before and they're supposed to be doing something for you, check how much time has elapsed so you know if they're all finished, or only halfway finished, etc.

[sack-c0s]

sounds viable.

I'd also have the enemies placed in a work queue and have several worker threads up and running to take the work from the queue and process them so you get the benefit of multicore CPUs.

[gorf68]

I think it may depend on the type of game they are writing, if it’s a modern 3D perspective game your reasoning sounds sane enough to me.

 

 

If it’s a retro or top-down maze based game however, there may be another option...

How about doing what was done on good old Dandy way back in the eighties-

E.g. use a 'game of life' style system to 'move' a set of on-screen (or off screen) enemies based on a set of rules rather than keeping individual positions for each.

 

This lets you have a lot of very fast on-screen action without having to individually x/y position-track anything apart from your player controlled character.

It also means that all the off-screen action can be just as 'inteligent' as the on-screen ones.

Edited October 22, 2012 by gorf68

[Andromeda Stardust]

How about 10,000 enemy sprites on the VCS?

 

It's something that can be accomplished with modern muscle. I was blown away while playing Paper Mario The Thousand Year Door when I went into the first dungeon in the game, and the room filled up with literally hundreds of dry-bones onscreen simultaneously. That's like 100s of 2D sprites onscreen at once, with fluid lag-free animation. One of my more impressive graphical moments on Game Cube.

 

When you said "10,000 enemy sprites," the first thing I thought of were the Orcs armies in Lord of the Rings Trilogy, but in realtime. I'd bet the PS4 or Xbox720 will be able to handle that sort of graphical load, but I'll be gaming on Wii-U because Nintendo is more fun and innovative.

[+Gemintronic]

How about 10,000 enemy sprites on the VCS?

 

It's something that can be accomplished with modern muscle. I was blown away while playing Paper Mario The Thousand Year Door when I went into the first dungeon in the game, and the room filled up with literally hundreds of dry-bones onscreen simultaneously. That's like 100s of 2D sprites onscreen at once, with fluid lag-free animation. One of my more impressive graphical moments on Game Cube.

 

When you said "10,000 enemy sprites," the first thing I thought of were the Orcs armies in Lord of the Rings Trilogy, but in realtime. I'd bet the PS4 or Xbox720 will be able to handle that sort of graphical load, but I'll be gaming on Wii-U because Nintendo is more fun and innovative.

 

I'm not sure I understand how this is feedback on my original question. Especially for the PC.

 

In any case, I don't think anyone has seen any major flaws in the general outline of how to do this. Given the acceptance of the basic premise, how does one account for collision detection of a major group? Since each level of abstraction accounts for larger and larger amounts of NPCs one must still take the pixel by pixel world map into consideration. Hmmmn..

Edited October 22, 2012 by theloon

[RevEng]

Given the acceptance of the basic premise, how does one account for collision detection of a major group? Since each level of abstraction accounts for larger and larger amounts of NPCs one must still take the pixel by pixel world map into consideration. Hmmmn..

 

You don't have to run collision detection on the larger non-visible areas. Instead you can make data structures that describe the possible paths in a screen (e.g. exits to the top, right, and bottom) as well as path costs. (e.g. route from top to right (or reverse) takes 35 units of time, route from top to bottom takes 50 units of time, ...)

 

While off-screen, an NPC uses map logic. It moves according to it's goal on the current screen, and how much time it has spent pursuing that goal.

 

When the player visits a screen with a travelling NPC, you can use a data structure that maps the NPC's goal and time to an actual screen position. (after which the live screen-by-screen NPC logic takes over)

 

The devil is in the details, of course. There are a lot of data structures to fill out for this kind of map-logic - best to make special tools to do this - but this basic idea will scale to larger and larger regions as needed.

[+Gemintronic]

That's something I should have seen. Those same rules that generate the terrain could also be used to determine navigation paths. The only complication is when weather or NPC terraforming changes things. Gotta update the navigation data for that section of land.

 

Thanks RevEng!

[GroovyBee]

For NPC's traversing weighted terrains you might want to Google "A* pathfinding".