It is currently Mon Nov 19, 2018 2:19 am

All times are UTC - 7 hours



Forum rules





Post new topic Reply to topic  [ 37 posts ]  Go to page Previous  1, 2, 3  Next
Author Message
PostPosted: Sun Apr 29, 2018 5:01 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6956
Location: Canada
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
 Profile  
 
PostPosted: Mon Apr 30, 2018 12:28 am 
Offline

Joined: Tue Feb 07, 2017 2:03 am
Posts: 626
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
 Profile  
 
PostPosted: Mon Apr 30, 2018 2:01 am 
Offline

Joined: Sun Mar 27, 2016 7:56 pm
Posts: 171
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
 Profile  
 
PostPosted: Tue May 01, 2018 4:26 am 
Offline
Formerly Espozo
User avatar

Joined: Mon Sep 15, 2014 4:35 pm
Posts: 3381
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
 Profile  
 
PostPosted: Tue May 01, 2018 9:31 am 
Offline

Joined: Tue Feb 07, 2017 2:03 am
Posts: 626
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
 Profile  
 
PostPosted: Tue May 01, 2018 11:23 am 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6956
Location: Canada
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
 Profile  
 
PostPosted: Tue May 01, 2018 11:39 am 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20783
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
 Profile  
 
PostPosted: Tue May 01, 2018 11:45 am 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6956
Location: Canada
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
 Profile  
 
PostPosted: Tue May 01, 2018 5:16 pm 
Offline

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


Top
 Profile  
 
PostPosted: Tue May 01, 2018 10:13 pm 
Offline

Joined: Tue Feb 07, 2017 2:03 am
Posts: 626
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
 Profile  
 
PostPosted: Wed May 02, 2018 7:59 am 
Offline

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


Top
 Profile  
 
PostPosted: Wed May 02, 2018 8:07 am 
Offline

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


Top
 Profile  
 
PostPosted: Wed May 02, 2018 9:09 am 
Offline

Joined: Tue Feb 07, 2017 2:03 am
Posts: 626
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
 Profile  
 
PostPosted: Wed May 02, 2018 11:19 am 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6956
Location: Canada
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
 Profile  
 
PostPosted: Wed May 02, 2018 11:35 pm 
Offline

Joined: Tue Feb 07, 2017 2:03 am
Posts: 626
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
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 37 posts ]  Go to page Previous  1, 2, 3  Next

All times are UTC - 7 hours


Who is online

Users browsing this forum: 93143, koitsu and 3 guests


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

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group