path finding
Author
i have read thru Justin Heyes-Jones''s A* path finding. Its very impressive. I have made a bit change in the coding which is when the goal was in a place that block by ocstacle in all direction which means that the start node will never reach the goal node and in this situation i will return the nearest path to the goal. The problem i encounter is when this situation happen, the program will delay for 1 or 2 second (its because the "while loop" will loop untill he find the goal node). Can anyone tell me how to fix this problem?
optimize your program or reduce number of nodes! it won't work faster than nodes number!(in the worst case)
what is your problem that you solve with a*?
ps. excuse me for my english!
excuse me for my russian english
[edited by - wormball on October 21, 2003 12:12:43 PM]
what is your problem that you solve with a*?
ps. excuse me for my english!
excuse me for my russian english
[edited by - wormball on October 21, 2003 12:12:43 PM]
Author
i means when the goal node was at the place that the start node will never reach it and the program have to go thru every node, it this case if my map its big then the time it take to complete the search will increase. I am using MFC visual c++ because i put the search in a while loop so when A* is searching for the goal node the delay make me cant even click on the menu or tool bar even though its just 1 or 2 second delay in searching. So i would like to know how to eliminate this problem
quote:Original post by chengseesin
i means when the goal node was at the place that the start node will never reach it and the program have to go thru every node, it this case if my map its big then the time it take to complete the search will increase. I am using MFC visual c++ because i put the search in a while loop so when A* is searching for the goal node the delay make me cant even click on the menu or tool bar even though its just 1 or 2 second delay in searching. So i would like to know how to eliminate this problem
imho if target node won''t be reached from the start node, you have to watch all nodes to define this fact. mfc/c++ don''t matter to this problem. how large is your graph? what your graph means? is it game tree, game map, or it is something else? do you use heuristic function?(if you don''t, it is a, but not a*!)
if possible, post your a* procedure and/or graph example!
Author
i am using Justin Heyes-Jones''s A* path finding example, actually my problem is if the start node can reach the goal node then it won''t have any delay else it will go thru all the nodes and take long time for example
* = ocstacle
- = path
A------
-
-
- ****
-**B*
****
in this case i means that the start node A will never reach the B node because it was surrounded by the ocstacle. So i will go thru every node and get the node that with the less f score and treat it as my new goal( the nearest point to the goal).
* = ocstacle
- = path
A------
-
-
- ****
-**B*
****
in this case i means that the start node A will never reach the B node because it was surrounded by the ocstacle. So i will go thru every node and get the node that with the less f score and treat it as my new goal( the nearest point to the goal).
If the goal is unreachable A* will perform an exaustive search. My recommendation is to time splice the function that finds path so that it will get split up over several frames if the time goes too long.
thats a degenerate case. A* can''t know if it can reach the goal until it exhaust all the searchable nodes. Some variants of A* run the search from both ends, and abort if either side exhaust their walkable nodes.
For the general case it''s better to try to determine these walkable sets ahead of time, and check sets to make sure both goal and start are in the same set of nodes.
Good Luck!
-ddn
For the general case it''s better to try to determine these walkable sets ahead of time, and check sets to make sure both goal and start are in the same set of nodes.
Good Luck!
-ddn
An other solution would be to validate your nodes when create them. A node surrounded by obstacle CAN''T be picked. When dealing with dynamic obstacle, you should get a valid path but then, validate as you walk if the next node is available, if not you can either wait until it''s available or pick an other way.
Hope this helps.
Hope this helps.
If you have the few extra bucks and want to learn a lot about pathfinding , then i''d suggest picking up a copy of AI Game Programming Wisdom (http://www.amazon.com/exec/obidos/tg/detail/-/1584500778/qid=1066768267/sr=8-1/ref=sr_8_1/103-2015179-6298200?v=glance&s=books&n=507846). There is an artical that book that talks about some ways to solve A* from testing every node. That book is well worth the money.
But one basic way to prevent flooding is to kill the while loop once the closed list is X number of nodes big, basicaly giving up. You could calculate X by using a heristic. Also, once you have given up you could move the guy to the closest point you found before giving up, then run the A* again.
Hope that helps
But one basic way to prevent flooding is to kill the while loop once the closed list is X number of nodes big, basicaly giving up. You could calculate X by using a heristic. Also, once you have given up you could move the guy to the closest point you found before giving up, then run the A* again.
Hope that helps
What if you preprocess the level and group all nodes that can reach each other, any nodes that are unreachable are placed in another node list, or are simply tagged as part of a different group. Before performing the A* search, you check whether the target and start nodes are in the same group, if they are, voila, they will reach each other so you can begin the search, if not, exit immediately and you don''t even have to start the A* search.
- James
- James
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement