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 200</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-ivar">@positions</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>