I am developing a libgdx game. It is a top down shooter and I am trying to make a good AI. I have tried to implement A* from the AI library from libgdx and it works fine but when i have a lot of enemies it starts to slow down the game. Have tried implementing a Pathfinding manager to manage threads and path requests but I have trouble implementing it and still slows down.

Also I know A* is a bit overkill for my game, which is a big open zone mostly (see pic of my map) Map

So I tried to implement this collision avoidance Steering Behaviors: Collision Avoidance but it doesn't go well when the player is inside houses.

My question is, does exists some type of algorithm that fits perfectly for what I am asking? There are a lot of games with hundreds of enemies going to kill you so I bet there is a way, just I cant find out

pd: Any doubt ask and I will provide more information if necessary

  • \$\begingroup\$ It sounds like you might be looking for flow fields. \$\endgroup\$ – DMGregory Nov 28 '18 at 13:24
  • \$\begingroup\$ @DMGregory Thank you! I had no idea of the existance of this algorithm and I have implemented it. Is there any efficiency problem with doing a graph and storing each field value (all of the 3 fields in the algorithm) in its node? Btw make an answer with it so I can check it! \$\endgroup\$ – Raul Mabe Dec 1 '18 at 16:05
  • \$\begingroup\$ I recommend writing up your solution as an answer, that way you can include details of your implementation and gather feedback on it from comments/edits. It's totally OK to answer your own question here, and accept that answer (after a short delay, I believe). \$\endgroup\$ – DMGregory Dec 1 '18 at 16:10

Instead of path finding from every enemy to the player pathfind from the player to every enemy and make every enemy follow the from pointer. You cannot use A* for this until you have reached most of them.

You don't need to repath every enemy every frame. Instead you have a rotating set of enemies getting repathed to the player. Because the player isn't going to move a big distance far lot this is fine. If you ever implement teleports you can use the delay of the animation of the teleport to repath every enemy to the destination of the teleport.

Decrease the density of the nav graph. in wide open spaces reduce the number of nav nodes and use a path smoothing algorithm.


Followed @DMGregory advice and I implemented flow field algorithm.

enter image description here

I made a graph and store in each node its neighboors, its distance and its direction vector. So zombies can ask its node what direction may he go.


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.