I've been developing a path-finding module to use in my games. The idea is to place nodes on a map, add those nodes to the module, and interface with the module anytime I want to find the closest path between two nodes.
Nodes are just geometric points within my map that are placed strategically as to allow enemies to find their way around the map without running into walls. Instead of going off the raw map data, they use these nodes as guidelines to find their way around. This is much like finding your way around a maze blindfolded by following a rope that connects to other ropes. The ropes may break off into many paths, but one path on the rope leads to the end.
I coded a recursion algorithm to find all the possible paths between node A and node B. Then it would return the next node on the closest path to B (or A, depending which way you are going).
After I coded it, I tested it and it worked alright. So I added more nodes to my map and adjusted my algorithm a bit. Then it just froze my program whenever I called the path-finding code. I've been stumped on this for a couple weeks. I couldn't find anything wrong with my code!
Then I finally found the answer. Turns out that it's just way too slow to find all the possible paths, depending on how many nodes and possible paths there are.
I became suspicious of this and did a test. I ran my program and I walked away for a bit, made a sandwich, and came back. And when I returned, the algorithm had finished! It wasn't broken, just slow.
There are a few things I can do to remedy this. I just need to make sure that I keep my node count down and try to keep my paths as linear as possible, to reduce the number of total possible paths. That way it should keep up to speed. Or I can just try another approach to path-finding. We'll see.
Sounds like you need an A* algorithm - they are *well* worth learning in my opinion (http://en.wikipedia.org/wiki/A*_search_algorithm).
ReplyDeleteIf I recall, the algorithm works by the following:
====================================
You are trying to get from node start to node end. You say that start has a list of possible connected nodes to visit, for example a,b or c. Each node has a known distance from the start node, and also an estimated distance to the finish node. You add all nodes you can visit (a..c for now) to your node list. You pick then node where the known pre-distance plus the estimated distance is the least, and continue expanding this node.
You may find exploring this node is the best way and leads to the finish in the best distance, OR you may find that the total distance traveled to the current node plus the estimated distance to the finish is greater than the total traveled distance plus estimated distance to finish for a node visited earlier, possibly even one of the very first nodes. You keep expanding until eventually you get to the finish.
This is a fairly standard optimal path finding algorithm, I have no idea how fast or how much memory it will use, as it is specific to your implementation and usage - but it should be fairly good.
Note that this algorithm requires you know which nodes are connected to which nodes (a graph), and they cannot simply be random unconnected nodes.
Cool! Thanks, I'll check it out.
ReplyDelete