I am working on a game which will consist of several ai's trying to get to the closest target possible by following the shortest path possible (zombies). It is a 3D game environment, and I've done this before by using Dijkstra's Algorithm and nodes but that seems very inefficient to me. Is there a better way to do it? Any suggestions are greatly appreciated. I don't think it matters but I will be writing with Lua.
Asked
Active
Viewed 1,141 times
-2
-
Close and downvoters: You should comment and explain what's wrong with the question, or the OP will never learn how to ask a good question. Also, I think that close voting less than 2 minutes after the question was posted is a bad practice, with some rare exceptions, and especially without providing the reason for the vote. – amit Feb 17 '14 at 18:15
-
@amit: (didn't close/downvote) Can OP not see the close-vote reasons? – Niklas B. Feb 17 '14 at 18:39
-
@NiklasB. I am not sure he can actually, he cannot vote after all. He'll be able to if it gets closed. Besides, they are way too generic, a comment could be much more helpful. – amit Feb 17 '14 at 19:26
-
@amit: At least "unclear what you're asking" points to http://stackoverflow.com/help/how-to-ask which I think any user can be expected to read before posting a question here and which this question does not live up to (although I agree that we should be more friendly especially towards new users :) – Niklas B. Feb 17 '14 at 19:28
-
@amit I wouldn't be quick to vote to close this, but the downvotes could be explained by the lack of sufficient research effort - a simply Google search of path finding algorithms quickly leads one to the A* algorithm. – Bernhard Barker Feb 17 '14 at 20:45
2 Answers
1
You can use A* Algorithm if you have some information on (heuristic) on the distance to the target. A* is basically an informed dijkstra's algorithm, and is both complete1 an optimal2 when using admissible heuristic function.
An alternative is using BFS or bi-directional BFS (if you have single target), which will also find the shortest path and is more efficient than Dijkstra's Algorithm, and require no heuristic function. However, these only work if the graph is unweighted.
This thread gives some information on bi-directional search. The question is different, but the same principles apply.
(1)Complete: Always finds a path if there is one.
(2) Optimal: finds the shortest path.
