Computer Science Canada Best path-finding algorithm |
| Author: | SNIPERDUDE [ Thu Apr 21, 2011 12:47 pm ] |
| Post subject: | Best path-finding algorithm |
Greetings and salutations. Now that formalities are out of the way, what would be the best path-finding algorithm? What are the various types out there, and what are the pros and cons of each? Semi out of curiosity, just for a side project I'm working on. First Person shooter if that changes the response to the question at hand. That being said, if it doesn't stray too much off-topic I'd like to ask about AI (for agents) methods. Was looking into a weight-based system embedded with a genetic algorithm system. Thoughts? Tips? Cheers |
|
| Author: | SmokeMonster [ Thu Apr 21, 2011 4:01 pm ] |
| Post subject: | Re: Best path-finding algorithm |
Djikstra and Floyd are the two path finding algorithms that are the most popular. Djikstra finds the shortest path between one node to every other node in the graph, whereas Floyd finds the shortest path between every pair of nodes in the graph. There are implementations of Djikstra which can run in O(k + n*long(n)) time, whereas the runtime of Floyd is O(n^3), keep in mind that Djikstra is just finding the shortest path from a given node to every other node, to find the shortest path between any two pair of nodes in graph (i.e what floyd does), djikstra will take O(n*k + (n^2)*log(n)). As to which one is the better algorithm the answer is it depends- if you need the shortest path between every pair of points then Floyd is *probably* the way to go. Eventhough Djikstra appears to be asymptotically faster than Floyd for this case, in practice Floyd *often* works better, again it depends upon what your graph looks like but Floyd is very simple algorithm and performs very few operations and as a result is often faster than Djikstra when finding shortest path between any pair of points. If you only need the shortest path between one point and any other point (like you want to move an AI unit to a different point) then Djikstra is probably the way to go. Implementation wise Floyd is a piece of cake, it is crazy how easy it is to implement such a powerful algorithm. Djikstra is harder to implement. |
|
| Author: | A.J [ Thu Apr 21, 2011 4:08 pm ] |
| Post subject: | RE:Best path-finding algorithm |
If you intend to implement a path finding algorithm for an FPS, I would suggest starting of with implementing an A* search algorithm, as this is probably one of the most rewarding algorithms to implement in one's game; not only do you learn a lot more about path finding algorithms while doing so, but you also work with heuristics, which can always be fun. A* uses a BFS to find the path from some root node to a given destination that minimizes cost. It utilizes heuristics to determine what order to visit the nodes in (this technique is commonly used in chess). Having said all that, there are plenty of path finding algorithms, and I don't think any one of them can be considered 'the best' unless you are given a specific circumstance. My advice, however, stands. |
|
| Author: | SNIPERDUDE [ Thu Apr 21, 2011 9:52 pm ] |
| Post subject: | RE:Best path-finding algorithm |
I have heard of A* (wasn't too sure how it works, though your mentioning of heuristics intrigues me) before, but I wanted some other mentionable methods to look into. Any advice on my AI methodology choice? |
|
| Author: | A.J [ Fri Apr 22, 2011 10:04 am ] |
| Post subject: | RE:Best path-finding algorithm |
Mind being a bit more specific regarding 'Was looking into a weight-based system embedded with a genetic algorithm system'? |
|
| Author: | SNIPERDUDE [ Sat Apr 23, 2011 5:27 pm ] |
| Post subject: | RE:Best path-finding algorithm |
Haha, haven't put to much thought into it past that. Help? What I meant by my statement was a method that uses 'weights' (of various appropriate scale) to look at the prerequisites to the decision at hand (ie: decision attack sums to 0.3 and decision retreat sums to 1.7 [when all factors are added]). Toss that in with a "learning" system, using a genetic algorithm approach to rate how well that decision succeeded, helping vary the weights to better make decisions in the future. |
|
| Author: | A.J [ Sat Apr 23, 2011 9:00 pm ] |
| Post subject: | RE:Best path-finding algorithm |
Well, what you are essentially getting at is the notion of 'heuristics': utilizing some form of 'scoring' system to sort your possible game tree to make searching faster. However, genetic algorithms only tend to come in handy when you are dealing with a process that can be refined to yield a better result (this is where the idea of mimicking natural selection comes into play). However, in an FPS you have a very dynamic environment, with different decision trees that can take place depending on a single action (this is kind of hard to grasp, especially because I don't think I am doing a good enough job explaining it). I think as far as creating an AI for an FPS goes, just rely on a few key details: - Pathfinding (you seem to be pretty comfortable with this). - Additional Heuristics that governs the enemy's 'mindset' (e.g. 'aggressive', 'passive', 'patrolling', etc...) - Inter-enemy interactions (this is similar to games like 'Galacon' where multiple planets send ships to other planets for various different reasons. This is by far the hardest part of an AI, as it is really flexible and depends entirely on what you want). Being in the planning stage, you should create a rough plan prior to actually starting to code. |
|