PATHFINDING!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
STILL NOBODY ANSWERED MY FIRST QUESTIONS!
I'm searching code for pathfinding through mazes!!!!!!!!
Thanks!
Errr.... That URL gets me to here :(
HTTP Error 404
404 Not Found
The Web server cannot find the file or script you asked for. Please check the URL to ensure that the path is correct.
Please contact the server's administrator if this problem persists.
404!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
THERE IS NO ERRORCODE I HATE MORE!
Hey Escaflowne, I hope you can correct the URL if not I know that's not your fault! But I was so disappointed!
Thanks
Just finished implementing A*
I'll email you my source soon...
In case it helps other people in the future, the A* algorithm is easy to implement (although the research I did seemed to try to make it sound more complex than it really is).
The idea is that for each possible move starting from the start point, you assign the potential move a rating based on various criteria. It is common to include proximity to target and movement cost (if there is any) as well as obstacle avoidance in the calculation.
This calculation (referred to as f) is how each potential path is compared with previous paths that have reached the same point.
The basic system for storing the nodes in the search is to maintain two "lists". One is called the open list and the other is the closed list.
You must ensure that the next node to check (from the open list) is the node with the lowest possible f. How you do this is up to you, but the best method is referred to as a priority queue. This is simply a storage system in which items going in are inserted in the correct place in the queue (i.e. sorted) but the only item that can be pulled out is the top one (i.e. the one with the lowest f).
The closed list is really just a means to specify that the particular node has been checked.
In the main loop, you would get the next node from the queue. Note that a node is pretty much anything you want, but normally you will want to store information in the node about the position on the map. Essential for a node is the ability to store the f value and the parent node.
Determine all legal moves. If a move is legal, attempt to add it to the Open list. When adding to the open list, first check to see if the node is already on the open list with a lower f. If it is, then do not add it, just bail out. Next, check if it is on the closed list with a lower f. If it is, bail out. If it is not on either list, or if it is, but with a higher f value, then: remove it from both lists, and add it to the open list.
Eventually your main loop will reach the end of the search space or it will reach the target - depends on what you want. For games, I recommend adding a time criteria, giving your algorithm say 1000ms to complete the search before aborting. Otherwise, on a 1000 x 1000 map, you could be looking at a few minutes to search the entire search space. Normally, this algorithm will find you the most direct route which also happens to be the cheapest in cost.
I know it's not that great an explanation, but it's a starting point for someone who has been unable to find material on the net or in their library. Basically, there is nothing too hard about it :)
Cheers
