I have kind of an abstract problem and I was hoping someone might be able to point me in the right direction. I have some dynamic data in the form of points on a grid (red), a player (yellow), and a sight range (light yellow). I want to walk from the left side of the grid to the right on a path that lets him see each point (red). It's easy enough to implement a solution where he just walks directly over each point but what i'd like to do is minimize how often he has to change directions (ie. i'd like to have him spend as much time as possible moving straight from left to right before having to turn). The path drawn in yellow is what I'd consider to be a good solution for this example. I've gone through resources on pathfinding and optimization problems and no approach has really jumped out at me as being suitable =/ Any thoughts or suggestions on areas to research would be much appreciated.

Maybe look up the travelling salesman problem? It's not an easy thing to solve for small problems, and it scales badly because it's NP complete.

I'd try to regroup red cells into linear chunks, then search through the options between those chunks...

It looks like a job for dynamic programming. I'll write some sample code later.

Couldn't this be done with regular A* ?
Simply penalize direction changes when calculating the cost and possible increasing the cost of each point the further away from its local "line-center".

Quote: Original post by alexjc
Maybe look up the travelling salesman problem? It's not an easy thing to solve for small problems, and it scales badly because it's NP complete.

I'd try to regroup red cells into linear chunks, then search through the options between those chunks...

It's not quite that bad, I don't think? There's only going to be 1 point per column to see. So he should never need to backtrack or anything.

Alvaro,

I'm curious if dynamic programming would work here. I've used it to solve problems where there's a clear "flow" -- so you know which direction you're propagating information from and to, but in this case it seems a much more general case. (For example, This is used to create motion graphs, see Kovar and Gleicher for reference.)

Say for example you had the start (top left), the finish (bottom right) and two mid points in the other corners. Dynamic programming would struggle there IMHO.

Alex

Quote: Original post by alexjc
Alvaro,

I'm curious if dynamic programming would work here. I've used it to solve problems where there's a clear "flow" -- so you know which direction you're propagating information from and to, but in this case it seems a much more general case. (For example, This is used to create motion graphs, see Kovar and Gleicher for reference.)

Say for example you had the start (top left), the finish (bottom right) and two mid points in the other corners. Dynamic programming would struggle there IMHO.

Alex

Well, the wording of the problem is not very clear, but by looking at the example, it seems there is a single red square per column. That, together with "walk from the left side of the grid to the right" lead me to believe that perhaps he doesn't allow moving to the left. It would be good to get clarification on this point.

If you can move any way you want, then it becomes kind of TSP, I agree.

[Edited by - alvaro on November 20, 2009 6:18:18 PM]