5.6.6 Path Finding

Most game worlds have maps. Often, these games have a need to move non-player characters around in an unscripted fashion. For example, in a real-time strategy game, the player may command one of their units to attack something in the enemy base. To do so, the unit must calculate the shortest route to get there. It wouldn’t be a very fun game if units didn’t know how to transport themselves efficiently. This is where path finding algorithms come in handy. The (chickadee data path-finding) module provides a generic implementation of the popular A* path finding algorithm. Just add a map implementation!

The example below defines a very simple town map and finds the quickest way to get from the town common to the school.

(define world-map
  '((town-common . (town-hall library))
    (town-hall . (town-common school))
    (library . (town-common cafe))
    (school . (town-hall cafe))
    (cafe . (library school))))
(define (neighbors building)
  (assq-ref town-map building))
(define (cost a b) 1)
(define (distance a b) 1)
(define pf (make-path-finder))
(a* pf 'town-common 'school neighbors cost distance)

In this case, the a* procedure will return the list (town-common town-hall school), which is indeed the shortest route. (The other possible route is (town-common library cafe school).)

The a* procedure does not know anything about about any kind of map and therefore must be told how to look up neighboring nodes, which is what the neighbors procedure in the example does. To simulate different types of terrain, a cost procedure is used. In this example, it is just as easy to move between any two nodes because cost always returns 1. In a real game, perhaps moving from from a field to a rocky hill would cost a lot more than moving from one field to another. Finally, a heuristic is used to calculate an approximate distance between two nodes on the map. In this simple association list based graph it is tough to calculate a distance between nodes, so the distance procedure isn’t helpful and always returns 1. In a real game with a tile-based map, for example, the heuristic could be a quick Manhattan distance calculation based on the coordinates of the two map tiles. Choose an appropriate heuristic for optimal path finding!

Procedure: make-path-finder

Return a new path finder object.

Procedure: path-finder? obj

Return #t if obj is a path finder.

Procedure: a* path-finder start goal neighbors cost distance

Return a list of nodes forming a path from start to goal using path-finder to hold state. neighbors is a procedure that accepts a node and returns a list of nodes that neighbor it. cost is a procedure that accepts two neighboring nodes and returns the cost of moving from the first to the second as a real number. distance is a procedure that accepts two nodes and returns an approximate distance between them.