xna - How do I avoid pathfinding characters getting stuck in corners?

I used A* pathfinding to return a list of Tiles to get from an enemy to the player. After that, I wasn't sure how to actually move the enemy.

What I ended up doing was get the first Tile in the path. Then, check all 8 directions from the enemy's current tile. If the path tile is in the enemy tile's adjacent bottom square, move like this. If it's the right square, do that, etc. When the tile of the enemy is the same as that tile in the path, remove it from the path, and repeat for the next one.

This works, except my character sometimes gets caught around corners. This is because it thinks it should be moving horizontally (the next tile in the path is above it) when it's actually more of a diagonal movement to actually get to it.

I need to know two things:

1. Is there a better way I should do the movement after calculating the tiles in the path?


2. What are some ways to deal with the corners and diagonals? I was thinking perhaps some sort of random movement, but it's kind of janky. In the end, don't care how silly it is as long as the enemy doesn't get stuck!

Really new to all of this, so would appreciate some advice!

Answer

It seems your pathfinding and collision detection have different ideas of what's OK, when it comes to walking around corners.

Say your pathfinding plans out this path (brown squares are walls, yellows are empty space, green is an enemy character, arrows are the planned path):

The enemy character then moves directly toward each point from the previous one, expecting to be able to do this

...but hits a wall here.

Now, what does your collision resolution code do?

I suspect based on your video, that when the enemy hits a wall, they're just sent back to the direction they came from. (Or the enemy doesn't try to move there in the first place. Same idea.) This means the same thing happens again next frame.

...hence why cornering enemies get stuck.

Both your collision resolution and your pathfinding methods make valid but different assumptions about corners.

You could either change your pathfinding to not cut corners

or change your collision detection, perhaps to Separating Axis Theorem, so the enemy is popped out by the smallest possible displacement.

Fancier solutions I've seen games use include special collision detection logic for corners, considering characters' sizes in the waypoint graph and smoothing calculated paths' motion. (This question might also be handy.)