Collisions in my iOS game

This is part seven of a series on making iOS games.

Getting collision behaviour right, can take some time.
For me it meant working on two things:

  • An algorithm for finding collisions and making sure that that algorithm does not take too long
  • working out the right behaviour post collision

Algorithm

There are three areas in the game where I have to detect and respond to collisions:

  • moving entities, e.g. bullets and monsters
  • particles hitting sprites
  • players and monsters hitting a wall or going off tile
Moving entities

I use the function CGRectIntersectsRect for moving entities.

Particles

For particle effects, those that actually impact other things like a flame weapons, I place an invisible sprite on top of the approximate size of the effect, thats much easier than trying to check every particle against other moving sprites, and much quicker.

Tiles

With tiles I realised that I couldn’t use CGRectIntersectsRect because checking the collisions of (say) 100 moving sprites against each of the 1600 tile sprites (160,000 checks) would take too long. So to do tile collision checks I took a leaf out of Michael Daily’s book, and instead in each (moving) sprite’s update method, I check based on its position if it has moved into a tile that it can’t move into for some reason (like a wall or empty space).

Working out post collision behaviour

Post collision behaviour is very game dependent. Sometimes you may want momentum conserved, sometimes you may reflect small sprites off large ones, sometimes you may want all velocities killed when sprites hit each other. One sprite may impart velocities onto another if that sprite is (for example) a catapult or linear accelerator.

For my game I found that the trickiest situation was to figure out the correct behaviour when colliding against tiles. I went through a number of iterations. I want the sprite, when it hits a wall, to be able to slide along that wall, not come to a stop immediately and not bounce (or bounce the wrong way). One has to determine what are the possible collisions and for each collision possibly rollback the location, and/or impart a new velocity – and do this on both axes.
Here is an image of my attempts at figuring out what to do post collision.

Which ever of sx or sy, (for the corner of the sprite being checked) when divided by the x or y velocity, is smaller, is considered the first axis to collide with the tile. One can use sx and sy also to reposition the sprite more accurately, so you rollback not the last x or y coord, but to the nearest x or y coord next to the wall.

The diagram looks nice – but unfortunately this algorithm does not work. As the sprite slides along a wall it will inevitably – when it reaches a new tile – collide with a tiny corner of the next tile, and the wrong axis will be chosen. Here is a diagram of that.

The y velocity in this case will be the lowest it can be – because in the previous frame it was up against the wall, for a very a small denominator you’d expect the sy/vy to be the larger (and so the y axis coord is rollbacked to the previous one) but happenstance has made sx tiny – so that even with a large velocity sx/vx < sy/vy.

This tended to happen in my game every 10 tiles or so - the player sprite would be speeding along the wall and then suddenly stop.

My solution to this was to go back to the drawing board and implement a much simpler algorithm.
Instead of this:

  • check to see if corner is in a non passable tile
  • if so determine sx/vx and sy/vy
  • rollback where necessary

I do this:

  • check to see if the corner is on a non passable tile
  • check to see if the corner would have been on a non passable tile if vx or vy were set to zero
  • rollback where necessary

This allows the sprite to slide along a wall, and it can do it as fast as it likes without bouncing or stopping seemingly randomly.

Another thing that one could do, would be to amalgamate tiles into larger rectangular units, but this would not always solve the first problem of the occasional wrong post collision action, just make it happen less frequently. One might want to do this for optimisation reasons, but then you would need another algorithm.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>