Game Development Stack Exchange is a question and answer site for professional and independent game developers. It only takes a minute to sign up.
Sign up to join this community
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.
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.
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.
