Path Finding (The Chickadee Game Toolkit)

From 25c5eac5e6ca1035db1eddd7bea9ac78531da57e Mon Sep 17 00:00:00 2001 From: David Thompson Date: Thu, 28 Dec 2023 11:23:49 -0500 Subject: Delete manuals! Good riddance! These are hosted on files.dthompson.us now! --- manuals/chickadee/Path-Finding.html | 171 ------------------------------------ 1 file changed, 171 deletions(-) delete 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 deleted file mode 100644 index 150ef88..0000000 --- a/manuals/chickadee/Path-Finding.html +++ /dev/null @@ -1,171 +0,0 @@ - - - - - - -Path Finding (The Chickadee Game Toolkit) - - - - - - - - - - - - - - - - - - - - -

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. -

- -

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