Path Finding (The Chickadee Game Toolkit)

From f16fed3d50fd3d56deb46a3d4641a81460e389de Mon Sep 17 00:00:00 2001 From: David Thompson Date: Wed, 12 Dec 2018 09:20:10 -0500 Subject: Update Chickadee manual and home page for 0.3.0. Better late than never! --- manuals/chickadee/Path-Finding.html | 180 ++++++++++++++++++++++++++++++++++++ 1 file changed, 180 insertions(+) create mode 100644 manuals/chickadee/Path-Finding.html (limited to 'manuals/chickadee/Path-Finding.html') diff --git a/manuals/chickadee/Path-Finding.html b/manuals/chickadee/Path-Finding.html new file mode 100644 index 0000000..63819aa --- /dev/null +++ b/manuals/chickadee/Path-Finding.html @@ -0,0 +1,180 @@ + + + + + + +Path Finding (The Chickadee Game Toolkit) + + + + + + + + + + + + + + + + + + + + + +

+ +

2.2.9 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 math 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. +

+ +

+ + + + + + -- cgit v1.2.3