Drawing auto adjusting path on a grid

Question

I need to let the user draw a path on a grid but without a precision - the algorithm should adjust the path.

Example images where red line indicates the continuous path user will draw and blue dots are the final path

or

• I cant get away with pathfinding as I dont need the optimal path
• I need it to update on each user input(while drawing red line)

I am thinking something about intersections(red dots) so I would add intersection to the list from which to pathfind until the current input and maybe some weighted graph approach but have no final idea. I would appreciate any advice on this.!

Answer 1

Just to be sure I see it the right way:

• straight line means best path is used

• curved line means be as close as possible to it ...

  1. So sample the user given path as set of points
  2. remove all points not on road
  3. align them to grid
  4. use piecewise best path finding
• can use mine A* algorithm

[notes]

• you can do steps 2,3 in single step
• can avoid use of A* for neighboring cells paths
• can use A* data from previous piece (no need to clear buffers just continue from last used index...
• unless your input path goes in circles ...

Answer 2

At any point you can either change X or change Y, not both, so you can make changeX a boolean, with changeY its NOT. Suppose changeX is true. Then you just take the X coordinate of the user input. Vice versa for ~changeX and Y coordinate of user input.

The variable changeX can be altered only at the intersections. One way to decide whether to update would be to calculate which of the next points would be closest to the pointer. You just need to compare the squares of the distances so that saves you from an expensive square root calculation.

You could probably calculate every next point on that basis, but it's probably overkill for the situation when the grid is square.