Evehelper.rb

# Copyright Lisa Seelye (2006-2009) 
# lisa@thedoh.com
# Not for commercial use without prior permission.

module float32
  def float32.float32(o1,o2)
    Math.sqrt( (o1.x - o2.x) ** 2 + (o1.y - o2.y) ** 2 + (o1.z - o2.z) ** 2)
  end
end

Pathfind.rb

# Copyright Lisa Seelye (2006-2009) 
# lisa@thedoh.com
# Not for commercial use without prior permission.


class Array
  def is_system_node(systemNode)
    Proc.new { |h| h.system.id == systemNode.system.id } 
  end

  def find_system(systemNode)
    return nil if self.empty? || systemNode.nil?
    self.find(&is_system_node(systemNode))
  end

  def has_system?(systemNode)
    return false if self.empty? || systemNode.nil?
    self.any?(&is_system_node(systemNode))
  end

  def delete_system!(systemNode)
    return if self.empty? || systemNode.nil?
    self.delete(self.find(&is_system_node(systemNode)))
  end

  def peek
    self.last
  end
end

class PathObject
  
  attr_accessor :system, :parent, :f, :src_stargate, :dest_stargate, :parent_size

  public

  def initialize(system,parent,src,dest,doscore=true,srcgate=nil,destgate=nil)
    @system = system
    @parent = parent
    @src_stargate = srcgate
    @dest_stargate = destgate
    @f = 5e+20
    @parent_size = 0
    @f = score(srcgate,destgate) if doscore && srcgate && destgate
  end

  def <=>(comp)
    comp.f <=> @f # <=> @f
  end

  def score(src,dest)
    unless src && dest
      @f = 0
      return
    end

    factor = (@system.security < 0.5) ? 2 : 1
    @f = (h(dest) + g(src)) * factor
  end

  def h(dest)
#    return 0.0 # djikstra
    tscore = 1
    if @system.connects_to_region?(dest.system.region_id)
      tscore = 0.90
    elsif @system.connects_to_constellation?(dest.system.constellation_id)
      tscore = 0.45
    elsif @system.constellation_id == dest.system.constellation_id
      tscore = 0.35
    elsif @system.region_id == dest.system.region_id
      tscore = 0.50
    end
      
    tscore * Distance.distance(@src_stargate,dest)
  end

  def g(src)
    sum = 0.0
    parent = self.parent
    while ( ! parent.eql?(nil) )
      @parent_size += 1
      sum += parent.f
      parent = parent.parent
    end
    sum + Distance.distance(@dest_stargate,src)
  end

end

module Pathfind
  require 'EveHelper'

  # Find quickest path from system s1 to system s2
  # Returns an array with the path starting at s1 at position 0 and s2 in the
  # last position
  def Pathfind.pathfind(src,dest,options = {})
    $checked_sys = 0
    closed = Array.new   # do not search
    open   = Array.new   # to search list
    path   = Array.new   # holds a list of System objects in order

    root = PathObject.new(src,nil,src,dest,false,src.stargates[0],src.stargates[0])
    final = PathObject.new(dest,nil,src,dest,false,dest.stargates[0],dest.stargates[0])

    open.push(root)

    if options.has_key?('ignore')
      options['ignore'].each do |ignoresys|
        closed.push(PathObject.new(ignoresys,nil,src,dest)) unless ignoresys.id == dest.id # skip some nodes except dest
      end
    end
    

    i = 0 
    # While there are nodes to consider do some work
    while (open.size > 0)
      i+= 1
      
      currentNode = open.pop                  # Get the node with the lowest score
      next if closed.include?(currentNode.system.id) # Skip the this node if it's already been considered
      
      # Check to see if this is the right node.
      if ( currentNode.system.id == final.system.id )
        # We have found our way
        while (! currentNode.eql?(nil) )
          # Reverse the result list
          path.push(currentNode.system)
          currentNode = currentNode.parent
        end  
        return path.reverse
      end # End check if final


      # If currentNode isn't the final node (above test) then add it to the
      # closed list and examine its neighbouring systems
      closed.push(currentNode.system.id)
      
      currentNode.system.cached_stargates.each do |stargate| 
        $checked_sys += 1
        neighbourNode = PathObject.new(System.cached_get(stargate.to_system_id),
                                       currentNode,
                                       src,
                                       dest,
                                       true,
                                       stargate,
                                       dest.stargates[0])
        
        next if closed.include?(neighbourNode.system.id) #If we have seen this system then skip it

        # Havent seen this node so add it to the list to consder
        # But first check to see if this node is better than another node
        queuedNode = open.find_system(neighbourNode)
        if (! queuedNode.nil? && neighbourNode.f < queuedNode.f)
          open.delete_system!(queuedNode)
        end
        open.push(neighbourNode)
      end # End processing successor nodes
      open.sort!

    end # End while
    [] # No path
  end

  # src - System to start from
  # n - number of jumps away from src
  # options - hash of options. valid pairs:
  #  security => [ Ignore systems with security below this number (float) ],
  #  ignoresrc => [ Ignore starting system (bool)) ], default = false
  #  ignore => [ List of Systems to explicitly ignore (Array) ], default = []
  #  only_constellation => [ Only consider systems in Src's constellation (bool) ], default = false
  #  only_region => [ Only consider systems in Src's region (bool) ],  default = false
  def Pathfind.systems_n_jumps_away(src,n=0,options={})
    ret = Array.new
    return ret unless n > 0 && src

    open = Array.new
    closed = Array.new
    open.push(PathObject.new(src,nil,nil,nil))
    ret << src unless options.has_key?('ignoresrc') && options['ignoresrc']

    if options.has_key?('ignore')
      options['ignore'].each do |ignoresys|
        closed.push ignoresys.id
      end
    end

    only_constellation = options.has_key?('only_constellation') ? options['only_constellation'] : false
    only_region = options.has_key?('only_region') ? options['only_region'] : false

    j = 0 # jumps away from src
    while ( ! open.empty? )
      j += 1
      currentNode = open.pop
      closed.push(currentNode)
      currentNode.system.stargates.find(:all, :include => [ :dest_system ]).each do |jump|
        neighbourNode = PathObject.new(jump.dest_system,currentNode,nil,nil,false)
        next if options.has_key?('minsec') && options['minsec'] > neighbourNode.system.security #low sec
        next if closed.has_system?(neighbourNode) #ignored system
        next if open.has_system?(neighbourNode)   #already in list
        next if (src.constellation_id != jump.dest_system.constellation_id) && only_constellation
        next if (src.region_id != jump.dest_system.region_id) && only_region

        if j <= n
          open.push(neighbourNode)
        end
        ret << neighbourNode.system
      end
    end
    ret
  end


end