1 <?xml version=
"1.0" encoding=
"iso-8859-1"?>
3 PUBLIC
"-//W3C//DTD XHTML 1.0 Transitional//EN"
4 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
8 <title>cache_valid_moves (Board)
</title>
9 <meta http-equiv=
"Content-Type" content=
"text/html; charset=iso-8859-1" />
10 <link rel=
"stylesheet" href=
"../.././rdoc-style.css" type=
"text/css" media=
"screen" />
12 <body class=
"standalone-code">
13 <pre><span class=
"ruby-comment cmt"># File lib/libttc.rb, line
191</span>
14 <span class=
"ruby-keyword kw">def
</span> <span class=
"ruby-identifier">cache_valid_moves
</span>
15 <span class=
"ruby-comment cmt"># A hash of arrays. The has key is the name of a positions. The array
</span>
16 <span class=
"ruby-comment cmt"># element [i] stores the positions that are i spaces from here
</span>
17 <span class=
"ruby-ivar">@valid_moves
</span> =
<span class=
"ruby-constant">Hash
</span>.
<span class=
"ruby-identifier">new
</span>
18 <span class=
"ruby-comment cmt"># A hash of hashes. Given two names, return the shortest distance between
</span>
19 <span class=
"ruby-comment cmt"># the two locations
</span>
20 <span class=
"ruby-ivar">@distance_between
</span> =
<span class=
"ruby-constant">Hash
</span>.
<span class=
"ruby-identifier">new
</span>
21 <span class=
"ruby-ivar">@positions
</span>.
<span class=
"ruby-identifier">each
</span> <span class=
"ruby-keyword kw">do
</span> <span class=
"ruby-operator">|
</span><span class=
"ruby-identifier">place
</span>,
<span class=
"ruby-identifier">position
</span><span class=
"ruby-operator">|
</span>
22 <span class=
"ruby-ivar">@valid_moves
</span>[
<span class=
"ruby-identifier">place
</span>] =
<span class=
"ruby-constant">Array
</span>.
<span class=
"ruby-identifier">new
</span>
23 <span class=
"ruby-ivar">@distance_between
</span>[
<span class=
"ruby-identifier">place
</span>] =
<span class=
"ruby-constant">Hash
</span>.
<span class=
"ruby-identifier">new
</span>
24 <span class=
"ruby-ivar">@valid_moves
</span>[
<span class=
"ruby-identifier">place
</span>][
<span class=
"ruby-value">0</span>] = [
<span class=
"ruby-identifier">place
</span>]
25 <span class=
"ruby-ivar">@distance_between
</span>[
<span class=
"ruby-identifier">place
</span>][
<span class=
"ruby-identifier">place
</span>] =
<span class=
"ruby-value">0</span>
26 <span class=
"ruby-comment cmt"># Find the shortest routes by Dijkstra's algorithm
</span>
27 <span class=
"ruby-identifier">agenda
</span> = [
<span class=
"ruby-identifier">position
</span>]
28 <span class=
"ruby-identifier">closed_list
</span> = [
<span class=
"ruby-identifier">position
</span>]
29 <span class=
"ruby-identifier">i
</span> =
<span class=
"ruby-value">1</span>
30 <span class=
"ruby-keyword kw">while
</span> <span class=
"ruby-keyword kw">not
</span> <span class=
"ruby-identifier">agenda
</span>.
<span class=
"ruby-identifier">empty?
</span>
31 <span class=
"ruby-ivar">@valid_moves
</span>[
<span class=
"ruby-identifier">place
</span>][
<span class=
"ruby-identifier">i
</span>] = []
32 <span class=
"ruby-identifier">new_agenda
</span> = []
33 <span class=
"ruby-identifier">agenda
</span>.
<span class=
"ruby-identifier">each
</span> <span class=
"ruby-keyword kw">do
</span> <span class=
"ruby-operator">|
</span><span class=
"ruby-identifier">pos
</span><span class=
"ruby-operator">|
</span>
34 <span class=
"ruby-identifier">valid_extensions
</span> =
<span class=
"ruby-identifier">pos
</span>.
<span class=
"ruby-identifier">neighbours
</span>.
<span class=
"ruby-identifier">reject
</span> {
<span class=
"ruby-operator">|
</span><span class=
"ruby-identifier">new_position
</span><span class=
"ruby-operator">|
</span> <span class=
"ruby-identifier">closed_list
</span>.
<span class=
"ruby-identifier">include?
</span>(
<span class=
"ruby-identifier">new_position
</span>) }
35 <span class=
"ruby-ivar">@valid_moves
</span>[
<span class=
"ruby-identifier">place
</span>][
<span class=
"ruby-identifier">i
</span>]
<span class=
"ruby-operator">+=
</span> <span class=
"ruby-identifier">valid_extensions
</span>
36 <span class=
"ruby-identifier">valid_extensions
</span>.
<span class=
"ruby-identifier">each
</span> {
<span class=
"ruby-operator">|
</span><span class=
"ruby-identifier">ext
</span><span class=
"ruby-operator">|
</span> <span class=
"ruby-ivar">@distance_between
</span>[
<span class=
"ruby-identifier">place
</span>][
<span class=
"ruby-identifier">ext
</span>.
<span class=
"ruby-identifier">place
</span>]
<span class=
"ruby-operator">||=
</span> <span class=
"ruby-identifier">i
</span> }
37 <span class=
"ruby-identifier">closed_list
</span> <span class=
"ruby-operator">+=
</span> <span class=
"ruby-identifier">valid_extensions
</span>
38 <span class=
"ruby-identifier">new_agenda
</span> <span class=
"ruby-operator">+=
</span> <span class=
"ruby-identifier">valid_extensions
</span>
39 <span class=
"ruby-keyword kw">end
</span>
40 <span class=
"ruby-identifier">agenda
</span> =
<span class=
"ruby-identifier">new_agenda
</span>
41 <span class=
"ruby-identifier">i
</span> <span class=
"ruby-operator">+=
</span> <span class=
"ruby-value">1</span>
42 <span class=
"ruby-keyword kw">end
</span>
43 <span class=
"ruby-keyword kw">end
</span>
44 <span class=
"ruby-keyword kw">end
</span></pre>