# Best way to handle cornering in a 2D maze game?

I want to implement smooth cornering in a grid, much like Pacman moving in his maze. A big difference with Pacman, my characters can stop- thus the player has to keep pressing the controls to keep moving.

I also want the speed of the character to be variable (depending on various game mechanics). Now this felt like a simple mechanic to code, however it's giving me more trouble than I expected. The code only works properly if the character aligns exactly with the tiles.

The green character moves down and the player want to enter the corridor on the right. However the character doesn't align properly thus the collision prevents it from moving.

Now the character "jumps" noticably if I did my collision check on the center of the character. I wanted the character corner a bit earlier to give the player some wiggle room. Thus I implemented 8 collision points:

It also keeps the character nicely aligned to the grid. All seemed fine until this happened:

The character keeps bouncing back and forth as the collision code pushed the character out of the colliding boundaries.

I feel my code is getting more complex than needed. I googled to check various pacman implementations, but most I found deal with fixed speeds and rely on the fact that pacman keeps moving.

So what is the best way to deal with navigating a gridlike maze with variable speeds?

My game is in Monogame (C#) my maze is an array of tiles[x][y].

My current collision code goes like this:

For each collision point I check the tile in it's path (to prevent bullet through paper- while my character won't go as fast- I might get projectiles in the game later).

 TileData tileinpath = Line(X0, Y0, X1, Y1, new Vector2(obj.PosX + obj.CollisionPoints[i].RelativePosition.X, obj.PosY + obj.CollisionPoints[i].RelativePosition.Y));


Line is Bresenham on my tilemap to return the nearest tile in the collision path. Then depending on the location of the collisionpoint:

            case CollisionPosition.BottomRight:
if (moveY <= 0) //check if we're really moving that direction
break;

//apparently we hit something, so adjust everything accordingly.
obj.SpeedY = 0; //stop movement in that direction.
obj.PosY = tileinpath.Y * CollisionMap.TileHeight - obj.BoundingBox.Height / 2;
obj.CollisionPoints[i].CollisionDetected = true;
break;


Can the grid movement be done simpeler? What am I missing ...

EDIT, based on solution:

I ended up using VaTTeRGeR suggestion. I have the character move from tile center to tilecenter and make decisions based on the options whenever the character crosses a tilecenter.

    public void NavigateTo(Entities.Mobile mobile, Entities.Mobile.Direction intendeddirection, float dt)
{
Entities.Mobile.Direction CurrentDirection = mobile.CurrentDirection; //current direction of travel.
float DeltaMove = mobile.Speed * dt; //amount of pixels moved in this frame.

//what is our current tile?
int currentTileX = MathHelper.Clamp((int)mobile.Position.X / CollisionMap.TileWidth, 0, CollisionMap.Width - 1);
int currentTileY = MathHelper.Clamp((int)mobile.Position.Y / CollisionMap.TileHeight, 0, CollisionMap.Height - 1);

Vector2 TileCenter = new Vector2(currentTileX * CollisionMap.TileWidth + CollisionMap.TileWidth / 2,
currentTileY * CollisionMap.TileHeight + CollisionMap.TileHeight / 2);

//determine the position compared to the centernode.
bool IsInFrontOfNode = InFrontOfNode(mobile.Position, TileCenter, CurrentDirection);
bool IsTargetPastOfNode = PastOfNode(mobile.Position, TileCenter, DeltaMove, CurrentDirection);
bool WantsToReverse = Reversing(CurrentDirection, intendeddirection);

if (IsInFrontOfNode)
{

if (WantsToReverse)
{
//it is assumed that the check to get here was already done.
//the wants to reverse check already made sure we are moving in the revers direction of the travel direction
MoveInDirection(mobile, intendeddirection, DeltaMove);
return;
}

if (!IsTargetPastOfNode) //we're still in front of our node.
{
//Safely move the direction we were moving.
MoveInDirection(mobile, CurrentDirection, DeltaMove);
return;
}

//so now we're here:
//the mobile wants to move past a node and can potentially change direction here.

//check if we can move in the direction we want.
if (intendeddirection != CurrentDirection)
{
//we want to change directions!
if (IsTileAvailableInDirection(currentTileX, currentTileY, intendeddirection))
{
//yes we can move that way.

//how much can we move in the new direction?
float remaining = RemainingMove(mobile.Position, TileCenter, DeltaMove, CurrentDirection);

//first move to the node.
mobile.Position = TileCenter;

//now move the remainder of the move.
MoveInDirection(mobile, intendeddirection, remaining);
return;
}
//no way, there is no tile over there.
}

//try to move in the current direction.
if(IsTileAvailableInDirection(currentTileX,currentTileY,CurrentDirection))
{
//we can still move that direction.
MoveInDirection(mobile, CurrentDirection,DeltaMove);
return;
}

//we can not move further than the node (tilecenter).
mobile.Position=TileCenter;
return;
}

if (!IsInFrontOfNode)
{
//past the node. we can only reverse or continue in the direction we're moving in.

if (WantsToReverse)
{
//it is assumed that the check to get here was already done.
//the wants to reverse check already made sure we are moving in the revers direction of the travel direction
MoveInDirection(mobile, intendeddirection, DeltaMove);
return;
}
//we should already have checked this some frames ago, but there is no harm in checking each frame...

//try to move in the current direction.
if(IsTileAvailableInDirection(currentTileX,currentTileY,CurrentDirection))
{
//we can still move that direction.
MoveInDirection(mobile, CurrentDirection,DeltaMove);
return;
}

//we can not move further than the node (tilecenter).
mobile.Position=TileCenter;
return;
}

}


The helper functions do some minor calculations where the axis (X,Y) and relation to direction are relevant.

• Are your levels always solely grid? Do you have bigger open spaces in your levels? – wondra Aug 14 '15 at 22:21
• For the moment just a maze on a grid. – Felsir Aug 15 '15 at 6:38

## 2 Answers

I would do it like this:

If the player wants to go around a corner/change direction, check if the distance he will be able to move in this tick (speed*delta, GREEN ARROW) is bigger than the distance from his center LEFT BLUE DOT to the connecting blocks center ORANGE RECTANGLE.

If true: move him to the center of the connection-block ORANGE RECTANGLE and then move him the remaining distance (speed*delta minus former distance to center) in the direction he wants to turn. This moves him along the RED ARROW to the position the RIGHT BLUE DOT is at. Do all this in one tick.

if not: just move him forward.

• I'm not entirely sure if I understand the if statement: the green and red arrows both are of equal length right? I do like the suggestion to create the path and follow it along. – Felsir Aug 14 '15 at 18:20
• Yes, they should not exist as data in the game though. The two arrows are both of the length of the maximum distance the player can travel in one frame. If he is able to move beyond the middle point of the junction (green arrow goes across orange rectangle) and wants to go right, like in this example, he will travel to the midpoint of the junction and then travel the remaining distance in the new direction to the right (red arrow). These two movements are executed in one go. – VaTTeRGeR Aug 14 '15 at 19:09
• Imagine it as splitting the players movement around the corner in two sub-moves to get him "in the new lane". – VaTTeRGeR Aug 14 '15 at 19:17
• I'll try this next week (away from the computer this weekend) – Felsir Aug 15 '15 at 6:41

I would look at the problem differently: I would use navigation graph instead. I would "bend" the original navigation graph to your problem - each junction is a node(with 0 radius), and each edge stores its length and its direction. Player navigate on graph instead of in a world full of solid walls. Player can move each frame at desired speed along edge he is on if either "correct" direction button is pressed (note this could be generalize to support 8 or more directions). Another benefit is that generating such graph is trivial for uniform grid (any flood-type algorithm will do). Whenever player would at his current speed cross a junction there is decision to be made which way he will be moved. You have many possibilities what logic choose here, first one to come to mind is pick the last held(=last pressed, still down) button direction. You could implement this for example by storing keydown(up) events on a stack.
In your original image, if player was on edge between nodes A and B, 1.1 units from B and moved 1.6 units in direction of B, decision would be made(trivial check 1.1 < 1.6). If he held button S first(for moving down) and "short" before junction pressed button D, he would cross the junction, turning right and continued (remaining 0.5 units) on edge from B to D.

• Hmm, a node grid may also benefit pathfinding for enemies I think? – Felsir Aug 15 '15 at 6:40
• Sure, why not? You are free to use it for all moving entities. You can do much more magic easier with simplified worlds (like this for example). I can imagine you could even reverse the process and generate maze from a graph or dynamically change maze and check the change correctness with the graph. – wondra Aug 15 '15 at 9:24