Forums

Sega Master System / Mark III / Game Gear
SG-1000 / SC-3000 / SF-7000 / OMV
Home - Forums - Games - Scans - Maps - Cheats - Credits
Music - Videos - Development - Hacks - Translations - Homebrew

View topic - A Question about Collision Detection

Reply to topic
Author Message
  • Joined: 09 Dec 2007
  • Posts: 21
Reply with quote
A Question about Collision Detection
Post Posted: Wed May 16, 2018 6:23 am
Hi everyone, long time lurker here.

So I'm studying game development at university. My group and I were talking about our group project with our tutor when I commented that I wanted to change the character collider to a box rather than a capsule. Because capsules tend to slip of the edges of platforms, stick to the sides of them and just do all kinds of strange things in 2.5D games.

Our tutor claimed that they have always used spheres or capsules in collision detection. Even back in the 8 and 16-bit consoles. While I realize they probably could have done this my understanding is that most games, specially platformers, would use box collisions. My understanding was the engines either use the actual pixels of the sprites, did it on a tile/sprite element basis or did it manually by checking the sprit's position within a range relative to what they were testing.

Anyway, I was just wondering if someone could talk more authoritatively on this subject. Am I correct or am I missing something?
  View user's profile Send private message
  • Site Admin
  • Joined: 19 Oct 1999
  • Posts: 12384
  • Location: London
Reply with quote
Post Posted: Wed May 16, 2018 6:58 am
There's really only enough CPU to do AABB checks, ie. rectangles. Often only one per character, except for big bosses. Pixel perfect collision checks are hard, and often not necessary - players quite like generous collision detection.

On the basic level, AABB checks require only comparisons (which is equivalent to subtraction), whereas circles require computing the centre distance (Pythagoras, so multiplication at least). One of these is massively faster than the other.

Saying that, for Ono I had only circular sprites in three sizes so I did Pythagorean collision checks (as the game needs it), using lookup tables after an AABB check. Other optimisations may apply depending on the game.
  View user's profile Send private message Visit poster's website
  • Joined: 28 Jan 2017
  • Posts: 356
  • Location: Málaga, Spain
Reply with quote
Post Posted: Wed May 16, 2018 12:16 pm
Ummmm... Interesting theme!

Two ways to save time doing this are:

1. Dont perform checks all frames, exceptn if there are little and fast boxes involved (a shmup?)

2. I doubt about the use of quadtrees on máster system, about in other stronger system could be nice. In fact, in 3d engines with octrees involved, you can use these (used for discard the rendering of blocks) to discard the possibility of collisions.

Regards
  View user's profile Send private message
  • Joined: 14 Mar 2018
  • Posts: 17
Reply with quote
Post Posted: Wed May 16, 2018 1:18 pm
Total 100% crap. I'm will to say that there is not a single 8bit game and probably not a single 16bit game(maybe something on the Amiga might for whatever reason) would have a capsule as a collision.

One mostly does points to AABB boxes.(aka X/8 y/8 look at what the tile is in the position) In that Mario for example has 2 points he checks and only checks in the direction he is facing. Speed runners use this to turn around frame perfect to clip into walls. I believe Sonic is the same.

You do see a lot and I've used Minkowski collision but that is always been point to AABB rectangle. When you get to SNES and mode7 its hardware multiplies make Circle collision a lot more sane however even then they usually did 2 points from an octagon against the world it seems.
  View user's profile Send private message
  • Site Admin
  • Joined: 08 Jul 2001
  • Posts: 7927
  • Location: Paris, France
Reply with quote
Post Posted: Wed May 16, 2018 2:00 pm
I guess the use of sphere/capsule would be up to how cheap it is to perform a square on the host CPU (as you'd want to compare the squared distance, so, one multiplication on each axis). With integer position and it's fairly easy to use a square lookup table, add both results and compare.

Capsule are unlikely but it's possible that some games occasionally used spheres, though the display and game design being so biased toward rectangle-fitting objects, that the majority of games most probably used AABB, at least on consoles. The display systems of computers of a similar era were different and encouraged different type of game design, making spheres collisions maybe more prominent.
  View user's profile Send private message Visit poster's website
  • Joined: 14 Mar 2018
  • Posts: 17
Reply with quote
Post Posted: Wed May 16, 2018 2:07 pm
Open a paint program. Draw a 16x16 square, draw a 8r Circle in the middle. Ask yourself is it worth it ;)
  View user's profile Send private message
  • Joined: 05 Sep 2013
  • Posts: 2239
Reply with quote
Post Posted: Wed May 16, 2018 3:07 pm
in Waimanu I used an even simplified
(abs(x1-x2)+abs(y1-y2))<K

which works great (for example, permits Waimanu turns even if it's chased by a Weka that's so close that would catch him in the corner...)
[of course the sprites were square and of the same size...]
  View user's profile Send private message Visit poster's website
  • Joined: 14 Oct 2008
  • Posts: 261
Reply with quote
Post Posted: Wed May 16, 2018 4:15 pm
oziphantom wrote
Total 100% crap. I'm will to say that there is not a single 8bit game and probably not a single 16bit game(maybe something on the Amiga might for whatever reason) would have a capsule as a collision.

One mostly does points to AABB boxes.(aka X/8 y/8 look at what the tile is in the position) In that Mario for example has 2 points he checks and only checks in the direction he is facing. Speed runners use this to turn around frame perfect to clip into walls. I believe Sonic is the same.

You do see a lot and I've used Minkowski collision but that is always been point to AABB rectangle. When you get to SNES and mode7 its hardware multiplies make Circle collision a lot more sane however even then they usually did 2 points from an octagon against the world it seems.


I'm sure there's a reason the term is hitBOX and not hitSPHERE. :D
  View user's profile Send private message
  • Joined: 09 Dec 2007
  • Posts: 21
Reply with quote
Post Posted: Thu May 17, 2018 5:55 am
Hey everyone, thanks for the great responses. I was pretty sure this was the case but it's nice to have some expert backup from people who have actually developed a system of this generation. I'm going to reference this thread in my journal assessment. XD
  View user's profile Send private message
Reply to topic



Back to the top of this page

Back to SMS Power!