# A-Star Search with 3D Universe

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.

• Welcome to Code Review! For what Python version did you write this and does it work correctly? – Mast Jul 14 '18 at 8:09
• To make it easier to reproduce, could you add your imports? Currently PrioritySet (and Universe) are undefined. – Graipher Jul 14 '18 at 8:22
• @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 – wKavey Jul 14 '18 at 15:42
• @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 – wKavey Jul 14 '18 at 15:43

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.

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