3
\$\begingroup\$

I am attempting to write up a program in Python that will find the shortest path between two nodes in 3D space. The actual domain is the EVE-Online Universe, which is composed of systems connected by stargates.

The input to my program is a list of systems, represented as Python dicts (JSON). I am trying to use the physical 3D distance as well as an incrementing step-cost as my two heuristics.

from math import sqrt
from Queue import PriorityQueue

class Universe(object):
    def __init__(self, systems):
        self._id_to_system = {system["system_id"]: system for system in systems}
        self._name_to_system = {system["name"]: system for system in systems}

    @property
    def num_systems(self):
        return len(self._id_to_system)

    def __getitem__(self, key):
        if key in self._id_to_system:
            return self._id_to_system[key]
        elif key in self._name_to_system:
            return self._name_to_system[key]
        else:
            raise KeyError("No system with a name or id equal to {}".format(key))

def distance(a, b):
    """ Returns straight-line distance in AUs between two systems """
    a_pos = a["position"]
    b_pos = b["position"]

    x_dist = b_pos["x"] - a_pos["x"]
    y_dist = b_pos["y"] - b_pos["y"]
    z_dist = b_pos["z"] - b_pos["z"]

    distance = sqrt((x_dist)*(x_dist) + (y_dist)*(y_dist) + (z_dist)*(z_dist))
    # Convert from meters to AUs before returning - helps keep this number reasonable
    return distance / 1.496e+11


class SystemNode(object):
    """ Used to represent a system inside the open and closed sets """
    def __init__(self, system, parent, step_cost):
        self.system = system
        self.parent = parent
        self.step_cost = step_cost


def find_stargate_route(universe, start_system, end_system, step_cost=10):

    # Create open and closed sets
    frontier_nodes = PriorityQueue(universe.num_systems)
    closed_system_ids = {}

    # Add starting system to frontier
    start_node = SystemNode(start_system, None, 0)
    frontier_nodes.put((0, start_node))

    while not frontier_nodes.empty():
        # Grab the node with the lowest cost
        current_node = frontier_nodes.get(False)[1]

        # Check if we have found our goal
        if current_node.system == end_system:
            print("Found Route to {}".format(end_system["name"]))
            break

        # Calculate next node step cost
        next_step_cost = current_node.step_cost + step_cost

        # Add each output system if we haven't seen it yet
        for system_id in (
            stargate["destination"]["system_id"] for stargate in current_node.system["stargates"]
        ):
            system = universe[system_id]
            system_node = SystemNode(system, current_node, next_step_cost)

            # Check if system is in our closed list
            if system_id in closed_system_ids:
                continue

            # Add to our frontier with priority=step_cost + distance
            total_cost = distance(system, end_system) + next_step_cost
            frontier_nodes.put((total_cost, system_node))

        # Add the current node to the closed set            
        closed_system_ids[current_node.system["system_id"]] = current_node

    if current_node.system != end_system:
        return None
    else:
        # Return a list of systems from start to end
        route = []
        while current_node != None:
            route.insert(0, current_node.system)
            current_node = current_node.parent
        return route

And then a little program to run it...

A jsonl.gz file with all of the systems is available in this gitlab snippet (see the attached file - "combined_systems.jsonl.gz")

import gzip
import json

with gzip.open("combined_systems.jsonl.gz", 'rb') as gzfp:
    systems = [json.loads(line) for line in gzfp]


start_name = "Amarr"
end_name = "Jita"

universe = Universe(systems)

route = find_stargate_route(
    universe, universe[start_name], universe[end_name]
)

print(len(route))

Any suggestions? This was meant more as a coding exercise to help me grasp the A-star algorithm, so any pointers are much appreciated :)

EDIT: Removed the dependency on PrioritySet - it works the same with Queue.PriorityQueue. Also added my Universe class (basically just getters for the different systems). Also added a link to the jsonl.gz file containing all of the systems, see the gitlab link.

\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! For what Python version did you write this and does it work correctly? \$\endgroup\$ – Mast Jul 14 '18 at 8:09
  • 2
    \$\begingroup\$ To make it easier to reproduce, could you add your imports? Currently PrioritySet (and Universe) are undefined. \$\endgroup\$ – Graipher Jul 14 '18 at 8:22
  • 1
    \$\begingroup\$ @Mast - It is in python2.7 and yes! It works correctly and finds routes, although I'm not too sure if they are the best routes out there \$\endgroup\$ – wKavey Jul 14 '18 at 15:42
  • 1
    \$\begingroup\$ @Graipher - Added the Universe dependency, and removed my custom PrioritySet - it was basically just a PriorityQueue with some extra stuff thrown around. The above code should work now \$\endgroup\$ – wKavey Jul 14 '18 at 15:43
2
\$\begingroup\$

Let's start with the distance function.

distance = sqrt((x_dist)*(x_dist) + (y_dist)*(y_dist) + (z_dist)*(z_dist)) is how you would probably write it in C++, in Python there exists a more readable way using the ** operator:

distance = sqrt(x_dist**2 + y_dist**2 + z_dist**2)

It is not even slower than doing the multiplication yourself:

In []: %timeit 123456789123456789123456789**2
12.4 ns ± 0.184 ns per loop (mean ± std. dev. of 7 runs, 100000000 loops each)

In []: %timeit 123456789123456789123456789*123456789123456789123456789
12.5 ns ± 0.199 ns per loop (mean ± std. dev. of 7 runs, 100000000 loops each)

You also have a bug in that function:

y_dist = b_pos["y"] - b_pos["y"]
z_dist = b_pos["z"] - b_pos["z"]

So your distance only takes into account the distance in x. In y and z it is always zero.

1.496e+11 is a magic number. You should save it as a constant on the module level: METER_PER_AU = 1.496e+11.


In find_stargate_route, at the end when you have found the target system, you create the route to it. You do that using this code:

route = []
while current_node != None:
    route.insert(0, current_node.system)
    current_node = current_node.parent
return route

This has a bad runtime, because list.insert has a worst case runtime of \$\mathcal{O}(n)\$. Instead either use a data structure that supports appending on the left (like collections.deque), or just build the path using list.append and return list(reversed(route)) at the end.

You should also not compare to None using == or !=, instead use is and is not.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the suggestions - can't believe I missed the distance function calculations (it explains why I was getting a sub-optimal route). \$\endgroup\$ – wKavey Jul 14 '18 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.