Hi,

I'm trying to implement the A.I. of the NPC of my game, and I want them to go after the closest enemy.

However, the closest enemy (in euclidian distance) might not always be the enemy with the shortest path to it (imagine an enemy behind a very large wall).

So, the only way I can think of solving this problem is using dijkstra from where the NPC is, to get the distance to all enemies, and then choose to attack the one with the shortest waypoint-distance, but dijkstra would have to go through all the waypoints in the scene, which might not be the best thing every time any NPC looks for an enemy to attack to.

It would be better to use something more efficent like A*, but that requires knowing your target beforehand in order to compute the heuristic to determine the best next waypoint to build the path.

Any advice?

You could try using diffusion and vector field instead greedy graph algorithms:
Every enemy drops energy to the grid or a graph.
Diffuse energy over the whole map. (That's the expensive step - performance depends on map size but not on enemy / NPC count)
Each NPC calculates the gradient of the energy and follows its direction, or you calculate the gradient for every cell. (It does not know where the enemy is, but it will find the closest one.)

I tried it out and posted a working code for a chase the player game here: https://www.gamedev.net/forums/topic/709827-how-to-prepare-an-influence-map-to-take-the-influence-of-obstacles-into-account/5438478/?page=1​ Code on page 2, images on page 1.

A simple breadth-first search, terminated when the first enemy is found, would probably be the most efficient.

It is possible to run a single A* search where the target isn't a single node, but a set of nodes, possibly even an infinite set of nodes. I've done it before. However, this complicates the heuristic function. Remember that the heuristic function is allowed to underestimate, but not overestimate, the remaining distance from a given node to the goal. When there are multiple goal nodes, that's the distance to the nearest goal. The naïve but “correct” approach is to estimate the distance from the node to each possible goal node and take the minimum of your estimates. The problem is that this is an O(n) operation (where n = number of goal nodes). In practice, it's often faster to simply use the heuristic function h(x) = 0. This reduces the A* search to a simple breadth-first search. You'll need to look at more nodes, but your heuristic function runs in constant time.

That's assuming that you have many enemies and few nodes. If you have very few enemies and very many nodes, the O(n) heuristic function is probably going to win. Or you can try to write a heuristic function that's smarter than h(x) = 0 but still runs in constant time.

a light breeze said:
It is possible to run a single A* search where the target isn't a single node, but a set of nodes, possibly even an infinite set of nodes. I've done it before. However, this complicates the heuristic function.

Interetsing… what did you consider on the heuristic when the target were multiple nodes?.. like checking each step the shortest distance to all possible target-nodes and moving to the closest?

JoeJ said:
You could try using diffusion and vector field instead greedy graph algorithms

uhmmm… an interesting approach indeed, I'll take a look at it and see how would that fit into my game.

a light breeze said:
It is possible to run a single A* search where the target isn't a single node, but a set of nodes, possibly even an infinite set of nodes. I've done it before. However, this complicates the heuristic function.

The simpler form is to make the player the target where you have multiple starting points. Simply add them all in the open list. The closest one will be expanded towards you :p

If direction of taking a path matters, you can take “backward” steps, like the enemy is walking backwards to you.

そら said:

a light breeze said:
It is possible to run a single A* search where the target isn't a single node, but a set of nodes, possibly even an infinite set of nodes. I've done it before. However, this complicates the heuristic function.

Interetsing… what did you consider on the heuristic when the target were multiple nodes?.. like checking each step the shortest distance to all possible target-nodes and moving to the closest?

Simple example, not really relevant to your problem: a wounded opponent is trying to flee from the player by heading for the edge of the map. In this case the heuristic function is simply min(distance_to_top_edge, distance_to_bottom_edge, distance_to_left_edge, distance_to_right_edge).

Alberth said:

The simpler form is to make the player the target where you have multiple starting points. Simply add them all in the open list. The closest one will be expanded towards you :p

If direction of taking a path matters, you can take “backward” steps, like the enemy is walking backwards to you.

That's an interesting approach that should work well for most real-world scenarios. Maybe not for huge maps with thousands of opponents, and definitely not for my “edge of map” example.

a light breeze said:
Maybe not for huge maps with thousands of opponents

Many open nodes isn't necessarily a problem, unless they are all at the same distance. If they are at different distances, only the closest one is expanded, all the other ones aren't even considered if the nearest one succeeds.

You can just flood fill. Just start filling from the starting point, numbering each cell with the distance back to the start, and recording the distance for each enemy you find. Pick the closest enemy. You only need one pass of flood fill, not one pass per target.

Useful if you have a lot of enemies.

Alberth said:

Many open nodes isn't necessarily a problem, unless they are all at the same distance. If they are at different distances, only the closest one is expanded, all the other ones aren't even considered if the nearest one succeeds.

You still need to visit each goal node once in order to add it to the open list, however. Consider the pathological case where every single node on the whole map is a goal node. Breadth-first search can then find a path to the nearest goal in O(1), but adding all nodes to the open list is O(number of nodes in map).

Like I said, starting from the goal nodes is a good approach that probably beats breadth-first for most real-world scenarios. Just not all.

a light breeze said:
Like I said, starting from the goal nodes is a good approach that probably beats breadth-first for most real-world scenarios. Just not all.

Haha, indeed. Our algorithms are just too specialised, they should work reasonably for all possible cases without having the extremely bad performance in the worst case. ?

That would save a lot of work.