CODEWITHSUNDEEP
algorithmgraphnodesvertex
user1924308
user1924308

Reputation: 53

Best path algorithm while avoiding moving enemies?

I have a general graph/path-finding question that I had for an interview.

Suppose you are trying to get to a specific node on a 2D graph, and there are enemy units that are transversing the graph's nodes, searching for you: what is the best way to maximize the chances of you reaching the goal without encountering an enemy unit?

I am very curious of the best algorithm or general approach to handle this.

P.S: You know where the enemy units are located

Upvotes: 0

Views: 957

Answers (1)

Eulerson
Eulerson

Reputation: 159

Assuming that you want to do what a human in a dangerous maze would do: Just go ahead and run away whenever you see an enemy, here is a simple idea:

  1. Run breadth first search once starting from the goal over the whole graph to store the distance to the goal in every node. In this step, ignore the enemies. Of course this is assuming that you have some distance measure in your graph. Otherwise just counting up the number of nodes during the bfs will do for some applications. Also keep the distance of the last node to the goal, let us call this quantity maxdist.

  2. Run a "small" breadth first search from every enemy towards all directions. Small, because you stop this after a distance of k, where k is the number of graph nodes you want to keep away from enemies or some other suitable metric (this represents the "seeing"). Do a similar thing in this bfs: store the distance towards this enemy where the enemy sits in, denote it as d_i for an arbitrary node i. In this bfs you overwrite the distance to the goal in node i by maxdist + k - d_i. Notice that this quantity is always at least as high as maxdist. In this step you need to be careful on how to update this node i when another enemy has written into it (keep the larger value).

Now, in every timestep you pick as the next node the one node in your neighborhood that has closest distance to the goal. Since nodes that are "close" to an enemy are always at least as expensive as maxdist, you are automatically avoiding enemies. And if you get cornered by enemies from two sides, you will automatically stay in the middle between the two, hoping for as long as possible that one of them turns around.

This might not necessarily maximize your chances, especially not if you can do predictions about the enemy movement. Furthermore this behaves "stupid" as it would run towards an enemy even if you can't pass it until it "sees" it, from where it would turn around.

But it is a general approach, that might even be the best one can do, especially if you cannot see enemies from too far away and if you have no information about their movement, but you have a map to see where you are and where the goal is.

Upvotes: 1

Related Questions