2
\$\begingroup\$

What is the best way to, in a grid, to find a path (not necessarily shortest) from a start point to an end point (for both of which the coordinates are known)?

The grid is approximately 60x60, and has some obstacles in it. The coordinates of the start point, the end point, and all of the obstacles are known and easily accessible. Searches such as Breadth-first and A* work, however they seem to do an unnecessarily large amount of "searching" when you should already know where you are going.

Improve this question
\$\endgroup\$
1
  • 4
    \$\begingroup\$ A* is about as good as you can get in the general case. When unimpeded by obstacles, its heuristic should lead it to roughly beeline to the destination. It's only when the direct route is blocked that its search area starts to grow more exhaustive. For a grid as small as 60x60, even worst-case A* performance is unlikely to be a big problem for you. I'd recommend just implementing A* and profiling to see if this is a case where you really need a more tailored solution. \$\endgroup\$
    – DMGregory ♦
    Aug 18, 2016 at 14:58

2 Answers 2

Reset to default
4
\$\begingroup\$

Grids with known start and end points are the ideal inputs for algorithms like A*. Especially considering you have some obstacles in your grid. A*, in fact, would not work if you didn't know the start point, end point and obstacles.

Your program does not know where it's going until you tell it where to go. While it may seem trivial for you to look at a grid and find a path from one point to another, computers have no idea unless you tell them. With the information you've provided, A* would be ideal for pathfinding.

However, if you don't actually need pathfinding, and just want to go from A to B, you don't have to find a path first, you can just start going. You can essentially find the path as you go, with movement that emulates a depth-first search algorithm. Simply head directly towards the goal, if something gets in the way, move left or right to go around.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ How would one go about the algorithm for going from A to B, without pathfinding? More specifically, what would be the algorithm for the obstacle avoidance (as just moving from A to B on a grid in itself is trivial), without having to go one way then backtracking the other way again? \$\endgroup\$
    – Theo
    Aug 18, 2016 at 16:06
  • \$\begingroup\$ It's important to understand there's a difference between path following and path finding. You can go from A to B without pathfinding by finding the next best step. In most cases, that's simply towards the direction of B. Unless there's an obstacle in the way. You said you didn't need the shortest path, so backtracking would be allowed. The whole point of path finding in advance is to find an optimal path, i.e. one that does not include backtracking or wrong turns. \$\endgroup\$
    – House ♦
    Aug 18, 2016 at 16:14
1
\$\begingroup\$

If you're not concerned with finding an optimal path & want to reduce the searching, tweak your preferred algorithm to bail out when the first path is found. This tweak is pretty straight forward, but keep in mind that you can get some pretty dumb looking answers this way.

Sometimes a hybrid approach is used. For this you start with an optimal path finding algorithm, keep the best path found so far & return that if the search is taking too long.

As suggested by @DMGregory, it's wise to actually check your performance via profiling before customizing / optimizing your path finding. Personally, I wouldn't commit dev time to a hybrid approach unless I knew it was warranted. On the other hand, the bail out approach might actually take less time to develop since only only need to test the result is a legal path & you don't need to test if the result is actually optimal.

Improve this answer
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .