Algorithms For Dummies

Explaining Path Finding Algorithms

This last part of the chapter concentrates on explaining two algorithms, best-first 

search and A* (read as “A star”), both based on heuristics. The following sections 

demonstrate that both these algorithms provide a fast solution to a maze problem 

representing a topological or occupancy grid map that’s represented as a graph. 

Both algorithms are widely used in robotics and video gaming.

Creating a maze

A topological or occupancy grid map resembles a hedge maze, as mentioned pre-

viously, especially if obstacles exist between the start and the end of the route. 

There are specialized algorithms for both creating and processing mazes, most 

notably the Wall Follower (known since antiquity: You place your hand on a wall 

and never pull it away until you get out of the maze) or the Pledge algorithm (read 

more  about  the  seven  maze  classifications  at 

http://www.astrolog.org/ 

labyrnth/algrithm.htm

). However, pathfinding is fundamentally different from 

maze  solving  because  in  pathfinding,  you  know  where  the  target  should  be, 

---

378

 

   

  PART 5