DEV Community

Cover image for Pathfinding Algorithms
Osinachi Chukwujama
Osinachi Chukwujama

Posted on

Pathfinding Algorithms

Pathfinding algorithms solve the problem of finding the shortest path between two points.

According to Wikipedia

Pathfinding or pathing is the plotting, by a computer application, of the shortest route between two points

Why is pathfinding important?

You find yourself rushing to a hotel in a new city where a meeting that determines the fate of your career would be held. The meeting is scheduled for 5 pm. The time is 4:30 pm. Asking around would take at least 40 minutes. You have to use the shortest route to ensure you are punctual to the meeting. Luckily, google maps calculate the shortest route. No worries on your side. You arrive at the hotel at 4:55 pm. A pathfinding algorithm in google maps saved your career.

Uses of pathfinding

The anecdote shows one use of pathfinding algorithms. There are tons of applications. These include

  1. Video games: think maze games, RPG games, etc
  2. Mobile robots: moving an object from point A to B in the shortest time
  3. Delivery drones

Different Pathfinding Algorithms

I won't go deeply into the various pathfinding algorithms. But here are a few.

  1. Dijkstra's Algorithm (say dike-stra): the father of pathfinding algorithms; guarantees the shortest path
  2. A* Search: arguably the best pathfinding algorithm; uses heuristics to guarantee the shortest path much faster than Dijkstra's Algorithm
  3. Greedy Best-first Search: a faster, more heuristic-heavy version of A*; does not guarantee the shortest path
  4. Swarm Algorithm: a mixture of Dijkstra's Algorithm and A*; does not guarantee the shortest-path

I got this information from this site. It is a visualizer for pathfinding algorithms. Here's a visualization of Dijkstra's algorithm

Dijkstra's algorithm visualization.gif

Please share this article if you found it useful and also leave a like. Thanks for reading. Adios โœŒ๐Ÿฝ๐Ÿงก

Credits

  1. Cover image from growing with the web

Top comments (0)