[C++/SDL2] Tile Based Collision Detection

[HalfNOoB]

Hi guys

I've posted this question some time ago but couldn't solve it up until now...
(Old Topic: http://www.cplusplus.com/forum/general/144884/) I've just been doing some other stuff up until now but I got to a Point where i can no longer ignore the collisions...

I hope there are some more expierenced SDL-users who are able to help me. I do get the principle of detecting collisions of a single object such as the Player with another object like a wall.

Setting:
I'm working with rectangular tiles/grids that are loaded from a ".txt"-file containing the map data into a vector of the type "CTile" who is a puclic member of the class "CMap". The map loading works just fine and without Errors. The way I do the maploading is from sdltutorials.com (http://www.sdltutorials.com/sdl-maps) in case you'd like to check up on it.

The class "CTile" has two variables in it: TileID (e.g. Grass / Brick-Tile,...) and the TypeID (e.g. walkable, hurts Player, Player can move through,...).

So to check for collision, we have to use TypeID. Thats as far as i know what to do :P

What's recommended? Should I check my Player with EVERY tile rendered on the Screen or is there a way to check just with the tiles around my Player? How can I do that? Tips are appreciated, code examples even more ^^. the Movement of the Player is separated in X and Y-axis (if it helps)

I've already searched on Google and didn't find anything understandable.

(If necessary I'll upload my Project on GitHub, just tell me to)

I hope we can solve it this time, Greets

HalfNOoB

[ezchgg]

If you know where the player is, then why can't you just check the adjacent tiles positions? Just to get the 4 sides near the current position would just be adding and subtracting 1 from the player's position. Then using that coordinate in the map to see what type of tile is there.

(0,0)  (1,0)  (2,0)
(0,1)  (1,1)  (2,1)
(0,2)  (1,2)  (2,2)

So if the player is at (1,1) do you see how to get the coordinates of adjacent tiles?

[poteto]

* http://lazyfoo.net/tutorials/SDL/39_tiling/index.php *

[HalfNOoB]

I do get what you mean :) This will be a pretty fast way to do so i think, since the Computer will have to check only few tiles...


my Players dimensions are:

int PlayerWidth = 28;
int PlayerHeight = 32;

if I'm right he can stand at a Maximum of 9 tiles (16x16) and a Minimum of 4 tiles right? But how does that help me?

Should i do something with the move direction?

like

 if (SpeedX > 0) //moving to the right
{
    if (Map.TileList[...].TypeID == 1) //If Tile on right side of Player is TypeID 1 which is blocking
    {
       if (CheckCollision(rcColPlayer, Map.TileList[y*map_size_in_tiles + x].rcDestination) == true)
       {
           PosX --;
       }
    }

}

Could this work? I would Need to add a SDL_Rect to each CTile and then do normal collision detection with the hitbox of the Player?

Thanks for your help! Ill clean up my code tommorrow evening and upload it to GitHub :)

[HalfNOoB]

Thanks poteto, but I usually don't really like the way lazyfoo does things...

But somehow his Approach makes sense to me xdd


1) Setting the collisionrectangels for the Player and the tiles

2) check if tiles are on Screen --> compare camera-rectangle with tile-rectangle

3) whenever I move, check for collision between the Player-rectangle and tile-rectangle. Loop through all tiles with a for Loop...

4) if theres collision between Player & tile set the movement back??? thats why i hate lazyfoo :P Why set it back? I want it to be as Close to the tile as possible :)

5) render tiles & Player relatively to camera

Any corrections? if not, ill try to implement a System like this to my Project...

[Z e r e o]

4) if theres collision between Player & tile set the movement back??? thats why i hate lazyfoo :P Why set it back? I want it to be as Close to the tile as possible :)

Generally I would do the collision detection before I actually move the object and not move the object and then do collision detection.

To do so is quite simple

1. Calculate where you are going to be moving to and store that value temporarily.
2. Run collision checks on that new position
   a. If no collisions happen move to that location 
   b. If collisions do happen run whatever needs to happen. 

For b. it could be something simple like destroying the object, or in your case if you want to move as close as possible to the collision point just recalculate the movement to be as close as possible and then move the object.

Other then that you collision process seems sound. Though you might need to add in some more checks later to reduce the number of collision checks you need to do but that is only if you start getting a large number of objects that can collide on the screen.

[HalfNOoB]

I'm working on the collision System... I think I'll go with something like the one of jnrdev#1...

As soon as I am done with it I'll post it here :)

If you still got suggestions, feel free :P

[poteto]

I recommend the lazy foo way because it only has 2 if statements with only 2 values, which is elegant.

But I would change it so that when you press a key, you dont +=, instead just =, so that there isnt the bug where if you hold down a key like "d" then click out the window, and go back in and holding "d" again.

[HalfNOoB]

Well thats true... But in my opinion, the jnrdev way is more efficient. have you checked it out?

http://web.archive.org/web/20100618081806/http://jnrdev.72dpiarmy.com/

It's only checking the tiles of a certain area... I couldn't finish yesterday evening so ill just do it tomorrow... (Not on Christmas eve :P)

If it Fails, ill go with the lazy foo way as recommended from you :)

thanks for everything so far

[HalfNOoB]

Somehow it won't work out as planned :/

I have uploaded my project to GitHub: https://github.com/HalfNOoBee/Collision-Problem
(Hopefully everything is working ^^)

As soon as the tile under the player is solid (TypeID = 1) the movement of the player is restricted. I can only move in an area of 4 pixels. If I jump and the TypeID of the tile under the play is 0, then i can move around freely... I'm sure that I'm pretty close but I can't figure out the last step myself :/

Would be great if you guys could help me out :) The functions that are mattering for collision detection can be found in CPlayer and CMap...

[poteto]

If you care about efficiency and the map is monospaced, you could immediately find the tile that you are colliding like this:

This is only for the x value, you can easily add in the y if you want.

 //note: if tile width > player.w*2, this wont work, but you can add a points down the middle to fix it.
bool Check_Collision(/*entity object*/) //pretending that tileset & player are global values
{
  //note: removing the remainder is unnecessary because the compiler will automatically round it, but its just my style
  if( tileset[ ( player.x - ( player.x % tile_width ) ) / tile_width ].solid ) 
    return true;
  //Now we check the right corner (or topright if this was 2d)
  else if( tileset[ ( player.x + player.w - ( ( player.x+player.w ) % tile_width) / tile_width) ].solid )
    return true;
  else
    return false; //no collisions.
}

[HalfNOoB]

I like your style then :P

Well basically thats what I'm already doing. I'm calculating the tiles im on and Loop through them (with a for-loop)

bool CPlayer::Collision_Hor(int x, int y, int &TileCoordY, CMap* Map)
{
	int TileXInPixels = x - (x % Tile.GetSize());	//calculate the x position (pixels!) of the tiles we check against
	int CheckEnd = x + PLAYER_WIDTH;		//calculate the end of testing (just to save the x+w calculation each for loop)

	TileCoordY = y / Tile.GetSize();			//calculate the y position (map coordinates!) of the tiles we want to test

	int TileCoordX = TileXInPixels / Tile.GetSize();	//calculate map x coordinate for first tile

	while(TileXInPixels <= CheckEnd)
    {
		if(Map->GetTypeOfTile(TileCoordX, TileCoordY) == 1)
        {
			return true;
        }

		TileCoordX++;
		TileXInPixels += Tile.GetSize();
	}

	return false;
}

bool CPlayer::Collision_Ver(int x, int y, int &TileCoordX, CMap* Map)
{
	int TileYInPixels = y - (y % Tile.GetSize());
	int CheckEnd = y + PLAYER_HEIGHT;

	TileCoordX = x / Tile.GetSize();

	int TileCoordY = TileYInPixels / Tile.GetSize();

	while(TileYInPixels <= CheckEnd)
    {
		if(Map->GetTypeOfTile(TileCoordX, TileCoordY) == 1)
        {
            std::cout << TileCoordX << "/" << TileCoordY << "\n";
            return true;
        }

		TileCoordY++;
		TileYInPixels += Tile.GetSize();
	}

	return false;
}

Here is the GetTypeOfTile()-funtion

int CMap::GetTypeOfTile(int X, int Y)
{
    return TileList[Y * MAP_WIDTH_IN_TILES + X].TypeID;
}

and this is where I'm actually checking for collision and tell the Compiler what to do if a collision occurs...

void CPlayer::Update(CMap* Map)
{

    VelX = 0;
    VelY = 0;
    PosY += 1.0f; //Gravity

    SDL_PumpEvents();

    const Uint8* Keystates = SDL_GetKeyboardState(NULL);

    if (Keystates[SDL_SCANCODE_A])
    {
        m_bMovingLeft = true;
        VelX = -4;
        CurrentFrame++;
    }
    else if (Keystates[SDL_SCANCODE_D])
    {
        m_bMovingRight = true;
        VelX = 4;
        CurrentFrame++;
    }
    else if (Keystates[SDL_SCANCODE_SPACE])
    {
        if (m_bLockJump == true)
        {
            m_bisJumping = true;
            VelY = -VELOCITY_Y;
            CurrentFrame = 1;
        }

    }
    int TilePos = 0;

    std::cout << "MovingLeft in Update(): " << m_bMovingLeft << "\n";
    std::cout << "MovingRight in Update(): " << m_bMovingRight << "\n";

	//x axis first (--)
	if(VelX > 0) //right
    {
		if(Collision_Ver(PosX + VelX + PLAYER_WIDTH, PosY, TilePos, Map) == true)
        {
			PosX = (TilePos * Tile.GetSize()) - PLAYER_WIDTH;
			std::cout << "collision: Setting player to " << PosX << " ///// " << "TilePos: " << TilePos <<"\n";
        }
		else
        {
            PosX += VelX;
            std::cout << "no collision: moving right...\n";
        }

	}
	else if(VelX < 0) //left
	{
		if(Collision_Ver((PosX + VelX), PosY, TilePos, Map) == true)
        {
            PosX = (TilePos + 1)* Tile.GetSize();
            std::cout << "collision: Setting player to " << PosX << " ///// " << "TilePos: " << TilePos <<"\n";
        }
		else
        {
            PosX += VelX;
        }

	}

	//then y axis (|)
	if(VelY < 0) //up
    {
		if(Collision_Hor(PosX, (PosY + VelY), TilePos, Map) == 1)
        {
			PosY = (TilePos + 1)* Tile.GetSize();
			VelY = 0;
			std::cout << "collision: Setting player to " << PosY << " ///// " << "TilePos: " << TilePos <<"\n";
		}
		else
        {
			PosY	+= VelY;
			PosY	+= 1;
		}
	}
	else
    {		//moving down / on ground
		//printf("test: down, vely:%d\n", vely);
		if(Collision_Hor(PosX, (PosY + VelY + PLAYER_HEIGHT), TilePos, Map))
		{
			PosY = (TilePos * Tile.GetSize()) - PLAYER_HEIGHT;
			VelY = 1;

			/*if(!keystates[SDLK_RSHIFT])	//player only may jump again if the jump key is released while on ground
				lockjump = false;*/
		}
		else
        {
			PosY += VelY;
			VelY += 1;

			if(VelY >= Tile.GetSize())
            {
				VelY = Tile.GetSize();
            }

			m_bLockJump = true;			//don't allow jumping after falling of an edge
		}
	}
}

I know it's a lot of code... Ignore the std::cout-statements, they sould have helped me Debugging (but they didn't) Does anyone see an obvîous error?

[poteto]

Man... you have to focus on making your code as short as possible...

Firstly for the love of god remove the C's that you put infront of your filenames and class names...

You don't need 2 functions for vertical and horizontal collisions...

I recommend using the "SDL_Rect" way, and for entities you use lazyfoo's collision function:

bool collision( SDL_Rect a, SDL_Rect b )
{
  int leftA = a.x, leftB = b.x;
  int rightA = a.x + a.w, rightB = b.x + b.w;
  int topA = a.y, topB = b.y;
  int bottomA = a.y + a.h, bottomB = b.y + b.h;

  if( bottomA <= topB )
      return false;
  else if( topA >= bottomB )
      return false;
  else if( rightA <= leftB )
      return false;
  else if( leftA >= rightB )
      return false;
  return true;
}

And for tile collisions, create the function I showed you above, with x&y, and takes the arguments: bool tile_collision(SDL_Rect a,int tiles[][1000]), also make your tiles not pointers, in c++ there is no point of using pointers unless your using dynamic memory(don't), or using polymorphism.

If you think that you can't make grass move because of using the int, you can create a last_x, & last_y in your player, do in player's loop:if(xpos/tile_size != last_x || ypos/tile_size != last_y){last_x=xpos/tile_size;//then y... , then if the tile is grass, I would insert a "moving_grass_entity" infront of the entity list ontop of that tile that only lasts a sec.

You should first change your game into a state-full system.
Essentially use polymorphism, make an abstract class like this:

class State
{
  public:
  virtual void Input() = 0; 
  virtual void Logic() = 0; 
  virtual void Render() = 0;
  virtual ~State(){};
};

Then make 2 classes called StartScreen and Game, beside the class's name, do : public State, then make sure that it has the 3 functions.

Make an "enum class" called States with "STATE_STARTSCREEN", and "STATE_GAME", and "STATE_NULL".

Make a global variable(in a header like global.h) called State* CurrentState = STATE_NULL;
Then in main, before the loop do: CurrentState = new StartScreen();(and to be neat remember to delete current state after the main loop.)

Now you can use current state in your loop.

//new starscreen state
while(!quit)
{
  while( SDL_PollEvent( &e ) != 0 )
  {
    //User requests quit
    if( e.type == SDL_QUIT )
    {
      quit = true; 
    }
    CurrentState->Input(); //like over here
  }
  //Clear screen
  SDL_SetRenderDrawColor( Renderer, 0, 0, 0, 255 ); //clear with black
  SDL_RenderClear( Renderer );

  CurrentState->Main(); //or over here

  CurrentState->Render(); //and over here

  ChangeState(); //I'll explain

  //Update Screen
  SDL_RenderPresent( Renderer );

  SDL_Delay(5); //to save cpu
  }
}
//delete current state 

Now for ChangeState();

Make another global variable States Next_State = States::STATE_NULL;.

ChangeState basically checks if next_state is not null, if it isnt it changes the state.

void ChangeState()
{
  if(nextState != STATE_NULL)
  {
    delete CurrentState;

    switch(nextState)
    {
    case STATE_STARTSCREEN:
      nextState = STATE_NULL;
      CurrentState = new StartScreen();
      break;
    case STATE_GAME:
      nextState = STATE_NULL;
      CurrentState = new Game();
      break;
    }
  }
}

And now instead of having a class called player, you can just put the variables into Game's class, and in it is the int tileset[1000][1000]; ,your map isnt 1000 tiles big, its just the buffer(if you think your map could be bigger, increase it), you will have a global variable called MAP_WIDTH & MAP_HEIGHT that are defined when you read your map(the first 2 numbers in my file define mine).

And then you will have a vector of entities with polymorphism, with "think" or "logic", and "render" or "draw". The abstract class will also require int type, x, y;, and logic requires the parameters of the entities, in reference, and tiles, maybe reference(if the map is not modifiable). Render should also have a parameter of a rect called camera, if you pan over your character.

Also if you need a working example of states here is lazyfoos:
http://lazyfoo.net/articles/article06/index.php

[HalfNOoB]

Hi poteto


Thanks for the variety of your tips! You are right, I have yet to implement a state Manager class, but since I'm not too well-informed about encapsulation, inheritance and the likes this will have to wait some more time. The linked tutorial will be help for sure :)

The "C" before a class was recommended by the book to eazily find out that it's a type i defined/declared myself. Probably the book is way too outdated ^^

I could fix the error: For those interested ;) I missed out on a -1 in the Collision_Ver()-function.

The entitycheck is already Happening the way you suggest poteto... Right now they are checked individually, but in the near future I'll probably create an Entity class and create a vector storing all entities. Then Looping through the vector and check for collision between the hitboxes (still being rectangles). Same Thing for enemies...

I won't go anymore off-Topic sorry... Thanks everyone, especially poteto! :D