Sign in to follow this  

collision detection in maze issue

This topic is 819 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi,

 

I have been able to successfully generate a random maze but am having issues with the collision detection for a simple square moving around the maze.

 

I have been able to get it to work effectively. My issue I think is in the timestep.

 

My current issue is that when the square is moving along the maze and then comes across a T intersection. Refer picture for better explanation

 

[attachment=29136:collisionDetectionIssue.jpg]

 

The blue player cannot go down.

 

I thought of one way to do it is that when the player stops moving, check to see which direction they were moving and if it is say 3 pixels away from covering the tile completely then move the extra 3 pixels. The problem with this is that if I'm moving say left and down, it still won't go in the down direction until I stop moving.

 

Currently in my code I check all 4 points of the blue square to see what tile it is going to move into. so when he is in that position going down the Right bottom corner will be in a wall so it won't let him move down.

 

Here is all the code for main.cpp. I will eventually move it into classes etc, but just want to get it working properly first.

#include "main.h"

std::vector <int> MazeData;

int TileSizeX = 32;
int TileSizeY = 32;
int playersize = 32;
int scale = 1; // not in use currently
int MazeSizeX = 15; int MazeSizeY = 15;
struct collision
{
	bool TopLeft;
	bool TopRight;
	bool BottomLeft;
	bool BottomRight;
};
collision CheckCollision(sf::Vector2f PlayerPosition, int movex, int movey); // check to see if new position is valid

int main()
{
	float TimePerFrame = 1.f / 60.f; // 60 updates a second
	float timesincelastupdate = 0;
	sf::Clock DeltaTime;
	sf::Clock FPS;
	DeltaTime.restart().asSeconds();
	FPS.restart().asSeconds();
	int framerate = 0;

	float DT; // Delta Time

	sf::RenderWindow mywindow(sf::VideoMode(912,912),"Mazes");
	srand( unsigned (time(0)));
	MazeData.resize(MazeSizeX*MazeSizeY);

	MazeGenerator NewMaze;
	NewMaze.GenerateNewMaze(MazeData, MazeSizeX, MazeSizeY);

	sf::Sprite Wall;
	sf::Sprite Floor;
	sf::Sprite Player;
	sf::Texture WallTexture;
	sf::Texture FloorTexture;
	sf::Texture PlayerTexture;
	PlayerTexture.loadFromFile("./Res/Player.png", sf::IntRect(0, 0, playersize, playersize));
	WallTexture.loadFromFile("./Res/Wall.png", sf::IntRect(0, 0, TileSizeX, TileSizeY));
	FloorTexture.loadFromFile("./Res/Floor.png", sf::IntRect(0, 0, TileSizeX, TileSizeY));
	Wall.setTexture(WallTexture);
	Floor.setTexture(FloorTexture);
	Player.setTexture(PlayerTexture);
	// setup player
	int x = 1; int y = 1;
	Player.setPosition(x * TileSizeX, y * TileSizeX); 
	float PlayerSpeed = 400.0f;
	int MoveX = 0;
	int MoveY = 0;



	while (mywindow.isOpen())
	{
		sf::Event event;
		while (mywindow.pollEvent(event))
		{
			if (event.type == sf::Event::Closed)
				mywindow.close();
		}
		if (sf::Keyboard::isKeyPressed(sf::Keyboard::Escape))
		{
			mywindow.close();
		}
		while (timesincelastupdate > TimePerFrame)
		{
			MoveY = 0;
			MoveX = 0;
			timesincelastupdate -= TimePerFrame;
			if (sf::Keyboard::isKeyPressed(sf::Keyboard::Up))
			{
				MoveY += -1;
			}
			if (sf::Keyboard::isKeyPressed(sf::Keyboard::Down))
			{
				MoveY += 1;
			}
			if (sf::Keyboard::isKeyPressed(sf::Keyboard::Left))
			{
				MoveX += -1;
			}
			if (sf::Keyboard::isKeyPressed(sf::Keyboard::Right))
			{
				MoveX += 1;
			}
			float PlayerPosX = 0;
			float PlayerPosY = 0;
			if (MoveX != 0)
			{
				PlayerPosX = Player.getPosition().x;
				float test = PlayerPosX;
				PlayerPosY = Player.getPosition().y;
				if (MoveX == 1)
				{
					PlayerPosX += TileSizeX; // if player moving right, check right side of player
				}
				PlayerPosX += MoveX * PlayerSpeed * TimePerFrame;
				int tilex = PlayerPosX / TileSizeX;
				int tiley = PlayerPosY / TileSizeY;
				int newtile = tilex + (tiley * MazeSizeX);
				if (MazeData[newtile] != 0)
				{
					collision collide = CheckCollision(Player.getPosition(), MoveX, 0);
					if (collide.TopLeft == false && collide.TopRight == false 
						&& collide.BottomLeft == false && collide.BottomRight == false)
					{
						Player.move(TimePerFrame * PlayerSpeed * MoveX, 0); // no collision so move player
					}
				}
				if (MoveX == -1 && MazeData[newtile]  == 0) // moving left and hit wall tile so we move player up against wall
				{
					int xtile = newtile % MazeSizeX;
					int ytile = newtile / MazeSizeX;

					Player.setPosition((xtile * TileSizeX) + TileSizeX, Player.getPosition().y);
				}
				if (MoveX == 1 && MazeData[newtile] == 0) // moving right and hit wall tile so we move player up against wall
				{
					int xtile = newtile % MazeSizeX;
					int ytile = newtile / MazeSizeX;

					Player.setPosition((xtile * TileSizeX) - TileSizeX, Player.getPosition().y);
				}
			}
			if (MoveY != 0)
			{
				PlayerPosX = Player.getPosition().x;
				PlayerPosY = Player.getPosition().y;
				PlayerPosY += MoveY * PlayerSpeed * TimePerFrame;
				int tilex = PlayerPosX / TileSizeX;
				if (MoveY == 1)
				{
					PlayerPosY += TileSizeY;
				}
				int tiley = PlayerPosY / TileSizeY;
				int newtile = tilex + (tiley * MazeSizeX);
				if (MazeData[newtile] != 0)
				{
					collision collide = CheckCollision(Player.getPosition(), 0, MoveY);
					if (collide.TopLeft == false && collide.TopRight == false
						&& collide.BottomLeft == false && collide.BottomRight == false)
					{
						Player.move(0, TimePerFrame * PlayerSpeed * MoveY);
					}
				}
				if (MoveY == -1 && MazeData[newtile] == 0) // moving left and hit wall tile so we move player up against wall
				{
					int xtile = newtile % MazeSizeX;
					int ytile = newtile / MazeSizeX;

					Player.setPosition(Player.getPosition().x, (ytile * TileSizeY) + TileSizeY);
				}
				if (MoveY == 1 && MazeData[newtile] == 0) // moving right and hit wall tile so we move player up against wall
				{
					int xtile = newtile % MazeSizeX;
					int ytile = newtile / MazeSizeX;

					Player.setPosition(Player.getPosition().x, (ytile * TileSizeY) - TileSizeY);
				}
			}
		}
		mywindow.clear(sf::Color::Blue);
		// DRAW TILES
		for (int x = 0; x < MazeSizeX; x++)
		{
			for (int y = 0; y < MazeSizeY; y++)
			{
				int a = MazeData[x + y * MazeSizeX];
				if (a == 0)//draw wall
				{
					Wall.setPosition(x * TileSizeX * scale, y * TileSizeY * scale);
					mywindow.draw(Wall);
				}
				else // draw floor
				{
					Floor.setPosition(x * TileSizeX * scale, y * TileSizeY * scale);
					mywindow.draw(Floor);
				}
			}
		}
		// draw player
		mywindow.draw(Player);
		mywindow.display();
		framerate++;
		DT = DeltaTime.getElapsedTime().asSeconds();
		timesincelastupdate += DT;
		PlayerMovecount -= DT;
		DeltaTime.restart().asSeconds();
		//
		if (FPS.getElapsedTime().asSeconds() > 1.0)
		{
			// 1 second has passed so print FPS in title
			mywindow.setTitle("Mazes V0.3  |  " + std::to_string(framerate) + " FPS");
			framerate = 0;
			FPS.restart().asSeconds();
		}
	}
	return 0;
}

collision CheckCollision(sf::Vector2f PlayerPosition, int movex, int movey)
{
	collision testcollision{ false, false, false, false };
	float PosX = PlayerPosition.x + movex;
	float PosY = PlayerPosition.y + movey;
	int tilex = (PosX / TileSizeX);
	int tiley = (PosY / TileSizeY);

	int newtileTL = tilex + (tiley * MazeSizeX);
	tilex = (PosX + TileSizeX -1) / TileSizeX; // top right
	tiley = (PosY / TileSizeY);

	int newtileTR = tilex + (tiley * MazeSizeX);
	tilex = (PosX / TileSizeX ); // Bottom Left;
	tiley = (PosY + TileSizeY-1) / TileSizeY;

	int newtileBL = tilex + (tiley * MazeSizeX);
	tilex = (PosX + TileSizeX-1) / TileSizeX;
	tiley = (PosY + TileSizeY-1) / TileSizeY;
	int newtileBR = tilex + (tiley * MazeSizeX);
	if (MazeData[newtileTL] == 0)
	{ 
		testcollision.TopLeft = true;
	}
	if (MazeData[newtileTR] == 0)
	{
		testcollision.TopRight = true;
	}
	if (MazeData[newtileBL] == 0)
	{
		testcollision.BottomLeft = true;
	}
	if (MazeData[newtileBR] == 0)
	{
		testcollision.BottomRight = true;
	}
	return testcollision;
}

Thanks

 

P.S. Yeah I am a beginner so be gentle! smile.png

Share this post


Link to post
Share on other sites

Does the blue box fit in any of vertical corridors? Also, double-check where your collision points are: they might be one pixel too far outside.

 

This is one of those cases where the literal simulation of the physics may not be what you want. Shrinking your collision box a bit will work, or putting the collision detection points in the middle of the sides of the box instead of the corners (and maybe changing the wall collision boxes too). 

 

These links might give you some ideas for other ways to implement this:

http://gamedev.stackexchange.com/questions/8336/how-did-loz-a-link-to-the-past-handle-sub-tile-collisions

http://home.comcast.net/~jpittman2/pacman/pacmandossier.html#CH2_Cornering

http://troygilbert.com/deconstructing-zelda/movement-mechanics/

Share this post


Link to post
Share on other sites

I would recommend that when trying to move in one direction and noticing that it doesn't work, check if movement is possible in the perpendicular directions, and if it is test moving the square in those directions 1, 2, 3 and 4 pixels and then in the original direction again. If it works, move the square 1 pixel in the direction where it became possible to move. So when trying to move down at a corner like that it will first glide past the corner and then move down.

if cant move down:
  for(i = 1 -> 4)
    test move down i pixels to the right/left
    if(worked)
      move right/left depending on which direction a downward movement worked

Share this post


Link to post
Share on other sites

I'm still new and only recently have started using a fixed time step for my game loops in any of my programming adventures. Is there anything wrong with having multiple fixed time steps in a game?

 

First the rendering is unlimited of course.

 

Then a time step for AI/enemies etc.

 

Then another time step for the player.

 

What I have ended up doing is something simple and with the small amount of testing so far seems to work.

 

The fixed time step in the above code is 1/60.f. With my player speed at 400.f works out to be approx 6.6 pixels each update.

So what I have done is instead of using the time step in my move function, I have just got the player sprite to move 2 pixels.

This allows the sprite to always be "divisible???" of 32 and therefore will always land perfectly on an intersection. 4,8,16 and 32 also work.(X2 )?

One thing I have discovered is that if I adjust the Fixed time step to 1/120.f then my player sprite doubles the speed. I can also adjust it to say 1/80.f and have no issues with the player moving in and around intersections.

 

So in effect I have the ability to move the player sprite 1 pixel each time but adjust the speed via the fixed time step.

Will my theory work out ok? I'm not making Quake 5 or anything, but I just want to make sure that if I run my game on another machine, be it faster or slower, It will still perform the same.

 

Obviously when the time comes for bad guys and AI. I would use a different time step that is actually fixed.

 

Thanks again for all your input! smile.png

 

Werdy666ph34r.png

Share this post


Link to post
Share on other sites

The problem with this is that if I'm moving say left and down, it still won't go in the down direction until I stop moving.


This line needs some clarification. If the player starts moving down before being fully in the maze cell, he'll end up moving through the wall. The character MUST continue moving in the original direction of travel to clear the wall. That is, unless you plan on rotating the character, at which point you would be better off doing a radius collision test.

It would help if we knew more of your ultimate goals for this.

Share this post


Link to post
Share on other sites

My ultimate goal for this will be a little game, something like Boulderdash crossed with Pacman.

 

Using a fixed player speed and having a time step that can change, I have made the player aligned to the grid now which, so far, is still working. Or I can have set player speed in pixels, and keep the time step fixed. In essence making sure the player can only move 1,2,4,8,16 or 32 pixels every update.

 

 

Posted Today, 07:35 AM

The problem with this is that if I'm moving say left and down, it still won't go in the down direction until I stop moving.


This line needs some clarification. If the player starts moving down before being fully in the maze cell, he'll end up moving through the wall. The character MUST continue moving in the original direction of travel to clear the wall. That is, unless you plan on rotating the character, at which point you would be better off doing a radius collision test.

It would help if we knew more of your ultimate goals for this.

 

My original problem was that my grid is 32x32, the player is also 32x32.

When I was using a fixed time step with a variable player speed, the player would move as an example 6 pixels each update. I would then hit a wall, which as an example,was only 2 pixels away from the player and the collision code would stop him moving but still allow him to move the 2 pixels to be right against the wall. then going back along that same path traveling at 6 pixels a move, he would never be perfectly aligned with a corridor anymore and would not be able to move back through that corridor.

 

-

I will make my own Pacman one day and I think I can understand the cornering for Pacman. This allows him to get away from ghosts who can't cut corners. I assume the original Pacman didn't have to worry about time steps etc because they knew exactly how fast the game was going to run because the hardware was the same for everyone. IE Arcade machines, C64's etc.

Share this post


Link to post
Share on other sites

I will make my own Pacman one day and I think I can understand the cornering for Pacman. This allows him to get away from ghosts who can't cut corners. I assume the original Pacman didn't have to worry about time steps etc because they knew exactly how fast the game was going to run because the hardware was the same for everyone. IE Arcade machines, C64's etc.

Actually they didn't "worry about time steps" for technical reasons: older hardware like that simply doesn't have the processing power for variable time steps.

 

Variable time steps require constantly multiplying values by the delta time. Mutiplication is extremely slow on 8-bit CPUs, and still fairly slow on most 16-bit CPUs.

 

Instead, games on those older types of hardware would just use a fixed time step, use the vertical retrace interrupt (which occurs at a fixed frequency based on the display system) for timing, and if any given step took too long to process, the game would just slow down.

Share this post


Link to post
Share on other sites

My ultimate goal for this will be a little game, something like Boulderdash crossed with Pacman.


I apologize. I didn't finish my thought; it was a LONG day for me. We are trying to help you based on a very rudimentary image. Is it safe to assume that the graphics shown are simply placeholder graphics? If so, your character bounding box is far too large. In fact, it is far too large even if these are the final graphics! The collision bounds needs to be as small as possible so as to not cause false positives. There is precious little reason for your character's collision bounds to be so large as to force a collision with the environment. As it stands now, your character is always in contact with the walls. If you were to use an actual physics library, your character wouldn't move at all.

All of your problems would go away if you were to reduce the size of the blue square and you would have a much easier time if it were a circle and you did a radius collision test.

Share this post


Link to post
Share on other sites

This topic is 819 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this