## Rotating room collision.

Discussion of hardware and software development for Super NES and Super Famicom.

Moderator: Moderators

Forum rules
• For making cartridges of your Super NES games, see Reproduction.
rainwarrior
Posts: 7979
Joined: Sun Jan 22, 2012 12:03 pm
Contact:

### Re: Rotating room collision.

psycopathicteen wrote:I thought about that, but I realized the character's running speed would be wrong. I'll show a drawing of what I mean by it.
Well, just to show you that the approach you were taking is equivalent, here's proof:

Code: Select all

``````A = cos(a)               (0)
B = sin(a)               (1)
AA + BB = 1              (2) definition of a circle

X =  Ax +  By            (3) rotation matrix
Y = -Bx +  Ay            (4) rotation matrix

Ax =  X -  By            (5) from (3)
Ay =  Y +  Bx            (6) from (4)

Ax = X - B(Y + Bx)/A     (7) from (6) and (5)
AAx = AX - BY - BBx      (8) from (7) multiplied by A
(AA + BB)x = AX - BY     (9) from (8)

x = AX - BY              (10) from (9) and (2)
y = BX + AY              (11) reached by similar set of steps``````
You had (5) and (6), but note that your equation for x included a y term and vice versa. Once you combine them (7) then you can eventually get back to just the simple rotation matrix (10/11) where B has been negated to reverse the rotation.

Oziphantom
Posts: 1021
Joined: Tue Feb 07, 2017 2:03 am

### Re: Rotating room collision.

Espozo wrote:Making the hitbox of everything a circle has been brought up, but would it be at all feasible to check a rotated box against the collision map?
It depends upon the sizes of things, but basically you never really check rotated boxes against other things. You rotate the other things to be aligned to the box. So you find edges you think you might collide with(doing a holds all AABB check), rotate the edge -Angle Box is rotated, then do an AABB check of edge to box.

However, if I was in mode 7 and doing rotated things on the SNES. I would use 'Minkowski collision', where I would expand the worlds box and drop all my moving things to points, hence a point in a box is still a point in a box no matter how the point is rotated in world space The flaw is, all things now must have the same size collision box, I think this is how Contra does it, from memory I think everything you can shoot is the same size as the player for the most part. If you need different sizes you could shrink the "box" and then make a player say 4 points, and a pickup 1 point, and a large enemy 8 or 6 or 12 points etc.

Nicole
Posts: 218
Joined: Sun Mar 27, 2016 7:56 pm

### Re: Rotating room collision.

Oziphantom wrote:I would use 'Minkowski collision', where I would expand the worlds box and drop all my moving things to points, hence a point in a box is still a point in a box no matter how the point is rotated in world space The flaw is, all things now must have the same size collision box
Super Mario 64 actually uses this approach, believe it or not. Mario himself is just a point, with stuff like wall hitboxes extended out to compensate. Different hitboxes are used depending on Mario's state as well, like when he's standing, jumping, or swimming.

I'm not sure what exactly it does for stuff like enemies colliding with the environment, though. I imagine some things could be simplified since they're controlled by AI.

Drew Sebastino
Formerly Espozo
Posts: 3503
Joined: Mon Sep 15, 2014 4:35 pm
Location: Richmond, Virginia

### Re: Rotating room collision.

Oziphantom wrote:However, if I was in mode 7 and doing rotated things on the SNES. I would use 'Minkowski collision', where I would expand the worlds box and drop all my moving things to points, hence a point in a box is still a point in a box no matter how the point is rotated in world space The flaw is, all things now must have the same size collision box, I think this is how Contra does it, from memory I think everything you can shoot is the same size as the player for the most part.
I remember reading in a developer interview that the player's collision in R-Type is done this way, and that the enemy and enemy bullet hitboxes are drawn larger to compensate. I presume it's done the same way in R-Type II, and even R-Type III. It explains how your collision with the stage is far more lenient than that of enemy objects.
Oziphantom wrote:It depends upon the sizes of things, but basically you never really check rotated boxes against other things. You rotate the other things to be aligned to the box.
Well, it wouldn't make sense for the hitboxes to be rotated for object to object collision in the first place. The problem is checking it against the stage, in which case, if the object is not rotating visually with the stage, there will be a growing disparity between the object's appearance and the hitbox. I don't know if you already said this in a different way.

Oziphantom
Posts: 1021
Joined: Tue Feb 07, 2017 2:03 am

### Re: Rotating room collision.

No my point was when you do the actual collision check you don't do a rotated thing against another rotated thing, that is long and complicated math with accuracy issues. What you do is you look at the two things you want to collide, in this case an edge from the world, and your hit box. You get the edge relative to your hit box, then rotate it - your angle of rotation. So now you have your hit box Axis Aligned, and the two edge points are relative to your origin. So now your hitbox is about the origin, and the edge is relative to the origin, the box is axis aligned, so you just need to check the points against an AABB. Which is fast.

rainwarrior
Posts: 7979
Joined: Sun Jan 22, 2012 12:03 pm
Contact:

### Re: Rotating room collision.

Maybe it's a little bit of a red herring to talk about point-vs-box as an alternative to box-vs-box in a thread about rotating stuff? It's really its own optimization, applicable without rotation.

With box vs box, you have to do some math to generate both boxes, then subtract and compare 4 pairs of sides against each other.

If you're going to compare a player box against many bullets of the same size, instead of generating boxes for the bullets, you increase the size of the player box once, and compare against points. Still subtracting 4 sides for the test, but now you've skipped/batched the work for generating the bullet boxes by doing them one time. This is only really useful if you have multiple items with the same bounding box size; for a single collision it's roughly the same work.

There's a further optimization if you have some kind of fast way of computing an absolute value, i.e. subtract centre point from centre point, and compare the absolute value of the difference with the sum of the widths of your two bounding boxes (precalculated once). Now you're just subtracting points on 2 axes and the absolute value operation fills in for the other two. This is great with floating point, but absolute value might be a wash for 6502 family.

tepples suggestion of sphere collision is sort of an extension of point vs point to multiple dimensions, i.e. by squaring and summing the result on each axis you can compare against a single radius. Sphere collisions are invariant against rotation, which is why they're also highly applicable in this case. Taking the centre point and using a bounding box on the other hand isn't, but its still can be an effective optimization, and using centre points helps with the approximation anyway in a context that can rotate. (i.e. A box rotating around a centre point is probably a lot more useful hitbox approximation than a box rotating around its corner.)

Now there's also the question of whether when things are rotating you actually do want rectangular hitboxes, and when they're rotated, you want collision between those rotated shapes... that gets a lot more complicated. If both boxes have the same rotation, no problem, just do the original calculation in the space you had before the rotation. If one is rotated and the other isn't, you're now basically in the realm of colliding arbitrary convex polygons. I won't get into how to do that, but I'll just say that it's pretty difficult without an efficient multiply. That's the difference between an "axis aligned bounding box" (AABB) and boxes that can freely rotate.

Very often engines will do a sphere test or and AABB test with a shape that is large enough to encompass an entire object as a fast first step to check for potential collisions (with false positives) before doing more expensive collision tests to see where/if they actually collided. This presupposes that you want to do a more complicated collision than that first step, though.

At a higher level still, you might also have some sort of space partitioning tree or other structure to accelerate figuring out which objects are near another to collide. Not really important when you have a low number of objects but when there's a lot of stuff around, narrowing down that list of things that you have to check against each other for collision can reduce the workload by an order of magnitude. (Depends on how much work you have to begin with, whether it will pay off.)

edit: tepples points out below that sphere tests might be fairly efficiently implemented on 6502
Last edited by rainwarrior on Tue May 01, 2018 11:46 am, edited 1 time in total.

tepples
Posts: 22233
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

### Re: Rotating room collision.

rainwarrior wrote:tepples suggestion of sphere collision is sort of an extension of point vs point to multiple dimensions, i.e. by squaring and summing the result on each axis you can compare against a single radius. Again maybe not well suited to 6502 family because of the lack of multiply.
You don't really need multiply for this because squaring each displacement coordinate and the sum of radii is fast with a lookup table from x to x^2.
rainwarrior wrote:At a higher level still, you might also have some sort of space partitioning tree or other structure to accelerate figuring out which objects are near another to collide.
Or its one-dimensional counterpart, which is X- or Y-sorting.

rainwarrior
Posts: 7979
Joined: Sun Jan 22, 2012 12:03 pm
Contact:

### Re: Rotating room collision.

tepples wrote:You don't really need multiply for this because squaring each displacement coordinate and the sum of radii is fast with a lookup table from x to x^2.
Ah, yes squaring is a much simpler problem than multiplication.

psycopathicteen
Posts: 2975
Joined: Wed May 19, 2010 6:12 pm

### Re: Rotating room collision.

My collision uses a center point for walking on the ground, but uses 2 corner points when walking on an edge.

Oziphantom
Posts: 1021
Joined: Tue Feb 07, 2017 2:03 am

### Re: Rotating room collision.

rainwarrior wrote:
tepples wrote:You don't really need multiply for this because squaring each displacement coordinate and the sum of radii is fast with a lookup table from x to x^2.
Ah, yes squaring is a much simpler problem than multiplication.
I would argue that on a 256x240 screen where you have an object that is 16x16 ->32x32 the difference between a circle and slightly smaller square is neither here nor there. And thus you can skip the square and just do X1-X2 <AA1w+AA2w & Y1-Y2 < AA1h+AA2h where in AA1 and AA2 are probably the same size anyway

Also should be noted this is the SNES portion of the forum and so yes it does have a decent mul, 7 clocks and done, so avoiding a square is not really that big a deal.

psycopathicteen
Posts: 2975
Joined: Wed May 19, 2010 6:12 pm

### Re: Rotating room collision.

Wouldn't having circular tiles mean the floor will be bumpy?

tepples
Posts: 22233
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

### Re: Rotating room collision.

Colliding circular sprite hitboxes against axis-aligned square terrain is still reasonably efficient.

Oziphantom
Posts: 1021
Joined: Tue Feb 07, 2017 2:03 am

### Re: Rotating room collision.

psycopathicteen wrote:Wouldn't having circular tiles mean the floor will be bumpy?
For Ent to World you would use the Minkowski collision. I.e Point to axis aligned edges/bounding boxes/tiles etc

rainwarrior
Posts: 7979
Joined: Sun Jan 22, 2012 12:03 pm
Contact:

### Re: Rotating room collision.

Oziphantom wrote:For Ent to World you would use the Minkowski collision. I.e Point to axis aligned edges/bounding boxes/tiles etc
I don't think there's really an effective way to convolve a tile grid with the player hitbox? psychopathicteen is already testing two edge points against the world, that's probably somewhat optimal.

Oziphantom
Posts: 1021
Joined: Tue Feb 07, 2017 2:03 am

### Re: Rotating room collision.

Well I was thinking each tile would just have its own BB, so you work out what tile you are on, which way you are moving and then check against the right tiles, where if the tile is solid you check against the expanded box for the tile.
Having two points means you need to rotate said two points, so having a middle + 2 offsets. However thinking about it more said rotation can just be a LUT, to which doing the base + delta > tile check tile x2 probably works out much of a muchness vs the oversampling of the other method..