0
\$\begingroup\$

If I have one enemy that should chase the player, I can use a path-finding algorithm such as BFS to find the shortest path from the enemy to the player (taking into account obstacles along the way), and advance the enemy along the path.

But if there are two enemies, this is not necessarily the most efficient strategy. For example, if there is a large obstacle, instead of both enemies chasing the player from the east, it may be more efficient for tnem to cooperate, one of them should go chase the player from the east while the other blocks the player's escape route from the west.

My question is: what is an algorithm for efficiently coordinating the chase behavior of two enemies?

Improve this question
\$\endgroup\$
1
\$\begingroup\$

"Algorithm efficiency" is a very broad expression. If I understand correctly, you want an heuristic to predict the path of enemy AI's so they can trap the player. There are multiple ways to handle this and the best solution also depends on the victory condition.

Does the player has an objective to go somewhere in the map, or is he just trying to survive for the longest time?

Considering the player just has to survive for the longest time, one suggestion of an algorithm I can make is:

  1. Compute the sum of distances of all the paths the player can go without going into any enemy range.
  2. Compare which combination of directions of movement each AI can take and choose the combination that mostly minimizes the sum computed in step 1.
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Why do you measure the sum of all paths, and not the maximum path? \$\endgroup\$ – Erel Segal-Halevi May 21 '20 at 11:31
  • \$\begingroup\$ For two reasons: First, the player might have a path behind him (instead of just left or right) that has the maximum distance. If so, any movement of the AI won't minimize that maximum path. Second, as I don't have enough information about the gameplay, i assumed it's a real-time game, instead of turn-based. If so, we want all AI's to make their decision at the same time, in a coordinated fashion. \$\endgroup\$ – Vinícius Queiroz May 22 '20 at 18:07
  • \$\begingroup\$ Btw, I'm also assuming the game is 2D, and thinking from a top-view perspective. If it's a 3D game, sum the area of available movements in step 1, instead of the length of the paths. \$\endgroup\$ – Vinícius Queiroz May 22 '20 at 18:12

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.