Donkey Kong Country LOTS of sprites?

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.
turboxray
Posts: 348
Joined: Thu Oct 31, 2019 12:56 am

Re: Donkey Kong Country LOTS of sprites?

Post by turboxray »

93143 wrote: Fri May 20, 2022 4:41 am Sure.

Just to reiterate: the actual hard part here is the collision routine: each of the 128 sprites has to know if it's overlapping any of the other 127 sprites, and this happens 60 times per second. It was all I could do to get all the processing to finish in about 90% of a frame. Without the collision routine, the much simpler task of bouncing 128 16x16 sprites around on the screen is in no way challenging for the hardware.
Heh! In my algorithms I class, we used a dynamic quadtree to solve this with space partitioning. And early opt out (if collision happens, flip/turn-on but don't bother checking against the rest in the space.. for an n(n+1)/2 'ish runtime inside that node space). Did you do something different?
93143
Posts: 1717
Joined: Fri Jul 04, 2014 9:31 pm

Re: Donkey Kong Country LOTS of sprites?

Post by 93143 »

That sounds somewhat similar to what I did. I'll quote myself:
93143 wrote: 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.
There had been a discussion about grid-based collision methods, and when the topic of 128x128 collision came up, I decided to try it. I won't guarantee that my method is the fastest possible, but it's enough for 60 fps.
Post Reply