Collision Rectangles

The Partridge Family were neither partridges nor a family. Discuss.
MrGodin
Posts: 721
Joined: November 30th, 2013, 7:40 pm
Location: Merville, British Columbia Canada

Collision Rectangles

Post by MrGodin » November 11th, 2017, 1:05 am

So I am working on my platformer and decided to change things up a bit. What I've done is to encapsulate tiles that are non passable (solid) that are adjacent to one another (right now just ones on the same row) int o a single rectangle. This works fine for horizontal neighbors but I am struggling with vertical ones (keeping them separate from horizontal). Here is what i have so far

Code: Select all

void Level::GetCollisionRects()
{
	for (int r = 0; r < m_currentLevelData.rowsColumns.y; r++)
	{
		RectF rect;
		for (int c = 0; c < m_currentLevelData.rowsColumns.x; c++)
		{
			const int index = r *m_currentLevelData.rowsColumns.x + c;
			Tile* t = GetTile(index);
			if (t)
			{
				if (!t->Passable())// solid
				{
					rect = t->CollisionRect();
					// pass the column (c) as a reference so SetCollisionRect can iterate through
					// the column and qwhen done, this (c) will be the new value
					SetCollisionRect(r, c, rect);
					m_collisionRects.push_back(rect);
					
					
				}
				
			}
		}
	}
}
Grow the rectangle here

Code: Select all

void Level::SetCollisionRect(const int & row, int & col, RectF & rect)
{
	
		for ( ;col < m_currentLevelData.rowsColumns.x-1; col++)
		{
			const int index = row *m_currentLevelData.rowsColumns.x + col;
// pass index and the next parameter is -1 or 1 to determine which direction to get the tile 
// horizontally
			Tile* t = GetTileHorizontal(index, 1);
			if (t)
			{
                               // no more tiles to the right so exit
				if (t->Passable())
					return;
				else
				{
					//grow rect
					rect.right = t->CollisionRect().right;
				}
			}

		}
	
}


any suggestions ?
Last edited by MrGodin on November 11th, 2017, 1:20 am, edited 2 times in total.
Curiosity killed the cat, satisfaction brought him back

MrGodin
Posts: 721
Joined: November 30th, 2013, 7:40 pm
Location: Merville, British Columbia Canada

Re: Collision Rectangles

Post by MrGodin » November 11th, 2017, 1:11 am

This is how it looks with the collision rect drawn in white around the tiles
Attachments
Image15.png
(256.06 KiB) Not downloaded yet
Curiosity killed the cat, satisfaction brought him back

MrGodin
Posts: 721
Joined: November 30th, 2013, 7:40 pm
Location: Merville, British Columbia Canada

Re: Collision Rectangles

Post by MrGodin » November 11th, 2017, 1:26 am

I the try and determine which tile is closest

Code: Select all

void Level::GetCollisionRectsInView(Vec2f& player_pos)
{
	m_collisionRectsInView.clear();
	// camera view frustum
	RectF viewRect = m_cam.GetViewFrame();
	for (auto& it : m_collisionRects)
	{
		// if any are inside the view rectangle
		if (it.Overlaps(viewRect))
			m_collisionRectsInView.push_back(it);
	}
	// sort by closest ? .. works but isn't too efficient
	std::sort(m_collisionRectsInView.begin(), m_collisionRectsInView.end(), [player_pos](RectF& A, RectF& B)
	{
		// center of player to center of rectangle
		Vec2f AC(A.left + A.GetWidth() * 0.5f , A.top + A.GetHeight() * 0.5f);
		Vec2f BC(B.left + B.GetWidth() * 0.5f, B.top + B.GetHeight() * 0.5f);
		return (player_pos - AC).LenSq() < (player_pos - BC).LenSq();
	});
	
}
Curiosity killed the cat, satisfaction brought him back

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Collision Rectangles

Post by albinopapa » November 11th, 2017, 2:02 am

If you want efficient, then precalculate the collision rects for the platforms during instantiation of the level. It may take some time to load the level this way, but during play will be fine.

You have an interesting issue though. You have four cases,
1) Solid tiles are aligned horizontally, not touching any tiles above or below.
2) Solid tiles are aligned vertically, not touching any tiles to the left or right.
3) Solid tiles touch in both directions, like say a T shape or + shape.
4) Solid tiles are solo, not touching any other solid tiles.

Then there might be cases where you have multiple rows or multiple columns that can be included in the overall rectangle...think of two rows of solid tiles or a 3 x 2 matrix of solid tiles.

You might have to make multiple passes using the different rules for what tiles to encompass in the rect. For instance, if the shape is a +, do you have a vertical rect with two solo solid tiles on each side, or vice versa, a horizontal rect with solo solid tiles on the top and bottom. Same with a t shape or cross, a horizontal line, a vertical line and a solo solid tile at the top, or a single vertical line with two solo solid tiles on either side of the vertical line.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Collision Rectangles

Post by albinopapa » November 11th, 2017, 2:11 am

As for sorting, I think what you have is fine and is probably a pretty efficient way of doing it. Since there are only a few rects now on screen when you combine them in this fashion. There are only 4 rects in the screenshot you posted, I'd imagine there might be at most 10 doing it this way. Even if there are 50, I still think it'll be fast enough.

If all else, you could track them and only remove the ones that go off screen and add ones that show up instead of starting over by clearing the vector and readding each frame.

You could look into setting up a quadtree for the screen, adding rects to quadtree leaves. If a leaf is empty, you skip and go to next leaf. This would only be super useful though if you have a lot of stuff on screen to check collisions for I suppose.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

MrGodin
Posts: 721
Joined: November 30th, 2013, 7:40 pm
Location: Merville, British Columbia Canada

Re: Collision Rectangles

Post by MrGodin » November 11th, 2017, 5:34 am

Then there might be cases where you have multiple rows or multiple columns that can be included in the overall rectangle...think of two rows of solid tiles or a 3 x 2 matrix of solid tiles.
.. lol yes , i actually want to get it all down to lines and normals for collisions. As in efficient i suppose i meant the order of "closest" is still relevant to velocity and sometimes the order of operations with the surrounding rectangles isn't in proper prespective.
Curiosity killed the cat, satisfaction brought him back

MrGodin
Posts: 721
Joined: November 30th, 2013, 7:40 pm
Location: Merville, British Columbia Canada

Re: Collision Rectangles

Post by MrGodin » November 11th, 2017, 7:03 am

f you want efficient, then precalculate the collision rects for the platforms during instantiation of the level. It may take some time to load the level this way, but during play will be fine.
Yes, all the rectangles in m_collisionRects are set during Initialization
Curiosity killed the cat, satisfaction brought him back

MrGodin
Posts: 721
Joined: November 30th, 2013, 7:40 pm
Location: Merville, British Columbia Canada

Re: Collision Rectangles

Post by MrGodin » November 12th, 2017, 8:02 am

Well now i've gone completely sideways lol. I am trying a new way of collision detection for rectangles and have worked it down to this.
This determines an overlap and penetration;

Code: Select all

bool Intersect::BoundingBox(const RectF& A, const RectF& B, Vec2f& correction)
{
	
		float xOverlap = 0.0f, yOverlap = 0.0f;
		correction = { 0.0f,0.0f };
		// axis are out of any possible collision ?
		bool axisX = (A.Max().x <= B.Min().x || B.Max().x <= A.Min().x);
		bool axisY = (A.Max().y <= B.Min().y || B.Max().y <= A.Min().y);
		if (axisX || axisY)
			return false;
		
		RectF penetration = A;
		penetration.ClipTo(B);
		correction = Vec2f(penetration.right - penetration.left, penetration.bottom - penetration.top);
       return true
}
I am using it in this fashion, but it's a bit janky..

Code: Select all

for (auto& it : m_collisionRectsInView)
	{
		Vec2f correction;
		RectF cRect_ent = ent->GetCollisionRect();
		
		if (Intersect::BoundingBox(cRect_ent, it, correction))
		{
			Vec2f player_pos = m_player.GetPosition();
			Vec2f player_vel = m_player.GetVelocity();
			Vec2i dir(Sign<int>(player_vel.x), Sign<int>(player_vel.y));
			if (correction.x > correction.y)
			{
				player_pos.y += (-dir.y * correction.y);
				player_vel.y = 0.0f;
				m_player.SetPosition(player_pos);
				m_player.SetVelocity(player_vel);
				if (m_player.Type() == _EntityType::player)
				{
					dir.y > 0 ? m_player.SetState(EntityStates::idle) : m_player.SetState(EntityStates::jumping);
				}
				

			}
			else if(correction.x < correction.y)
			{
				
				player_pos.x += (-dir.x * correction.x);
				player_vel.x = -player_vel.x;
				m_player.SetPosition(player_pos);
				m_player.SetVelocity(player_vel);
				m_player.CoreData()->direction.Set(-dir.x);
			}
			
		}
	}
Anyone else take this kind of approach?... not sure what i'm missing..
Curiosity killed the cat, satisfaction brought him back

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Collision Rectangles

Post by albinopapa » November 12th, 2017, 9:33 am

Not really relevant, but this might save some typing in some cases.
Instead of:

Code: Select all

centerA.x < centerB.x ? xOverlap = A.Max().x - B.Min().x : xOverlap = B.Max().x - A.Min().x;
centerA.y < centerB.y ? yOverlap = A.Max().y - B.Min().y : yOverlap = B.Max().y - A.Min().y;

      correction = Vec2f(xOverlap, yOverlap);

if (m_player.Type() == _EntityType::player)
{
     dir.y > 0 ? m_player.SetState(EntityStates::idle) : m_player.SetState(EntityStates::jumping);
}
You could use the fact that the ternary operator can return values, not just choose a path of execution

Code: Select all

correction.x = centerA.x < centerB.x ? A.Max().x - B.Min().x : B.Max().x - A.Min().x;
correction.y = centerA.y < centerB.y ? A.Max().y - B.Min().y : B.Max().y - A.Min().y;

if (m_player.Type() == _EntityType::player)
{
     m_player.SetState( dir.y > 0 ? EntityStates::idle : EntityStates::jumping );
     // or
     // const auto state = dir.y > 0 ? EntityState::idle : EntityState::jumping;
     // m_player.SetState( state );
}
This has the benefit of making your variables const when initializing them.

This:

Code: Select all

bool Intersect::BoundingBox(const RectF& A, const RectF& B, Vec2f& correction)
{
      float xOverlap = 0.0f, yOverlap = 0.0f;
      correction = { 0.0f,0.0f };

      // axis are out of any possible collision ?
      bool axisX = (A.Max().x <= B.Min().x || B.Max().x <= A.Min().x);
      bool axisY = (A.Max().y <= B.Min().y || B.Max().y <= A.Min().y);

      if (axisX || axisY) 
            return false;

      Vec2f centerA = Vec2f((A.Min().x + A.Max().x) / 2.0f, (A.Min().y + A.Max().y) / 2.0f);
      Vec2f centerB = Vec2f((B.Min().x + B.Max().x) / 2.0f, (B.Min().y + B.Max().y) / 2.0f);

      centerA.x < centerB.x ? xOverlap = A.Max().x - B.Min().x : 
            xOverlap = B.Max().x - A.Min().x;
      centerA.y < centerB.y ? yOverlap = A.Max().y - B.Min().y : 
            yOverlap = B.Max().y - A.Min().y;

      correction = Vec2f(xOverlap, yOverlap);

      return true;
}
Becomes:

Code: Select all

bool Intersect::BoundingBox(const RectF& A, const RectF& B, Vec2f& correction)
{
      // axis are out of any possible collision ?
      const bool axisX = (A.Max().x <= B.Min().x || B.Max().x <= A.Min().x);
      const bool axisY = (A.Max().y <= B.Min().y || B.Max().y <= A.Min().y);

      if (axisX || axisY)
      {
            correction = { 0.0f,0.0f };
            return false;
      }

      const Vec2f centerA = Vec2f((A.Min().x + A.Max().x) / 2.0f, (A.Min().y + A.Max().y) / 2.0f);
      const Vec2f centerB = Vec2f((B.Min().x + B.Max().x) / 2.0f, (B.Min().y + B.Max().y) / 2.0f);

      correction = Vec2f( 
            centerA.x < centerB.x ? A.Max().x - B.Min().x : B.Max().x - A.Min().x,
            centerA.y < centerB.y ? A.Max().y - B.Min().y : B.Max().y - A.Min().y
      );

      return true;
}
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

MrGodin
Posts: 721
Joined: November 30th, 2013, 7:40 pm
Location: Merville, British Columbia Canada

Re: Collision Rectangles

Post by MrGodin » November 12th, 2017, 9:47 am

Hehe, i've hacked it down to this

Code: Select all

bool Intersect::BoundingBox(const RectF& A, const RectF& B, Vec2f& correction)
{
		
	if (!A.Overlaps(B))
	{
		correction = { 0.0f,0.0f };
		return false;
	}
			
	RectF penetration = A;
	penetration.ClipTo(B);
	correction = Vec2f(penetration.GetWidth(), penetration.GetHeight());
  return true;
}
Curiosity killed the cat, satisfaction brought him back

Post Reply