Implementing Dijkstra and A* Algorithms

Creating the Directed Weighted Graph

Directed Weighted Graph:Directed Weighted Graph:

Directed Weighted Edge:

Node that stores coordinates to provide meaningful information for the A* algorithm:

Small Graph:

The small graph represents a few cities, but the roads are singly directed.

I made the small graph hard coded so that the content remains the same during each run. This way, I was able to debug my Dijkstra and A* algorithms’ implementations.

The weights of the edges are the Euclidean distances.

Large Graph:

I had the large graph randomly generated with 10000 edges.

Performance of Dijkstra and A*:

After implementing the Dijkstra and A* algorithms, I had both run the same graph and find the same shortest path, record their time consumed, and print them out.

The heuristic function I implemented for A* was an Euclidean distance between the coordinates of two cities:

However, I found out soon that the order of the two algorithms affects their times recorded. Hence, I had both the algorithms be called once before calling them again to time them. Below are the results I got:

Small Graph:

Large Graph:

For the small graph, the time difference between the two algorithms was very small, with A* being slightly faster than Dijkstra at most of the times.

For the large graph, the time difference between the two algorithms was very large, with A* being consistently 10 – 20 times faster than Dijkstra.

The main reason why A* is faster than Dijkstra is that it uses a heuristic function to guide its search, which often results in fewer nodes being explored, making it faster, especially on large graphs.

The reason why the time difference was not obvious on the small graph is that while doing pathfinding on the small graph, the Dijkstra algorithm did not have many more nodes to explore than A* had.

Heuristics:

I implemented two heuristics functions. One is a constant guess; another is a Euclidean distance:

Admissibility: A heuristic is admissible if it never overestimates the cost to reach the goal.

Consistency: A heuristic is consistent (or monotone) if for every node N and each successor P of N, the estimated cost of reaching the goal from N is no greater than the step cost of getting to P plus the estimated cost of reaching the goal from P.

For the constant guess:

It is admissible because it always returning 0. It is consistent because of the same reason.

For the Euclidean distance:

It is admissible because its return value is never greater than the actual cost (it is exactly the cost). It is consistent because the calculated cost decreases when getting closer to the goal.

If using the constant guess which always returns 0, it effectively converts the A* algorithm into a Dijkstra algorithm, which leads to its performance being the same as the Dijkstra algorithm.

If using the Euclidean distance as the heuristics function, the A* algorithm’s performance becomes much better due to exploring less nodes.

Combining A* and Boid’s Seek

Implementation

I created a tile map data structure which is a two-dimensional array of Booleans, 0 represents empty, 1 represents obstacle:

Then I made a pathfinding boid that derives from my common Boid class from the Fundamental Behavior Project:

In the new class, the mousePressed() and mouseDragged() does not set the seek target anymore, instead, it sets the pathfinding target and computes a path using A*:

Then, I update the next target for SEEK behavior in the Update() function:

Result