I'm creating a top-down rpg (no tile-based) using libgdx. Now I need to make enemies move on map with obstacles. What is the best approach to realize that? A*(I think, if enemy see player, he should turn to Pursue+Raycasting, because A* is bad for following moving targets) or just combining steering behaviors Seek+Raycasting?


There is no 'best' solution to this problem. Ultimately you're going to have to find by trial and error something that gives the best tradeoff between performance and believable intelligence.

However if you want to use any sort of path finding algorithm you're going to need to subdivide your world in some way. Whether you go with tiles, polygonal zoning or way-point nodes, your path finding algorithm needs some sort of graph to traverse. Using simple steering behaviours without any path finding will result in your AI getting stuck behind obstacles.

For seeking targets over large distances I use Jump Point Search which is considerably faster than A*, especially if your map has open areas.

For localized searching, such as aggro detection I use a simple Dijkstra algorithm. Unlike A*, with Dijkstra you don't ask it to search for a specific end point, you instead describe the type of end point and it will find the closest for which there is a valid path.

For example, you might have a soldier class within your game and you want it to attack any enemies that come within a certain radius of the soldier. You can simply feed the Dijkstra algorithm only the tiles that are within the radius. You then tell it that the only valid end points are tiles which contain an enemy. This will cause the soldier to always move towards an enemy if it is within aggro range.

You can couple the above approach with Steering Behaviours / Boids. Do the Dijkstra scan as described, then once an enemy target is found, stop scanning and allow your soldier to follow the path. Once your soldier is quite close switch to following by Steering Behaviours. This will work most of the time but because Steering Behaviours are not a path finding algorithm your soldier will occasionally get stuck behind objects in crowded areas. To solve this you must keep track of the distance to the enemy target. If the distance increases by X amount for Y seconds you know your soldier is likely stationary and the target is moving away from it. In this case, stop following with Steering Behaviours and perform another Dijkstra scan.

  • \$\begingroup\$ Got a little question, grid means that all the obstacles will be represented as squares (or not?), but I wanted my terrain to consist from polygons or even to be like it is in Worms (navigation mesh?). Does it have sense or better make tiled map? \$\endgroup\$ – Andrei Yusupau Aug 31 '15 at 6:44
  • \$\begingroup\$ A grid doesn't mean all objects have to be represented as squares. Each tile can be treated as a bucket which can hold an object of any shape. However, there's no specific need to use a grid if it doesn't suit your requirements. All a path-finding algorithm needs is a graph to traverse. A graph is simply a set of nodes. Each node has edges which connect it to other nodes. The graph doesn't really care about the shape that each node represents, it only cares about what each node connects to. \$\endgroup\$ – Fibbles Aug 31 '15 at 16:55

The way I have done it in the past is with A*, but tweaked. Calculate the A* path, but remove the last n waypoints from the path. Then when that point is reached, recalculate.

Only remove the last n waypoints if there are at lease n+m waypoints. Otherwise, send to target, and recalculate. Once there is only one way point, the calculation is minimal.

This prevents the need to constantly run the A* algorithm. After doing this, tweak according to your specific game. A good starting point for n is 3.

An example of this approach can be seen at https://github.com/Evorlor/Outnumbered, which has 20ish entities chasing a moving target in a maze.


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.