2D Platformer Collision Detection

[firedraco]

So, I've been working on my 2D platformer for a while, and I'm running into a couple of problems. I'm using a line based collision detection (Disch or Duaos suggested it, idr who, and I can't find the thread anymore -_-), but it seems to become laggy even when only about 25 entities need to do collision detection with the 8 walls in the area.

Since it will be completely possible for the player/enemies to create plenty of projectiles that need to check if they are hitting walls, I'm guessing that the reason it is slow is because I implemented it badly. Therefore, if anyone could glance over the code and see if I am doing something stupid, that would be really helpful.

Hopefully the code isn't too hard to read...I know there are some things that I'd like to refactor but if the code itself is the problem then I might as well just rewrite it all differently. I like to think all the function/variable names make it obvious what is going on, but I doubt it...

Only one thing to note: the BOOST_FOREACH(const Edge& edge, this->GetCollisonBoxEdges()) { sections actually aren't a loop, all players and enemies are basically a vertical line for purposes of hitting walls, so that's why there is some weird stuff in there (like assuming the edge is oriented a certain way, etc).

Asset::WallCollision Asset::GetClosestWallCollision(const std::vector<const Room::Wall*>& walls) const {
	typedef std::pair< sf::Vector2<CoordT>, sf::Vector2<CoordT> > Edge;
	const Room::Wall* wall_hit = NULL, * landing_wall = NULL;
	util::intersect_ret temp, closest;
	VelocityT para_vel;
	if(this->m_StandingOn) para_vel = this->m_StandingOn->get_unit_parallel_vector() * this->mVelocity.x;
	else para_vel = this->mVelocity;
	//if we aren't standing on anything, we just move wherever our velocity takes us
	BOOST_FOREACH(const Room::Wall* wall, walls) {
		if(!wall->thin) {
			// test intersections of wall with player collision box
			BOOST_FOREACH(const Edge& edge, this->GetCollisonBoxEdges()) {
				temp = util::find_intersection(std::make_pair(wall->start, wall->start - para_vel), edge);
				if(temp.has_intersect && temp.distance < closest.distance) {
					std::cout<<"wall->start collision with "<<this<<" edge w/ distance of "<<temp.distance<<"\n";
					closest = temp;
					wall_hit = wall;
				}
				temp = util::find_intersection(std::make_pair(wall->end, wall->end - para_vel), edge);
				if(temp.has_intersect && temp.distance < closest.distance) {
					std::cout<<"wall->end collision with "<<this<<" edge w/ distance of "<<temp.distance<<"\n";
					closest = temp;
					wall_hit = wall;
				}
			}
		}
	}
	BOOST_FOREACH(const Edge& edge, this->GetCollisonBoxEdges()) {
		//test intersections of player collision box with walls	
		BOOST_FOREACH(const Room::Wall* wall, walls) {
			if(!wall->thin) {
				temp = util::find_intersection(std::make_pair(edge.first, edge.first + para_vel), std::make_pair(wall->start, wall->end));
				if(temp.has_intersect && temp.distance < closest.distance) {
					std::cout<<this<<"'s top center pt collision with wall w/ distance of "<<temp.distance<<"\n";
					closest = temp;
					wall_hit = wall;
					landing_wall = NULL;
				}
			}
			if(!wall->thin || para_vel.y > 0) {
				temp = util::find_intersection(std::make_pair(edge.second, edge.second + para_vel), std::make_pair(wall->start, wall->end));
				if(temp.has_intersect && temp.distance < closest.distance) {
					std::cout<<this<<"'s bot center pt collision with wall w/ distance of "<<temp.distance<<"\n";
					closest = temp;
					//since this is a bottom (standing part), remember to set that we are LANDING on this wall, not just hitting it!
					wall_hit = landing_wall = wall;
				}
			}
		}
	}
	return WallCollision(wall_hit, landing_wall, closest);
}

	template <typename Coord_Type>
	intersect_ret find_intersection(const std::pair<sf::Vector2<Coord_Type>, sf::Vector2<Coord_Type> >& one, 
		const std::pair<sf::Vector2<Coord_Type>, sf::Vector2<Coord_Type> >& two) {
		//if the lines segments have the same slope, this function will say they have no intersects, regardless of
		//whether they actually do or not
		intersect_ret ret;
		ret.has_intersect = false;
		//
		sf::Vector2<Coord_Type> s1 = one.second - one.first;
		sf::Vector2<Coord_Type> s2 = two.second - two.first;

		double s, t;
		s = (-s1.y * (one.first.x - two.first.x) + s1.x * (one.first.y - two.first.y)) / (-s2.x * s1.y + s1.x * s2.y);
		t = ( s2.x * (one.first.y - two.first.y) - s2.y * (one.first.x - two.first.x)) / (-s2.x * s1.y + s1.x * s2.y);

		if (s >= 0 && s <= 1 && t >= 0 && t <= 1) {
			ret.has_intersect = true;
			ret.distance = t;
			ret.intersection.x = one.first.x + (t * s1.x);
			ret.intersection.y = one.first.y + (t * s1.y);
		}
		return ret;
	}

[MiiNiPaa]

Why is it in the Lounge?

Anyway, I didn't look into code, but it might be that your walls vector is too large to iterate over it efficiently. You can load only neighbour walls into std::deque (allows for fast insertion and deletion on both ends), insert those you came closer to and delete them when you are too far away.

Also cout is unbuffered when directed into windows console and if there is many collisions it can slow down game too. (Outputting 2Mb info on screen ≈1 min, outputting into file: less than one second)

[firedraco]

Why is it in the Lounge?

Because I fail.

Anyway, even when there are only 8 walls, it lags even without any actual collisions, so I don't think that's the issue.

[firedraco]

Bump.