doc/classes/Board.src/M000027.html

   1 <?xml version="1.0" encoding="iso-8859-1"?>
   2 <!DOCTYPE html
   3      PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
   4      "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
   5
   6 <html>
   7 <head>
   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" />
  11 </head>
  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>
  45 </body>
  46 </html>