Platformer

[firedraco]

Continuing sort of from within: http://cplusplus.com/forum/lounge/65258/2/

I was trying to use Disch's system but ran into a problem of how to deteremine whether or not I could actually "land" on the wall I was hitting. For example, if I jumped up into a wall I don't want to be considered "standing" on it.

Any ideas on how you dealt with this specifically?

[xander333]

Check if you're going down?

Alternatively you can check the position of the block you're colliding with.

[hamsterman]

It might be a simple and solid idea to assign each line of length (x,y) a normal vector (-y, x). Then you can see if the line is facing up or down. You 'll need to use different lines for floors and ceilings but that's hardly a bad thing as a 1 pixel wide border between rooms would look ugly.

[Disch]

Take a look at the shape of my object in those example pictures:
http://i41.tinypic.com/33csm69.png

it's basically a rectangle with the bottom corners cut out so that the bottom forms a 'V' shape.

The very bottom tip is what I call the "focal" point. If that point is touching a wall, that is the wall the player is standing on. If that point is not touching a wall, the player is airborne.

the bottom left and bottom right corner points (at the top of the 'V' shape) can be adjusted. The 'steeper' the V, the steeper slope the object can climb. But if those corner points hit anything, it's considered to be a wall, and not a floor.

When you do your collision detection, just check to see which part of the object hit the wall, and respond to the collision appropriately.

[firedraco]

Thanks for the input guys. Can't believe I didn't think of that, seems so obvious now, heh.

[hanst99]

I haven't actually checked it, but if you were using SAT you could just check the surface normal you get back, and treat any surface with a certain ascent as a 'wall'.

[Disch]

checking slopes/ascents won't differentiate between floors and ceilings.

[firedraco]

Ok, I finished that and I was working on dealing on movement if they are standing on a platform, and I think I have an issue. If the player is on something sort of like this:

PP
PP -> ====
PP
=========

Then they could easily clip through the wall since the only places I am checking for collisions are from the corners. Do I have to check in reverse or something, possibly from the wall endpoints backwards towards the player or something?

[Disch]

Yes. That's what the bottom picture of this ugly and hard to understand diagram was about:
http://i41.tinypic.com/33csm69.png

You move the corners of the player towards the wall and see if they hit any wall lines.
You also move the corners of the walls towards the player and see if they hit any player lines.

[firedraco]

You also move the corners of the walls towards the player and see if they hit any player lines.

So basically from the wall endpoints I just do the same thing and see if the wall lines intersect the players hitbox basically?

[hamsterman]

@Disch, I think some operations can be saved if you changed line from map corner with player edge intersections (2 of your image) to checking whether a corner is inside a convex polygon (the polygon line 1B). There would be more checks to perform (7 instead of 3), but testing if a point is on the right side of a line is much more simple than finding an intersection of lines. Of course, this is insignificant.

[Disch]

I'm not sure I understand what you mean, hamsterman. Can you elaborate? I'm very interested.

[hamsterman]

I didn't look, but I assume that you have a function like this:

bool check_for_collisions_with_corners(PLAYER, OFFSET, MAP) {
  for each corner C in MAP
    L = make line from C to C - OFFSET
    for each line E in PLAYER, if L intersects_with E, return TRUE
}

Here PLAYER and MAP are lists of lines and points that make up the dummy from your drawings
and the surrounding environment respectively. OFFSET is how much PLAYER moved since you
last checked for collisions.

The intersects_with method finds the intersection of two lines using http://en.wikipedia.org/wiki/Cramer's_rule as I don't think there is faster way to solve a system of 2 linear equations. This means 7 multiplications, 1 division, 5 additions/subtractions and also logic to check that solution is in [0; 1].

What I'm suggesting is

bool check_for_collisions_with_corners(PLAYER, OFFSET, MAP) {
  POLYGON = make_poly(PLAYER, OFFSET)
  for each corner C in MAP
    if for all lines L in POLYGON, C is_on_the_left_side_of L, return TRUE
}

bool is_on_the_left_side_of (POINT, LINE) {
  return dot( POINT - LINE.START , normal(LINE) ) < 0
}

The idea is that if a point is inside a convex polygon, it is on the same side of all of its edges. As you see, is_on_the_left_side_of only has 2 multiplications and 3 additions/subtractions. Plus the logic of for_all loop. dot() is dot product, START is one of the ends of a line, normal(x, y) = (-y, x). The hard part is that all lines must be orientated correctly. That is the job of make_poly. It's a bit more complex, but it is only going to run once. It could be something like

Polygon make_poly(PLAYER, OFFSET) {
  (BACK, FRONT) = PLAYER . partition lines by ( dot(_, normal(OFFSET)) >= 0 )
  FRONT . for each point ( _ += OFFSET )
  TOP = make line from BACK.TOP to FRONT.TOP
  BOTTOM = make line from FRONT.BOTTOM to BACK.BOTTOM
  return BACK + TOP + FRONT + BOTTOM
}

I hope scalaish _ is not unclear. BACK and FRONT are list of lines, TOP and BOTTOM are lines connection their ends.

I like geometry.

[hanst99]

checking slopes/ascents won't differentiate between floors and ceilings.

No, but the sign of the y component on the surface normal does.

[Disch]

@hamsterman & hanst

I see now what you guys are saying, but those ideas wouldn't work for my particular implementation because it assumes too much about the structure of the map.

The maps in my demos were constructed with a series of line segments, which did not necessarily form closed polygons.

[hamsterman]

@Disch, the idea of my previous post only assumes that the player is a closed polygon.
The idea to check floors/ceilings with a surface normal, while isn't much needed, doesn't assume anything at all, except that the same line will not be both.

[Disch]

@Disch, the idea of my previous post only assumes that the player is a closed polygon.

Then I'm afraid I don't understand what your post was talking about.

I thought you were getting at the idea that you can skip checking for collisions for corners in the wall that are concave (which is true). But if you're talking about the player as a polygon, then I don't see the relevance.

Reading the post again, it looks like you are checking to see if a point is within a polygon - but that check alone is not good enough because it allows for tunneling. It also doesn't tell you how far the player can move before colliding with the wall corner. But maybe I'm just still misunderstanding?

The idea to check floors/ceilings with a surface normal, while isn't much needed, doesn't assume anything at all, except that the same line will not be both.

Which would be a false assumption for some of my test cases (and likely some practical cases in my game).

[hanst99]

Kinda off topic, but how do you determine which lines to check for collision? I haven't figured out an efficient way to quickly find polygons which need to be checked for collision (well, quadtrees and kd-trees, but I'm not sure how to apply them for polygons rather than points). Just checking everything works fine for the small test stuff I've done so far, but I doubt it would work so well for anything just a little larger than that.

[hamsterman]

Reading the post again, it looks like you are checking to see if a point is within a polygon - but that check alone is not good enough because it allows for tunneling. It also doesn't tell you how far the player can move before colliding with the wall corner.

That's pretty much it. To prevent tunneling, I'm taking a larger polygon that contains player polygon both before and after moving. You do lack a bit of information after detecting a collision, so you have to do what you are already doing, except that now you only have to check zero or several points, instead of N. Like I said, gain is insignificant as there is no point in having absurd numbers of lines.

Which would be a false assumption for some of my test cases (and likely some practical cases in my game).

Don't 1 pixel wide walls look ugly?

Edit: I just realized that this problem is what linear programming does. I think a better optimization can come from looking at it like this. I'll give it a try.

Edit: Here's a suggestion.
Construct a polygon with my make_poly. Then for each line L from MAP, do this:
For each point P in polygon, calculate P is_on_the_left_side_of L. If some results are true and some are false, there could be an intersection (there would be if that line was infinite). Assuming that you filter lines by distance and your map is not full of random spikes, only a few lines will go past this point. 7*5*N operations performed so far, instead of 2*3*13*N.

Now do the same thing for the two lines that go through ends of L and are perpendicular to it, except that now you're only looking for at least one true value. Of course, orientations must be correct. Although now you only know that there is an intersection, not where it is. It might be better to do what you are already doing. The difference is that almost all lines will have already been filtered out.

[Disch]

@hanst:

Check this post for how I'm doing it:
http://cplusplus.com/forum/lounge/65258/2/#msg353967


@hamsterman:

What you're doing seems like a coarse range check. Faster, but less accurate. In the event that your check determines there might be a collision, you still have to do a more precise check to see if there actually is one and where it is.

What concerns me is that your coarse check assumes there already is an existing coarse check ("Assuming that you filter lines by distance"). So it's kind of like you are suggesting 3 layers of collision detection instead of the more typical 2. I'm not sure it'd be worth it.

It's definitely interesting though.

Don't 1 pixel wide walls look ugly?

Well in practice you wouldn't see the actual wall lines, as they'd be covered by a graphical layer.