trjhtr

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.

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 $mathcalO(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.