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 - Managing a big number of objects that can collide

Reply to topic
Author Message
  • Joined: 05 Sep 2013
  • Posts: 3763
  • Location: Stockholm, Sweden
Reply with quote
Managing a big number of objects that can collide
Post Posted: Wed Jun 17, 2015 12:34 pm
Not only SMS related by the way...
I was wondering which approach would you use in managing a game that has a pretty big number of objects that can collide with each other. I do have some ideas, but I'd like to compare them to yours and see if there's something that could be more practical.
For instance, imagine a shoot 'em up or a run and gun game... how these kind of games work on a (humble) SMS?
  View user's profile Send private message Visit poster's website
  • Site Admin
  • Joined: 19 Oct 1999
  • Posts: 14690
  • Location: London
Reply with quote
Post Posted: Wed Jun 17, 2015 1:35 pm
Not every object interacts with every other, so reduce comparisons to what is needed. You should do AABB checks first, maybe just leave it at that. If objects can reach a point where they can no longer interact, e.g. enemy bullets which have gone past the player, you can stop checking them. You could do checks at 30fps (check half per frame) to get more capacity. Ultimately it is quite expensive and scales badly as you get more objects.
  View user's profile Send private message Visit poster's website
  • Joined: 05 Sep 2013
  • Posts: 3763
  • Location: Stockholm, Sweden
Reply with quote
Post Posted: Wed Jun 17, 2015 1:56 pm
Maxim wrote
Not every object interacts with every other, so reduce comparisons to what is needed. You should do AABB checks first, maybe just leave it at that.


Yes, surely I'll check only objects which can interact with each other.
I don't get what "the AABB checks" means anyway :(
  View user's profile Send private message Visit poster's website
  • Joined: 30 Mar 2009
  • Posts: 282
Reply with quote
Post Posted: Wed Jun 17, 2015 2:02 pm
Axis Align Bounding Box.

Some more info:
http://studiofreya.com/3d-math-and-physics/simple-aabb-vs-aabb-collision-detecti...

https://developer.mozilla.org/en-US/docs/Games/Techniques/2D_collision_detection
  View user's profile Send private message Visit poster's website
  • Joined: 17 Sep 2013
  • Posts: 128
  • Location: Gravataí, RS, Brazil
Reply with quote
Post Posted: Wed Jun 17, 2015 2:12 pm
If all objects are sprites, you can test for collisions only when the colision flag is set. This have a small side effect, that you can detect a colision only because another colision is detected, but I believe this is a smaill issue.

Another tecnique that I don't know if work, but I believe is worth the try, is instead of testing a colision between two boxes, is to test a colision between a bigger box and a dot. I beliebe this can work in a good amount of colisions types.
  View user's profile Send private message
  • Joined: 06 Apr 2011
  • Posts: 250
  • Location: Netherlands
Reply with quote
Post Posted: Wed Jun 17, 2015 2:20 pm
This link talks about collision detection including assembly routines:

http://web.archive.org/web/20131014100830/http://infinitemsx.com/index.php?option=com_content&view=article&id=27:collision-detection&catid=16:blog&Itemid=7

In my projects I always have a list of objects (default at 32 objects) that depending on flags do 3 types of checks. This to lower the collision check CPU load:

- No colission check
- Collision with player and player bullets check
- Collision with player check

Objects can be of any type (item, bullet, enemy, special trap, script trigger, etc.)
  View user's profile Send private message
  • Joined: 05 Sep 2013
  • Posts: 3763
  • Location: Stockholm, Sweden
Reply with quote
Post Posted: Wed Jun 17, 2015 2:27 pm
AABB: lol, I understand what's that now. I didn't know it had a name :D

About doing the check only if the hardware flag is raised: I actually don't like that, and it won't make it faster when needed. Also it would fail in case one of the two objects can't be drawn because of sprite-per-scan-line limit.

About testing box-with-a-dot-collision... I was also thinking about this approach, but I don't have any info on how it would perform. Any more hints/suggestions on this? It seems to me it would be a nice trick...

Zipper: I'll check that now :)
  View user's profile Send private message Visit poster's website
  • Joined: 17 Sep 2013
  • Posts: 128
  • Location: Gravataí, RS, Brazil
Reply with quote
Post Posted: Wed Jun 17, 2015 2:57 pm
@sverx: Well, than you can test the colisionseither when colision flags set, or the sprite overflow flag is. I believe It would makes things faster when you have a scene where you have a good amount of objects but just happens to be no colision at all. I don't know if this case is likely in your project, but generally its not that rare of a situation
  View user's profile Send private message
  • Joined: 01 Feb 2014
  • Posts: 849
Reply with quote
Post Posted: Wed Jun 17, 2015 5:22 pm
Incidentally, I'm pondering the same thing at the moment. In my new project I'm going to have quite a couple of objects on screen and there's no way I can check for collision for all of them.

One approach I'm thinking about at the moment is to divide the screen into a couple of collision zones and only check for collisions of objects that are in the same zone or an adjacent one. The tricky bit is to find the right size for these collision zones. Make them too small and they become useless, make them too big and you end up checking the whole playfield again.

Maxim wrote
You could do checks at 30fps (check half per frame) to get more capacity.

This is what I did in Bruce Lee when I experienced my first occurrences of slowdown spikes. The game still checks on every frame if the player's attack hits an enemy, but half of the other collisions are only checked at odd frames, the other half at even frames. This sped up things considerably.

gvx32 wrote
If all objects are sprites, you can test for collisions only when the colision flag is set.

Interesting idea, I never really thought of that.
  View user's profile Send private message
  • Site Admin
  • Joined: 19 Oct 1999
  • Posts: 14690
  • Location: London
Reply with quote
Post Posted: Wed Jun 17, 2015 9:25 pm
If all the bullets are the same size, you can expand the player box by the size of a bullet and then simply check if each bullet coordinate is in the box, that being the point check mentioned above.
  View user's profile Send private message Visit poster's website
  • Joined: 08 Dec 2013
  • Posts: 200
Reply with quote
Post Posted: Thu Jun 18, 2015 1:28 am
Please excuse the terse response, I am writing this on a dumbphone. I too am interested in this problem; A sonic1 level has up to 32 objects (I call these "mobs") per level, Sonic always occupies 1 slot. Collision-detection is done on all mobs every frame, even if off screen. I would like to boost the mob-cap to 256, but would need to overhaul collision-detection. What I imagine I would do is maintain a shortlist of on-screen mobs to detect, with the option for some mobs to be permanent - those that the player must wait for off-screen such as moving platforms.
  View user's profile Send private message Visit poster's website
  • Joined: 29 Mar 2012
  • Posts: 879
  • Location: Spain
Reply with quote
Post Posted: Thu Jun 18, 2015 7:33 am
I'll tell how we have managed that in 1985Alternativo regarding "Antarex" on the Sega Megadrive.

We tried quite a few aproaches, but most of them were way to slowly for a shootem up with almost 50 entities at the same moment in the screen. Then we get inspired by this:
http://gendev.spritesmind.net/page-collide.html

So, we have three kind of entities, Good, Bad, and Ugly. The ugly ones are the entities that are ignored for collision detection.

Then, as a first step, we divide the screen in 8pixel colums, and we look wich columns have a good entity (Player Ship, Player Bullets). We've to ensure that there is only one entity by column, but one entity can be in more than one column.

Then, we start drawing bad entities (Enemies and enemy bullets). We look at the column where they'll be, and if there's a good entity there, we check collision, otherwise, we don't have to check anything.

Look at the speed we've managed in Megadrive:
https://www.youtube.com/watch?t=183&v=ZmDpRG8Xnhc
(Minute 3:00)
  View user's profile Send private message
  • Joined: 05 Sep 2013
  • Posts: 3763
  • Location: Stockholm, Sweden
Reply with quote
Post Posted: Thu Jun 18, 2015 8:38 am
Kagesan wrote
One approach I'm thinking about at the moment is to divide the screen into a couple of collision zones and only check for collisions of objects that are in the same zone or an adjacent one.


You mean to slice the screen in rows or columns OR you mean square (rectangular) zones? If an area is big at least as the bigger of your objects, you'll be sure that an object won't appear in more than 4 zones.
Unfortunately if these zones are big, you might end up having a big amount of objects within just one (or few) of them, which would cancel your efforts...

Maxim wrote
If all the bullets are the same size, you can expand the player box by the size of a bullet and then simply check if each bullet coordinate is in the box, that being the point check mentioned above.


Might work if collisions were only player vs. bullets. It would affect every other collision. But anyway I think that box-vs-point collisions could be interesting because it's a special case of box-vs-box collision where the second box is (x0,y0)-(x0,y0) (a box made of a single pixel) so we just have to check if the pixel fall into the box, and such a check will likely cost only 50% than a complete AABB.
Or am I wrong?
  View user's profile Send private message Visit poster's website
  • Joined: 05 Sep 2013
  • Posts: 3763
  • Location: Stockholm, Sweden
Reply with quote
Post Posted: Thu Jun 18, 2015 8:43 am
kusfo wrote
we divide the screen in 8pixel colums, and we look wich columns have a good entity (Player Ship, Player Bullets). We've to ensure that there is only one entity by column, but one entity can be in more than one column.


Thank you for this insider view into your great work :) It's indeed an interesting approach, but the limit is quite heavy. Say you want your ship to shoot also on his sides... how would you handle this?
(I don't mean you have to do that, your project - your choices ;) )
  View user's profile Send private message Visit poster's website
  • Joined: 29 Mar 2012
  • Posts: 879
  • Location: Spain
Reply with quote
Post Posted: Thu Jun 18, 2015 8:52 am
sverx wrote
kusfo wrote
we divide the screen in 8pixel colums, and we look wich columns have a good entity (Player Ship, Player Bullets). We've to ensure that there is only one entity by column, but one entity can be in more than one column.


Thank you for this insider view into your great work :) It's indeed an interesting approach, but the limit is quite heavy. Say you want your ship to shoot also on his sides... how would you handle this?
(I don't mean you have to do that, your project - your choices ;) )


That's not a problem, the only problem arise when two player bullets are in the same 8pixel columns. we've managed also that with a bit of twisting (adding chained references for player bullets that travel one on top of the other)

So, this method is quite useful for the kind of game (One player, bullets that follow simple paths, no 8 direction movement)
  View user's profile Send private message
  • Joined: 05 Sep 2013
  • Posts: 3763
  • Location: Stockholm, Sweden
Reply with quote
Post Posted: Thu Jun 18, 2015 9:04 am
kusfo wrote
That's not a problem, the only problem arise when two player bullets are in the same 8pixel columns.


Well, I meant that, actually. But thanks for the additional details. I was thinking about something similar (hash table with chaining) but I have to calculate the cost of handling that...
  View user's profile Send private message Visit poster's website
  • Joined: 01 Jan 2005
  • Posts: 360
  • Location: Stockholm, Sweden
Reply with quote
Post Posted: Thu Jun 25, 2015 2:48 pm
Make list of box coordinates: top/left, right/bottom
Check first collision source against collision target: use source top/left and target bottom/right. If target bottom/right < source top/left, then skip to next target.
If target bottom/right > source top/left, check if target top/right < source bottom/left.
Repeat.
  View user's profile Send private message Visit poster's website
  • Joined: 29 Mar 2012
  • Posts: 879
  • Location: Spain
Reply with quote
Post Posted: Thu Jun 25, 2015 3:27 pm
idrougge wrote
Make list of box coordinates: top/left, right/bottom
Check first collision source against collision target: use source top/left and target bottom/right. If target bottom/right < source top/left, then skip to next target.
If target bottom/right > source top/left, check if target top/right < source bottom/left.
Repeat.


That's not enough in a Master System if there's plenty of entities, it's compulsory to avoid some checks.
  View user's profile Send private message
Reply to topic



Back to the top of this page

Back to SMS Power!