Update Chickadee manual and home page for 0.3.0.

Better late than never!
author: David Thompson <dthompson2@worcester.edu> 2018-12-12 09:20:10 -0500
committer: David Thompson <dthompson2@worcester.edu> 2018-12-12 09:20:10 -0500
commit: f16fed3d50fd3d56deb46a3d4641a81460e389de (patch)
tree: 71659ed643b65eadb17110b3f8f0c5d5cfdd3031 /manuals/chickadee/Path-Finding.html
parent: c4b418c2dcfba3c741f67058a51a3e490aa4b297 (diff)
1 files changed, 180 insertions, 0 deletions
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 @@
+<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
+<html>
+<!-- Copyright (C) 2017  David Thompson davet@gnu.org
+
+Permission is granted to copy, distribute and/or modify this document
+under the terms of the GNU Free Documentation License, Version 1.3
+or any later version published by the Free Software Foundation;
+with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.
+A copy of the license is included in the section entitled "GNU
+Free Documentation License".
+
+A copy of the license is also available from the Free Software
+Foundation Web site at http://www.gnu.org/licenses/fdl.html.
+
+
+The document was typeset with
+http://www.texinfo.org/ (GNU Texinfo).
+ -->
+<!-- Created by GNU Texinfo 6.5, http://www.gnu.org/software/texinfo/ -->
+<head>
+<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
+<title>Path Finding (The Chickadee Game Toolkit)</title>
+
+<meta name="description" content="Path Finding (The Chickadee Game Toolkit)">
+<meta name="keywords" content="Path Finding (The Chickadee Game Toolkit)">
+<meta name="resource-type" content="document">
+<meta name="distribution" content="global">
+<meta name="Generator" content="makeinfo">
+<link href="index.html#Top" rel="start" title="Top">
+<link href="Index.html#Index" rel="index" title="Index">
+<link href="index.html#SEC_Contents" rel="contents" title="Table of Contents">
+<link href="Math.html#Math" rel="up" title="Math">
+<link href="Graphics.html#Graphics" rel="next" title="Graphics">
+<link href="Bezier-Curves.html#Bezier-Curves" rel="prev" title="Bezier Curves">
+<style type="text/css">
+<!--
+a.summary-letter {text-decoration: none}
+blockquote.indentedblock {margin-right: 0em}
+blockquote.smallindentedblock {margin-right: 0em; font-size: smaller}
+blockquote.smallquotation {font-size: smaller}
+div.display {margin-left: 3.2em}
+div.example {margin-left: 3.2em}
+div.lisp {margin-left: 3.2em}
+div.smalldisplay {margin-left: 3.2em}
+div.smallexample {margin-left: 3.2em}
+div.smalllisp {margin-left: 3.2em}
+kbd {font-style: oblique}
+pre.display {font-family: inherit}
+pre.format {font-family: inherit}
+pre.menu-comment {font-family: serif}
+pre.menu-preformatted {font-family: serif}
+pre.smalldisplay {font-family: inherit; font-size: smaller}
+pre.smallexample {font-size: smaller}
+pre.smallformat {font-family: inherit; font-size: smaller}
+pre.smalllisp {font-size: smaller}
+span.nolinebreak {white-space: nowrap}
+span.roman {font-family: initial; font-weight: normal}
+span.sansserif {font-family: sans-serif; font-weight: normal}
+ul.no-bullet {list-style: none}
+@media (min-width: 1140px) {
+    body {
+        margin-left: 14rem;
+        margin-right: 4rem;
+        max-width: 52rem;
+    }
+}
+
+@media (min-width: 800px) and (max-width: 1140px) {
+    body {
+        margin-left: 6rem;
+        margin-right: 4rem;
+        max-width: 52rem;
+    }
+}
+
+@media (max-width: 800px) {
+    body {
+        margin: 1rem;
+    }
+}
+
+-->
+</style>
+<link rel="stylesheet" type="text/css" href="https://dthompson.us/css/dthompson.css">
+
+
+</head>
+
+<body lang="en">
+<a name="Path-Finding"></a>
+<div class="header">
+<p>
+Previous: <a href="Bezier-Curves.html#Bezier-Curves" accesskey="p" rel="prev">Bezier Curves</a>, Up: <a href="Math.html#Math" accesskey="u" rel="up">Math</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Index.html#Index" title="Index" rel="index">Index</a>]</p>
+</div>
+<hr>
+<a name="Path-Finding-1"></a>
+<h4 class="subsection">2.2.9 Path Finding</h4>
+
+<p>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&rsquo;t be a very fun
+game if units didn&rsquo;t know how to transport themselves efficiently.
+This is where path finding algorithms come in handy.  The
+<code>(chickadee math path-finding)</code> module provides a generic
+implementation of the popular A* path finding algorithm.  Just add a
+map implementation!
+</p>
+<p>The example below defines a very simple town map and finds the
+quickest way to get from the town common to the school.
+</p>
+<div class="example">
+<pre class="example">(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)
+</pre></div>
+
+<p>In this case, the <code>a*</code> procedure will return the list
+<code>(town-common town-hall school)</code>, which is indeed the shortest
+route.  (The other possible route is <code>(town-common library cafe
+school)</code>.)
+</p>
+<p>The <code>a*</code> 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 <code>neighbors</code> 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
+<code>cost</code> 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 <code>distance</code> procedure isn&rsquo;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!
+</p>
+<dl>
+<dt><a name="index-make_002dpath_002dfinder"></a>Procedure: <strong>make-path-finder</strong></dt>
+<dd><p>Return a new path finder object.
+</p></dd></dl>
+
+<dl>
+<dt><a name="index-path_002dfinder_003f"></a>Procedure: <strong>path-finder?</strong> <em><var>obj</var></em></dt>
+<dd><p>Return <code>#t</code> if <var>obj</var> is a path finder.
+</p></dd></dl>
+
+<dl>
+<dt><a name="index-a_002a"></a>Procedure: <strong>a*</strong> <em><var>path-finder</var> <var>start</var> <var>goal</var>                       <var>neighbors</var> <var>cost</var> <var>distance</var></em></dt>
+<dd>
+<p>Return a list of nodes forming a path from <var>start</var> to <var>goal</var>
+using <var>path-finder</var> to hold state.  <var>neighbors</var> is a procedure
+that accepts a node and returns a list of nodes that neighbor it.
+<var>cost</var> is a procedure that accepts two neighboring nodes and
+returns the cost of moving from the first to the second as a real
+number.  <var>distance</var> is a procedure that accepts two nodes and
+returns an approximate distance between them.
+</p></dd></dl>
+
+<hr>
+<div class="header">
+<p>
+Previous: <a href="Bezier-Curves.html#Bezier-Curves" accesskey="p" rel="prev">Bezier Curves</a>, Up: <a href="Math.html#Math" accesskey="u" rel="up">Math</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Index.html#Index" title="Index" rel="index">Index</a>]</p>
+</div>
+
+
+
+</body>
+</html>
author	David Thompson <dthompson2@worcester.edu>	2018-12-12 09:20:10 -0500
committer	David Thompson <dthompson2@worcester.edu>	2018-12-12 09:20:10 -0500
commit	f16fed3d50fd3d56deb46a3d4641a81460e389de (patch)
tree	71659ed643b65eadb17110b3f8f0c5d5cfdd3031 /manuals/chickadee/Path-Finding.html
parent	c4b418c2dcfba3c741f67058a51a3e490aa4b297 (diff)