2d Platform Slope Collision

[like80ninjas]

Hey, can someone help me figure out how to calculate collisions for platform slopes, I have basic rect vs rect collision in my game, and i just want some 45 degree slopes.

I've been trying to program it, and have been searching Google non-stop and can't get it to work smoothly enough for my game. I'm no math guru and can use a simple solution, thanks!

[Ginto8]

Separating Axis theorem. Tutorials here (with fancy pictures) and here (avansc's very nice explanation, with code but only one semi-fancy picture).

[like80ninjas]

Thank you! Both of these links are VERY helpful.

[N64vSNES]

Just to cut in, I did a Sonic physics engine a while back and with Sonic being famous due to it's slopes, 360 angles, ramps etc you might find this useful:

http://info.sonicretro.org/SPG:Solid_Tiles#Height_Masks

[bnpph]

There is no need to use either of those methods for simple 45 degree tile slopes.

How I would do it:
1. Check if player is withing tile boundary box
2. If so, check if relative x >= relative y

[Ginto8]

There is no need to use either of those methods for simple 45 degree tile slopes.

This is true, but he seemed to think that 45 degree slopes were the minimum he wanted, and if he can do more, I'm all for it.

[N64vSNES]

There is no need to use either of those methods for simple 45 degree tile slopes.

How I would do it:
1. Check if player is withing tile boundary box
2. If so, check if relative x >= relative y

Most definitely yes. But if you're going to add 45 degree slopes, using this method you can add slopes of any degree. Why stop at 5 when the full package is 6?

[like80ninjas]

I agree with N64, I'm using the Separating Axis method.

[like80ninjas]

I'm using avansc's method for separating axis but something isn't working right. I implemented it like this, but it seems to always return true.

Code: Select all

bool Entity::CollisionCheckSAT( int check_x, int check_y, Entity* other )
{
	if (other != this)
	{
		   
		GetBBox()->WorldCoordinates();
		other->GetBBox()->WorldCoordinates();
   
		VRect *list[3];
		list[0] = GetBBox();
		list[1] = other->GetBBox();
		list[2] = GetBBox();
		Vector2f *p;
   
		float t1;
		float t2;
		float min;
		float max;
   
		for(int i = 0;i < 2;i++)
		{
			for(int a = 0;a < 2;a++)
			{
				p = new Vector2f(list[i]->world_coords[a+1]->x - list[i]->world_coords[a]->x, list[i]->world_coords[a+1]->y - list[i]->world_coords[a]->y);
				p->Normalize();
      
				t1 = list[i]->world_coords[a]->Projection(p)->Magnitude();
				t2 = list[i]->world_coords[a+1]->Projection(p)->Magnitude();
				min = std::min(t1, t2);
				max = std::max(t1, t2);
      
				float proj[4];
      
				for(int b = 0;b < 4;b++)
				{
					proj[b] = list[i+1]->world_coords[b]->Projection(p)->Magnitude();
				}
      
				if(!this->SATUmbrellas(min, max, proj))
					return false;
			}
		}
      
		return true;
	}
}
bool Entity::SATUmbrellas( float min, float max, float proj[] )
{
	bool less = false;
    bool more = false;
   
    for(int loop = 0;loop < 4;loop++)
    {
       if(proj[loop] >= min && proj[loop] <= max)
       {
          return true;
       }else if(proj[loop] < min)
       {
          less = true;
       }else if(proj[loop] > max)
       {
          more = true;
       }
    }
   
    if(less && more)
       return true;
   
    return false;
}

and here is my vector class and rect class

Code: Select all

#include "vector2f.h"

Vector2f::Vector2f()
{
	x = 0;
	y = 0;
}
Vector2f::Vector2f( float new_x, float new_y )
{
	x = new_x;
	y = new_y;
}
Vector2f::~Vector2f()
{
}
void Vector2f::Normalize()
{
	float mag = Magnitude();
	x = x/mag;
	y = y/mag;
}
float Vector2f::Magnitude()
{
	return sqrt( (x*x)+ (y*y) );
}
float Vector2f::DotProduct( Vector2f* vect )
{
	return (x * vect->x + y * vect->y);
}
Vector2f* Vector2f::Projection( Vector2f* vect )
{
	Vector2f projected;
	projected.x = DotProduct( vect ) / vect->x / (vect->Magnitude()*vect->Magnitude());
	projected.y = DotProduct( vect ) / vect->y / (vect->Magnitude()*vect->Magnitude());
	return &projected;
}

#include "vrect.h"

VRect::VRect()
{
	center = new Vector2f( 0, 0 );
	w = 32;
	h = 32;
	ang = 0;
}
VRect::VRect( float new_x, float new_y, float new_w, float new_h )
{
	center = new Vector2f( new_x, new_y );
	w = new_w;
	h = new_h;
	ang = 0;
}
void VRect::WorldCoordinates()
{
   float deg = this->ang/180*PI;

   this->world_coords[0] = new Vector2f((cos(deg) * -this->w - sin(deg) * -this->h)+this->center->x,
                             (sin(deg) * -this->w + cos(deg) * -this->h)+this->center->y);
   
   this->world_coords[1] = new Vector2f((cos(deg) * -this->w - sin(deg) * this->h)+this->center->x,
                             (sin(deg) * -this->w + cos(deg) * this->h)+this->center->y);
   
   this->world_coords[2] = new Vector2f((cos(deg) * this->w - sin(deg) * this->h)+this->center->x,
                             (sin(deg) * this->w + cos(deg) * this->h)+this->center->y);
   
   this->world_coords[3] = new Vector2f((cos(deg) * this->w - sin(deg) * -this->h)+this->center->x,
                             (sin(deg) * this->w + cos(deg) * -this->h)+this->center->y);
   
}

Honestly it's almost copy-pasted with changes may to compile. Can anyone help me see what I'm doing wrong? I implemented the math functions on the vector class myself so they might suck... like i said it seems to return true all the time.

Also ignore the check_x and check_y parameters they aren't used.

[bnpph]

There is no need to use either of those methods for simple 45 degree tile slopes.

How I would do it:
1. Check if player is withing tile boundary box
2. If so, check if relative x >= relative y

Most definitely yes. But if you're going to add 45 degree slopes, using this method you can add slopes of any degree. Why stop at 5 when the full package is 6?

That method works with any right-triangle as long as you scale it properly. Separating axis is for polygonal meshes - most platformers aren't polygon-based.

[N64vSNES]

There is no need to use either of those methods for simple 45 degree tile slopes.

How I would do it:
1. Check if player is withing tile boundary box
2. If so, check if relative x >= relative y

Most definitely yes. But if you're going to add 45 degree slopes, using this method you can add slopes of any degree. Why stop at 5 when the full package is 6?

That method works with any right-triangle as long as you scale it properly. Separating axis is for polygonal meshes - most platformers aren't polygon-based.

Wow wow dude I'm not suggesting separating axis.
And I'll take your word for it if your method is a simpler way. I'm just putting my own suggestion forward

[like80ninjas]

What is the method for doing it without SAT, I'd like to know both.

[Falco Girgis]

I haven't actually sat down and looked at your algorithm, but something really caught my eye:

Code: Select all

void VRect::WorldCoordinates()
{
   float deg = this->ang/180*PI;

   this->world_coords[0] = new Vector2f((cos(deg) * -this->w - sin(deg) * -this->h)+this->center->x,
                             (sin(deg) * -this->w + cos(deg) * -this->h)+this->center->y);
   
   this->world_coords[1] = new Vector2f((cos(deg) * -this->w - sin(deg) * this->h)+this->center->x,
                             (sin(deg) * -this->w + cos(deg) * this->h)+this->center->y);
   
   this->world_coords[2] = new Vector2f((cos(deg) * this->w - sin(deg) * this->h)+this->center->x,
                             (sin(deg) * this->w + cos(deg) * this->h)+this->center->y);
   
   this->world_coords[3] = new Vector2f((cos(deg) * this->w - sin(deg) * -this->h)+this->center->x,
                             (sin(deg) * this->w + cos(deg) * -this->h)+this->center->y);
   
}

I really, REALLY hope you aren't dynamically allocating the world coordinates with new each frame. Why isn't that a stack array of four Vector2's, since you will only ever have four? Not only is this terribly slow each frame, but I don't see where you are even calling delete[] to free the memory.

MEMORY LEAK ALERT!

[like80ninjas]

At the moment it isn't suppose to be any sort of fast, I just want to get it to work first lol.

[Falco Girgis]

At the moment it isn't suppose to be any sort of fast, I just want to get it to work first lol.

This isn't a matter of speed, optimization, or design. This is a matter of you're committing an unforgivable C/++ crime.

You're leaking 256 bytes of memory every frame.

How much harder would it be to change that array of pointers to just an array and not call new? It would be even easier.

You don't happen to come from a C#/Java background, do you?