Win a copy of Succeeding with AI this week in the Artificial Intelligence and Machine Learning forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
  • Campbell Ritchie
  • Paul Clapham
  • Ron McLeod
  • Liutauras Vilda
  • Junilu Lacar
  • Tim Cooke
  • Jeanne Boyarsky
  • Knute Snortum
Saloon Keepers:
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Carey Brown
  • Piet Souris
  • salvin francis
  • fred rosenberger
  • Frits Walraven

Collision detection

Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
Ranch Hand
Posts: 3061
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.

Jack Smith
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
Roses are red, violets are blue. Some poems rhyme and some don't. And some poems are a tiny ad.
Two software engineers solve most of the world's problems in one K&R sized book
    Bookmark Topic Watch Topic
  • New Topic