The moose likes Beginning Java and the fly likes Collision detection Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login

JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Collision detection" Watch "Collision detection" New topic

Collision detection

Jack Smith

Joined: Oct 04, 2005
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

Joined: Dec 06, 2001
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.


Java API Documentation
The Java Tutorial
Jack Smith

Joined: Oct 04, 2005
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?
I’ve looked at a lot of different solutions, and in my humble opinion Aspose is the way to go. Here’s the link:
subject: Collision detection
It's not a secret anymore!