Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

chengseesin

path finding

This topic is 5531 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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?

Share this post


Link to post
Share on other sites
Advertisement
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]

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!