Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!
What's the best algorithm to find the most logical/reasonable path between a list of points in space?
It doesn't have to be the shortest path but one that would connect all points and would seem the most reasonable to the eye...
There can be multiple solutions in a single case but the path has to appear like it's the simplest way through all points.
Is there such a thing?
A*
I know, I know, A* is typically used as a shortest path algorithm. But that's not really what A* actually is. It's an 'optimal' path algorithm, where optimal is defined by the implementation. A* uses a cost-calculation function to calculate the cost of a given path up to the node being considered, and a cost-estimation function to estimate the cost of the path at completion. The typical use case is cost-calculation=how far to get here and cost-estimation=how far to the destination, but these are not requirements. If you can come up with a calculation function and heuristic function that estimates 'logicalness/reasonableness' of a path, then you can drop them right into an A* implementation and it should work.
The trick, of course, is ironing out your calculation and heuristic.
But that's exactly what I was asking for - the "coming up with the calculation" part...
Also, doesn't the fact that A* finds the most optimal path, mean that it would choose to avoid some points in the list?
My goal is to go through all points while making the simplest path possible. Sorry if I wasn't clear about it 
You want to visit all points? That sounds like the Travelling Salesman Problem.
See also: https://en.wikipedia.org/wiki/Hamiltonian_path
I forget what the algorithm is called, but I implemented a Hamiltonian path solver for complete graphs by starting with a minimum spanning tree and iteratively removing edges from vertices that have 3+ edges and then connecting the two isolated parts via the ends. This eventually makes a hamiltonian path, which is not necessarily optimal but may look decent.
Similar and also based on spanning tree: https://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree
But it still has branches which you probably don't want.
On 3/27/2018 at 2:07 AM, berengard2 said:A* finds the most optimal path, mean that it would choose to avoid some points in the list?
Then why not use the points as the target, like a simple waypoint system? That way you can keep using A* and reuse it at every point.
By definition, any good TSP solution is going to look logical and reasonable because usually people don't care about anything but minimum path cost; at worst a good approximate solution can differ from the optimal one by in noticeable ways, but the different choices look (and actually are) approximately equally expensive (i.e. never obviously stupid).
Consider approximating other logical and reasonable behaviour, for example a greedy patrol route on a changing waypoint graph in which you set as goal the closest one of the nodes that you haven't visited for the longest time (accidentally visiting other nodes along the way).
On 3/27/2018 at 2:07 AM, berengard2 said:Also, doesn't the fact that A* finds the most optimal path, mean that it would choose to avoid some points in the list?
My goal is to go through all points while making the simplest path possible.
@JTippetts is speaking about optimal path, but not in the way you interpret it.
Basically A* is a generic search algorithm, you are in one state, and you want to go to some known destination state, but you are not sure how to get there. The usual problem where A* is thrown at, is where "state" means "position in the world", and the first state is then "i am here", and the destination state is "I want to go there". Transition from one state to the next is then "move in the world".
However, state can mean anything you like (which is what JTippets means). For you, state could mean "I have some points connected". First state is then "I have no points connected", and last state is "I have all points" connected. Then your search space is connecting points in the path. Transition to the next state is "connect a point". A heuristic could be "cleanliness of the solution so far", ie your "reasonable" notion. For example, make the solution worse if many paths cross each other.
Depending on how many points you have, a brute force approach may also be an option.
