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!

  • 2
    \$\begingroup\$ Only update enemies within a certain range and/or use some type of spatial partitioning to reduce the areas you check/update \$\endgroup\$ – wes Sep 1 '13 at 5:03
  • \$\begingroup\$ Thanks wes, I've thought about this - but wouldn't the quadrants need to overlap, since what if an enemy was at the edge of a quadrant? Or I suppose the quadrants could be smaller and I'd check surrounding quadrants as well? Hmmm... Thanks! You've given me something to think about. \$\endgroup\$ – user29049 Sep 1 '13 at 5:07
  • \$\begingroup\$ Profile the code, that's the best way to know what's slowing it down. Currently, your question it too broad. A discussion with suggestions about how you might improve it, is too open ended a question for this site. You can try chat too. \$\endgroup\$ – MichaelHouse Sep 1 '13 at 5:46
  • \$\begingroup\$ Ahh, I see. Thanks @Byte56 I'll try to be more specific in furture. While profiling the code, it cam down to the fact that for every frame, every enemy has to scan through every 'attackable' object to see whether its in its sight radius. Do you think wes was on the right track? \$\endgroup\$ – user29049 Sep 1 '13 at 5:53
  • \$\begingroup\$ Yes, there are a number of questions about such optimizations on the site. Searching for spatial partitioning will reveal a few of them. \$\endgroup\$ – MichaelHouse Sep 1 '13 at 5:57

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.

  • \$\begingroup\$ "calculate the activity in the zone which happened in the meantime using a simplified model" YES! Thank you so much, if only stack overflow had a 'tip' feature. Really appreciate the thought you put into that and the great explanation :) \$\endgroup\$ – user29049 Sep 19 '13 at 10:44
  • \$\begingroup\$ @JoeRocc Actually, there is a tip-feature. But you need more reputation to use it. \$\endgroup\$ – Philipp Sep 19 '13 at 11:01

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).

  • \$\begingroup\$ Thanks so much! This infinite world thing is looking so much more feasible now, really appreciate you help - wish I could accept all these answers. \$\endgroup\$ – user29049 Sep 19 '13 at 10:45

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.

  • 1
    \$\begingroup\$ Oh, that is neat - thanks Mick! Web Workers it is! \$\endgroup\$ – user29049 Sep 19 '13 at 10:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy