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!

Or you could make the player a bit smaller such that he can fit in the corridors.

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/

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

One solution, given you are grid aligned, is that when the player lets go of a move key the square keeps moving in the last direction until it is aligned correctly with a square. That way the T section issue solves itself.

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!

Werdy666

One way to go might be the players position snapped to a grid instead of allowing arbitrary positions. (done in such a way as to ensure horizontal and vertical movement) Unless I'm misunderstanding exactly what you're asking.

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.

Games like Pac-Man addressed this by allowing motion 3-4 pixels early and late.

(They also don't use a physics engine, which is problematic for this type of thing as mentioned in other posts.)

There is a writeup of this in an older Gamasutra article, it is the first half of this page.

It allows the player to turn slightly early or slightly late, in addition to allowing a potential speed boost/slowdown relative to the ghosts when turning corners that strategic players can use.

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.