Square grid path-finding approaches

[seyuup]

Hi, I'm currently trying to implement game play where a player and an enemy are snapped to the grid and the enemy will constantly find a path to the player (even while the player is moving). The entities can only move in the directions left, right, up, and down.

1.) My first approach was to implement path finding using Breadth-first search (no thread).

The game lags (of course) because the computer is having to do too much work.

2.) My second approach was to implement path finding still using Breadth-first search except this time using a thread.

Using a non-detached thread, the game doesn't lag anymore, however, the enemy freezes at times (I assume from trying to calculate the constant movement).

I choose to find a new path only when the enemy is snapped to the grid and when the last found unused path is retrieved by the enemy controller.

Any ideas on another approach to this problem? I'm only going to have one enemy which constantly calculates a path to the player. I'll try to post some code later today.

I hope someone will be able to assist me!

Update (3/5/2016 8:12 PM):

I was able to fix the problem. It was a logic error, fortunately. I was checking for a path based on the player's (x,y) position (which can be a float value) instead of integer values divisible by the grid's (width, height).

[Nexus]

Is there a reason why you don't use state-of-the-art algorithms for pathfinding? Breadth-first search is highly inefficient for shortest paths, because it exhaustively checks all possible paths. The Dijkstra algorithm improves on this by taking into account the distance from the start, and A* achieves even better results through heuristics that estimate the distance to the target from any node.

There are existing implementations of graph algorithms in the LEMON library. A* is currently not in the main branch, but available as an external contribution. But already Dijkstra's algorithm (which is a part of LEMON) is better than BFS.

[Hiura]

What Nexus said should not be underestimated. I've found this tutorial to be gold if you want to understand how these algorithms works and compare them: http://www.redblobgames.com/pathfinding/a-star/introduction.html

[seyuup]

Is there a reason why you don't use state-of-the-art algorithms for pathfinding? Breadth-first search is highly inefficient for shortest paths, because it exhaustively checks all possible paths. The Dijkstra algorithm improves on this by taking into account the distance from the start, and A* achieves even better results through heuristics that estimate the distance to the target from any node.

There are existing implementations of graph algorithms in the LEMON library. A* is currently not in the main branch, but available as an external contribution. But already Dijkstra's algorithm (which is a part of LEMON) is better than BFS.

I used it as a placeholder just to try and get things working first. I will definitely implement a better algorithm later. I have seen that redblob site also, it's very helpful.

[SeriousITGuy]

Thanks for the article Hiura, this is a very good and short read about that topic.