How collision detection surprized me…

That's right, I didn't think about collision detection enough when I tried to implement the level loader code. The level file format specifications are ready and I've already written code to load it, but the question is: where to store this loaded data?

I need to split up the sprite lists. Inserting new sprites while ordering them on their Z value (so they are rendered in good order) is nice, but not when the list contains 10.000+ items… Besides creating a second list that contains the static sprites, I think it's also a good idea to use a quad-tree instead for faster rendering. And that's what got me thinking: how about the collision stuff? Do I want to put that in the game logic code? How would entities use the collision system – do they need to know things beforehand, or afterwards, or consistently… and so on?

For now, I've decided to create a new 'module' for the collision handling, that behaves much like the rendering module: entities can register an instance, update it, and request collision checks. A quad-tree for the static items, and a list for the dynamic items sounds like a fair solution, too.
With this approach, the entity system doesn't get cluttered with collision-specific code, and non-physical entities do not clutter the collision system. I hope…

And that all because of quad-trees… :)

How collision detection surprized me…

2 thoughts on “How collision detection surprized me…

  1. Hey,

    I’ve been reading your site and thought I’d give u a hint on the collision detection problem.

    A little history, I’ve been working part time on a game engine of my own. Its written in java and i’ve been able to peice together a few simple games like tetris and pong(not as easy as it seems, expecially collisions), so I know this issue a little bit, but im not a genius.

    Ok, u seem more informed than me either way, but I’ll suggest my method of handling collisions.

    I use the concept of a SceneManager to handle all things related to updating and rendering the scene. For a tile game u would define a TileScene, for a static board you could define a StaticScene etc, but they all extend the basic QuadScene which is a blank scene with a QuadTree attached. This scene manager takes care of collision detection by using a QuadTree that is the size of the entire world, map whatever u call it. All actors (moveable-like a player for instance, and static-like walls and chairs) are added to the scene manager that simply adds them to the quadTree. Scene.update() calls Tree.update() which calls update() on all tree.nodes and each node calls update on objects in its personal list aka the actors on the scene. Now this engine is clearly not the most efficient, but it developed to keep OO in mind at all time. Its a purist thing to me.

    Each Actor(sprite) contains a list of objects that it collided with. This list is processed everytime the actor is updated, so in theory no collisions will remain in the list after an update. To make sure of this I actually clear the list each update, not necessary, but I keep it there to maintain a stable engine until time to optimize.

    Ok, so basically when a collision between a wall, ball, bullet or whatever is detected, the actor has a pointer to the collided object. Then in processCollisions() my actor is able to define for itself, based on its class, how to react to each collision. Multiple bullets will cause multiple damage, a wall will cause the actor to stop, and a mine would cause it to die and switch animation to exploding body, ur imagination can fill in the blanks there : ). Not sure if I helped any, or atleast gave some inspiration, but I thought id share. Lemme know ur thoughts on this and if you have questions suggestions for me. I’d love to know how u finally tackled this issue.

  2. I’ve never finished this engine – I was over-complicating and abstracting matters and didn’t keep a focus on the game I originally wanted to build. Nowadays, I’m building games, not engines, and I’m simply reusing code from past games. Eventually this forms a sort of framework, that gradually gets better as you build more games with it. That way, I end up with code that’s actually proven to be usefull, not code that just seems usefull at first sight. No problem if something doesn’t work flawless the first time – I’ll simply refactor it or take a different approach the next time.

    Anyawy. I’ve worked on some other games after this one, so I’ve gained some more experience on the subject. The problem here isn’t really collision detection, but handling. It’s mostly a matter of design.

    I’m currently writing a top-down scrolling shooter. Somewhere in the games update code, I check if any enemy bullets hit the player. I then check if any player bullets hit any enemies. And then if the player collides with an enemy. Obviously, when more and more different object types get involved, this becomes unworkable. It’s not a very flexible system, but this shooter doesn’t really need anything else, so that’s just fine.

    I’ve worked on a 3D adventure game that had to be much more flexible. There were 3 artists working on the levels and I wanted to give them the flexibility I had when creating levels for Half-Life, because that would allow us to build many more levels with relatively little additional programming – if any. For the collision handling, there were two main reactions. First, objects shouldn’t be able to move through level geometry. Second, objects should react to collisions with each other – a player picking up an item, a bullet hitting a monster, etc.

    The engine I worked with already had a collision system in place. Game objects could register a collision shape with it and ask the collision system if it collided with any other shapes. The system would return a list with collision information in return. I gave these collision shapes specific tags (SOLID, GHOST, etc.) and depending on this tag, I would either correct the position of the object (such as when colliding with the world), or send a message to the other object (such as when picking up a key – the key has to know it’s being picked up). I did this through a MessageManager, though nowadays I’d use the observer pattern for it.

    One thing that I believe is worth mentioning is that game objects aren’t always visible and touchable. An invisible trigger area needs a collision area, but not a sprite. On the other hand, a piece of detail scenery doesn’t need a collision area. That’s why I would split up these aspects into components. Game objects can then contain one or more of these components – as much as they need. A particle engine, for example, could contain numerour sprites. The key difference here is that a game object isn’t a sprite, it has a sprite. It isn’t a collision object, it has one. Or none, or more, depending on it’s needs.

    So yeah, how I would tackle this problem depends on the needs of the game I’m working on. :)

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s