1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
|
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!-- Copyright (C) 2017-2023 David Thompson dthompson2@worcester.edu
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.
* Chickadee: (chickadee). Game programming toolkit for Guile.
The document was typeset with
http://www.texinfo.org/ (GNU Texinfo).
-->
<!-- Created by GNU Texinfo 6.7, 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" rel="start" title="Top" />
<link href="Index.html" rel="index" title="Index" />
<link href="index.html#SEC_Contents" rel="contents" title="Table of Contents" />
<link href="Data-Structures.html" rel="up" title="Data Structures" />
<link href="Copying-This-Manual.html" rel="next" title="Copying This Manual" />
<link href="Grids.html" rel="prev" title="Grids" />
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.indentedblock {margin-right: 0em}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.lisp {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}
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">
<span id="Path-Finding"></span><div class="header">
<p>
Previous: <a href="Grids.html" accesskey="p" rel="prev">Grids</a>, Up: <a href="Data-Structures.html" accesskey="u" rel="up">Data Structures</a> [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Index.html" title="Index" rel="index">Index</a>]</p>
</div>
<hr />
<span id="Path-Finding-1"></span><h4 class="subsection">5.6.6 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’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
<code>(chickadee data 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="lisp">
<pre class="lisp"><span class="syntax-open">(</span><span class="syntax-special">define</span> <span class="syntax-symbol">world-map</span>
<span class="syntax-symbol">'</span><span class="syntax-open">(</span><span class="syntax-open">(</span><span class="syntax-symbol">town-common</span> <span class="syntax-symbol">.</span> <span class="syntax-open">(</span><span class="syntax-symbol">town-hall</span> <span class="syntax-special">library</span><span class="syntax-close">)</span><span class="syntax-close">)</span>
<span class="syntax-open">(</span><span class="syntax-symbol">town-hall</span> <span class="syntax-symbol">.</span> <span class="syntax-open">(</span><span class="syntax-symbol">town-common</span> <span class="syntax-symbol">school</span><span class="syntax-close">)</span><span class="syntax-close">)</span>
<span class="syntax-open">(</span><span class="syntax-special">library</span> <span class="syntax-symbol">.</span> <span class="syntax-open">(</span><span class="syntax-symbol">town-common</span> <span class="syntax-symbol">cafe</span><span class="syntax-close">)</span><span class="syntax-close">)</span>
<span class="syntax-open">(</span><span class="syntax-symbol">school</span> <span class="syntax-symbol">.</span> <span class="syntax-open">(</span><span class="syntax-symbol">town-hall</span> <span class="syntax-symbol">cafe</span><span class="syntax-close">)</span><span class="syntax-close">)</span>
<span class="syntax-open">(</span><span class="syntax-symbol">cafe</span> <span class="syntax-symbol">.</span> <span class="syntax-open">(</span><span class="syntax-special">library</span> <span class="syntax-symbol">school</span><span class="syntax-close">)</span><span class="syntax-close">)</span><span class="syntax-close">)</span><span class="syntax-close">)</span>
<span class="syntax-open">(</span><span class="syntax-special">define</span> <span class="syntax-open">(</span><span class="syntax-symbol">neighbors</span> <span class="syntax-symbol">building</span><span class="syntax-close">)</span>
<span class="syntax-open">(</span><span class="syntax-symbol">assq-ref</span> <span class="syntax-symbol">town-map</span> <span class="syntax-symbol">building</span><span class="syntax-close">)</span><span class="syntax-close">)</span>
<span class="syntax-open">(</span><span class="syntax-special">define</span> <span class="syntax-open">(</span><span class="syntax-symbol">cost</span> <span class="syntax-symbol">a</span> <span class="syntax-symbol">b</span><span class="syntax-close">)</span> <span class="syntax-symbol">1</span><span class="syntax-close">)</span>
<span class="syntax-open">(</span><span class="syntax-special">define</span> <span class="syntax-open">(</span><span class="syntax-symbol">distance</span> <span class="syntax-symbol">a</span> <span class="syntax-symbol">b</span><span class="syntax-close">)</span> <span class="syntax-symbol">1</span><span class="syntax-close">)</span>
<span class="syntax-open">(</span><span class="syntax-special">define</span> <span class="syntax-symbol">pf</span> <span class="syntax-open">(</span><span class="syntax-symbol">make-path-finder</span><span class="syntax-close">)</span><span class="syntax-close">)</span>
<span class="syntax-open">(</span><span class="syntax-symbol">a*</span> <span class="syntax-symbol">pf</span> <span class="syntax-symbol">'town-common</span> <span class="syntax-symbol">'school</span> <span class="syntax-symbol">neighbors</span> <span class="syntax-symbol">cost</span> <span class="syntax-symbol">distance</span><span class="syntax-close">)</span>
</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’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 id="index-make_002dpath_002dfinder">Procedure: <strong>make-path-finder</strong></dt>
<dd><p>Return a new path finder object.
</p></dd></dl>
<dl>
<dt id="index-path_002dfinder_003f">Procedure: <strong>path-finder?</strong> <em>obj</em></dt>
<dd><p>Return <code>#t</code> if <var>obj</var> is a path finder.
</p></dd></dl>
<dl>
<dt id="index-a_002a">Procedure: <strong>a*</strong> <em>path-finder start goal neighbors cost distance</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="Grids.html" accesskey="p" rel="prev">Grids</a>, Up: <a href="Data-Structures.html" accesskey="u" rel="up">Data Structures</a> [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Index.html" title="Index" rel="index">Index</a>]</p>
</div>
</body>
</html>
|
