Archived

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

chengseesin

path finding

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
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
quote:
Original post by weasalmongler
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


Sure this would solve one problem, but introduce a new overhead to all pathfinding calculations (which may or may not be significant depending on the specifics of the world and the implementation). There are some pre-culling operations you could use before using such a solution, such as, for any given grouping of nodes, have a centre point and a radius which envelopes all the nodes within the group. Then check if the target node falls within this circle (or sphere if you''re working in 3D). If it does then it still might not be connected, but if it doesn''t then it certainly is not connected and you can early-out with a failure.

I would also suggest that any grouping you used for the nodes be contained in such a manner as to allow fast retreival. Instead of using a list or a vector, for instance, you could a set, where the container simply stores a set of unique keys, the key could be the address of a node. This is a fast method (perhaps not the fastest, but orders of magnitude faster than a list retrieval) for finding out if a node is in a grouping.

Mike

Share this post


Link to post
Share on other sites
quote:
Sure this would solve one problem, but introduce a new overhead to all pathfinding calculations (which may or may not be significant depending on the specifics of the world and the implementation). There are some pre-culling operations you could use before using such a solution, such as, for any given grouping of nodes, have a centre point and a radius which envelopes all the nodes within the group. Then check if the target node falls within this circle (or sphere if you''re working in 3D). If it does then it still might not be connected, but if it doesn''t then it certainly is not connected and you can early-out with a failure.

I would also suggest that any grouping you used for the nodes be contained in such a manner as to allow fast retreival. Instead of using a list or a vector, for instance, you could a set, where the container simply stores a set of unique keys, the key could be the address of a node. This is a fast method (perhaps not the fastest, but orders of magnitude faster than a list retrieval) for finding out if a node is in a grouping.

Mike


be simpler! the grouping algorithm has linear complexity and i don''t think that it may be optimized in anyway.

Share this post


Link to post
Share on other sites
quote:
Original post by wormball
be simpler! the grouping algorithm has linear complexity and i don''t think that it may be optimized in anyway.


Which grouping algorithm has linear complexity? What has complexity got to do with it? What may not be optimized? I''m confused

Mike

Share this post


Link to post
Share on other sites
you go around the connected nodes and paint they in the same color (with linear complexity!), then you take another node disconnected from already painted group, and paint the nodes connected with this node, also with linear complexity, etc.

ps. how can you speak this language? russian is much more cool

Share this post


Link to post
Share on other sites
One of the best ways to improve the speed (specially when you have more than one unit) is limiting your number of iterations.
If you can´t find the path in something like 80 iterations, just break, and set your goal to the nearest point found.

This is what starcraft do, and in the worst case, when you reach this sub-goal, you can recalculate.

---------------------------------------------
If God with me, Who against me?
Sitio de desarrollo de videojuegos en español
Digital Moon Studio...

There is no spoon

[edited by - NeonGE on October 22, 2003 10:15:51 AM]

Share this post


Link to post
Share on other sites