Path finding in a graph? (GPS)?

Question

The city in my game is essentially a graph of roads and intersections.

Each road has a reference to the start and end intersections.

each intersection has either a reference to the top, left, bottom, right roads or null if it is a 3 way, 2 way intersection etc.

Roads are rectangles.

Given this, is there a way to generate a path to get from road A to road B? (Something simpler than say A*?

Thanks

Answer 1

Dijkstra's algorithm is pretty easy.

Answer 2

If you don't want to implement all the path finding algorithms yourself I highly recommend JGraphT. It is an excellent library for all your graphing needs. It can find for you the shortest path by returning a list of edges.

It certainly has a learning curve, though. I started out with wanting to use WeightDirectedGraphs and that took a bit of Googling to find the appropriate way to use it.

Edit: I just noticed you tagged your post as both Java and C++, but JGraphT is a Java library (as the J in the name implies).

Answer 3

Since the graph is unweighted, you can try BFS - though it is uninformed and probably will be slower then A* algorithm (with reasonable heuristic function for A*).

You can speed it up a bit by doing bi-directional BFS - which is also optimal in unweighted graphs and should be much faster then standard BFS.
The idea of bi-directional BFS is simple: Do a BFS step (depth 1, depth 2, ...) from the start and from the end at the "same time" (one after the other), and once you find out that the fronts of the two searches intersects - you have your path.
It is much faster, since each direction only searches up to the middle, giving you total O(2 * B^(d/2)) = O(B^(d/2)) nodes to explore (where d is the depth of the best solution, and B is the branch factor - 4 in your case), while regular BFS is O(B^d)