Welcome to GameHourz.com!
FAQFAQ   SearchSearch      ProfileProfile    Private MessagesPrivate Messages   Log in/Register/PasswordLog in/Register/Password

A* and multi-goals

  
   Game Forums (Home) -> AI Games RSS
Related Topics:
TBC Fast Package(1-70) - Any Class Free 2000G - Wow per level per level. Dear Sir or Madam Hot Sale!For all of our news and are some Special Package! We now provide measured by..

bigtest - bigtest

AI and C# - HI all... does anybody know a book about AI, which includes examples in c#? thx for reading ;)

2006 Chatterbox Challenge - The online voting for the 2006 Challenge at has begun. Visit the site and vote for the 3 best bots. No or anything required to vote. Voting ends 4/30/06. Wendell

mistake in AIAMA python code - im no expert so im not 100% these are errors def an n-person, state = while True: for player in players: move = state) ..
Next:  AI Games: algorithms, heuristics, & data-structures  
Author Message
eric.boissard

External


Since: Mar 01, 2006
Posts: 1



(Msg. 1) Posted: Wed Mar 01, 2006 2:33 am
Post subject: A* and multi-goals
Archived from groups: comp>ai>games (more info?)
Hello,

I am using A* to find the shortest path in a 3D environment, I have
waypoints at each intersections, rooms, interesting points to create
the graph. At the moment I can select a start and goal node, the A*
algorithm do the rest and my character simply follows the path.
Now I would like to modify it in order to set intermediate goals/nodes
in the path. I want to make sure that the character pass through some
'mandatory' nodes before reaching the final destination. I can have
maybe 3 or 4 intermediate destinations. The order to visit them is not
important. Is there a simple way to do that ? One solution would be to
calculate the cost of each 'intermediate' paths and combine them in
order to get the shortest path to the 'final' goal. Is there a way to
simply 'tweak' the A* algorithm ? Thanks for your help

Eric

 >> Stay informed about: A* and multi-goals 
Back to top
Login to vote
Bjorn Reese

External


Since: Jan 18, 2005
Posts: 4



(Msg. 2) Posted: Wed Mar 01, 2006 4:55 pm
Post subject: Re: A* and multi-goals [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)
eric.boissard.TakeThisOut@gmail.com wrote:

> Now I would like to modify it in order to set intermediate goals/nodes
> in the path. I want to make sure that the character pass through some
> 'mandatory' nodes before reaching the final destination. I can have
> maybe 3 or 4 intermediate destinations. The order to visit them is not
> important. Is there a simple way to do that ? One solution would be to
> calculate the cost of each 'intermediate' paths and combine them in
> order to get the shortest path to the 'final' goal. Is there a way to
> simply 'tweak' the A* algorithm ? Thanks for your help

Create a goal-set, containing all the intermediate goals and the final
goal. Change A* to stop when it has found a path to any one of these
goals. Let the character move to this goal. When the goal is reached,
remove it from the goal-set, and repeat the process until the final
goal has been reached.

--
mail1dotstofanetdotdk

 >> Stay informed about: A* and multi-goals 
Back to top
Login to vote
Rémi

External


Since: Mar 02, 2006
Posts: 1



(Msg. 3) Posted: Thu Mar 02, 2006 8:55 am
Post subject: Re: A* and multi-goals [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)
Bjorn Reese wrote:
> eric.boissard RemoveThis @gmail.com wrote:
>
>> Now I would like to modify it in order to set intermediate goals/nodes
>> in the path. I want to make sure that the character pass through some
>> 'mandatory' nodes before reaching the final destination. I can have
>> maybe 3 or 4 intermediate destinations. The order to visit them is not
>> important. Is there a simple way to do that ? One solution would be to
>> calculate the cost of each 'intermediate' paths and combine them in
>> order to get the shortest path to the 'final' goal. Is there a way to
>> simply 'tweak' the A* algorithm ? Thanks for your help
>
>
> Create a goal-set, containing all the intermediate goals and the final
> goal. Change A* to stop when it has found a path to any one of these
> goals. Let the character move to this goal. When the goal is reached,
> remove it from the goal-set, and repeat the process until the final
> goal has been reached.
>

This is a simple idea that works.

But it is greedy and may be suboptimal.

Finding the best path is more difficult in general. It is a variation of
the traveling-salesman problem. Look it up in Google and you'll find
plenty of references.

Rémi
 >> Stay informed about: A* and multi-goals 
Back to top
Login to vote
Geoffrey Summerhayes

External


Since: Mar 02, 2006
Posts: 5



(Msg. 4) Posted: Thu Mar 02, 2006 12:15 pm
Post subject: Re: A* and multi-goals [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)
eric.boissard.DeleteThis@gmail.com wrote:
> Hello,
>
> I am using A* to find the shortest path in a 3D environment, I have
> waypoints at each intersections, rooms, interesting points to create
> the graph. At the moment I can select a start and goal node, the A*
> algorithm do the rest and my character simply follows the path.
> Now I would like to modify it in order to set intermediate goals/nodes
> in the path. I want to make sure that the character pass through some
> 'mandatory' nodes before reaching the final destination. I can have
> maybe 3 or 4 intermediate destinations. The order to visit them is not
> important. Is there a simple way to do that ? One solution would be to
> calculate the cost of each 'intermediate' paths and combine them in
> order to get the shortest path to the 'final' goal. Is there a way to
> simply 'tweak' the A* algorithm ? Thanks for your help

Unfortunately, no. Best bet, based on the criteria given, is to:
1-Build paths from Start to all waypoints
2-Build paths from all waypoints to Goal
3-Build paths from all waypoints to all waypoints,
meaning doing both Point1 to Point2 and Point2 to Point1
(the paths will most likely be different)
4-Select a total path from the permutations, not to bad,
4 waypoints is only 4! or 24 paths to be considered and
4+4+12=20 paths to be calculated and if more than one
of the waypoints are fixed you could always precalc those
particular paths.

--
Geoff
 >> Stay informed about: A* and multi-goals 
Back to top
Login to vote
Sc0rpi0

External


Since: Jul 18, 2005
Posts: 3



(Msg. 5) Posted: Fri Mar 03, 2006 9:55 am
Post subject: Re: A* and multi-goals [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)
Geoffrey Summerhayes:

> Unfortunately, no. Best bet, based on the criteria given, is to:
> 1-Build paths from Start to all waypoints
> 2-Build paths from all waypoints to Goal
> 3-Build paths from all waypoints to all waypoints,
> meaning doing both Point1 to Point2 and Point2 to Point1
> (the paths will most likely be different)
> 4-Select a total path from the permutations, not to bad,
> 4 waypoints is only 4! or 24 paths to be considered and
> 4+4+12=20 paths to be calculated and if more than one
> of the waypoints are fixed you could always precalc those
> particular paths.

Hmm, I think the better way is in fact wp table distances, but
not precalculated - instead it may be build during constructing
paths and checked if it is already known. Also if any path is
done OK then 1. we have all wp distances calculated, 2. else
paths with greater distanance value apearing somewhere in the
middle can be just throw out as worse path and we of course
builing remaining path part with distances order shortest->longest
always. This won't work only when wpA->wpB path cannot be
treated as equal to wpB->wpA.


--
Sc0rpi0
I hated going to weddings.
All the grandmas would poke me saying "You're next".
They stopped that when I started doing it to them at funerals.
 >> Stay informed about: A* and multi-goals 
Back to top
Login to vote
pinoyangtumapos3




Joined: Nov 20, 2006
Posts: 50



(Msg. 6) Posted: Wed Nov 22, 2006 4:52 pm
Post subject: Re: A* and multi-goals [Login to view extended thread Info.]
Hey I received an email and a link in it, they have great services. They
Offer power leveling, rentals, they buy and sell, they can even trade. Check
Out http://oloot.com
 >> Stay informed about: A* and multi-goals 
Back to top
Login to vote
Display posts from previous:   
   Game Forums (Home) -> AI Games All times are: Ekaterinburg, Islamabad, Karachi, Tashkent (change)
Page 1 of 1

 
 You can post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum



[ Contact us | Terms of Service/Privacy Policy ]