Optimisations for large number of moving object collisions, input please!

Newbie & Debugging Questions
#1

Hi again guys,

Rapid development is an amazing thing, but often I find that it’s easy to get ahead of yourself and glaze over what could potentially become bigger problems in future. Which is why I’d like some fellow developer input on this one :slight_smile:

Here’s a screen-grab of a WIP project:

This game is intended have a large number of enemies on the level (not necessarily the screen) at any one time (~300).

From my tests, it seems that the overall game logic time hits about 10ms at the 120 enemy mark. I want to know if my approach is correct, and what optimisations I could possibly make.

Bear in mind that I know I could just stop calculating enemy positions and movement when they’re off screen - but because they spawn from specific locations, it’d be silly to have them spawn and not move anywhere until they’re closer to the player. It’d look like they’ve all just suddenly spawned when the game starts processing their logic.

Here’s my current process:

Every game tick:

  1. Cycle through each map tile, calculate the potential collision with the player and the environment (i.e. walls).

  2. Within each of these discrete per-tile calls, I cycle through the whole ArrayList of enemies, and once again check whether or not they either collide with that wall - or with the player - and respond accordingly.

So essentially, it’s a loop within a loop. The pseudo-code loop structure looks a bit like this:


int tileIndex = 0;

for (int y = 0; y < GAME_HEIGHT_IN_TILES; y++)
{
    for (int x = 0; x < GAME_WIDTH_IN_TILES; x++)
    {
        // get a reference to this tile
        Tile t = tileMap[y][x];

        // is this an obstacle?
        if (!t.walkable)
        {
            checkPlayerCollisionWithTile(t);

            // run through the enemy arraylist and check their potential to collide with both this obstacle and the player
            for (Enemy e : enemyList)
            {
                checkEnemyCollisionWithPlayer();
                checkEnemyCollisionWithTile(t);
            }
        }

        tileIndex++;

    }
}

This method feels, I don’t know, a bit ugly I guess. It seems to work perfectly in practice, and to be honest if I wasn’t having so many enemies trackable in the game simultaneously - I may have just conceded this as a hackish method of calculating multiple collision events and pushed on with the rest of the game.

Maybe this is the only tangible way of approaching this problem? After all, each enemy still needs to be tracked off screen and their collisions with the environment honoured, so can I ever escape this?

I’m not a professional game developer, though, and I’m all for learning new tricks and optimisations for these types of scenarios, so I’d be most grateful for some input from fellow developers on this approach.

EDIT: Updated the rather annoying lack of tabs on my code block!

#2

I’m not a developer, but my advice would be to limit the amount of entities (Creatures) for which you’ll have to check the logic for. I don’t mean have fewer enemies per level, rather have a separate list for enemies within some bounds for which movement matters.

Say, if you’ve got rooms, only have enemies within the current “room” and adjacent rooms perform logic. Distance can also work. Either way, every update you check your list of enemies for the criteria (And hopefully the checks are faster than the collision logic ends up being), and add those that pass to an ‘enemiesThatMatter’ list. That list is what collisions are checked against. Further, since you probably don’t need all of your enemies moving at the same time, only update those who met the criteria. It’ll hopefully help keep the processing time to a minimum.

#3

It’s definitely a step in the right direction. I have considered this distance vs. importance approach, but the problem I have is in the way the enemies need their off-screen behaviour to be processed.

Here’s a better explanation of my problem:

In the above image, the player only occupies a small part of the level. However, in order to make the level feel ‘populated’, there are enemy spawners placed in strategic locations. During the normal course of gameplay, the spawners regularly generate enemies that have some generic wandering AI to keep them ambling around.

By the time you reach the other areas of the level, there’s already a good spread of enemies around - all of which have had time to move around a bit and such, whilst respecting the need to collide with the scenery and respond accordingly.

Since there are no enemies instantiated on level start, discounting the spawn or calculation of enemies off-screen would result in the player reaching those zones, only to discover all the enemies crowded around the spawn point (after which they’d start moving / getting processed).

Perhaps it’s just a case of limiting the number of potential enemies so that it doesn’t impact too harshly?

#4

I’d just keep track of where each entity is and then on every tick loop through the list with entities and ask them to perform their move logic. This way you only need 1 loop. So just store the entities (x,y) coords with them and when they move they should just ask the map if where the plan on moving is a valid position.

That way you’ll only have one loop that loops through ~300 objects, instead of loops that run through WIDTHHEIGHTEntities. :slight_smile:

#5

Yes, I think I can see what you’re getting at. I’m not sure why I’m looping through every single tile, actually. Perhaps there was something else going on before that I was trying to catch wind of.

I’ll change over the logic processing to a more ‘necessary-only’ form, which focuses on just the entities, rather than the whole environment.

Thanks for the input, guys!

#6

One small addition. I don’t use extended for-loops or whatever its called inside the main game loop because each time an iterator object gets created in the background. When using ArrayList index access is better.

#7

Doesn’t the iteration get destroyed once the calling method ends? I thought they were treated as local variables, and as such are garbage-collected immediately on completion of the method within which the for loop resides?

#8

Yes, but I hate (easily) avoidable garbage :wink:

#9

Fair enough, it’s all a matter of preference I guess!

#10

Update:

Thanks for the suggestions, I’ve changed the way the game loop handles all movement tracking / collision reponses.

Now, rather than iterating through the entire level grid, I just run through the ‘collidable’ tile arraylist (which, to be fair, are all I need to track), and update check collisions for each enemy object against both this tile and the player simultaneously in the same function call. I also check the player’s collision state against this tile.

The pseudo-code now looks something like this:


for (Tile t : wallTiles)
{
    checkPlayerCollisionWithTile(t);
    
    for (Enemy e : enemyList)
    {
        e.checkTileAndPlayerCollision(player, t);
    }
}

How does this stack up? Well, as per my original post - I was getting about a 12ms logic processing cycle when about 120 or so enemies were in the level (whether on screen or not). Now, I can get all 300 on with the same logic processing time - that’s about a 60% reduction in CPU process time!

Although I was intially disappointed by the lack of developer interaction on this forum - it’s really starting to show its colours now. It seems like a great, knowledgeable community!

Thanks guys!

#11

You can still discard one more loop.

  • Only iterate through your enemies.
  • For each enemy identify its tile.
  • Directly look up the nature of the tile using some kind of map and do the collision check.

(same once for the player)

#12

Thanks, this will no doubt be invaluable information.

I do store the tileX and tileY values for both the enemies and the player, in order to render everything in the correct order when the level tiles are drawn.

Using your method, I could simply iterate through the enemies array, and for each case look at the direction it’s travelling in (I’m fortunate that they can only move in the four main compass directions), and analyse the tile directly to the right of them, and determine whether it’s walkable or not - and just do a single check.

This way, the collision loop for the enemies is just O(n), keeping it clean and simple. The player can be given the same check, but is obviously a single entity - and therefore immune from the loop entirely, really.

It’s an enlightening concept, I should have thought of this before - but you know how it is when you spend too long looking at a problem!

Thanks for this, I really appreciate it. +1 for taking the time to reply.

#13

Isn’t that exactly what I said to begin with? :wink:

#14

Do spawners have a maximum number of enemies? Like, there can only be X number of enemies spawned by them at any given time? Does their movement logic keep them from moving outside of some distance from the spawner (Prior to seeing the player).

If so, you can use that fact to help limit the number of creature computations. Say, you only process enemies if they’re within some distance R from the player. R is the range of movement for enemies around the spawner (Without following the player). Then, there is a distance R + R that will cause a requirement for enemies to populate the map. What this means is that when you move to R + R, you figure out how many enemies should have been spawned so far, then randomly place them within the radius of R. But you don’t start processing their AIs. When you you get < R from them, then you start processing them. Ideally, R will be greater than your view port size. Enough so that you won’t notice that they’re not moving when you’re out of range.

So, at time steps (IF the player has moved), you check distance from spawners. If they’re outside of R + R, you ignore them. If they're outside of R, but inside R + R, you check whether a spawn should happen, and place it randomly within R`. If they’re inside of R, you treat them as if they were close enough to see them.

Then, you check enemies. If they’re outside Y, they “sleep”, if they’re inside R, you process them.

In this diagram (Which I took from your earlier post and edited), shows the different cases. The Green spawner is active inside of Y. The Blue Spawners are inside of R + R. The Yellow one is outside of R+R. Green enemies are inside of R, and therefore moving, and Blue ones are outside of R, and therefore sleeping. You’d have to check every enemy/spawn area, each tick for distance, but it seems like it’d be better than applying logic and collision detection.

#15

Why not work out the tile each player and enemies are on, and then check if that tile is solid and if so then react?


int tileX = player.getX()/tile.getWidth()
int tileY = player.getY()/tile.getHeight()

To make it more accurate check four points around the player or even more e.g. top right point


int tileX = player.getX()+player.getWidth()/tile.getWidth()
int tileY = player.getY()/tile.getHeight()

and do the same with baddies, think it might take less loops than your code as…
If you have a map size of 300x300 and 100 baddies
100 solid tiles
100x100x100 = 1x10^6
where if only 4 loops are needed to check the corners of each baddie/player
4x100 = 400… and some extra math

#16

I really like this idea. I guess in layman’s terms, it’s just a case of keeping a count running for each mob spawner as to how many mobs should have spawned at that time period, and when the player is within a certain threshold of the spawner - create the relevant number of mobs scattered around the radius of the spawner.

There could be an issue with the fact that the player could potentially reach each of these spawners, kicking off their ‘spawn’ functions - thereby creating a list of trackable mobs which then needs to be considered regardless of whether or not they’re in view.

However, using your logic, I could just scatter them randomly if the player has moved far enough away before coming back (thereby setting them all temporarily dormant and waiting for the player to encroach back on the radius, at which point they’ll just take new positions).

Some interesting food for thought here, thanks.

#17

I’ve actually written a new, similar optimisation for my code that only actively processes tiles within a certain radius of the player.

Previously, I was looping through the whole grid in an O(nn) fashion, which was really a big waste of time. Now, I just take the player’s current tile grid reference (x / y), and run through a similar O(nn) loop - but constrained to the bounds of the local screen area instead. Only the local bounds get check (for anything) now.

I’m going to combine your input on this with UprightPath’s method to restrict processing to the local region only. It’s clear that there are ways around the ‘what’s happening offscreen?’ problem that don’t involve spamming unecessary collision detection routines.

Thanks again for your help. I’m learning a lot about this (clearly well grounded) area of game development.