Point of interest search
Hi,
I'm in need of an algorithm to find a path to the more or less most interesting point in the environment. I.e. my agents needs to drink and there're 4 watersources available, to which watersources exists the shortest path ?
Well, so far I thought about three approaches:
(1) scan & multiple A*:
I scan the environment for watersources and calculate the shortest path to each goal per A*. My agent will take the best path. This results in calling A* for n times, where n is the number of POIs.
(2) scan & single A*:
Same as 1. but with the exception of only calling a modified A* once. The heuristic of A* will be heuristic(x):=min( distance_to_goal_i(x)).
(3) dijkstra:
Executing a modified dijkstra. At each node an additional test (goal has been reached) will be executed.
Hmm... (3) seems to be nice in terms of not needing to scan the environment, but dijkstra is not the fastes. Will (2) be really faster than (1)?
I tend to (2), but I'm not sure. Does anyone has any experiences with this kind of approach ? Maybe a better approach ?
--
Ashaman
Do (2) in reverse. You start A* by putting all the water sources in the open list as nodes reachable with cost 0, and you place the agent as the goal. Then continue A* normally.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement