4
\$\begingroup\$

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!

\$\endgroup\$
14
\$\begingroup\$

Scenario

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):

Path plan

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

Expected actual movement

...but hits a wall here.

Collision!

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.

Getting stuck on a corner

...hence why cornering enemies get stuck.

Quick solutions

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

More corner-conservative pathfinding

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

SAT on a cornering enemy

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.)

\$\endgroup\$
  • 1
    \$\begingroup\$ Yes! When I woke up this morning, I came up with the same of idea of changing the pathfinding. I realized to move diagonally, all I have to do is another pathfind but only using horizontal/vertical directions... then my enemy will know how to navigate to that diagonal tile using only up/down/left/right! Thank you for always answering my questions with your beautiful graphics. :P \$\endgroup\$ – atkayla Mar 29 '14 at 16:57
  • \$\begingroup\$ As before, happy if I helped. :) If your solution ends up being very different from this one, add it as an answer too! \$\endgroup\$ – Anko Mar 29 '14 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.