0
\$\begingroup\$

In my tile-based game, I'm using a A-star algorithm, which I have not written myself but I believe should be correctly implemented.

The problem I have is that the enemy AI can get stuck so that the enemy never gets any closer to the player.

Here's an ascii example of what I mean (x = enemy, p = player, . = ground):

....
x..p
....
....

Now, if I move the player down and process turn (which moves the enemy), the pathfinder finds the the next tile to be at south... and if I move the player up again, the pathfinder finds the next tile to be at north... so the enemy never gets any closer to the player (unless there are some obstacles, or I am closer to the enemy).

I feel stupid not to be able to figure this out on my own (at least in a nice way), but here we are. Is this a common problem, or am I doing something stupid?

\$\endgroup\$
  • \$\begingroup\$ This can happen in games as old as Chess. What do you want the enemy to do in this situation? \$\endgroup\$ – amitp Jul 3 '14 at 22:04
  • \$\begingroup\$ I wanted the enemy to get next to the player. \$\endgroup\$ – user2499946 Jul 4 '14 at 7:27
3
\$\begingroup\$

Well according to the rules of the game, the AI is doing the right thing - moving towards the player every time! It's only due to a quirky situation that the player can "trap" the AI in a loop:

               Start    Player   AI        Player   AI
                        moves    moves     moves    moves
               ....     ....     ....     ....     ....
               x..p     x...     ....     ...p     x..p
               ....     ...p     x..p     x...     ....
               ....     ....     ....     ....     ....
AI distance:     3        4        3        4        3

This is because the AI has two equally valid moves to take, one of which leads to loops. You can fix this by using a different heuristic. Euclidean distance is a good one - a.k.a. straight line distance, as the crow flies - in this case it will move horizontally:

               Start    Player   AI         AI
                        moves    moves  or  moves
               ....     ....     ....       ....
               x..p     x...     ....       .x..
               ....     ...p     x..p       ...p
               ....     ....     ....       ....
Euclidean  :     3       3.2       3         2.2

Note that even with this heuristic, you can get stuck in loops eventually. It is up to you to decide what to do in this situation:

               Start    Player   AI        Player   AI
                        moves    moves     moves    moves
               ....     ....     ....     ....     ....
               .xp.     .x..     ..x.     ..x.     ....    ...
               ....     ..p.     ..p.     .p..     .px.
               ....     ....     ....     ....     ....
\$\endgroup\$
  • \$\begingroup\$ Great explanation, thank you! I got it working with Euclidean Distance. \$\endgroup\$ – user2499946 Jul 4 '14 at 7:25

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.