Collision Detection between 128 Objects?
Moderator: Moderators
Forum rules
- For making cartridges of your Super NES games, see Reproduction.
- Drew Sebastino
- Formerly Espozo
- Posts: 3496
- Joined: Mon Sep 15, 2014 4:35 pm
- Location: Richmond, Virginia
Re: Collision Detection between 128 Objects?
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.
-
- Posts: 611
- Joined: Mon Jan 23, 2006 7:47 am
- Location: Germany
- Contact:
Re: Collision Detection between 128 Objects?
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
Super Famicom ("2/1/3" SNS-CPU-GPM-02) → SCART → OSSC → StarTech USB3HDCAP → AmaRecTV 3.10
Re: Collision Detection between 128 Objects?
And...creaothceann wrote:Add some techno music and release it on pouet.net
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?)
Re: Collision Detection between 128 Objects?
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.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.
Do you think this method could serve as a component of a serious demo? I haven't forgotten Titan's challenge...creaothceann wrote:Add some techno music and release it on pouet.net
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...noyen1973 wrote:And...
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.
-
- Posts: 611
- Joined: Mon Jan 23, 2006 7:47 am
- Location: Germany
- Contact:
Re: Collision Detection between 128 Objects?
Sure. Many demos, especially older ones, have screens like this shown with some music for a minute or more.93143 wrote:Do you think this method could serve as a component of a serious demo? I haven't forgotten Titan's challenge...creaothceann wrote:Add some techno music and release it on pouet.net
You also have the APU, assuming the audio doesn't take all of its processing power.93143 wrote:I don't know about some of those. I've only got maybe 9% of the frame left.
My current setup:
Super Famicom ("2/1/3" SNS-CPU-GPM-02) → SCART → OSSC → StarTech USB3HDCAP → AmaRecTV 3.10
Super Famicom ("2/1/3" SNS-CPU-GPM-02) → SCART → OSSC → StarTech USB3HDCAP → AmaRecTV 3.10
Re: Collision Detection between 128 Objects?
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...
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...)
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...
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.You also have the APU, assuming the audio doesn't take all of its processing power.
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...)
-
- Posts: 3140
- Joined: Wed May 19, 2010 6:12 pm
Re: Collision Detection between 128 Objects?
What kind of algorithm did you use?
Re: Collision Detection between 128 Objects?
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.
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.
Re: Collision Detection between 128 Objects?
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.
-
- Posts: 3140
- Joined: Wed May 19, 2010 6:12 pm
Re: Collision Detection between 128 Objects?
Everybody knows the SuperFX can do it. It's more impressive seeing a 3.58 Mhz CPU pulling it off.
Re: Collision Detection between 128 Objects?
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.
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.
Re: Collision Detection between 128 Objects?
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.
If you were trying to get 128x128 collision to work in a game, a coprocessor would probably be required.
-
- Posts: 3140
- Joined: Wed May 19, 2010 6:12 pm
Re: Collision Detection between 128 Objects?
I think this can be done in a SHMUP, if only player bullets are sorted into cells.
Re: Collision Detection between 128 Objects?
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:
(this is a 256-colour image, so you can use Mode 3 for a nice background, converted using Rilden's Tiled palette quantization tool)
(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.
Re: Collision Detection between 128 Objects?
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.
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.