I'v been working on this game for "OneGameAMonth". So far it's been going pretty good, with only minor hiccups until just recently. I'm trying to do the collision and I just can't figure out what to do!

My world is built on a grid ( 2D array ) and uses 32x32 tiles, my Player and Monsters however are free moving and not bound by the grid, this has caused some problems when trying to do collision.

Here is an image:


Frankly I don't know how to do it, I tried converting my character coordinates to tile coordinates which works kinda... until you try to move through the small passages or "doorways", then it goes wild, suddenly you can walk through walls and what not.

The code looks something like this:

void Player::update(float dt, const Tiles& tiles)
{
	float x = m_x;
	float y = m_y;
	
	if( sf::Keyboard::isKeyPressed( sf::Keyboard::Up ) )
	{
		y -= m_speed;
	}
	if( sf::Keyboard::isKeyPressed( sf::Keyboard::Down ) )
	{
		y += m_speed;
	} 
	if( sf::Keyboard::isKeyPressed( sf::Keyboard::Left ) )
	{
		x -= m_speed;
	} 
	if( sf::Keyboard::isKeyPressed( sf::Keyboard::Right ) )
	{
		x += m_speed;
	}
	
	int topY = y / 32;
	int leftX = x / 32;
	int bottomY = ( 32 + y )/32;
	int rightX = ( 32 + x )/32;
	
	if( tiles[leftX][topY] == 1 && tiles[rightX][topY] == 1)
	{
		m_x = x;
	}
	
	if( tiles[leftX][bottomY] == 1 && tiles[rightX][bottomY] == 1)
	{
		m_y = y;
	}
	
	m_sprite.setPosition(m_x, m_y);
}

I'm out of ideas and don't know what to do!

EDIT:
I'm using C++ and SFML

The way I done my collision in Java was to bound each object that requires collision detection to be bounded by a Rectangle object(which is built into the Java language) and you can use the built in intersects method to see if these rectangles overlapped. This type of bounding box or bounding rectangle collision works well for circle, oval or rectangle shaped objects which would pretty much work with the objects you have in the picture above. Your code looks like OOP C++ so there is probably something similar for that language.

I am curious about your code. Why are you testing for the elements in a 2D array to be equal to 1? Is that the code to prevent the character from reaching a certain boundary?

The way I done my collision in Java was to bound each object that requires collision detection to be bounded by a Rectangle object(which is built into the Java language) and you can use the built in intersects method to see if these rectangles overlapped. This type of bounding box or bounding rectangle collision works well for circle, oval or rectangle shaped objects which would pretty much work with the objects you have in the picture above. Your code looks like OOP C++ so there is probably something similar for that language.

I am curious about your code. Why are you testing for the elements in a 2D array to be equal to 1? Is that the code to prevent the character from reaching a certain boundary?

Yes, SFML does have a rectangle class, but I'm quite new to collision detection and I didn't quite know what to do with the tiles, seeing as a tile is just a number I can't attach any additional information, such as a bounding box, and really seeing as the map is 1000x1000 I think maybe that many bounding-boxes would be a bit to much?

I'm testing against 1 seeing as that is the walkable tile.

You should be able to treat the Rectangle object like a data member(C++)/instance variable(Java) of the Wall class.

In Java, it would look like this:

public class Wall{

private Rectangle rectangle;

}

In your case, it would look similar to this:

public class Tiles{

private Rectangle rectangle;

}

The idea I have is that you can test for collision when the character is close to object it is not suppose to be able to over-lap. That would make the code less expensive.

You should be able to treat the Rectangle object like a data member(C++)/instance variable(Java) of the Wall class.

In Java, it would look like this:

public class Wall{

private Rectangle rectangle;

}

In your case, it would look similar to this:

public class Tiles{

private Rectangle rectangle;

}

The idea I have is that you can test for collision when the character is close to object it is not suppose to be able to over-lap. That would make the code less expensive.

But I don't want to have a tile class, i.e I don't want to have 1'000'000 bounding boxes....



EDIT:

I came up with this:

void Player::collision(Tiles& tiles)
{
	int startY = ( m_y - 32 ) / 32;
	int startX = ( m_x - 32 ) / 32;
	int endY = ( m_y + 64 ) / 32;
	int endX = ( m_x + 64) / 32;
	
	for( int sy = startY; sy < endY; sy++ )
	{
		for( int sx = startX; sx < endX; sx++ )
		{
			if( tiles[sx][sy] != 1 && tiles[sx][sy] != 5 )
			{
				sf::IntRect wall;
				wall.top = sy * 32;
				wall.left = sx * 32;
				wall.width = 32;
				wall.height = 32;
				m_boundingbox.top = m_nextY+20;
				m_boundingbox.left = m_nextX+8;
				if(m_boundingbox.intersects(wall))
				{
					return;
				}
				
			}
		}
	}
	m_x = m_nextX;
	m_y = m_nextY;
}

That's true about lots of bounding boxes. Now that I think about it some more, you might want to try creating a bounding box around the object only when the collision function is called.

How can the character be towards the left but slide on the x axis to the right?

On a side note: you should try to avoid "magic numbers" instead replace the value of a variable with a variable name.

until you try to move through the small passages or "doorways", then it goes wild, suddenly you can walk through walls and what not.

I've encountered this problem too. Try giving your free moving entities a slightly smaller rectangle, so that there won't be any exact fits.

It works BUT... I'm not sure how to make the character "slide" against a wall if the collision is only because of one axis. Example:
If you are moving both up and right and there is an collision because you are moving upwards you don't want to move up but towards the left instead, making the character slide on the x-axis ( to the right ).

What you want to do is make two collision checks. First, check for collision along the X axis (the destination X value + the old Y value) then check for collision along the Y axis (the destination Y value + the "old" X value. Note that this X value would have been updated to the new position if the previous check had no collision).

It works BUT... I'm not sure how to make the character "slide" against a wall if the collision is only because of one axis. Example:
If you are moving both up and right and there is an collision because you are moving upwards you don't want to move up but towards the left instead, making the character slide on the x-axis ( to the right ).

What you want to do is make two collision checks. First, check for collision along the X axis (the destination X value + the old Y value) then check for collision along the Y axis (the destination Y value + the "old" X value. Note that this X value would have been updated to the new position if the previous check had no collision).

Yes I was trying for that last night but it didn't want to work, I revamped the code ( you gave me an idea ) and here is the working code if anyone runs into the same problem:

void Player::update(float dt, const Tiles& tiles)
{
	float x = m_x;
	float y = m_y;
	
	if( sf::Keyboard::isKeyPressed( sf::Keyboard::Up ) )
	{
		y -= m_speed;
	}
	if( sf::Keyboard::isKeyPressed( sf::Keyboard::Down ) )
	{
		y += m_speed;
	} 
	if( sf::Keyboard::isKeyPressed( sf::Keyboard::Left ) )
	{
		x -= m_speed;
	} 
	if( sf::Keyboard::isKeyPressed( sf::Keyboard::Right ) )
	{
		x += m_speed;
	}
	
	// Find the nerest tiles around the player.
	int startY = ( m_y - 32 ) / 32;
	int startX = ( m_x - 32 ) / 32;
	// We add 64 because we need to compensate the sprites width as well.
	int endY = ( m_y + 64 ) / 32;
	int endX = ( m_x + 64) / 32;
	
	// Set up the movement variables.
	bool moveX = true;
	bool moveY = true;
	
	// Iterate through the nerest tiles.
	for( int sy = startY; sy < endY; sy++ )
	{
		for( int sx = startX; sx < endX; sx++ )
		{
			if( tiles[sx][sy] != 1 && tiles[sx][sy] != 5 )
			{
				// For each tile make a boundingbox.
				sf::IntRect wall;
				wall.top = sy * 32;
				wall.left = sx * 32;
				wall.width = 32;
				wall.height = 32;
				
				// Create two boundingboxes for the player, one for X-axis and one for Y-axis.
				sf::IntRect xaxis(x+8,m_y+20,16,8);
				sf::IntRect yaxis(m_x+8,y+20,16,8);
				
				// If we intersect on the x-axis, prevent moving through the x-axis.
				if( xaxis.intersects(wall) )
				{
					moveX = false;
				}
				// If we intersect on the y-axis, prevent moving through the y-axis.
				if( yaxis.intersects(wall) )
				{
					moveY = false;
				}
			}
		}
	}
	// If movement is true, then move accordingly.
	if( moveX ) m_x = x;
	if( moveY ) m_y = y;
}

you should get rid of the moveX and moveY variables.

If you detect a collision you should move the object along the axis such that it just touches the tile.

You should not reset to previous position.