Algorithm to find the shortest path, with obstacles

java algorithm pathing
Valchris picture Valchris · Mar 14, 2011 · Viewed 51.2k times · Source

I have a collection of Points which represents a grid, I'm looking for an algorithm that gets me the shortest distance between point A and B. The catch being any point (excluding A and B) can have an obstacle obstructing the path, and thus must be detoured. The path may not move in diagonals.

For anyone else looking to solve this type of problem, I found these references to be very useful:

http://optlab-server.sce.carleton.ca/POAnimations2007/DijkstrasAlgo.html

http://en.literateprograms.org/Dijkstra%27s_algorithm_%28Java%29#chunk%20def:visit%20each%20vertex%20u,%20always%20visiting%20vertex%20with%20smallest%20minDistance%20first

Answer

templatetypedef picture templatetypedef · Mar 14, 2011

This is an excellent spot to use the A* search algorithm, a heuristic search algorithm that finds optimal paths between points very quickly even when there are obstacles present. The idea is to convert the grid into a graph where each cell in the grid is a node and in which there is an edge between any two adjacent cells that aren't obstructed from one another. Once you have this graph, the answer you're looking for is the shortest path in the graph from the start node to the destination node.

In order to use A*, you'll need a heuristic function that "guesses" the distance from any point on the grid to the destination square. One good heuristic for this would be to use the Manhattan distance between the two points.

If you're looking for an easier but still extremely efficient algorithm for finding the shortest path, consider looking into Dijkstra's algorithm, which can be thought of as a simpler version of A*. It's a bit slower than A*, but still runs extremely quickly and guarantees an optimal answer.

Hope this helps!

Related questions

moving an object from point to point in a linear path

I'm trying to move a sprite across the screen in a straight line, towards on the location where've I touched the screen, what i did was upon the update() in each loop , it checks to see if the current sprite's …

Read More
Finding the max/min value in an array of primitives using Java

It's trivial to write a function to determine the min/max value in an array, such as: /** * * @param chars * @return the max value in the array of chars */ private static int maxValue(char[] chars) { int max = chars[0]; for (int ktr = 0; …

Read More
Generating all permutations of a given string

What is an elegant way to find all the permutations of a string. E.g. permutation for ba, would be ba and ab, but what about longer string such as abcdefgh? Is there any Java implementation example?

Read More