# A* algorithm optimization and implementation

I am implementing the A* algorithm in Python and have successfully completed the task. It works and even spits out the coordinates from the start to the end.

However, I am programming a bot for a game which times out after 2 seconds if no commands are sent. My code just to run takes 2.3 - 2.4 seconds each time and not to mention that moving from coordinate to coordinate is a waste. The game utilises angles and speed to move a ship around. I am baffled as to how I can incorporate my code to the bot to:

1. minimize execution
2. use the coordinates somehow to move the ship.

My code:

class GridWithWeights(SquareGrid):
def __init__(self, width, height):
super().__init__(width, height)
self.weights = {}

def cost(self, from_node, to_node):
x = from_node[0]
y = from_node[1]

results = {(x-1, y+1):14, (x, y+1):10, (x+1, y+1):14,
(x-1, y):10,                (x+1,y):10,
(x-1, y-1):14, (x, y-1):10, (x+1, y-1):14
}

try:
return results[to_node]
except Exception:
return 0

def in_bounds(self, id):
(x, y) = id
return 0 <= x < self.width and 0 <= y < self.height

def passable(self, id):
return id not in self.walls

def neighbors(self, id):
(x, y) = id
results = [(x-1, y+1), (x, y+1), (x+1, y+1),
(x-1, y),                (x+1,y),
(x-1, y-1), (x, y-1), (x+1, y-1)
]
if (x + y) % 2 == 0: results.reverse() # aesthetics
results = filter(self.in_bounds, results)
results = filter(self.passable, results)
return results

import heapq

class PriorityQueue:
def __init__(self):
self.elements = []

def empty(self):
return len(self.elements) == 0

def put(self, item, priority):
heapq.heappush(self.elements, (priority, item))

def get(self):
return heapq.heappop(self.elements)[1]

def reconstruct_path(came_from, start, goal):
current = goal
path = []
while current != start:
path.append(current)
current = came_from[current]
path.append(start) # optional
path.reverse() # optional
return path

def heuristic(a, b):
(x1, y1) = a
(x2, y2) = b
return abs(x1 - x2) + abs(y1 - y2)

def a_star_search(graph, start, goal):

frontier = PriorityQueue()
frontier.put(start, 0)
came_from = {}
cost_so_far = {}
came_from[start] = None
cost_so_far[start] = 0

while not frontier.empty():
current = frontier.get()

if current == goal:
break

for next in graph.neighbors(current):
new_cost = cost_so_far[current] + graph.cost(current, next)
if next not in cost_so_far or new_cost < cost_so_far[next]:
cost_so_far[next] = new_cost
priority = new_cost + heuristic(goal, next)
frontier.put(next, priority)
came_from[next] = current

return came_from, cost_so_far

diagram4 = GridWithWeights(360, 240)
diagram4.walls = [(2,5),(1, 7), (1, 8), (2, 7), (2, 8), (3, 7), (3, 8)]  # Obstructions

start, goal = (141, 42), (54, 190)
came_from, _ = a_star_search(diagram4, start, goal)
print(reconstruct_path(came_from, start=start, goal=goal))


Disclaimer: This is a competition (Halite 2) where the rules are leniant about taking help from outside and even promote creating a new pathfinding function/algorithm