next »

[st33d]

I've got my spatial hash map ready and I've got my rectangles - called Colliders. Colliders predictively collide, ray casting along x movement and recursively issuing move commands to any Colliders that get in the way. Then I do the y axis. I know it sounds wrong to separate them, but it actually works very well.

This leads to some very solid crates that can nudge each other along. And the cpu overhead is very, very low. I am literally going to need hundreds of these crates - hence the lo fi, yet solid collision.

However - I performed the ray casting in previous versions of Colliders by stepping in units down the side of the Collider and casting a ray from there.

But when I got to the bottom of the rectangle , I casted at the y position y + height - 1. Because if I casted at y + height, I would hit an object that is actually below the Collider.

See my hash-map thread to see what I mean:

http://forums.tigsource.com/index.php?topic=14917.0

Whilst y + height -1 and x + width - 1 worked as raycast positions and catching the bottom of the Collider, I'm pretty sure I'm doing it wrong.

If I wanted to ray cast (and bear in mind I'm using straight lines, no angles - so we can keep the math very simple) from the bottom corner of my Collider, where should I be doing it?

I'm open to the idea this time that perhaps I should just subtract 0.0001 or something silly like that, but it feels wrong. Is it? Is there another way?

[bateleur]

If you really want to do it like this (and if I'm being honest, my "nasty hack" warning light is going off) I'd recommend tweaking the ray code, not the starting point.

So basically what you do is add a boolean parameter to the ray function saying whether it's an inclusive or exclusive cast. What you have right now is inclusive casting. When you do an exclusive cast, you use strict inequality for collisions, so that running exactly along the edge of something will count as a miss.

[eugeneius]

Technically what you want to do is subtract the smallest representable unit, which in AS3 is Number.MIN_VALUE. This ensures that something occupying the point y + height won't collide with your object, but anything closer than that will - satisfying the definition of a half open interval from the other thread.

In practice though, you could just ignore this wrinkle and use y + height. Number.MIN_VALUE is incredibly small, so the difference won't be noticeable. While your bounding box will be the "wrong" size, it will just mean that a hard coded height value of 17 will result in an actual height of 17 + 5e-324.

Thinking about this again just before posting it, I realised that ignoring the problem might be a bad idea. Using half open intervals makes certain things nicer - for example, an entity can spawn a bullet/particle/whatever at y + height, and know that it won't be colliding with it.

[st33d]

So basically what you do is add a boolean parameter to the ray function saying whether it's an inclusive or exclusive cast. What you have right now is inclusive casting. When you do an exclusive cast, you use strict inequality for collisions, so that running exactly along the edge of something will count as a miss.

The origin of the cast is the problem. I can account for half open intervals with Boolean logic very easily (if pos < y + height). But not when I'm trying to pick a finite position to ray cast from. And I need to be able to ray cast from the bottom edge of the Collider, otherwise it's going to absorb other Colliders.

Number.MIN_VALUE does seem like a better compromise - it makes the code clearer. There are technically an infinite amount of floating point values below the interval closure so it does seem that a finite position will always be a hack. Thoughts?

[eugeneius]

Disclaimer: while I'm fairly sure what I've written below is accurate, I've never actually read the IEEE spec. There could conceivably be some property of floating point arithmetic that I'm not aware of and which invalidates some or all of this!

There can't be an infinite amount of floating point values, since floats are stored in a finite amount of memory. Subnormal numbers (which I'm still not sure I understand fully) complicate things a bit, but they are only used for very small values; smaller than Number.MIN_VALUE, in fact.

So, when y + height for an object is outside of the range (-Number.MIN_VALUE, Number.MIN_VALUE), there is no representable position between y + height - Number.MIN_VALUE and y + height.

Inside that range, which is an unfathomably tiny sliver of your game world, there is indeed a value which is closer to the interval closure. Depending on how you think about it, this would allow your objects to overlap by some amount smaller than Number.MIN_VALUE.

This is most likely not a serious problem.

Anyway, as the an object gets further from the origin and the base of your numbers go up, you lose enough precision to make all of this inconsequential. In fact now that I think about it, I'm pretty sure once you start moving away from values close to 1.0, foo - Number.MIN_VALUE is going to be equal to foo.

I've managed to confuse myself a bit here, so I'm going to use a scene break and then try to make a point.

---

I actually think bateleur's solution makes the most sense, for this particular case. He was saying you should raycast from (x, y + height), but reject collisions for which the ray is exactly touching an edge. Compared to trying to find the closest nearby ray and using that, this is a nice simple solution.

In the general case though, the kinds of errors we're dealing with here aren't going to affect gameplay. You expressed an aversion to subtracting 0.0001 in your first post, but that probably would have worked fine

[st33d]

I'm following what bateleur suggested now.

Something like this for a ray travelling right?

Code:

if(x >= collider.x && ((inclusive && y == collider.y) || (y > collider.y && y < collider.y + collider.height))){
return collider;
}

The half open interval thing means that it's only the top edge I'm worried about.

[raigan]

I think a better solution would be to implement the tests as a swept-AABB-vs-swept-AABB rather than raycasts; this boils down to a single ray-vs-AABB test, where the AABB is the Minkowski sum of the two boxes you're testing (which just means sum the widths/heights and position it at boxB_pos - boxA_pos).

[bateleur]

Something like this for a ray travelling right?

You got it.

I quite like raigan's suggestion though, having read it. (Even if the mathematician in me is horrified by the idea of something being called a "sum" when it's not commutative!)

[st33d]

edit:

Okay, considering a different approach now. The purpose of the raycast in previous engines of mine, was to find out what the character had hit first - another Collider or part of the static map that was represented by integers. The only way to do efficient collision in such an environment was to raycast, because I may be looking at a wall, a ledge or a movable boulder.

Since this is simply a crate simulation in a bounding box that's a hash map, I don't actually need to ray cast for anything. I can test against hash map cells next to me horizontally, then vertically. That allows me to do the recursive movement easily.

I think that reading through raigan's suggestion must have knocked something loose and I realised there was a much more efficient solution.