It is currently Tue Sep 18, 2018 2:21 pm

 All times are UTC - 7 hours

### Forum rules

• For making cartridges of your Super NES games, see Reproduction.

 Page 2 of 3 [ 37 posts ] Go to page Previous  1, 2, 3  Next
 Print view Previous topic | Next topic
Author Message
 Post subject: Re: Rotating room collision.Posted: Sun Apr 29, 2018 5:01 pm

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6798
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:
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.

Top

 Post subject: Re: Rotating room collision.Posted: Mon Apr 30, 2018 12:28 am

Joined: Tue Feb 07, 2017 2:03 am
Posts: 578
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.

Top

 Post subject: Re: Rotating room collision.Posted: Mon Apr 30, 2018 2:01 am

Joined: Sun Mar 27, 2016 7:56 pm
Posts: 163
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.

Top

 Post subject: Re: Rotating room collision.Posted: Tue May 01, 2018 4:26 am
 Formerly Espozo

Joined: Mon Sep 15, 2014 4:35 pm
Posts: 3362
Location: Richmond, Virginia
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.

Top

 Post subject: Re: Rotating room collision.Posted: Tue May 01, 2018 9:31 am

Joined: Tue Feb 07, 2017 2:03 am
Posts: 578
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.

Top

 Post subject: Re: Rotating room collision.Posted: Tue May 01, 2018 11:23 am

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6798
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.

Top

 Post subject: Re: Rotating room collision.Posted: Tue May 01, 2018 11:39 am

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20552
Location: NE Indiana, USA (NTSC)
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.

Top

 Post subject: Re: Rotating room collision.Posted: Tue May 01, 2018 11:45 am

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6798
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.

Top

 Post subject: Re: Rotating room collision.Posted: Tue May 01, 2018 5:16 pm

Joined: Wed May 19, 2010 6:12 pm
Posts: 2749
My collision uses a center point for walking on the ground, but uses 2 corner points when walking on an edge.

Top

 Post subject: Re: Rotating room collision.Posted: Tue May 01, 2018 10:13 pm

Joined: Tue Feb 07, 2017 2:03 am
Posts: 578
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.

Top

 Post subject: Re: Rotating room collision.Posted: Wed May 02, 2018 7:59 am

Joined: Wed May 19, 2010 6:12 pm
Posts: 2749
Wouldn't having circular tiles mean the floor will be bumpy?

Top

 Post subject: Re: Rotating room collision.Posted: Wed May 02, 2018 8:07 am

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20552
Location: NE Indiana, USA (NTSC)
Colliding circular sprite hitboxes against axis-aligned square terrain is still reasonably efficient.

Top

 Post subject: Re: Rotating room collision.Posted: Wed May 02, 2018 9:09 am

Joined: Tue Feb 07, 2017 2:03 am
Posts: 578
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

Top

 Post subject: Re: Rotating room collision.Posted: Wed May 02, 2018 11:19 am

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6798
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.

Top

 Post subject: Re: Rotating room collision.Posted: Wed May 02, 2018 11:35 pm

Joined: Tue Feb 07, 2017 2:03 am
Posts: 578
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..

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 2 of 3 [ 37 posts ] Go to page Previous  1, 2, 3  Next

 All times are UTC - 7 hours

#### Who is online

Users browsing this forum: Google Adsense [Bot] and 2 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ NES / Famicom    NESdev    NESemdev    NES Graphics    NES Music    Homebrew Projects       2018 NESdev Competition       2017 NESdev Competition       2016 NESdev Competition       2014 NESdev Competition       2011 NESdev Competition    Newbie Help Center    NES Hardware and Flash Equipment       Reproduction    NESdev International       FCdev       NESdev China       NESdev Middle East Other    General Stuff    Membler Industries    Other Retro Dev       SNESdev       GBDev    Test Forum Site Issues    phpBB Issues    Web Issues    nesdevWiki