class Node
    attr_accessor :predecessor,:f,:g,:h,:id,:x,:y
 
    def initialize(id,x,y)
        @id,@x,@y = id,x,y
        f = g = h = 0
        @predecessor = nil
    end
end
 
class Edge
    attr_accessor :to,:cost
    def initialize(to,cost)
        @to,@cost = to, cost
    end
end
 
class Graph
    def initialize
        @nodes = []
        @adjacency = {}
    end
 
    def add_node( id, x, y )
        @nodes.push Node.new( id, x, y )
        @adjacency[id] = []
    end
 
    def get_node( id )
        @nodes[@nodes.index {|node| node.id == id }]
    end
 
    def add_edge( from, to, cost )
        @adjacency[from] ||= []
        @adjacency[from] += [Edge.new( get_node( to ), cost )]
    end
 
    def get_neighbors( id )
        @adjacency[id]
    end
 
    def heuristic_function( current_node, end_node )
        x_distance = (current_node.x - end_node.x).abs
        y_distance = (current_node.y - end_node.y).abs
 
        if x_distance > y_distance
            return 14 * y_distance + 10 * (x_distance - y_distance)
        else
            return 14 * x_distance + 10 * (y_distance - x_distance)
        end
    end
 
    def lowest_f( set )
        lowest = nil
        set.each do |node|
            if ( !lowest || lowest.f > node.f )
                lowest = node 
            end
        end
        lowest
    end
 
    def update_neighbors ( node , end_node)
        get_neighbors( node.id ).map! do | neighbor |
            neighbor.to.g = node.g + neighbor.cost
            neighbor.to.h = heuristic_function( neighbor.to , end_node )
            neighbor.to.f = neighbor.to.g + neighbor.to.h
        end
    end
 
    def AStar( id_origin, id_end )
        origin_node = get_node id_origin
        end_node = get_node id_end
        closed_set = []
        open_set = []
 
        g_value = 0
        origin_node.g = 0
        origin_node.f = origin_node.g + heuristic_function( origin_node, end_node )
 
        open_set.push origin_node
        current = nil
 
        while open_set.empty? == false
            prev_current = current if current != origin_node
            current = lowest_f open_set
 
            current.predecessor = prev_current
            open_set.delete current
            closed_set.push current
 
            if current == end_node
                return reconstruct_path current
            end
 
            update_neighbors current, end_node
 
            get_neighbors( current.id ).each do | neighbor |
                open_set.push(neighbor)
            end
 
        end
    end
 
 
    def reconstruct_path ( node )
        path = []
        while ( node )
            path.push node
            node = node.predecessor
        end
        path
    end
end
 
g = Graph.new
g.add_node( "La asuncion", 15,15 )
g.add_node( "Los robles", 15,10 )
g.add_node( "Manzanillo", 16,17 )
g.add_edge( "Los robles", "Manzanillo", 3 )
g.add_edge( "La asuncion", "Los robles", 2 )
 
p g.AStar("La asuncion", "Manzanillo")

Y2xhc3MgTm9kZQogICAgYXR0cl9hY2Nlc3NvciA6cHJlZGVjZXNzb3IsOmYsOmcsOmgsOmlkLDp4LDp5CiAgICAKICAgIGRlZiBpbml0aWFsaXplKGlkLHgseSkKICAgICAgICBAaWQsQHgsQHkgPSBpZCx4LHkKICAgICAgICBmID0gZyA9IGggPSAwCiAgICAgICAgQHByZWRlY2Vzc29yID0gbmlsCiAgICBlbmQKZW5kCgpjbGFzcyBFZGdlCiAgICBhdHRyX2FjY2Vzc29yIDp0byw6Y29zdAogICAgZGVmIGluaXRpYWxpemUodG8sY29zdCkKICAgICAgICBAdG8sQGNvc3QgPSB0bywgY29zdAogICAgZW5kCmVuZAoKY2xhc3MgR3JhcGgKICAgIGRlZiBpbml0aWFsaXplCiAgICAgICAgQG5vZGVzID0gW10KICAgICAgICBAYWRqYWNlbmN5ID0ge30KICAgIGVuZAogICAgCiAgICBkZWYgYWRkX25vZGUoIGlkLCB4LCB5ICkKICAgICAgICBAbm9kZXMucHVzaCBOb2RlLm5ldyggaWQsIHgsIHkgKQogICAgICAgIEBhZGphY2VuY3lbaWRdID0gW10KICAgIGVuZAogICAgCiAgICBkZWYgZ2V0X25vZGUoIGlkICkKICAgICAgICBAbm9kZXNbQG5vZGVzLmluZGV4IHt8bm9kZXwgbm9kZS5pZCA9PSBpZCB9XQogICAgZW5kCiAgICAKICAgIGRlZiBhZGRfZWRnZSggZnJvbSwgdG8sIGNvc3QgKQogICAgICAgIEBhZGphY2VuY3lbZnJvbV0gfHw9IFtdCiAgICAgICAgQGFkamFjZW5jeVtmcm9tXSArPSBbRWRnZS5uZXcoIGdldF9ub2RlKCB0byApLCBjb3N0ICldCiAgICBlbmQKICAgIAogICAgZGVmIGdldF9uZWlnaGJvcnMoIGlkICkKICAgICAgICBAYWRqYWNlbmN5W2lkXQogICAgZW5kCiAgICAKICAgIGRlZiBoZXVyaXN0aWNfZnVuY3Rpb24oIGN1cnJlbnRfbm9kZSwgZW5kX25vZGUgKQogICAgICAgIHhfZGlzdGFuY2UgPSAoY3VycmVudF9ub2RlLnggLSBlbmRfbm9kZS54KS5hYnMKICAgICAgICB5X2Rpc3RhbmNlID0gKGN1cnJlbnRfbm9kZS55IC0gZW5kX25vZGUueSkuYWJzCiAgICAgICAgCiAgICAgICAgaWYgeF9kaXN0YW5jZSA+IHlfZGlzdGFuY2UKICAgICAgICAgICAgcmV0dXJuIDE0ICogeV9kaXN0YW5jZSArIDEwICogKHhfZGlzdGFuY2UgLSB5X2Rpc3RhbmNlKQogICAgICAgIGVsc2UKICAgICAgICAgICAgcmV0dXJuIDE0ICogeF9kaXN0YW5jZSArIDEwICogKHlfZGlzdGFuY2UgLSB4X2Rpc3RhbmNlKQogICAgICAgIGVuZAogICAgZW5kCiAgICAKICAgIGRlZiBsb3dlc3RfZiggc2V0ICkKICAgICAgICBsb3dlc3QgPSBuaWwKICAgICAgICBzZXQuZWFjaCBkbyB8bm9kZXwKICAgICAgICAgICAgaWYgKCAhbG93ZXN0IHx8IGxvd2VzdC5mID4gbm9kZS5mICkKICAgICAgICAgICAgICAgIGxvd2VzdCA9IG5vZGUgCiAgICAgICAgICAgIGVuZAogICAgICAgIGVuZAogICAgICAgIGxvd2VzdAogICAgZW5kCiAgICAKICAgIGRlZiB1cGRhdGVfbmVpZ2hib3JzICggbm9kZSAsIGVuZF9ub2RlKQogICAgICAgIGdldF9uZWlnaGJvcnMoIG5vZGUuaWQgKS5tYXAhIGRvIHwgbmVpZ2hib3IgfAogICAgICAgICAgICBuZWlnaGJvci50by5nID0gbm9kZS5nICsgbmVpZ2hib3IuY29zdAogICAgICAgICAgICBuZWlnaGJvci50by5oID0gaGV1cmlzdGljX2Z1bmN0aW9uKCBuZWlnaGJvci50byAsIGVuZF9ub2RlICkKICAgICAgICAgICAgbmVpZ2hib3IudG8uZiA9IG5laWdoYm9yLnRvLmcgKyBuZWlnaGJvci50by5oCiAgICAgICAgZW5kCiAgICBlbmQKICAgIAogICAgZGVmIEFTdGFyKCBpZF9vcmlnaW4sIGlkX2VuZCApCiAgICAgICAgb3JpZ2luX25vZGUgPSBnZXRfbm9kZSBpZF9vcmlnaW4KICAgICAgICBlbmRfbm9kZSA9IGdldF9ub2RlIGlkX2VuZAogICAgICAgIGNsb3NlZF9zZXQgPSBbXQogICAgICAgIG9wZW5fc2V0ID0gW10KICAgICAgICAKICAgICAgICBnX3ZhbHVlID0gMAogICAgICAgIG9yaWdpbl9ub2RlLmcgPSAwCiAgICAgICAgb3JpZ2luX25vZGUuZiA9IG9yaWdpbl9ub2RlLmcgKyBoZXVyaXN0aWNfZnVuY3Rpb24oIG9yaWdpbl9ub2RlLCBlbmRfbm9kZSApCiAgICAgICAgCiAgICAgICAgb3Blbl9zZXQucHVzaCBvcmlnaW5fbm9kZQogICAgICAgIGN1cnJlbnQgPSBuaWwKICAgICAgICAKICAgICAgICB3aGlsZSBvcGVuX3NldC5lbXB0eT8gPT0gZmFsc2UKICAgICAgICAgICAgcHJldl9jdXJyZW50ID0gY3VycmVudCBpZiBjdXJyZW50ICE9IG9yaWdpbl9ub2RlCiAgICAgICAgICAgIGN1cnJlbnQgPSBsb3dlc3RfZiBvcGVuX3NldAogICAgICAgICAgICAKICAgICAgICAgICAgY3VycmVudC5wcmVkZWNlc3NvciA9IHByZXZfY3VycmVudAogICAgICAgICAgICBvcGVuX3NldC5kZWxldGUgY3VycmVudAogICAgICAgICAgICBjbG9zZWRfc2V0LnB1c2ggY3VycmVudAogICAgICAgICAgICAKICAgICAgICAgICAgaWYgY3VycmVudCA9PSBlbmRfbm9kZQogICAgICAgICAgICAgICAgcmV0dXJuIHJlY29uc3RydWN0X3BhdGggY3VycmVudAogICAgICAgICAgICBlbmQKICAgICAgICAgICAgCiAgICAgICAgICAgIHVwZGF0ZV9uZWlnaGJvcnMgY3VycmVudCwgZW5kX25vZGUKICAgICAgICAgICAgCiAgICAgICAgICAgIGdldF9uZWlnaGJvcnMoIGN1cnJlbnQuaWQgKS5lYWNoIGRvIHwgbmVpZ2hib3IgfAogICAgICAgICAgICAgICAgb3Blbl9zZXQucHVzaChuZWlnaGJvcikKICAgICAgICAgICAgZW5kCiAgICAgICAgICAgIAogICAgICAgIGVuZAogICAgZW5kCiAgICAKICAgICAgICAKICAgIGRlZiByZWNvbnN0cnVjdF9wYXRoICggbm9kZSApCiAgICAgICAgcGF0aCA9IFtdCiAgICAgICAgd2hpbGUgKCBub2RlICkKICAgICAgICAgICAgcGF0aC5wdXNoIG5vZGUKICAgICAgICAgICAgbm9kZSA9IG5vZGUucHJlZGVjZXNzb3IKICAgICAgICBlbmQKICAgICAgICBwYXRoCiAgICBlbmQKZW5kCgpnID0gR3JhcGgubmV3CmcuYWRkX25vZGUoICJMYSBhc3VuY2lvbiIsIDE1LDE1ICkKZy5hZGRfbm9kZSggIkxvcyByb2JsZXMiLCAxNSwxMCApCmcuYWRkX25vZGUoICJNYW56YW5pbGxvIiwgMTYsMTcgKQpnLmFkZF9lZGdlKCAiTG9zIHJvYmxlcyIsICJNYW56YW5pbGxvIiwgMyApCmcuYWRkX2VkZ2UoICJMYSBhc3VuY2lvbiIsICJMb3Mgcm9ibGVzIiwgMiApCgpwIGcuQVN0YXIoIkxhIGFzdW5jaW9uIiwgIk1hbnphbmlsbG8iKQ==