Fastrom patches?

[tepples]

By "circular collision" you mean a bounding box test followed by comparing a²+b² to a threshold, right? What is this "grid based collision" and how is it slower than circular collision? Could, say, Super Mario World have gained a speedup from circular collision?

[psycopathicteen]

Grid based as in, instead of the bubbles having a single bounding box, they have multiple 8x8 bounding boxes.

[93143]

Pic from thread linked earlier:

Yeah, I'm pretty sure circular would be faster than that.

To be fair, a lot of them are smaller, but still. Also, you'd lose a lot of precision for the smallest ones (which may explain why I thought collision with those darn things was so janky)...

[Drew Sebastino]

And that looks substantially more difficult to implement; probably the first idea that came to the programmer's and they just had to go with it.

They could've used grid based collision in the arcade version of gradius III, because that game even has slowdown during the bubble level

i agree, good remark,on arcade systems that are overpowered, you can code almost as badly as you want, your game will be "always" smooth.

Given that the original arcade version of Gradius III uses 2, 10MHz 68000s, it's very possible it's programmed no better than the SNES port.

[psycopathicteen]

And that looks substantially more difficult to implement; probably the first idea that came to the programmer's and they just had to go with it.

They could've used grid based collision in the arcade version of gradius III, because that game even has slowdown during the bubble level

i agree, good remark,on arcade systems that are overpowered, you can code almost as badly as you want, your game will be "always" smooth.

Given that the original arcade version of Gradius III uses 2, 10MHz 68000s, it's very possible it's programmed no better than the SNES port.

Really? Let me guess. One 68000 to run the game, the other one as a "sound CPU".

[Drew Sebastino]

Nope, it's got a Z80 for that. Pretty damn overkill, especially when you consider Sega used the same CPU configuration for After Burner...

[psycopathicteen]

I looked around and I can't find any information about it.

[Drew Sebastino]

I found that information here: https://www.arcade-history.com/?n=gradi ... ail&id=999 Also, I haven't played the game in MAME before, but it also lists what chips are used in each game.

[rainwarrior]

Grid based collision is slower than circular collision on ANY cpu.

No, it isn't.

Grid based as in, instead of the bubbles having a single bounding box, they have multiple 8x8 bounding boxes.

No, they don't.

The whole point of a grid is to avoid testing bounding boxes, but more importantly to avoid making more tests than you need to.


You test for collision with an 8x8 grid by dividing the coordinate by 8 (i.e. right shift by 3), and looking up a value stored by that index.

You test for collision with a bounding box by making 4 comparisons.

You test for collision with a circle by subtracting two coordinates, squaring two results, then adding the two squares, then comparing that against a squared radius.


There is overhead in filling up the grid when objects move across it. I presume this is the big bottleneck with the bubbles, here. However, once you have built the grid, the actual collision is fast. The trade-off is how many collision tests you have to do vs. how much time do you spend rebuilding the grid.

In this case we have a lot of bullets and a player to test for collision against all bubbles. The grid makes individual collision test very fast. A bullet doesn't have to compare against 20 circles it can just look up 1 grid value. Collide 10 bullets against 20 circles and you need to do 200 circle tests, but it would still be only 10 grid lookups. That's the point of a grid.

Building the grid is a trade-off for fast collision tests. I don't know what the update pattern for this particular grid is like, but probably the motion of bubbles is slow and each might have to update its grid only every few frames. Potentially this could be a very good solution to the problem, though evidently however they did it wasn't good enough to avoid slowdown.


I'm not going to speculate too much about what they should have done, but a grid like this is neither unusual, nor a bad technique. It's a very well known and practical kind of collision solution. Whether this particular implementation is optimal, probably not, but the grid itself is a sensible approach.

Anything could be done multiple different ways, but your suggestion to just use circle tests instead seems incredibly naive to me. I'm not going to argue too much about a hypothetical, though, I'm just here to explain the purpose of the grid. My baseline assumption is that it's still better than doing a zillion circle tests, unless there's some additional acceleration/culling structure being used here.

[Kannagi]

So doing point / circle or rectangle / circle tests on SNES is not a good idea

For my part I don't make grid, that the binary shift are numerous and make 100 * 4 binary shift and clearly not advisable.

So in my case:
1) I always display my bullets and the same for their movement (I do not distinguish between bullet on the screen and off the screen), it avoids a lot of test

2) Same for the test I do them all, (except if the Y position and $ E0 that means that my bullet and off the screen), I do about 182 test per frame (and on both frames I do all my test so a total of 364 tests)
So I have 24 bullet for the ship, 12 enemies and 76 bullet ennemy

3) What also takes me a lot of% CPU, these are also see if balls are available then I have to test my 100 balls and put them in a "pile" (so that enemies can use bullets available quickly)

4)Then you just have to optimize the tests, I think I'm at 40-50 cycles per test
But the most greedy is to display the 100 bullets especially (it takes 24% of cpu : display + movement + limit screen)

I would put a source code, if I have a little time

[koitsu]

... I don't know what the update pattern for this particular grid is like, but probably the motion of bubbles is slow and ...

That's correct.

[rainwarrior]

I've played the game. That was a bit of a run on sentence, but the probably was meant to apply to the later part, i.e. probably you don't have to update every bubble's collision grid every frame. (Whether or not the game updated them all every frame, I don't know.)

[adam_smasher]

A grid lookup is pretty fast, but it looks like they're doing it ~50 times per bubble. That's probably slower than doing one circle test, to say nothing of the grid update as they move on top of that.

All we can do is speculate, but I suspect the reason why Gradius uses the scheme it does is because the engine was only written to support grid-based collisions (because that works for 99% of cases) and when implementing the bubbles, they just used pre-existing functionality that worked instead of wasting time writing extra code.

Most people who play the slowdown free version say it's unplayably difficult anyway, so it's a little hard to say they made a bad call.

[rainwarrior]

A grid lookup is pretty fast, but it looks like they're doing it ~50 times per bubble.

No, it's the opposite. The grid lookup is 1 time per bullet and that single lookup encompasses all colliding objects at once.

They add points to the grid 50 times per big bubble, but that's not a lookup. That's a sparse-drawing problem. Drawing 50 pixels on a grid is way lighter than doing 50 collision tests. This is a completely different kind of operation. All the pixels make it a heavy operation in aggregate, but the savings comes from the lookup side where you only have to test the 1 grid cell a single bullet is inside (simultaneously testing against all bubbles at once).

The real question is whether that 50 writes to the grid is better than e.g. the 20 circle tests against every bullet you're proposing to do instead... and I'd say probably yes, but the real answer depends on very specific numbers of objects/pixels/bullets/etc. (and other implementation details) so neither of these is a winner in every situation. Also, that's still assuming the circles are drawn every frame, which they might be, but there's another opportunity there to distribute the load that really makes the grid appealing.

...they just used pre-existing functionality that worked instead of wasting time writing extra code.

A grid system like this is a very natural solution to doing many collisions at once. There are other kinds of acceleration structures for this problem (e.g. BSP trees) but a grid like this is a really common and very effective solution for 2D collision. It's not some "compromise" due to coders who don't want to write a circle-to-point collision routine, it's a reasonable solution for a hard problem. The circle collision you're proposing probably isn't a viable solution to the problem. Without an acceleration structure, you're bogged down in in too many collision tests.

And yeah, there's certainly a more complicated and very specific-to-this-level additional solution they probably could have written, grid or no grid, but my point is that the grid is not a stupid way to do this by any stretch, and a circle test is not some no-brainer miracle they just didn't think of, it comes with its own hard problems.

[psycopathicteen]

The bubbles also collide with other bubbles.