# File lib/libttc.rb, line 200
  def cache_valid_moves
    # A hash of arrays.  The has key is the name of a positions.  The array 
    #  element [i] stores the positions that are i spaces from here
    @valid_moves = Hash.new
    # A hash of hashes.  Given two names, return the shortest distance between
    #  the two locations
    @distance_between = Hash.new
    @positions.each do |place, position|
      @valid_moves[place] = Array.new
      @distance_between[place] = Hash.new
      @valid_moves[place][0] = [@positions[place]]
      @distance_between[place][place] = 0
      # Find the shortest routes by Dijkstra's algorithm
      agenda = [position]
      closed_list = [position]
      i = 1
      while not agenda.empty?
        @valid_moves[place][i] = []
        new_agenda = []
        agenda.each do |pos|
          valid_extensions = pos.neighbours.reject {|new_position| closed_list.include?(new_position) }
          @valid_moves[place][i] += valid_extensions
          valid_extensions.each {|ext| @distance_between[place][ext.place] ||= i }
          closed_list += valid_extensions
          new_agenda += valid_extensions
        end
        agenda = new_agenda
        i += 1
      end
    end
  end