chrismingay.co.uk Me and my games

Objects Interacting With Objects : Part 2 : Optimising

In part one, I got to the point where we were able to iterate through all in game objects and check to see if they were overlapping.

This is great, but in its current state every single object will check itself against every single other object every frame. On a small scale this isn't a problem, but really we want to limit checks as efficiently as possible. I admit I am definitely naive to how much processing a "standard spec" computer (whatever that means) is capable of these days, but I always feel slightly uncomfortable if I don't at least attempt to optimise things. Years a go, I spent a whole day implementing what I thought was an amazing way of reducing CPU usage for a uni project (Pogo Fred). When I was actually able to run the optimisation in its entirety, it made no improvement whatsoever, in fact, it actually slowed things down ever so slightly. I didn't feel bad for trying and failing, but thought maybe I should give computers more credit!

To optimise these checks, we have to dismiss objects for checking as quickly as possible. I do this on a number of levels which I will go through below. Please click "Continue Reading" for more.

Active or not

Very simple, if an object is active we continue the checks. If the object is not active we move on to the next one. This a simple bool value that's either true of false.

Class GameItem
  Field X:Int
  Field Y:Int
  Field Width:Int
  Field Height:Int

  Field Active:Bool

  Method Update:Void()

  End

  Method Render:Void()

  End

End

We have added Field Active:Bool to the base GameItem class.

You might be wondering why this is even required. Why not just add and delete items when need and save checking many inactive items? This is because every time you remove an object in game, it still resides in memory. It is up to the garbage collector to sweep through memory and remove these now defunct items. While running natively on a PC, this doesn't tend to be much of a problem, however, as I found when making Ninjah, the Xbox 360 really struggles with garbage collection. All advice relating to Xbox development says "avoid creating garbage at all costs". Just to make it clear, this is just during play time (when the player is actually interacting with the game), during loading or initialization this isn't really a problem because it won't ruin the user experience.

With the active check now in place the iteration code now looks like...

For Local parentType:Int = 0 To ItemType.TYPES - 1
  For Local parentId:Int = 0 To 9

    If Items[parentType][pareintId].Active = True

      For Local childType:Int = 0 To ItemType.TYPES - 1
        For Local childId:Int = 0 To 9

          If parentType <> childType Or parentId <> childId

            If ItemOverItem(Items[parentType][parentId],Items[childType][childId]) = True

              ' DO STUFF HERE !

            End

          End

        Next
      Next

    End

  Next
Next

Line 4 shows the new check. The Active/Inactive checks can actually be improved to make it so only active objects are checked without having to check the item specifically. This requires sorting the item arrays so the active items are at the start of the list and the inactive ones are at the end. This is more advanced than I want to get to at the moment, so I'll leave it for now!

Moving or not

If an object isn't moving, we can assume that if the object wasn't over another object, it's not going to be over one now. We can store this as a simple bool.

Class GameItem
  Field X:Int
  Field Y:Int
  Field Width:Int
  Field Height:Int

  Field OldX:Int
  Field OldY:Int

  Field Active:Bool
  Field Moving:Bool

  Method Update:Void()

  End

  Method Render:Void()

  End

End

We've added three items this time on lines 7, 8 and 11. The simplest way to know if an object has moved is to compare its old position to it's current one.

If OldX <> X or OldY <> Y
  Moving = True
Else
  Moving = False
End

As all items that extend the base GameItem class will use this logic, we need to update the GameItem class again to make updating the Moving bool automatic. We need to avoid changing the Update() Method as we need to reserve this for the item specific behaviour. I do so in the following way.

Class GameItem
  Field X:Int
  Field Y:Int
  Field Width:Int
  Field Height:Int

  Field OldX:Int
  Field OldY:Int

  Field Active:Bool
  Field Moving:Bool

  Method FullUpdate:Void()
    PreUpdate()
    Update()
    PostUpdate()
  End

  Method PreUpdate:Void()
    OldX = X
    OldY = Y
  End

  Method PostUpdate:Void()
    If OldX <> X Or OldY <> Y
      Moving = True
    Else
      Moving = False
    End
  End

  Method Update:Void()

  End

  Method Render:Void()

  End

End

That looks like quite an extreme change, but in practice it's actually really simple. Instead of calling Update() for each object now. We call FullUpdate(). FullUpdate() calls PreUpdate which sets OldX and OldY to X and Y respectively, then it calls Update() which will contain code on a per item type basis (this is where any moving will occur, so maybe moving the object by the current speed). Finally PostUpdate() is called, this very simple checks to see if the object has moved and sets Moving appropriately.

So... this iteration process is now as follows.

For Local parentType:Int = 0 To ItemType.TYPES - 1
  For Local parentId:Int = 0 To 9

    If Items[parentType][pareintId].Active = True

      Items[parentType][parentId].FullUpdate()

      If Items[parentType][parentId].Moving = True

        For Local childType:Int = 0 To ItemType.TYPES - 1
          For Local childId:Int = 0 To 9

            If parentType <> childType Or parentId <> childId

              If ItemOverItem(Items[parentType][parentId],Items[childType][childId]) = True

                ' DO STUFF HERE !

              End

            End

          Next
        Next

      End

    End

  Next
Next

So line 6 updates the item and line 8 checks the Moving bool. If the item is moving, compare it to all other items, if it isn't don't bother. You might be wondering "hang on, just because the first item isn't moving doesn't mean another one can't collide with it", which is true, but because the second item is moving, it will be allowed to check through all items, including the static one.

Filter collision checks

So... we've filtered all inactive objects. We've filtered all static objects. Now we are going to only check items against item types where we have specifically said "these item types can interact with each other". To do this, I use a static class called a collision manager. It is in effect just a 2D array, it doesn't need to be in its own static class, but I have it this way.

Class CollisionManager

  Global Checks:Bool[][]

  Function Init:Void()

    Checks = New Bool[ItemType.TYPES][]

    For Local x:Int = 0 To ItemType.TYPES - 1

      Checks[x] = New Bool[ItemType.TYPES]

      For Local y:Int = 0 To ItemType.TYPES - 1

        Checks[x][y] = False

      Next

    Next

    AddCheck(ItemType.PLAYER,ItemType.COIN)
    AddCheck(ItemType.PLAYER,ItemType.SOME_ENEMY)

  End

  Function AddCheck:Void(typeOne:Int,typeTwo:Int)
    Checks[typeOne][typeTwo] = True
    Checks[typeTwo][typeOne] = True
  End

  Function Check:Bool(typeOne:Int,typeTwo:Int)
    Return Checks[typeOne][typeTwo]
  End

End

I'll split this up in to each function. Init() we call this at the start of the app to initialise the Check array, we use the ItemType.TYPES value to measure the dimensions and then fill the array with False values. Once the array is ready, we can then start adding the check definitions using the AddCheck() function. AddCheck() is just a simple interface for adding a check to the array. It takes two ItemType definitions (which remember, are just int values) and sets the corresponding position in the check array to true. You will notice it does this twice, to allow for both ways of writing a check (e.g. check ball against bat, and check bat against ball). Check() again requires two ItemType definitions (ints) and just returns the corresponding value in the 2d array, either true or false.

What's the point? Well, it's a simple (and quick CPU wise) interface for filtering the iteration process. If we know SomeEnemy objects will never interact with AnotherEnemy objects, there is no point checking them. If you look at lines 21 and 22 above you will see I only want to perform collision checks between Players and Coins and Players and SomeEnemy's. This quick true/false check prevents a lot of iteration. The new iteration process now looks like this...

For Local parentType:Int = 0 To ItemType.TYPES - 1
  For Local parentId:Int = 0 To 9

    If Items[parentType][pareintId].Active = True

      Items[parentType][parentId].FullUpdate()

      If Items[parentType][parentId].Moving = True

        For Local childType:Int = 0 To ItemType.TYPES - 1

          If CollisionManager.Check(parentType,childType) = True

            For Local childId:Int = 0 To 9

              If Items[childType][childId].Active = True

                If parentType <> childType Or parentId <> childId

                  If ItemOverItem(Items[parentType][parentId],Items[childType][childId]) = True

                    ' DO STUFF HERE !

                  End

                End

              End

            Next

          End

        Next

      End

    End

  Next
Next

Line 12 is the important one here and as you can see, the check has to be true for the parent item to iterate through all of the child items. You will notice on line 16 I've also said for it to only bother checking the child item if it's also active.

Reading this all back it seems quite overwhelming, but in essence it's actually quite simple. Apart from changing the ' DO STUFF HERE ! part (which I will get to), we need not visit this code again.

Up to this point, we've just put us in a position to check objects against each other, we've not actually done any checking. In part 3 I will describe the process I use for coding the interaction between objects.

Continue to part 3.