Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

# Collision detection

Jack Smith
Greenhorn
Posts: 2
I'm doing a tile based shooter with a top-down view.
I thought about making all the tiles instances of the TILE object. Like all got parameters for what image they use and if they are solid or not. I would make the constructor paint the image and make a bounding box. I have used bounding boxes for collission detection earlier but so far I have just used a few boxes.
Now I would wana know if there is a way to check if the players bounding box intersects with ANY of the tile bounding boxes. So that you don't need to test with all tiles separately.

I'm actually pretty confused on all this and if someone got a better idea please tell me.

Layne Lund
Ranch Hand
Posts: 3061
If I understand correctly, you are thinking about writing a Tile class and then creating Tile objects. Then during the game, you will need to do some collision detection between the player and these Tiles. Are you asking how to do this efficiently? If so, it highly depends on how you are storing the Tiles. So let's talk about some different data structures that you can use and see how each data structure affects efficiency.

The naive approach is to store the Tiles as a linked list (perhaps using the LinkedList class from the Collections API). This is probably what you are trying to avoid, however, since it requires doing the collision detection with every single tile. This algorithm will be O(n) where n is the number of Tile objects.

Obviously the above approach is poor. A much better approach may be to store the Tiles in a 2D array. Of course, this approach assumes that each "grid location" in the game only has a signle tile associated with it. This data structure will lead to a collision detection of O(1) (i.e. constant time) because if the player is in grid location (x, y), then you know the player collides with the Tile object in location (x, y). To me, this seems like a much more logical choice than the LinkedList idea above.

If you need to get more complex, especially if you want to make a 3D game (instead of just 2D), you may want to look into using what are called half-spaces. I won't get into this in much detail, but it will require a tree (typically a binary tree) as the data structure. You should google for more information if this sounds like what you need.

Good luck with your game. In the future, you may want to post questions in our Games Forum which is specific for these types of things.

Layne

Jack Smith
Greenhorn
Posts: 2
I managed to upload the game so you get a better idea what I'm trying to do.

The Game
Arrow keys and wasd is used for movement

Your second suggestion sounded pretty good but as you see the player doesn't move in tiles so I don't have the players cordinate in the grid stored anywhere. So do you have any suggestion how I should make it? All tiles are 20x20 pixels in size. My idea is that if player cordinates are e.g 56,89 then the place in the grid would be in tile 3 from left(56/20 = 2.8) and tile 5 from top(89/20 = 4,45). But this way it would only detect the collision of the left upper corner of the player. Any ideas?