This page is a mirror of Tepples' nesdev forum mirror (URL TBD).
Last updated on Oct-18-2019 Download

Collision Detection too slow

Collision Detection too slow
by on (#182910)
:shock:

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 :lol:
Re: Collision Detection too slow
by on (#182912)
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.
Re: Collision Detection too slow
by on (#182913)
Punch wrote:
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.
Re: Collision Detection too slow
by on (#182915)
koitsu wrote:
Punch wrote:
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.

tepples wrote:
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:
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... :lol:
Re: Collision Detection too slow
by on (#182936)
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.
Re: Collision Detection too slow
by on (#182950)
What does "TZP16" mean? Never seen it being used in asm code before.
Re: Collision Detection too slow
by on (#182951)
psycopathicteen wrote:
What does "TZP16" mean?

A macro, maybe? Apparently it's used to create pointers in zero page.
Re: Collision Detection too slow
by on (#182953)
psycopathicteen wrote:
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 :mrgreen: 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:
;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.
Re: Collision Detection too slow
by on (#182959)
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.

tomaitheous wrote:
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.
Attachment:
tendrils.PNG
tendrils.PNG [ 350.87 KiB | Viewed 3331 times ]

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.
Re: Collision Detection too slow
by on (#182967)
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.
Re: Collision Detection too slow
by on (#182969)
Sumez wrote:
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.
Re: Collision Detection too slow
by on (#182971)
tomaitheous wrote:
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?
Re: Collision Detection too slow
by on (#182972)
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.
Re: Collision Detection too slow
by on (#182974)
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.....
Re: Collision Detection too slow
by on (#182975)
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.
Re: Collision Detection too slow
by on (#182977)
If you want to start a quiet RIOT, you can use $4010 and $4013 as a crude timer. It's a RIOT in that you get an IRQ notifying you that time has passed, but it's quiet because you won't be able to play sampled sound in the background.
Re: Collision Detection too slow
by on (#182979)
Tepples: Nice :lol:

I meant knowing what your game logic can handle per frame, and using that regulate the max number of colisions for whatever objects for this frame, and the rest get queued for the next frame. Split it up however you want, but as someone else mentioned - certain collisions should have priority (player to map interface would be one) so they can be finished in one frame. But be careful, if the original queue overflowed to the next frame, and even just one from that queue overflowed to the following frame, I would stall game logic at that point and get it done. Because while roughly 1-2 pixel difference off from collision accuracy (due to a frame delay in logic relative to speed of object) might not be detectable by the player, anything larger than that probably will be detectable.

So, some game logic always runs 60fps (or every frame, to be more accurate), and some mitigates between every other frame and every frame (or is always assigned even or odd frame logic; either works). It won't guarantee you won't run into slowdown, but you'll reduce it and at the same time giving the appearance that everything is running 60 fps smooth - or done on every frame.

I've actually never done this in my own stuff. But I've noticed some games appeared to do this, and no one ever mentions anything about it - ignorance is bliss.
Re: Collision Detection too slow
by on (#182981)
I noticed that most of his code is spent looking up "collision box data" and setting everything up to do the collision detection.
Re: Collision Detection too slow
by on (#182984)
psycopathicteen wrote:
I noticed that most of his code is spent looking up "collision box data" and setting everything up to do the collision detection.

I avoid this by indexing my collision boxes (up to 256 sets of top+bottom+left+right offsets from an object's hotspot), and having a field in each object's RAM indicating what box it's currently using.

My collision routine takes the indices of 2 objects in registers X and Y, so it can quickly subtract/compare their coordinates. If the distance between them is over 256 pixels, I don't even do anything else. If it's smaller than 256, that means I can do the next calculations using 8-bit math, which is a plus. I then subtract the relevant edges (either left and right or top and bottom, depending on the axis being tested) of each object's box from the distance, and a negative result means the objects are overlapping. Objects have to overlap in both axes to register a collision.

With this method I believe I'm saving some CPU time, mostly because I don't need to mess with pointers, and because part of the math can be done in 8-bit.
Re: Collision Detection too slow
by on (#182987)
psycopathicteen wrote:
I noticed that most of his code is spent looking up "collision box data" and setting everything up to do the collision detection.

Oh wow, you're right.


Punch: That looks waaaaay over kill. What are you trying to do? (Something out of the norm?)

Why are you doing position translations of all corners? ;Obj2.x1 + Obj2.Posx

What is OBJ_COLLISION, x and what is OBJ_METASPRITE, x ? Are these projectiles? Destructible player objects? Enemy projectiles? Enemy objects?
Re: Collision Detection too slow
by on (#182988)
If you're dealing with object tables, it seems natural to just use register X for everything, then you have parallel arrays (one array for X low byte, one array for X high byte, etc...) that can all be indexed with just X or Y.
Re: Collision Detection too slow
by on (#182990)
I spent the day trying to code something better, and since I dropped the "multiple boxes per metasprite" requirement, I did just as tokumaru said. No more indirection for what I'm doing, at least. It's buggy and not working properly but I'll see what I can do tomorrow.

Compare the old collision table with the new one:
Old: https://gitlab.com/aleff/BrixBattle/blo ... lision.txt
New: https://gitlab.com/aleff/BrixBattle/blo ... lision.txt

Way simpler huh? This is the new collision code: https://gitlab.com/aleff/BrixBattle/blo ... lision.asm . Less stupider. :lol:

tomaitheous wrote:
psycopathicteen wrote:
I noticed that most of his code is spent looking up "collision box data" and setting everything up to do the collision detection.

Oh wow, you're right.


Punch: That looks waaaaay over kill. What are you trying to do? (Something out of the norm?)

Why are you doing position translations of all corners? ;Obj2.x1 + Obj2.Posx

What is OBJ_COLLISION, x and what is OBJ_METASPRITE, x ? Are these projectiles? Destructible player objects? Enemy projectiles? Enemy objects?


It is now that I think about it. The translations are done because the center of the object is arbitrary, it's not always the left corner of the sprite. See https://gitlab.com/aleff/BrixBattle/blo ... r/anim.txt for the format.

OBJ_COLLISION is a byte for registering which object from the list is currently colliding with the object. I might think of something better later but that will do for now.
OBJ_METASPRITE is the metasprite id for the object. One metasprite is paired with one or more bounding boxes. (now just one box per metasprite)
The objects can be anything, from projectiles to enemies to players to static sprites to anything really. They all have the same attributes for now since I have lots of free RAM.
Re: Collision Detection too slow
by on (#182991)
Double post: I wanted to implement this code: http://atariage.com/forums/topic/71120- ... ?p=1054049 but I can't figure out how it works. Anyone knows and wants to do an explanation of it?
Re: Collision Detection too slow
by on (#182992)
I suppose this would work, but this one only compares X, you would still need to check Y. I'm not convinced that it would be more efficient, but it's possible.

Code:
lda xpos1 ; x position, object 1
  sbc xpos2 ; x position, object 2 (without sec ??)
;the comment says n-1, perhaps you should clc first
  sbc #SIZE2-1 ;width of object 2(-1)
  adc #SIZE1+SIZE2-1 ;width of object 1+object2(-1)
; Carry set if overlap


I feel like there would be overhead for calculating sizes, therefore, not more efficient.
Re: Collision Detection too slow
by on (#182997)
Did anyone actually do that thing where you check your frame timing to see if you need to delay certain routines until the next frame?
I've heard it mentioned several times before, and I know some commercial games do it, but to me it just sounds incredibly flaky... At least when it affects logic as critical to gameplay as collisions.

As I said in my previous post, apart from optimizing your algorithms and indexing your data, etc. the most effecient thing you could do, should always be building your game logic around what you know you can "afford", and how much stuff you're actually expecting to happen. If you're planning to often have 10 or more enemies on screen at the same time, your collision detection should be able to handle all of them, and if you need to spread collisions of certain objects between multiple frames in order to handle them all, I would personally prefer to do this unconditionally, rather than depending on whether your program is "running slow".
Checking if you need to delay some collisions to the next frame would add extra overhead to your code even when it's not relevant, and certainly allows for more bugs and erratic behavior, making testing more cumbersome.

I guess what I'm getting to is that if your program has special features that allows it to handle critical situations with a lot of action going on, it should be able to handle it well enough that it might as well do the same thing when nothing much is going on? Maybe I'm just being judgmental, but it sounds like bad design to me. :)
Re: Collision Detection too slow
by on (#182999)
Quote:
Did anyone actually do that thing where you check your frame timing to see if you need to delay certain routines


Yes. Imagine that you do something as simple as update colors, which needs to be done during v-blank. Now imagine your game does some loading of information at some boundary (you crossed a room). Ok, the game will load all the information, which pushes the frame to the end of the next v-blank. You get to the color writing function, and instead of changing colors, you write junk tiles at the top of the screen. This scenario is easy to imagine for me, so I have to handle it by waiting till the next v-blank happens before writing those colors. Which is slow-down.

Super Mario Bros swaps colors of coins every frame. When too many hammers are on screen, which only happens rarely, it skips tons of frames, so it won't screw up timing on coin colors writes. I guess they didn't catch that in play testing, or maybe they would have limited the number of hammers. But, the programmers understood the importance of timing PPU writes.
Re: Collision Detection too slow
by on (#183009)
Wait? That doesn't make any sense? Updating the palette only takes writing 3 bytes. Does SMB manually write bytes to OAM instead of using sprite DMA?
Re: Collision Detection too slow
by on (#183012)
psycopathicteen wrote:
Does SMB manually write bytes to OAM instead of using sprite DMA?

No. Manual OAM updates are almost useless on hardware due to the DRAM decay. (I don't know of any games that use it, but I'm sure some exist. Not SMB though. Micro Machines polls $2004, but it doesn't use it to update sprites.)
Re: Collision Detection too slow
by on (#183013)
rainwarrior wrote:
No. Manual OAM updates are almost useless on hardware due to the DRAM decay. (I don't know of any games that use it, but I'm sure some exist. Not SMB though. Micro Machines polls $2004, but it doesn't use it to update sprites.)

RC Pro Am apparently does things... interestingly. Some other games, like Trojan (Tatakai no Banka) and Huge Insect do something even more odd (that's for $2003 though, but the point stands).

The short of it: NES OAM is a weird quirk-filled beast.
Re: Collision Detection too slow
by on (#183014)
rainwarrior wrote:
Micro Machines polls $2004, but it doesn't use it to update sprites.

I believe Super Cars does it too, to time a raster effect near the top of the screen.
Re: Collision Detection too slow
by on (#183023)
Punch wrote:
I spent the day trying to code something better, and since I dropped the "multiple boxes per metasprite" requirement, I did just as tokumaru said. No more indirection for what I'm doing, at least. It's buggy and not working properly but I'll see what I can do tomorrow.

Compare the old collision table with the new one:
Old: https://gitlab.com/aleff/BrixBattle/blo ... lision.txt
New: https://gitlab.com/aleff/BrixBattle/blo ... lision.txt

Way simpler huh? This is the new collision code: https://gitlab.com/aleff/BrixBattle/blo ... lision.asm . Less stupider. :lol:

tomaitheous wrote:
psycopathicteen wrote:
I noticed that most of his code is spent looking up "collision box data" and setting everything up to do the collision detection.

Oh wow, you're right.


Punch: That looks waaaaay over kill. What are you trying to do? (Something out of the norm?)

Why are you doing position translations of all corners? ;Obj2.x1 + Obj2.Posx

What is OBJ_COLLISION, x and what is OBJ_METASPRITE, x ? Are these projectiles? Destructible player objects? Enemy projectiles? Enemy objects?


It is now that I think about it. The translations are done because the center of the object is arbitrary, it's not always the left corner of the sprite. See https://gitlab.com/aleff/BrixBattle/blo ... r/anim.txt for the format.

OBJ_COLLISION is a byte for registering which object from the list is currently colliding with the object. I might think of something better later but that will do for now.
OBJ_METASPRITE is the metasprite id for the object. One metasprite is paired with one or more bounding boxes. (now just one box per metasprite)
The objects can be anything, from projectiles to enemies to players to static sprites to anything really. They all have the same attributes for now since I have lots of free RAM.


Is there any particular reason why you need center points?

As far as collision design goes, I think it should be tailored specifically to your game. If enemies collision don't affect one another, or enemy bullets don't affect other enemies - then don't check for them. In other words, have multiple collision routines. For instance, I have one that checks player projectiles only with enemies and their bullets. It doesn't check enemy projectiles against other enemy projectiles or other enemies (unless they are supposed to be destructible, but then I have them as spawns "enemies" rather than projectiles), and I don't check collision with other friendly projectiles or the player (or other player objects). In other words, I don't check for friendly fire collisions.

I also tend to avoid center point positions for objects, because if you have to cycle through all those objects more than once, then you have the overhead of translating them into a box every time. But then again, that depends on the design of your game. You might have no projectiles and only the player to check collision against (no attacks, only dodging).

Anyway, the idea is to remove redundancy in the collision routines. And like others have said, best to avoid using indirection of you can.

Also, since this is 65x related - I'm gonna post this here (I'm surprised sik didn't post this)
Quote:
Sik, on another forum, brought up a method he uses for his game logic on his work (Genesis). He uses a center coord system. So you only have Ax, Ay, and width/height. The compare logic is as follows; if [Ax-Bx]<= ((AxWidth+BxWidth)/2) then check Y. Although, he doesn't use the absolute value of Ax-Bx. If the value is negative, he uses the negative of (AxW+BxW)/2 as the compare. Now, that takes care of checking both Xn values (normally two compares) in a single compare, so you cut out one potential process right there. But now there's the added overhead of (AxW+BxW)/2, which can be optimize to (AxW+BxW)>>1 but it's still has additional overhead on every compare. Here's where he optimizes his engine; (AxW+BxW)/2 is not calculated on a per object box compare basis but rather it's calculated once and at assemble time. Now you're probably thinking that means he can only have one bounding size. He gets around this be having a set of box collision sizes. Usually, in a game of the PCE era, collision doesn't happen between every object. Or rather, only certain objects only interact with other objects. So there isn't a general need to check every object against every other object. And so you can write a few different collision routines to compare two hardcoded box sizes against each other. The other advantage is that you don't have to add movement offset to 4 coords, but only two coords (for when the object moves onscreen).


Though on the 65x, 4 corner compares should be relatively fast..

A simple 4 corner 8bit value check system:
Code:
CollisionAB:
  lda ObjAx2,y     
  cmp ObjBx1,x     
  bcc .nohit   
  lda ObjBx2,y
  cmp ObjAx1,x
  bcc .nohit
  lda ObjAy2,y
  cmp ObjBy1,x
  bcc .nohit
  lda ObjBy2,y
  cmp ObjAy1,x
  bcc .nohit
 ;hit
  jsr DoCollisionAB
 
.nohit

And obviously that can be optimized further if the routine is comparing one object to the whole list of other object (using a preload of 4 zp regs before the loop). Have lots of different arrays with all sorts of flags and attributes, but make sure they all have the same index value for the main object. Though that might be easier said than done if you're limited to the stock 2k ram of the NES.

The last thing I would check is; does optimizing your collision routine slow down other parts of object handling code? If so, is the trade off worth it? Maybe you're keeping track of objects that exist in a larger virtual map; everyone one of their positions would need to be evaluated and changed as you scroll about the camera window. If that's the case, and these objects stopping moving around (become inactive), outside of the camera view, it might be worth using a center point system on those - and then switch to corner offset positioning once active (moved to an active list). Dunno. But things like that weigh in on how you optimize your collision routine(s).
Re: Collision Detection too slow
by on (#184015)
Sumez wrote:
Did anyone actually do that thing where you check your frame timing to see if you need to delay certain routines until the next frame?
I've heard it mentioned several times before, and I know some commercial games do it, but to me it just sounds incredibly flaky... At least when it affects logic as critical to gameplay as collisions.

As I said in my previous post, apart from optimizing your algorithms and indexing your data, etc. the most effecient thing you could do, should always be building your game logic around what you know you can "afford", and how much stuff you're actually expecting to happen. If you're planning to often have 10 or more enemies on screen at the same time, your collision detection should be able to handle all of them, and if you need to spread collisions of certain objects between multiple frames in order to handle them all, I would personally prefer to do this unconditionally, rather than depending on whether your program is "running slow".
Checking if you need to delay some collisions to the next frame would add extra overhead to your code even when it's not relevant, and certainly allows for more bugs and erratic behavior, making testing more cumbersome.

I guess what I'm getting to is that if your program has special features that allows it to handle critical situations with a lot of action going on, it should be able to handle it well enough that it might as well do the same thing when nothing much is going on? Maybe I'm just being judgmental, but it sounds like bad design to me. :)


What's ironic is that the games I've seen mentioned for this are always games that have a lot of slowdown. Does using this trick actually make the game slower?