Hi, for a geo-based online game I'm looking for an algorithm which finds the shortest distance between a specified point and a known path connected by x/y-coordinates, so that I can kill all redundant points/nodes. A link or keyword for this algorithm would help me a lot! thanks for reading
For better understanding:
I suggest the best link is probably:
http://www.google.com/search?q=point+line+distance
The best answer will depend on how you represent your data and whether you need planar distance or geographic distance.
Other useful starting points might include:
http://www.google.com/search?q=spatial+index
http://www.google.com/search?q=surface+render+optimization
This is a point-to-point path-finding algorithm that is commonly used in games:
You might need to apply it a number of times between your point and path, but it is generally very fast. The algorithm has some optimizations for map grids (where the distances between squares are integers). There's a description of this in: Real-Time Strategy Game Programming using MS DirectX 6.0 by Mickey Kawick.
Djikstra's algorithm is a good general purpose path-finding algorithm from a single source node to all other nodes in the graph. You can stop the algorithm when you've found what you need - which in your case would be when the algorithm had found the shortest path to every node on the path.
I don't know of a specific "shortest path from node to path" algorithm.
Are you wanting to calculate this in order to say something like "if the point-to-path distance is zero, then remove the point"? If so, then there is probably an easier way to remove redundant nodes. Take the points three at a time (call them A, B, and C). Calculate the angle between A and B, as well as the angle between B and C. If the two angles are the same, then point B lies in the path between A and C and is redundant. You can use the 'atan2' function (or your language's equivalent) to do the angle calculations.