Ways to make my game world bigger without slowing users CPU

Question

I've been developing my first game for a little while now, but I've found that I want to make the game world MUCH bigger. It's currently about 300*300 tiles, but has creatures and bad guys running around the whole thing, so I've got to keep track of all the enemies movement and hostile-finding algorithms.

I'm wondering how I can scale something like this up? It seems (from code profiling) that enemies are the limiting factor, and it's mainly that for each enemy, I need to scan through all the player-units and creatures to see if they're close enough for the enemies to see/attack.

Edit: W,S,A,D,B,Q, if anyone's interested in controls :)

Edit 2: Please tell me if there's any way I could improve the question!

Answer 1

Just ignore any actors which are far away from the player(s). Don't update them and don't allow active actors to interact with them.

Most games divide the game world into zones, and only update the actors in the zones the player is in and the adjacent zones. Many even despawn the actors and respawn them at their initial positions when the zone becomes active again to save memory.

When it is important for your game concept that certain actors do things while the player is away (for most games it is not), you could freeze the action in inactive zones, and when the player comes near calculate the activity in the zone which happened in the meantime using a simplified model. When you have, for example, an RPG with a blacksmith NPC who makes swords by automatically collecting resources and bringing them to his forge, the simplified model would not do the routefinding but just use an estimation how many swords he would have made during the time the player was away, remove the required resources from the surrounding and give him that number of swords.

When you have actors which travel around the whole game world and you want them to keep doing that even when the player isn't close (like in Oblivion or Skyrim), you could strongly simplify the route-finding while the player is away. When you know by experience that traveling from town A to town B takes about 20 minutes, you can treat this as a single step with a cost of 20 minutes in your route-finding system. When the player now suddenly enters the area between town A and town B, and the NPC left town A 15 minutes ago, you would calculate the actual path and spawn the NPC on 3/4 of its way towards town B.

Answer 2

You could also do something similar to MineCraft so only the active blocks are loaded. For doing that, you could store each part (e. g. 32x32 tiles) in its own file and load always only the part the player is in and the surrounding. When the player enters another part, save the parts the player is two far away and load the new ones. If you use procedural generated terrain, it wouldn't be too complicated to create endless worlds without using too much CPU (of course, the game may lag short when the new map parts are loaded).

Answer 3

As everyone has already stated, Spatial Partitioning! I think a bare minimal 2D Grid vs. Bounding Sphere will cut it for most browser games.

Since nearly everyone has multiple processors, your game might benefit greatly from Web Workers.

This way you can let the main browser thread focus on providing a perfectly responsive interface at all times. Further, to combat the artifacts caused by updating entities at a lower FPS, you can calculate velocities in your AI update, and then predict positions every render frame.