Practical SFML - Game Design Issues

[Disch]

Line-based collision detection can be costly in larger amounts

So can tile based collision detection.

Efficiently constructed line based collision doesn't really have any worse performance. In a lot of ways it's even simpler.

I've dealt with tile based many times in the past. The work involved in getting slopes to work properly is stupid (unless you want to settle with a buggy system).

I'd go so far as to say that, provided you do adequate coarse range checks first (ie: only checking nearby walls), that line based collision would be faster than a tile-based system that has the same effect.

The thing with tile based systems is they either don't handle every case (they have problems when the map is designed a certain way) or they are littered with all sorts of special case code and end up being slower than you'd think.

are you sure that's entirely necessary?

It's not a matter of necessity. It's more like an alternative way to do it. Like anything else there are pros and cons to the decision. I personally feel that for my project, the pros outweight the cons.

What would be going so fast that it would completely go through an object?

Any object falling from a distance onto a very thin floor. It gets worse and worse the smaller and faster objects are. Something like a bullet will go through a paper thin wall far more often than not.


This is a very real problem and I've had to make special cases for it in every tile-based collision system I've made in the past, or else I had this happen. It wasn't a rare occurance either. It was very easy to reproduce and would have been a serious bug in the game had it gone untreated.

Many games "solve" the problem by simply not having thin floors. Which is a fine solution if you don't mind placing those kinds of restrictions on your level design.


EDIT:

I should mention that this approach is for object/map collision. Not object/object collision, which will be an entirely different mechanism in my game.

[Kyon]

So the line-based collision, as you implement it works somewhat like this:
1) The player wants to move to a certain spot (x,y).
2) Several lines are checked from the player's place to the destination, when a world piece is hit, the motion is changed. Another check is performed too, from the endpoints of each line piece. Lines are "checked" from these endpoints such that the lines are parallel to the "motion vector" of the player. When any of these lines hit the player, the motion is adjusted, too.
3) The (adjusted) motion is applied to the player.

[Disch]

That's basically it, yes.

It is more complicated in practice, as I don't simply stop the object when it hits a wall. Instead, I transfer motion to a new direction based on the angle of the wall you hit (and the part of the "body" that hit it)

For example if the object hits an angled ceiling from the side...
Illustration:

  /
 /<===
/

The objects motion will be transferred to a downward-left angle instead of just stopping them outright. That way you sort of "slide down" the ceiling.

[NGen]

I thought that you were using that for everything, never-me-mind.

[hamsterman]

I don't quite understand "Figure 2".
From which corners do you start the lines? How do you deal with cases where that line would intersect with the player, but no actual collision happens (moving towards a corner, but not into it) ?
Anyway, it seems needlessly complex. I think you could do it in a simpler way. Traverse through every point and check if it's in the area limited by the red lines and player's shape ("Figure 1B"). This shouldn't be hard since the red lines only form trapezoids.

Also, how will you do the object/object collision and what's wrong with current mechanism?

[Disch]

From which corners do you start the lines?

The map is a series of line segments. Each line segment has 2 endpoints. Those endpoints are all "corners" from which lines are projected.

I didn't draw all 3 projected lines in figure 2, i only drew the relevant one.

How do you deal with cases where that line would intersect with the player, but no actual collision happens (moving towards a corner, but not into it) ?

This never happens. The projected line is equal to the motion vector (just reversed so it's oriented in the opposite direction). If the line doesn't reach far enough to intersect with the player, then the player is not moving far enough to reach the wall.

Anyway, it seems needlessly complex

Perhaps it's just how I'm explaining it. I find the concept to be quite simple =x

Although the implementation does get a bit complicated, admittedly. But if you can show me an effective way to do collision detection that doesn't get somewhat complicated (and actually works in all cases), I'd be happy to hear it. AFAIK it can't be done.

I think you could do it in a simpler way. Traverse through every point and check if it's in the area limited by the red lines and player's shape ("Figure 1B").

This kind of defeats the whole point of the line approach. If you're only checking based on the state of the object after the move and not the move itself, then tunneling becomes a problem. Fast moving objects can go right through those kinds of checks, whereas a line based approach will always stop the object appropriately no matter how fast it's moving.

Besides, if you only check to see if the object is "in the wall", it's kind of already too late. How do you eject them from the wall? Of course you'd have to move them backwards until they're no longer in the wall, but by how much? The fundamental principle here is you stop the object before it gets "in the wall".

Also, how will you do the object/object collision and what's wrong with current mechanism?

Object/object collision I'm planning to do the typical way with hit boxes. This reintroduces the issue of tunneling, but I haven't really thought of a way to avoid that yet.

I wonder if I could apply the same line-based techniques here. To be honest I haven't really given that much thought.

[hamsterman]

The projected line is equal to the motion vector

Oh. No problem then.

Besides, if you only check to see if the object is "in the wall", <...>

That's not what I meant. Here a picture: http://i54.tinypic.com/jfynip.png
You need to check if there are any points in the yellow area. This is intended only for corners. A system with points seems more simple to implement. Though of course if you already have a working method, there's no reason to change it.

[Disch]

You need to check if there are any points in the yellow area

Ah, I see.

That would work, but you still have the ejection problem. I not only need to know whether or not the object hit a wall, I need to know how far they can move before hitting the wall. This would help with the former, but I'd still have to do something else to get the latter.

Plus, checking if a point is within a polygon is more complex than checking if two lines intersect. The method I would employ to see if a point is within a polygon would involve even more line projections and line intersection checks.

But that's an interesting idea nonetheless. In fact, I think a variation of that might be applicable to object/object collision.

[hamsterman]

Plus, checking if a point is within a polygon is more complex than checking if two lines intersect.

This isn't checking if a point is within a polygon, it's checking if a point is within a parallelogram (why do I find names of shapes so weird English?), which is way quicker.
Though I agree that this probably wouldn't work any faster.

As for the distance, the first step of the algorithm I'm thinking about would be to transform the given point to coordinate system where x axis is parallel to players direction vector. Then if you transformed player's coordinates too, you could get the distance from point to player.

[Disch]

it's checking if a point is within a parallelogram (why do I find names of shapes so weird English?), which is way quicker.

Is there some trick I don't know about? How would a parallelogram be any easier than any other convex polygon?

the first step of the algorithm I'm thinking about would be to transform the given point to coordinate system where x axis is parallel to players direction vector.

But then you have to start calculating sin and all this other stuff. Doesn't seem very practical.

Though I agree that this probably wouldn't work any faster.

Still interesting though!

[helios]

How would a parallelogram be any easier than any other convex polygon?

Given a point P and a parallelogram ABCD, get the intersection of [the line that's passes through P and is parallel to AB and CD] and [BC or DA] and of [the line that's passes through P and is parallel to BC and DA] and [AB or CD]. If the point is inside the parallelogram, you'll get two non-null intersections.

[Disch]

I still don't see what makes that easier. Similar logic can be applied to any polygon (even concave ones).

Draw a ray from point P extending to infinity (or "far enough") in any direction. Count the number of line intersections.

Point is inside the polygon if you have an odd number of intersections. Point is outside if you have an even number of intersections.


I guess with a parallelogram you only have to check against 2 lines whereas with an N-side polygon you have to check N intersections. But you don't have to worry about making lines parallel.

[helios]

Ah, I like that one even better.

//Point P;
//Segment side[4];
Ray R=Ray::in_any_direction_from(P);
if (!R.intersect(side[0]).null()){
	return (
			!R.intersect(side[2]).null() ||
			!R.intersect(side[1]).null() ||
			!R.intersect(side[3]).null()
		)?OUTSIDE:INSIDE;
}
if (!R.intersect(side[2]).null())
	return (
			!R.intersect(side[1]).null() ||
			!R.intersect(side[3]).null()
		)?OUTSIDE:INSIDE;
return (R.intersect(side[1]).null()==R.intersect(side[3]).null())?OUTSIDE:INSIDE;

[Disch]

You can't short circuit any checks though. You have to check all the sides every time. If you stop after you find one intersection you'll get false positives.

EDIT:

Unless I'm misunderstanding the code? ??

[helios]

The code is almost the same as

bool intersection=0;
for each side in convex_polygon
    if ray crosses side
        if intersection
            return OUTSIDE
        else
            intersection=1
return INSIDE

For the special case of a convex polygon, you only need to find two intersections. I changed the order because I had an idea for an algorithm that would let you skip checks by checking opposite sides, but then I realized I was missing cases, and I guess I forgot to rethink that part.
In other words, never mind. A parallelogram is no less complex than a convex quadrilateral.

[NGen]

Point is inside the polygon if you have an odd number of intersections. Point is outside if you have an even number of intersections.

Much simpler than my concept, you go through each angle in the polygon and check if the point is inside all of the angles. Although maybe that check isn't as bad since each check only requires 1-4 more operations with no division, and you can stop after you find just one angle that the point is outside of.

[Disch]

you go through each angle in the polygon and check if the point is inside all of the angles.

That could work. I've usually seen that as "make sure it's on the right side of each border" though. Same idea, but you check the polygon side instead of the border. It's pretty easy with some dot product wizardry, too.

For convex polygons, that's probably a lot more efficient. But it doesn't work for concave polygons. (Although we really were never talking about concave polygons, were we)


EDIT:

since we're posting fun little pseudocode:

bool IsPointInConvexPoly(const Point& P,const Point* poly,int sides)
{
  // sides if number of sides in the poly, minimum 3

  double d = PerpDot( P - poly[sides-1] , poly[0] - poly[sides-1] );
  if(!d)
    return false;

  bool pos = d > 0;

  for(int i = 1; i < sides; ++i)
  {
    bool p = PerpDot( P - poly[i-1], poly[i] - poly[i-1] ) > 0;
    if(pos != p)
      return false;
  }

  return true;
}

[hamsterman]

make sure it's on the right side of each border

That's what I was thinking about. Parallelogram has two pairs of parallel sides, so you only need to do two transformations.
Now that I think about this, you should be able to work out a matrix for transforming points into a coordinate system where x and y axes are parallel to the sides of this parallelogram. (That would be a shearing matrix * rotation matrix, I assume). The distance from player to pint could be easily calculated from one of transformed point's coordinates.
If I recall correctly, this is similar to how finding a triangle-ray intersection is done in 3d.
This method may require some thought and may be difficult to debug though.