Advanced collision detection discussion

  • (2 Pages)
  • +
  • 1
  • 2

24 Replies - 13134 Views - Last Post: 24 November 2009 - 03:51 AM Rate Topic: -----

#1 SixOfEleven   User is offline

  • Planeswalker
  • member icon

Reputation: 1055
  • View blog
  • Posts: 6,643
  • Joined: 18-October 08

Advanced collision detection discussion

Post icon  Posted 19 November 2009 - 03:10 PM

Well, I have the tile collision working pretty well now. There is a small issue with diagonals but I should be able to fix that at a later date. The readers want me to just get it working so I will fix the problem with diagonals later.
Is This A Good Question/Topic? 0
  • +

Replies To: Advanced collision detection discussion

#2 SixOfEleven   User is offline

  • Planeswalker
  • member icon

Reputation: 1055
  • View blog
  • Posts: 6,643
  • Joined: 18-October 08

Re: Advanced collision detection discussion

Posted 20 November 2009 - 08:37 AM

Fixed the problem with diagonals and the collision of the tiles with the sprite. There is one other topic that I might add eventually. At the moment this doesn't work so good with the transparency of the sprite and the tiles. That would require per pixel collision detection between the specific tile and the sprite. Something that I might add in later on.
Was This Post Helpful? 0
  • +
  • -

#3 Aurel300   User is offline

  • D.I.C Head

Reputation: 13
  • View blog
  • Posts: 230
  • Joined: 10-November 07

Re: Advanced collision detection discussion

Posted 20 November 2009 - 09:23 AM

Donīt use pixel by pixel collision. This is not the easiest thing to do neither in code nor performance. Games where a lot of collision detection is needed (like Street Fighter) use collision boxes.
In .NET it is a built in function (rect.Intersect(otherRect)), but it should be fairly easy to code manually.

This post has been edited by Aurel300: 20 November 2009 - 09:24 AM

Was This Post Helpful? 0
  • +
  • -

#4 NeoTifa   User is offline

  • NeoTifa Codebreaker, the Scourge of Devtester
  • member icon





Reputation: 4202
  • View blog
  • Posts: 18,441
  • Joined: 24-September 08

Re: Advanced collision detection discussion

Posted 20 November 2009 - 10:53 AM

But the things aren't purely square. If you were playing Call of Duty or something and they used, say, cube collision, and someone shot around your head and clipped the very far corner, which is no where near your head (headshot revetively), and got points for headshotting you, wouldn't you be pissed? I mean, pixel detection is far more accurate, and there is nothing wrong with it. Yes, it's a pain to code, but the rewards are worth it.
Was This Post Helpful? 0
  • +
  • -

#5 SixOfEleven   User is offline

  • Planeswalker
  • member icon

Reputation: 1055
  • View blog
  • Posts: 6,643
  • Joined: 18-October 08

Re: Advanced collision detection discussion

Posted 20 November 2009 - 12:23 PM

Per pixel collision detection does take a lot of processing. At the moment I'm using a form of rectangle collision for this and it works well. The sprite can never enter a tile that is impassable. I could restrict the player's motion like in the Pokemon games where they are only ever in one tile at a time but I think players prefer free range movement

I was thinking of possibly at some time adding in per pixel for the tiles if the sprite does collide with an impassable tile, just checking in those cases would reduce the amount of time spent processing per pixel collision.

To make it a bit better I might go with a bounding rectangle for the sprite and for the tiles, since they are somewhat rectangular, create a smaller rectangle for them and check collisions between those two rectangles to allow the sprite to get closer to the edge of the tiles. At the moment though what is important is that the sprite can't enter impassable tiles.

For character/object collision detection, like NeoTife said, it is usually better to do per pixel collision. It is frustrating for a player if the object just misses them and it counts as a hit. Though when they are playing against the computer and there is near miss that counts as a hit they never seem to complain. ;)
Was This Post Helpful? 0
  • +
  • -

#6 Aurel300   User is offline

  • D.I.C Head

Reputation: 13
  • View blog
  • Posts: 230
  • Joined: 10-November 07

Re: Advanced collision detection discussion

Posted 20 November 2009 - 01:04 PM

Yes, but in a Zelda (I mean top-view) RPG - I think that is different.
I donīt say you should have just ONE boundary box around the whole sprite - maybe there are going to be some bigger ones than 1x1 tiled - like a big dragon or something.
But for those 1x1... Do as you want, but without a good code some performance may be gone.
Was This Post Helpful? 0
  • +
  • -

#7 lesPaul456   User is offline

  • D.I.C Addict
  • member icon

Reputation: 175
  • View blog
  • Posts: 729
  • Joined: 16-April 09

Re: Advanced collision detection discussion

Posted 20 November 2009 - 01:15 PM

While per pixel collision detection does require more processing, there usually isn't a noticable difference in performance.

Another common 2D collision detection technique is to use polyogns that are the exact shape of the sprite. The performance remains about the same as rectangle collision. Granted, polygon collision detection is not always a feasible option...
Was This Post Helpful? 0
  • +
  • -

#8 SixOfEleven   User is offline

  • Planeswalker
  • member icon

Reputation: 1055
  • View blog
  • Posts: 6,643
  • Joined: 18-October 08

Re: Advanced collision detection discussion

Posted 20 November 2009 - 01:21 PM

Collision detection can be a complex topic in just about any situation. Issues like a lot of transparency and animation can compound the problem. For an animated sprites with a lot of transparency the problem can get worse. I'm going to split this thread about collision detection and move it to game programming for more of a discussion on the topic. I think it would be a good discussion there.
Was This Post Helpful? 0
  • +
  • -

#9 Aurel300   User is offline

  • D.I.C Head

Reputation: 13
  • View blog
  • Posts: 230
  • Joined: 10-November 07

Re: Advanced collision detection discussion

Posted 20 November 2009 - 03:11 PM

View PostAurel300, on 20 Nov, 2009 - 12:04 PM, said:

But for those 1x1... Do as you want, but without a good code some performance may be gone.

This post has been edited by Aurel300: 20 November 2009 - 03:11 PM

Was This Post Helpful? 0
  • +
  • -

#10 SixOfEleven   User is offline

  • Planeswalker
  • member icon

Reputation: 1055
  • View blog
  • Posts: 6,643
  • Joined: 18-October 08

Re: Advanced collision detection discussion

Posted 20 November 2009 - 07:49 PM

Yes, you would definitely want to optimize the code to reduce the number of times you are doing per pixel collision detection. For example, if you find that the player's sprite will collide with an object using say simple rectangle collision if it is even worth doing per pixel collision detection. Even when you do the per pixel collision detection you would want to try and optimize the code to reduce the performance impact. If you are tracking a lot of objects, like in an MMO, you would be better to find a different way to handle collision detection.
Was This Post Helpful? 0
  • +
  • -

#11 Hellbroth   User is offline

  • D.I.C Head
  • member icon

Reputation: 17
  • View blog
  • Posts: 190
  • Joined: 15-August 09

Re: Advanced collision detection discussion

Posted 20 November 2009 - 09:37 PM

That's realy nice of you SixOfEleven like always you help us so much.
Is this in your tutorials in somewhere else?Cause i realy want to look at it.


Thanx again for all your efforts.

That's realy nice of you SixOfEleven like always you help us so much.
Is this in your tutorials in somewhere else?Cause i realy want to look at it.


Thanx again for all your efforts.
Was This Post Helpful? 0
  • +
  • -

#12 Aurel300   User is offline

  • D.I.C Head

Reputation: 13
  • View blog
  • Posts: 230
  • Joined: 10-November 07

Re: Advanced collision detection discussion

Posted 21 November 2009 - 07:35 AM

An alternate solution (for tiles) would be that a tile would have a boolean value "hasWalkMap" and an array of points / polygon "walkMap".
If a player is walking over the tile and the hasWalkMap is false, none collision detection is done. However, if the value is true, then the walkMap determines the walkability.
I think that player would have just a normal boundary box and it will be tested for collision with the polygonal walkMap.

Plus, maybe a value "walkable" (boolean) would be needed too. If a tile isnīt walkable, no collision detection is needed either, and this thing would probably be used for water and things like that.

This post has been edited by Aurel300: 21 November 2009 - 07:37 AM

Was This Post Helpful? 0
  • +
  • -

#13 SixOfEleven   User is offline

  • Planeswalker
  • member icon

Reputation: 1055
  • View blog
  • Posts: 6,643
  • Joined: 18-October 08

Re: Advanced collision detection discussion

Posted 21 November 2009 - 09:07 AM

I went one step further than a boolean variable for this. I'm using an enumeration so that I can check for more than just walkable tiles eventually.

The way my collision layer works is when the player is moving, I don't check anything if the player isn't moving as that would be a waste of processing time, check which tile they are moving into using a bounding rectangle. Depending on which direction the player is moving depends on how the collision detection works. The collision layer returns the enum for the tile the player is walking into. At the moment I only have two values in the enum, passable and unpassable. The method that preforms the collision check returns true if the tile is unpassable and false otherwise. I have been considering, if the tile is unpassable, going further and doing a per pixel collision detection between sprite and tile. That would be very far off in the future though.
Was This Post Helpful? 0
  • +
  • -

#14 RudiVisser   User is offline

  • .. does not guess solutions
  • member icon

Reputation: 1010
  • View blog
  • Posts: 3,566
  • Joined: 05-June 09

Re: Advanced collision detection discussion

Posted 21 November 2009 - 10:31 AM

View PostNeoTifa, on 20 Nov, 2009 - 04:53 PM, said:

But the things aren't purely square. If you were playing Call of Duty or something and they used, say, cube collision,

Hitboxes darling, they are used :P

TF Hitboxes w/ Anti-Lag applied
Posted Image

ET Hitboxes
Posted Image Posted Image Posted Image

etc.

This post has been edited by RudiVisser: 21 November 2009 - 10:34 AM

Was This Post Helpful? 0
  • +
  • -

#15 Theaegd   User is offline

  • Hater & Lover

Reputation: -125
  • View blog
  • Posts: 944
  • Joined: 15-August 09

Re: Advanced collision detection discussion

Posted 21 November 2009 - 12:49 PM

There is no way (like the blue box) that it would cover that much area above the charecter. For 80% of 2d games, per pixel detection isnt necessary.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2