Collision Detection between 128 Objects?

Discussion of hardware and software development for Super NES and Super Famicom. See the SNESdev wiki for more information.

Moderator: Moderators

Forum rules
  • For making cartridges of your Super NES games, see Reproduction.
User avatar
Drew Sebastino
Formerly Espozo
Posts: 3496
Joined: Mon Sep 15, 2014 4:35 pm
Location: Richmond, Virginia

Re: Collision Detection between 128 Objects?

Post by Drew Sebastino »

Wow... What framerate is the collision detection happening at? Even after slowing down BSNES, I never saw any instances where the boxes where in the wrong state.
creaothceann
Posts: 611
Joined: Mon Jan 23, 2006 7:47 am
Location: Germany
Contact:

Re: Collision Detection between 128 Objects?

Post by creaothceann »

Add some techno music and release it on pouet.net ;)
My current setup:
Super Famicom ("2/1/3" SNS-CPU-GPM-02) → SCART → OSSC → StarTech USB3HDCAP → AmaRecTV 3.10
noyen1973
Posts: 32
Joined: Sat Oct 06, 2018 10:15 am

Re: Collision Detection between 128 Objects?

Post by noyen1973 »

creaothceann wrote:Add some techno music and release it on pouet.net ;)
And...
1. Graph a bar representing the number of collisions
2. Some kind of audio representing the number of collisions (volume?/pitch?)
3. Colour each sprite based on speed and cycle through shades of each colour incrementing on collision
4. Add a scrolling message.
And if you still have enough time left...
5. Do it all in mode 7 with an image moving around in the background. (Maybe not possible with the scroller unless split screen?)
93143
Posts: 1717
Joined: Fri Jul 04, 2014 9:31 pm

Re: Collision Detection between 128 Objects?

Post by 93143 »

Drew Sebastino wrote:Wow... What framerate is the collision detection happening at? Even after slowing down BSNES, I never saw any instances where the boxes where in the wrong state.
The whole thing is 60 frames per second. Compute time varies between frames, of course, but I've never seen it with fewer than about 23 scanlines free between wai and NMI. The method should be fairly resistant to load spikes caused by uneven clustering, and it doesn't care how fast the objects are moving.
creaothceann wrote:Add some techno music and release it on pouet.net ;)
Do you think this method could serve as a component of a serious demo? I haven't forgotten Titan's challenge...
noyen1973 wrote:And...
I don't know about some of those. I've only got maybe 9% of the frame left. Scrollers and Mode 7 are one thing; adding operations to the inner collision loop is another... I suppose it might work, but it's hard to say without coding the logic and checking...

I do have a few ideas of my own on how to enhance the presentation - let's just say HDMA is cheap - but I'm pretty busy in real life so none of this is likely to happen soon.
creaothceann
Posts: 611
Joined: Mon Jan 23, 2006 7:47 am
Location: Germany
Contact:

Re: Collision Detection between 128 Objects?

Post by creaothceann »

93143 wrote:
creaothceann wrote:Add some techno music and release it on pouet.net ;)
Do you think this method could serve as a component of a serious demo? I haven't forgotten Titan's challenge...
Sure. Many demos, especially older ones, have screens like this shown with some music for a minute or more.
93143 wrote:I don't know about some of those. I've only got maybe 9% of the frame left.
You also have the APU, assuming the audio doesn't take all of its processing power.
My current setup:
Super Famicom ("2/1/3" SNS-CPU-GPM-02) → SCART → OSSC → StarTech USB3HDCAP → AmaRecTV 3.10
93143
Posts: 1717
Joined: Fri Jul 04, 2014 9:31 pm

Re: Collision Detection between 128 Objects?

Post by 93143 »

I should probably post the source code at some point.

There are a number of other ideas I've dreamed up that could be fun to put in a demo. If I had all the free time, I'd love to cooperate on one. Unfortunately I do not, at the moment...
You also have the APU, assuming the audio doesn't take all of its processing power.
Unfortunately the APU is so isolated and so hard to talk to that it's not useful for many types of tasks. It can't access ROM, it can't manipulate the PPU, and it can't rapidly share data or do fine-grained multiprocessing with the CPU.

I suppose one could send and receive data with HDMA. My proposed method (assuming it works) should be adaptable to permit APU->CPU transfers, and gives you a practical maximum rate of around 800 bytes per frame at the cost of no more than several scanlines on the CPU side. But of course that would take most of the SMP's compute time just working the I/O ports, leaving very little for music. And it's entirely possible that you'd want to use a fair chunk of that bandwidth to feed the DSP, so you could still end up with a heavy I/O load even if whatever processing task you're offloading doesn't require that much data throughput.

So I guess it depends on what exactly is going on.

(I'm starting to want to try something with the APU...)
psycopathicteen
Posts: 3140
Joined: Wed May 19, 2010 6:12 pm

Re: Collision Detection between 128 Objects?

Post by psycopathicteen »

What kind of algorithm did you use?
93143
Posts: 1717
Joined: Fri Jul 04, 2014 9:31 pm

Re: Collision Detection between 128 Objects?

Post by 93143 »

It's based on the grid idea, using an 8x7 grid of 32x32-pixel cells. It assigns each sprite to one grid cell based on its position. Then it goes through the sprite list again, removing each sprite from its assigned cell and then doing box-point collision against any remaining sprites in cells where they could possibly collide with the current sprite. If a collision is detected, both sprites are lit.

The anti-clustering mechanism takes advantage of the Boolean nature of the collision response. If a sprite is already lit when the main loop reaches it, the whole procedure is skipped for that sprite, because it doesn't care if it collides with any more sprites, but it is not removed from its assigned cell because other non-lit sprites do care if they collide with it. The result is that if all 128 sprites are on top of one another, the number of collision checks is best-case instead of worst-case.

This procedure got me within about 15% of a solid 60 fps. What put me over the line was unrolling all fixed-length loops. (This necessitated a bump to HiROM and very nearly another bank - the ROM as posted has 159 bytes free). Fortuitously, the unrolling caused the inner collision loop to no longer run out of index registers, which sped it up dramatically and left me with a credible margin of free compute time.
noyen1973
Posts: 32
Joined: Sat Oct 06, 2018 10:15 am

Re: Collision Detection between 128 Objects?

Post by noyen1973 »

Could the collision detection be handed over to the SuperFX and then use WRAM to maintain the sprite XY coordinates and collision status? The SNES CPU would only update the coordinates and check the collision status for each sprite to perform the appropriate task.
psycopathicteen
Posts: 3140
Joined: Wed May 19, 2010 6:12 pm

Re: Collision Detection between 128 Objects?

Post by psycopathicteen »

Everybody knows the SuperFX can do it. It's more impressive seeing a 3.58 Mhz CPU pulling it off.
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Collision Detection between 128 Objects?

Post by tepples »

That and if you do finish an original game (as opposed to a fan-made port of a notable danmaku shmup without an announced license), I doubt you're going to find any new-old-stock Super FX chips anywhere or even enough pulls to make cartridges for your backers.

To speed up the search for nearby objects, use sorting in 1D or sectors in 2D. But in a shmup, so long as each enemy bullet can collide only with the player and each enemy ship can collide only with the player or a few bullets, you won't get to the O(n^2) complexity problem.
93143
Posts: 1717
Joined: Fri Jul 04, 2014 9:31 pm

Re: Collision Detection between 128 Objects?

Post by 93143 »

Some of the fancier suggested stuff that relies on enumerating unique encounters and tracking each contact between frames might become feasible at a solid 60 fps on a Super FX. But I don't think (before trying) that it would be a real challenge for the Super FX, even with the slow RAM reading. For a demo, you'd want to combine it with something else.

If you were trying to get 128x128 collision to work in a game, a coprocessor would probably be required.
psycopathicteen
Posts: 3140
Joined: Wed May 19, 2010 6:12 pm

Re: Collision Detection between 128 Objects?

Post by psycopathicteen »

I think this can be done in a SHMUP, if only player bullets are sorted into cells.
SNES AYE
Posts: 201
Joined: Mon Nov 07, 2022 11:28 am

Re: Collision Detection between 128 Objects?

Post by SNES AYE »

93143 wrote: Tue Jul 09, 2019 5:57 pm Do you think this method could serve as a component of a serious demo? I haven't forgotten Titan's challenge...
I'm curious, did you ever turn this into a serious demo as mentioned above?

If not, I'm sure people could suggest various ideas to make it look like something visually compelling, such that even casuals would immediately understand something rather impressive is happening on-screen here.

For example, how about adding in some night background scene and then making the objects a bunch of fireflies that light up when they collide with other fireflies:
Fireflies.png
(this is a 256-colour image, so you can use Mode 3 for a nice background, converted using Rilden's Tiled palette quantization tool)
Fireflies.rar
(1.61 MiB) Downloaded 19 times
(a quick example. It's only in Game Maker as I can't program for SNES)

Feel free to use if you want.

I think something like that could look cool as an example. It's functionally the same as what you already have basically, but just quicker/easier for people to understand at a glance what's happening. :)
93143
Posts: 1717
Joined: Fri Jul 04, 2014 9:31 pm

Re: Collision Detection between 128 Objects?

Post by 93143 »

I haven't done anything. I've been too busy to devote much time to my hobbies, and I've recently been working on a different project (nearly done).

However, I do have some ideas. Yours is interesting, but I was going to go in a different direction, adding in some other ideas that look visually impressive and/or computationally intensive, with a more abstract/surreal aesthetic similar to what it has now. There's not much CPU time left, but as creaothceann pointed out, the APU is free, and HDMA is cheap...

I should probably also slow down the sprites a bit. At this speed, it's extra clear that it's running at 60 fps, but it creates a slightly unpleasant swarming impression and it's hard to see what's going on without pausing the emulation.

...

I've got a bit of a list of things that could be done in a demo. Most of them are still at least partly theoretical, some with nontrivial algorithmic requirements on the offline data preparation side, and I need to carve out some time to actually prove them out.
Post Reply