# How can I better implement A star algorithm with a very large set of nodes?

I'm making a game with nodejs in which many enemies must converge on the player as the player moves around a relatively open space (right now it is an open field with few obstacles, but eventually there may be some small buildings in the field with 1 or 2 rooms). It's a multiplayer game using websockets, so the server needs to keep track of enemies and players.

I found this javascript A* library which I've modified to be used on the server as a nodejs module. The library utilizes a Binary Heap to track the nodes for the algorithm, so it should be pretty fast (and indeed, with a small grid, say 100x100 it is lightning fast).

The problem is that my game is not really tile-based. As the player moves around the map, he is moving on a more or less 1-to-1 per-pixel coordinate system (the player can move in 8 directions, 1 or 2 pixels at a time).

In preliminary tests, on an 800x600 field, the path-finding can take anywhere from 400 to 1000 ms. Multiply that by 10 enemies and the game starts to get pretty choppy.

I have already set it up so that each enemy will only do a path-finding call once per second or even as slow as once every 2 seconds (they have to keep updating their path because the players can move freely). But even with this long interval, there are noticeable lag spikes or chops every couple of seconds as the enemies update their paths.

I'm willing to approach the problem of path-finding differently, if there's another option. I'm assuming that the real problem is the enormous grid (800x600). It also occurs to me that maybe the large arrays are to blame, as I've read that V8 has trouble with large arrays.

-
Have you considered not using A*? That is if you asked the question as, "How can I best implement path finding with a large number of actors and a detailed playing field?" – Tim Holt Jun 25 '12 at 16:56
@Tim good question. As I said, I'm willing to approach the problem of path-finding differently. Any suggestions? – Stephen Jun 25 '12 at 17:34
have you heard of navigation meshes? – dreta Jun 25 '12 at 22:17
@dreta I'm reading about them now. And in fact, this is exactly what I'm going to do. I'm dropping the "grid" approach in favor of vertices and navigation meshes. It will take some re-programming, but I think I'll end up with a better game. I'll still use A* to navigate the nodes. – Stephen Jun 25 '12 at 23:38

Each pixel doesn't have to be its own node in your navigation mesh/graph. You should be able to subdivide areas by sections, and each section becomes a node in the graph for the A* algorithm. This leaves you with far fewer nodes and much faster searches, however you do have to calculate how to move through these nodes naturally with AI, as you won't just want to walk from node center point to node center point.

Here's a decent paper explaining how navmeshes can help solve issues like you're talking about: http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html

-
Great article. Thank you! – Stephen Jun 25 '12 at 18:39

Here is another good resource, how A* search was used in Left 4 Dead (A popular game by Valve). It contains some overlap with Nic's answer, but is still interesting.

http://www.valvesoftware.com/publications/2009/ai_systems_of_l4d_mike_booth.pdf

-
Thanks! Good read. – Stephen Jun 25 '12 at 20:15
That pdf is an invaluable read, it gives a great overview of how they built fast and efficient pathfinding for L4D and is a great source of inspiration for your own pathfinding. – thelastshadow Jun 23 '15 at 8:50