Search code examples
algorithmarduinogridpath-finding

An algorithm to find the shortest and best path in a grid for a robot linefollower


I need to write an algorithm to find the shortest path to a coordinate in a grid. For example, a robot is at point (2,4) in a grid (imagine a Cartesian coordinate system), and the robot needs to go to point (5,8). But the robot can't go through all the points. The robot must identify the shortest way to go to the specified point.


Solution

  • This is a Classical search problem. A*-Search is very simple for your problem. As Heuristic for the remaining costs you can simply use the Manhatten distance.

    Other approaches are breath first search. Also consider search from the start and the destination at the same time until both searches intersect.

    A* search algorithm