Posted 28 June 2012 - 10:25 PM
It is also important that you use the pathfinder most appropriate to a situation. On a tile grid, this is likely to be A* (just ensure you only call the A* pather if you need to; if there exists a straight line path, then use that instead). However, just blindly calculating an A* path and having the enemies follow it in a grid-based game is unlikely to lead to realistic movement. In this case, once you have the path you can perform a post-processing pass upon it. This pass will iterate the path from end to start and find the node that is furthest along the path to which the unit can path in a straight line. This will clip off any jaggies or zig-zags, and give the unit the impression of intelligence by having it head directly toward the route around the nearest blockage, instead of meandering in a wobbly line across the ground.
Even if you are on a grid, you still might want to look into using navigation meshes. There exist libraries such as Recast and Detour
that can help with the generation of nav meshes and pathfinding upon them. Using a navigation mesh library can boost performance immensely, especially if your levels tend to be large and open. Large, open levels partitioned on a grid tend to devolve to a lot of testing of nodes and overhead to cover the large open spaces, whereas a nav mesh will tend to condense all of those grid-sized nodes into larger mesh nodes, making the actual A* step a lot less computationally expensive at the expense of some pre-processing to build the nav mesh. The method you use to pathfind on a nav mesh may also allow you to eliminate the post-process step of finding the furthest node you can path to, as a nav mesh path tends not to have the regular jaggies and grid steps that an A* path on a tile grid has.
Edited by JTippetts, 28 June 2012 - 10:55 PM.
In a Diablo-clone, it is quite frequent to have more than 5 or 6 enemies at a time dinging the pathfinder. It is important, then, to clearly define your goals and design, and to allow for all scenarios. A* is only one tool in the tool box. You might notice that in some D clones, the enemies don't chase very far, or if you can put enough space between them and you you can leave them behind. Also, they don't "aggro" until you are nearby. One reason for this is it allows you to constrain your pather to a limited radius, and thus drastically reduce the time spent calculating paths. Target went out of range? Switch to idle mode. You can put checks in your A* pather to bail if no path less than a maximum length is found, and preliminary checks to keep the pather from being called.