Collision Detection between 128 Objects?

Discussion of hardware and software development for Super NES and Super Famicom.

Moderator: Moderators

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

Re: Collision Detection between 128 Objects?

Post by Drew Sebastino » Mon Jul 08, 2019 6:29 pm

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: 208
Joined: Mon Jan 23, 2006 7:47 am
Location: Germany
Contact:

Re: Collision Detection between 128 Objects?

Post by creaothceann » Mon Jul 08, 2019 11:05 pm

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: 27
Joined: Sat Oct 06, 2018 10:15 am

Re: Collision Detection between 128 Objects?

Post by noyen1973 » Tue Jul 09, 2019 10:18 am

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: 1104
Joined: Fri Jul 04, 2014 9:31 pm

Re: Collision Detection between 128 Objects?

Post by 93143 » Tue Jul 09, 2019 5:57 pm

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: 208
Joined: Mon Jan 23, 2006 7:47 am
Location: Germany
Contact:

Re: Collision Detection between 128 Objects?

Post by creaothceann » Tue Jul 09, 2019 10:58 pm

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: 1104
Joined: Fri Jul 04, 2014 9:31 pm

Re: Collision Detection between 128 Objects?

Post by 93143 » Wed Jul 10, 2019 5:09 pm

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: 2901
Joined: Wed May 19, 2010 6:12 pm

Re: Collision Detection between 128 Objects?

Post by psycopathicteen » Thu Jul 11, 2019 6:03 am

What kind of algorithm did you use?

93143
Posts: 1104
Joined: Fri Jul 04, 2014 9:31 pm

Re: Collision Detection between 128 Objects?

Post by 93143 » Thu Jul 11, 2019 3:57 pm

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: 27
Joined: Sat Oct 06, 2018 10:15 am

Re: Collision Detection between 128 Objects?

Post by noyen1973 » Sat Sep 07, 2019 10:46 pm

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: 2901
Joined: Wed May 19, 2010 6:12 pm

Re: Collision Detection between 128 Objects?

Post by psycopathicteen » Sun Sep 08, 2019 8:11 am

Everybody knows the SuperFX can do it. It's more impressive seeing a 3.58 Mhz CPU pulling it off.

tepples
Posts: 21707
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Collision Detection between 128 Objects?

Post by tepples » Sun Sep 08, 2019 9:50 am

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: 1104
Joined: Fri Jul 04, 2014 9:31 pm

Re: Collision Detection between 128 Objects?

Post by 93143 » Mon Sep 09, 2019 4:42 pm

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: 2901
Joined: Wed May 19, 2010 6:12 pm

Re: Collision Detection between 128 Objects?

Post by psycopathicteen » Mon Sep 09, 2019 10:52 pm

I think this can be done in a SHMUP, if only player bullets are sorted into cells.

Post Reply