CODEWITHSUNDEEP
algorithmgraphgraph-algorithm
lukas.pukenis
lukas.pukenis

Reputation: 13597

Drawing auto adjusting path on a grid

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

Example #1 or Example #2

Intersections

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.!

Upvotes: 1

Views: 248

Answers (2)

Spektre
Spektre

Reputation: 51835

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

example

[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 ...

Upvotes: 1

Edward Doolittle
Edward Doolittle

Reputation: 4100

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.

Upvotes: 0

Related Questions