Collision detection Fundamentals please

Apprentice
Posts: 14
Joined: 2007.04
Post: #1
Hi, first i have to say I'm a complete begginer into videogame development.

I'm planning to improve a small game that i made for one of my Universty classes. Its a small blocky version of space invaders. I have a doubt regarding to collision detection. My teacher says that the colition detection algorithm must be inside the characters classes (player and enemy). But i was thinking in a specialiced object wich receive the pointers to objects (player and enemies) and puts them in a list (linked list) and it constantly check for collision amongst all the objects in the list by accessing the cordinates and size of each one.

It sounds kinda complicated considering is a small game, but i want to develop it in a very professional way in the same way big games are developed. Wich one is more like it? Any other alternative?
Quote this message in a reply
Oldtimer
Posts: 834
Joined: 2002.09
Post: #2
I'd say that your way of doing it is very valid, unless you have very customized collision detection for each object. If most objects are just box-box with simple "collide/don't collide" flags, then splitting it off would be the best way (imho) to go about it.
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #3
I would not put collision detection within the player and enemy classes. The major reason for this is that most OO languages only have single dynamic dispatch (on the receiver of the message), and collision detection inherently requires dual dynamic dispatch. In my experience, dual dynamic dispatch is much better handled outside all of the classes involved, rather than randomly inside some and not others.

Of course, if all your collision detection is insanely simple (eg it's all circle-circle or rect-rect) then the dual dispatch thing isn't an issue.

Obviously, whichever you choose, responsibility for checking the collisions belongs to whatever object owns the list of all the entities in the game -- it makes no sense for the player to know where all the enemies are so that it can detect its own collisions with them, for example.
Quote this message in a reply
Member
Posts: 338
Joined: 2004.07
Post: #4
I put my collision code in my player/enemy/bullet classes for my first few games, and I can confidently say that it's a very clunky solution and I'll never do it again.

Your solution is much better, and expanding on it a bit, you could have your linked list have pointers to an abstract base class (say, Object, from which you derive Player and Enemy), which contains a Shape object used for collision. Shape is itself an abstract base class, and you can derive from it simple things like circle, square, and complicated things like convex hulls.

Your collision system could then take in two Shapes, and can then branch off internally depending on what those shapes are. This would make it extremely easy to add new bounding volumes, and you can reuse the same calling code.

Justin Ficarrotta
http://www.justinfic.com
"It is better to be The Man than to work for The Man." - Alexander Seropian
Quote this message in a reply
Apprentice
Posts: 14
Joined: 2007.04
Post: #5
Thank you all for the answers. So how far is my technique from the professional way of doing it? I mean, i know i must implement different collision detection resolutions (sphere, box, complex) and other stuff, but how is it overal? Should i make a double linked list? maybe more than one list? should i create a different class for every collision resolution or can i implement them as methods inside just one class?
Quote this message in a reply
Moderator
Posts: 3,577
Joined: 2003.06
Post: #6
jigzat Wrote:Thank you all for the answers. So how far is my technique from the professional way of doing it?
The truly professional way of doing collision detection is: whatever works.

Some ways are fast, some slower, some more accurate, etc. It depends on the application. I find most of my 2d stuff is plenty good with box or circle collision detection. I even have a polygonal collision detection scheme for oddly shaped objects. Polygonal is only slightly more complicated to pull off, but I would say it is as good as it gets for this kind of collision detection. The other way to do it is called per-pixel collision detection. As the name implies, it is accurate down to the pixels of the objects. Sometimes it is the best way to go, but again, it depends on your needs -- generally box or circle is Good Enough™.

Like everyone else said, I don't do my collision detection in the entity either, although I tried that at first too. I used to use a fancy linked list (even multiple linked lists), but I realized that it was overkill, so now I just put `em all in an array and be done with it.

All that being said, it seems to me that per-pixel collision detection might actually be best for a space invaders game. That way you could have the shields get eaten away by laser blasts, pixel by pixel. But whatever works...
Quote this message in a reply
Member
Posts: 338
Joined: 2004.07
Post: #7
jigzat Wrote:Should i make a double linked list? maybe more than one list? should i create a different class for every collision resolution or can i implement them as methods inside just one class?

For small numbers of objects you can get away with one list, and just checking every object against the rest.

The next step, and the way I'm currently approaching it, is to have several lists, where each list contains all objects of a certain type or allegiance. So for Space Invaders, one way to do it would be to have the player be in one list by itself, and there would be lists for player bullets, enemy bullets, enemies, and the bunkers.

You could then specify which lists can collide with which other lists. So player collides with enemy bullets and enemies. Enemies collide with player bullets. Bunkers collide with both types of bullets. This will both keep the number of objects you're checking for collision low, and also prevents goofy situations like the player getting shot by its own bullets as they leave the gun.

Justin Ficarrotta
http://www.justinfic.com
"It is better to be The Man than to work for The Man." - Alexander Seropian
Quote this message in a reply
Apprentice
Posts: 14
Joined: 2007.04
Post: #8
Thank you very much all of you, you guys rock and idevgames rocks too. Now i have a really good overal perspective of how collision detection works.

See you soon.
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #9
JustinFic Wrote:The next step, and the way I'm currently approaching it, is to have several lists, where each list contains all objects of a certain type or allegiance. So for Space Invaders, one way to do it would be to have the player be in one list by itself, and there would be lists for player bullets, enemy bullets, enemies, and the bunkers.

Even better is to use a spatial data structure that you can use to further reduce the number of collision checks. Not nearly as simple to implement, but If you intend on having hundreds of objects in a scene, this is vital though.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Apprentice
Posts: 14
Joined: 2007.04
Post: #10
What do you mean by spatial data structure?.....My english ain't that good.
Quote this message in a reply
Apprentice
Posts: 14
Joined: 2007.04
Post: #11
Never mind, i found that out. You were right is kinda complicated, but is usefull for more complex games.
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #12
It's a data structure that allows you to efficiently store and recall which objects are near, or probably near each other. http://en.wikipedia.org/wiki/Spatial_index

You don't need to bother with any this for a simple game, but you might want to be aware that such things exist for the future.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Apprentice
Posts: 14
Joined: 2007.04
Post: #13
Skorche Wrote:You don't need to bother with any this for a simple game, but you might want to be aware that such things exist for the future.

Yeah thats my purpose. That is why i decided to improve my little game to fullfill some standard good techniques.
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Optimize the collision detection alaslipknot 1 2,722 May 12, 2013 08:02 PM
Last Post: SethWillits
  Collision detection tutorial ThemsAllTook 7 22,691 Nov 5, 2011 05:20 PM
Last Post: SethWillits
  Help with Collision Detection..(i'm almost there) carmine 1 4,648 Jun 29, 2011 12:33 PM
Last Post: ThemsAllTook
  Time Delta, collision detection mk12 19 15,537 Sep 8, 2010 06:40 PM
Last Post: AnotherJake
  Collision detection for pinball game johncmurphy 0 4,771 Sep 6, 2009 02:46 PM
Last Post: johncmurphy