Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
2  
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
1  
have you heard of navigation meshes? –  dreta Jun 25 '12 at 22:17
1  
@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

2 Answers 2

up vote 7 down vote accepted

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

share|improve this answer
    
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

share|improve this answer
    
Thanks! Good read. –  Stephen Jun 25 '12 at 20:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.