Collision Detection between 128 Objects?

The FastRom patch thread had got me thinking about this; what I'm thinking of, is a demo with 128, 16x16 blocks that bounce off the sides of the screen and change color when they overlap (trying to keep this as simple as possible). Just speculating, is there any hope this would ever run at 60fps, even with nothing else going on? (Is there a similar demo on similarly powerful hardware?) It's entirely impossible you could achieve this level of performance by checking every block against every other block, because that would end up being 128 * 127 = 16,256 comparisons...

I have heard people suggesting using sorting when dealing with huge numbers of checks, but other than the obvious problem of having to sort the bounding boxes first, I don't know how you would apply this to both axis. You could still check whatever objects overlap on the sorted axis "regularly" though, and it should still be much faster than no sorting at all.

(Also, not relevant to this particular case, but, unless I'm not thinking straight, another problem with this approach would be dealing with bounding boxes that are different sizes, as it's possible one bounding box could entirely fit inside another one on that axis, in which case you can't really determine the order.)

The only other option I'm aware of, is to break the screen into quadrants, find what bounding boxes occupy what quadrants, and only perform checks for a bounding box for what quadrants it's in. I'm not really sure what the ideal size is; too small, and you'll end up with too many instances of bounding boxes spanning multiple quadrants (and too many quadrants to look through, depending on how this is implemented I suppose), but too large, and you'll end up doing to many collision checks in each quadrant.

Does anyone know what is actually used in practice, through looking at source code, looking at / creating disassemblies, etc.?

I would do that via a grid-linked-list, either 2d if they are all the same size or 1d if they vary. However no matter what the structure was, that's probably too much for SNES to handle.

Why do you want to do that?
Well, I tried to do it because I had a free morning.

On the other hand, you can not do this in a frame, on the SNES you have about 45000 cycles / frame (and about 5000 cycles for the VBlank).
So I had to do the test on a lot of frame, so there's a little latency between the collision and the display (where if the speed is too big too).

I 1024 collision test per frame, maybe with a grid in this particular case we could only do 1024 test, but good to be honest I do not see much interest to continue, impossible to make a game with so much constraint

Screen :

I used to write physics engines for a living, and this can be a fairly endlessly difficult problem if you want a super-duper-generic-and-scalable solution.

The most important step you can do first is to split your data into separate types that don't collide. (ex: moving/non-moving, player/enemy) I've often seen people trying to implement complicated solutions to collide a player against a list of bullets. You can't really improve the speed of colliding one object against many (that's already just O(n)).

The easiest solution to implement is probably 1D sort and sweep. (Example Code) Sort the objects on the axis you think they will be most spread out on (probably horizontally). Use insertion sort as the sorting will change little from frame to frame and you'll quickly settle into an average runtime of O(n). To collide the objects, start at the beginning (ex: leftmost side) of the list, and check collisions with objects until the bounds don't overlap anymore (ex: the right side of the current object is less than the left side of the next object to be checked for collisions). If your objects are well distributed it will run in ~O(n) time, but will end up as O(n^2) if they get too bunched up. 2D sort and sweep can help with that, but isn't so trivial to implement.

Another option that might work well on the SNES is a spatial grid or spatial hash like Calima suggested. Basically split the screen up into a grid, and either directly back each of the cells with 2D array, or hash the cell coordinates into a 1D array. Each cell contains a list of objects that are in the cell. The cell size needs to be chosen experimentally, but a good place to start is 2x the size of the average object. This algorithm scales much better than 1D sort and sweep, but is a lot more work to implement correctly. While it has an average runtime of O(n), it has a HUGE constant cost which will probably make it perform poorly with fewer than thousands of objects. On the upper end, it let me kinda-realtime simulate 20,000 particles 10+ years ago on a Core2 Duo: https://www.youtube.com/watch?v=dD-um_8KqpE

The algorithm I use in Chipmunk2D nowadays is an axis aligned bounding box tree + temporal coherence tidbits. Basically a binary tree whose nodes are smaller and smaller bounding boxes, and the leaves are objects you want to collide. The tree is kept (roughly) balanced by reinserting objects when their bounds change. To keep from rebuilding the tree every frame, objects are given bounding boxes that are slightly larger than their real size and also extruded slightly in their direction of movement. These are the bounds stored in the leaves, and only need to be reinserted in the tree when the actual object exits the extended bounds. To keep from having to traverse the tree every frame to find overlapping leaves, a set of colliding pairs is maintained in a separate structure during tree insertion. So to run the collision detection, it needs update the bounds of all the objects, reinsert a few of them in the tree, and iterate the colliding pairs set. This scales really well to thousands of objects even when there is no information about their size or distribution.

Reminds me of Agenda.

It's more like 8128 comparisons, because half of the comparisons are redundant.



What about sprites that are overlapping two regions at once?

@Kannagi
I'm surprised you were able to whip up a demo so fast.

You make a rule, like "top left corner determines the cell they go in". Then if the object being checked spans two to four cells, you check objects in those cells too.

@psycopathicteen
I developed an engine for SNES with optimized function / macro
So I can easily make demos quickly ^^

Anyway, whatever the chosen algorithm, it would be necessary to sort quickly and well and to have only 8 elements on average to test for each object (or 16, but it will be necessary to perform a one test out of two).
In any case, good luck, but a manic shooter is possible without necessarily going through such an extreme test of 128 * 127

Very cool demo! I could use frame advance, but I'm lazy, what is the frame rate? I was expecting it to be really sluggish, but it looked pretty smooth (although the sprites are moving fairly slow).


Yeah; this is useless for a game, because there are too little assumptions that have to be made (all objects are the same size, objects never spawn or are destroyed, etc.) and no game would ever have to do this, but I thought this might make a good demo idea. It's impressive when you know how much work the CPU has to do, and it's also visually appealing.

I don't think collision detection beyond "check every object against every other object" is totally out of the question for the SNES though; it's not impossible you could have a 2 player shooter where you have to check 32 player projectiles against 32 enemies (or some other similar configuration) in an extreme case. Of course, there will likely still be lag no matter what you do from having to process the rest of the game. I think I like the idea of the 1D sort and sweep for something like this; that's probably right where you have to many objects for "regular" collision detection but not so many that will justify the overhead of a more advanced algorithm.

There's a lot of academic literature out there on this subject. A lot of techniques in modern use aren't that different from things you might have used 30 years ago too.

The most important concept seems to be "broad phase" vs "narrow phase". In the broad phase you do some coarse approximation of collision to collect smaller groups of objects that are close together, and then in the narrow phase you do accurate collision tests between the objects in the small group only.

I think most of the techniques for broad phase have been mentioned already, but to summarize some of them:

• "Sweep and prune" keeps sorted lists of objects on each axis (or possibly just one axis). This makes selecting nearby objects within a range quick to do, since they will be adjacent in the list.
• Grid based methods collect objects into spaces of a coarse grid.
• Tree methods divide space into a searchable tree. Nearby objects will end up sharing a common branch in the tree. (e.g. BSP, Quadtree)

All of these have tons of variations and tweaks, and each method has different useful properties. A grid approach might require a relatively large memory buffer, but selecting an element from the grid might be very fast. Trees tend to be very good for sparsely populated spaces, especially in 3D spaces where grids start to take up a ton of memory. If most of your action occurs on a single axis, a sweep and prune list for one axis can be extremely effective.

I found this powerpoint while looking for some summary I could link to. It seems to give a lot of relevant terms at least, though it is light on description of them. A good starting point reference:
https://studylib.net/doc/5711955/collis ... structures

Thanks, the demo runs at 60 FPS, but the collisions are them at 4 FPS.
So there is a certain latency between the display / movement of the bullet(60FPS) and the collisions (4FPS).

It's more feasible to do 32 bullets * 32 enemies, that's 1024 test, exactly what I can manage in one frame
If you handle collisions on 30 FPS then a game is feasible.

But personally for my shmup, I prefer this configuration:
24 bullets ship
72 bullets ennemy
12 ennemy

It's 113 sprites (and I'll have sprites for the power up / effect) so I'll have 128 sprites in total (I'm forced to use meta sprite).
And I think I can reduce the number of ship bullets to add to enemy bullets.

The per-grid-space time cost can be eliminated entirely in exchange for some small per-item time and storage cost. If items are exact-match points, each item will need to indicate whether it is the first item in its grid space as well as the identity of the next item in its grid space (if any), each non-empty grid space must identify the "first" item therein, and empty grid spaces may identify any item. Before adding an item to a grid space, check whether the item identified thereby is the first item in that grid space. If not, figure that the grid space was actually empty.

Larger items may be handled as a group of point items, or using fancier approaches, but the trick of avoiding grid re-initialization applies regardless.

Sounds kinda similar to what I do in Chipmunk's spatial hash implementation. I timestamp the cells, and if the timestep doesn't match when inserting or querying against a cell, then the list is old and added back to the pool.

For something that high on something like a SNES you might be in Recursive Dimensional Clustering territory.(See Game Programming Gems 2) the main trick is your objects don't move that fast and hence once sorted to "update" sorts are 1~2 positions, this is something say a multiplexer sort exploits. You can also keep and maintain a "needs to move X to separate" and track that number rather than do a full collision each time.

Since you have fixed size you can do a Minkowski collision on the AABB of the one you are looking at compared to the centre points of the rest to speed it up, fairly easily.

For changing colour when overlapping I would exploit hardware and enable blending modes put them on different planes and let hardware do as much as it can.

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.

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?)

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.


Do you think this method could serve as a component of a serious demo? I haven't forgotten Titan's challenge...


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.

Sure. Many demos, especially older ones, have screens like this shown with some music for a minute or more.


You also have the APU, assuming the audio doesn't take all of its processing power.

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...


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...)

What kind of algorithm did you use?

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.

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.

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

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.

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.

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