Collision Detection too slow

[Punch]

I need help with collisions. Perhaps mine was too generic and unoptimized, or maybe processing 16^2 sprites is too much regardless of algorithm. But I think that taking 70166 cycles to update all objects, 12 running collision detection against everyone else, is kind of excessive. How many cycles per frame does a NES have? 30.000? And that's just for METASPRITES!

I just want some benchmarks so I can aim to a realistic result. A metasprite has 1 or more boxes, and my collision detection code checks ALL of them in a pair of metasprites until it finds a collision.

Here's the code if you insist in seeing it: https://gitlab.com/aleff/BrixBattle/blo ... lision.asm
Yes it is very large.

Since I'm not sure if I'll really need multiple bounding boxes per metasprite, I think I'll just scrap the whole function and write another one for 1 to 1 overlap check. I'm also not limiting collision between groups (pretty sure I don't need projectiles colliding with each other).

I might fall back to that function if I make a large boss or something that makes having multiple objects to represent a single one for collision detection too excessive. I figure this won't be a problem with some objects I want to write (snake-like objects can just run AI on the head object and the body "links" can just perform 1 box overlap verification against projectiles, for example). But I'm still worried that it might still be too slow since everything relies on table reads. Hopefully I won't need 16 objects at once if that happens

[tepples]

Groups can provide a big speedup.

There are two kinds of moving thing in The Curse of Possum Hollow: actors (maximum 6) and bullets (maximum 12). The player is an actor and collides with powerups and enemies (also actors), as does the player's fist during attack frames. The only time enemies collide with enemies is if they've been thrown, such as a crate or a severed zombie head, and there's only one of those active at once. Bullets can be set to collide with the player, with enemies, or with neither (such as the bullets used for some enemies' spawn and faint animations).

The most time-consuming thing in that game's engine is in fact walking, which has to read the list of platforms in order to process walls and floors above the level's lowest floor.

[koitsu]

How many cycles per frame does a NES have? 30.000?

You have ~2387 CPU cycles per VBlank (for NTSC), but this estimates the usable time to be more along the lines of ~2250 CPU cycles.

If you meant time *outside* of VBlank (i.e. during scanlines 0 to 239), from this we can determine the math: 240 scanlines * 113.666 CPU cycles per line = ~32078 CPU cycles. Again, this is for NTSC.

[Punch]

How many cycles per frame does a NES have? 30.000?

You have ~2387 CPU cycles per VBlank (for NTSC).

Edit: didn't saw what you added, yeah I'm looking for the total # of cycles, not just vBlank. Thankfully it's not just 2387.

Groups can provide a big speedup.

There are two kinds of moving thing in The Curse of Possum Hollow: actors (maximum 6) and bullets (maximum 12). The player is an actor and collides with powerups and enemies (also actors), as does the player's fist during attack frames. The only time enemies collide with enemies is if they've been thrown, such as a crate or a severed zombie head, and there's only one of those active at once. Bullets can be set to collide with the player, with enemies, or with neither (such as the bullets used for some enemies' spawn and faint animations).

The most time-consuming thing in that game's engine is in fact walking, which has to read the list of platforms in order to process walls and floors above the level's lowest floor.

I hope it improves the situation as much as improved yours. Come to think about it, maybe I shouldn't be too worried with the number of projectiles on screen. My "balls" interact strongly with the background, and the only sprite to sprite collision I can think of is:
-Regular Ball to Paddle and Background and Multi-Sprite Object
-Special Ball to Paddle and Background and Multi-Sprite Object
-Multi-Sprite Object to Paddle and Background
(The game is kind of an breakout+pong mix, with different block types and special projectiles that the player can earn)

I haven't thought too much about the game's design yet but I feel like too many regular balls would be confusing during play, special balls would be even more limited and multi-sprite objects would definitely be spawned ONE PER PLAYER and not be overly complex. I could even limit the multi-sprite object to be used just by an enemy boss so that CPU cost is more predictable.
Guess I'm looking roughly for:

Code: Select all

ball background checks -> 0 to 8 (8 bullet max, 4 per player, 1~2 per player under normal circumstances)
Sp ball background checks -> 4 (2 per player max)
Multi-Sprite background checks -> 2 * (1 to z, z = number of bounding boxes in MultiSP object)

ball sprite checks -> 2 + number of multi-sprite object bounding boxes
Sp ball sprite checks ->  2 + number of multi-sprite object bounding boxes
Multi-Sprite sprite checks -> 2.

So the worst case is 12 + 2z grid checks, 2*8 +2*4 + 2*1 + 2z = 2z + 26 sprite checks. And that's the worst case, I'm sure a regular NES game would be expected to slow down with so much stuff on screen.

To improve performance I can do a Y-pos based early check to remove some sprite checks, since the "paddles" stay at a fixed y position. I can also eliminate all player projectiles when the player uses a multi-sprite object to relieve the CPU (and the opposing player) of processing time.

I feel like I shoud have thought about the game's design more seriously...

[tomaitheous]

If the projectiles move one pixel at a time, you can cheat this; do certain collision detections on the next frame if you run over your allotted time limit. Or just assign certain collisions to always be done across two frames, while others are done in a single frame. I'm pretty sure there are some NES games that do this.

[psycopathicteen]

What does "TZP16" mean? Never seen it being used in asm code before.

[tokumaru]

What does "TZP16" mean?

A macro, maybe? Apparently it's used to create pointers in zero page.

[Punch]

What does "TZP16" mean? Never seen it being used in asm code before.

Err sorry, it's a macro, and in fact a quite large one. I was just tired of having to write it over and over.
I wasn't expecting anyone to inspect my code to be honest The code was written in a hurry and there's wasteful stuff all over it that I neglected, I just wanted to have a functional prototype quick.

Code: Select all

;Copies address from table to zero page
;TZP16(<Target, TableAddr)
 .macro TZP16
 .if (\# != 2)
	.fail
 .endif
	ASL A ;2-byte table index
	TAY
	BCS .sec\@ ;Slot 128 to 255 = index Y overflows
	
 .fst\@: ;Entry 0 to 127 chosen
	LDA \2, y
	STA <\1
	LDA \2 + 1, y
	STA <\1 + 1
	JMP .exit\@
 .sec\@: ;Entry 128 to 255 chosen; add $100 to compensate overflow
	LDA \2 + $100, y ;Loads pointer from table
	STA <\1 ;Saves pointer on zero page
	LDA \2 + $100 + 1, y
	STA <\1 + 1
 .exit\@:
	.endm

The table is just your usual sequence of .dw LABEL for pointer entries. I don't like indirection but I don't know another way of doing it. I also don't like how I duplicate code to avoid overflow when multiplying the index by two but I think that it is better than having to write the LOW and HIGH bytes from the addresses in separate places on the ROM.

The PHX PHY PLX PLY INC16 "instructions" are also macros. The first four are actually available as real instructions on the C6280A, shame that the original 6502 doesn't have it.

@tomaitheous I'll investigate about collision test postponing. I wanted to have movement with subpixel precision for the projectiles so I'm not sure if that would work out well.

[Sumez]

It's very rare in an NES game that you have a lot of objects that are all able to collide with eachother. Off the top of my head I actually can't think of any that do it. Usually, the worst case situation you'd have in a conventional 8bit action game is if you are able to fire a lot of projectiles at once, and all of them have a chance of colliding with the enemies. Thinking about this, it's probably not a coincidence that almost every 8bit title limits the player to 3 shots on screen at a time, causing interesting rapid-fire potential by pointblanking enemies, like you'll often see in Mega Man, Gradius, etc.

So while there's a lot of potential optimization to be done by grouping "collidable" objects in separate areas, there's usually more to gain by rethinking your business logic and avoiding unnecessary collision checks. First of all, if you have a large scrolling stage, are you calculating collisions for objects that aren't even visible? And if you are, how much would you really lose by removing those from the equation compared to the potential performance gain?
You also need to decide whether you really need subpixel precision on your collisions? Players definitely won't be able to see it, and if you could convert all your coordinates to 8bit values, that should also make comparisons much faster.
Of course this all depends on the design of your game, and there is never a single good solution. The NES DOES have a lot of limitations, but as long as you keep them in mind, you can usually design your game around it.

If the projectiles move one pixel at a time, you can cheat this; do certain collision detections on the next frame if you run over your allotted time limit. Or just assign certain collisions to always be done across two frames, while others are done in a single frame. I'm pretty sure there are some NES games that do this.

Definitely a lot of NES games that do this, and if you implement it well, it can be a really good solution - SMB at least is famous for only detecting harmful collisions at some frames.
As a general rule of thumb, you probably want to give your collisions a priority based on whether they are harmful or beneficial to the player, or the risk (and consequence) of items passing "through" eachother.


Most recently I noticed this practice in a Super Nintendo game. In Super Ghouls n Ghosts stage 5, near the checkpoint, ice tendrils start growing from the ground, and twisting in various directions.

Not only are their formations random, they obviously can't have completely square hitboxes, so to accurately detect collisions, each joint needs to detect separately. Even though only three tendrils can be spawned at a time, this suddenly requires a lot of collision detection, so what I suspect the game of doing, is only checking collisions on one joint per frame, moving an internal counter for each time collision is checked. On a tendril with ten joints, this means the player won't be able to stay inside any spot in a tendril for more than 10 frames, ie. ~167ms, which is still short enough for it to not be an issue, considering the slow pace of the game.
It does create some awkward situations where you think you're somehow standing in a safe space, only to get killed off a fraction of a second later. Of course, if the detection was done "properly", you'd be dead anyway, so it's still a preferable solution compared to excessive slowdown, which other parts of the games suffers heavily from.

[hackfresh]

Tecmo Super Bowl which has a lot of potential collisions (11 on 11 football)...does the following.

1. It checks if players are close to collision via a larger bounding box. If not they are marked as not close and then when that player is checked it can easily be dismissed saving going through other checks.

2. It checks 2 offensive players per frame vs all possible defenders.

3. It checks the Y direction first since players are more likely to be farther apart in that direction.

4. Players can't collide with players on their own team unless they run into an existing collision.


There is a very very slight chance for players to "ghost" through each other if a player is moving fast enough. You need two pretty fast players for this to happen and it needs to line-up perfectly.

[rainwarrior]

Most recently I noticed this practice in a Super Nintendo game. In Super Ghouls n Ghosts stage 5, near the checkpoint, ice tendrils start growing from the ground, and twisting in various directions.

(image)

Not only are their formations random, they obviously can't have completely square hitboxes, so to accurately detect collisions, each joint needs to detect separately. Even though only three tendrils can be spawned at a time, this suddenly requires a lot of collision detection, so what I suspect the game of doing, is only checking collisions on one joint per frame, moving an internal counter for each time collision is checked. On a tendril with ten joints, this means the player won't be able to stay inside any spot in a tendril for more than 10 frames, ie. ~167ms, which is still short enough for it to not be an issue, considering the slow pace of the game.
It does create some awkward situations where you think you're somehow standing in a safe space, only to get killed off a fraction of a second later. Of course, if the detection was done "properly", you'd be dead anyway, so it's still a preferable solution compared to excessive slowdown, which other parts of the games suffers heavily from.

I think these tendrils just go into the tiled collision map and act like solid ground tiles. Projectiles collide with these tendrils and there's no apparent delay from that collision; projectiles are fast and collide at consistent locations.

They may very well have separate hurtboxes for the player, but I don't see any evidence that it's trying to distribute the load across frames; the collisions seem accurate and responsive. (Also that section is quite susceptible to slowdown.) A pile of tests like that against just the player don't really seem like "a lot" for an SNES game to me.

[gauauu]

do certain collision detections on the next frame if you run over your allotted time limit.

Is there any easy way to track a time limit (ie some trick with the timer at $4017?), or is it just a matter of keeping track of how many comparison's you've done, and doing the math to know how long that's taken?

[tepples]

Many games just overflow the frame time and tell the NMI handler not to process video memory updates. This leads to old-fashioned slowdown.

A few games, such as Gradius, actually estimate how much CPU time they have used and defer further work to the next frame. Gradius does that because it's trying to make a bottom status bar without any sort of programmable interval timer on the cartridge, and missing the sprite 0 hit would cause the status bar to shake. Later mappers, in particular MMC3, incorporate an interval timer to count scanlines and trigger raster splits without needing constant attention from the CPU.

[gauauu]

So I guess the answer is no, no easy way to track it.

Makes me miss the timer in the RIOT chip on the Atari.....

[tokumaru]

If you have sprite 0 free, you could set up a hit near the bottom of the screen and periodically check whether the hit has happened. Once it happens, you know you don't have much time left, so you may skip some tasks and finish the mandatory calculations before vblank starts, if you really want to avoid typical lag frames.