views:

323

answers:

2

I currently have another question to do with path finding in Java. However I feel this is a separate question.

I'm making a game. The path-finding will need to be able to deal with multiple possible end points. All the path finding algorithms and tutorials I have found only have one end point.

Would this alteration be easy to tweak into an already existing bit of code, or am I better off trying to write my own from scratch?

+2  A: 

If you are using A*, but have multiple vertexes in your graph that can be considered goals, you could estimate the distance to each goal, and use the minimum. A* will work as long as you don't over-estimate the true distance to the goal.

This special behavior might lead you to write your own A* implementation, however. It isn't a lot of code; maybe a day or two of homework for a college student, IIRC.

erickson
Would work indeed. A* is basically an improved way to do Dijkstra; it optimizes the common, typical cases. Could be a bit slow if 2 goals are opposite to the starting point. You'd make quick progress to one point, then need to check a whole lot of points on the other side. But that's inevitable.
MSalters
+1  A: 

I don't know much about games but Floyd-Warshall is a multiple endpoint shortest path algorithm.

JP Alioto
A bit overkill; it will get you all possible pairs. That's N*(N-1) of them.
MSalters