5
\$\begingroup\$

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

Read 'A Journey of a Thousand Li Starts Beneath One’s Feet'.

Read 'Community Policies'

\$\endgroup\$
  • \$\begingroup\$ In some challenge sites (hacker rank) the timeout period is defined greater for Python, simply because its comparably slower than C/C++ or Java. If not, I would simply switch to C++, which would allow far more complex algorithms. \$\endgroup\$ – Gürkan Çetin Dec 30 '17 at 15:16
  • \$\begingroup\$ The problem is I'm not as comfortable (if at all) with C++ or Java as I have limited knowledge of it \$\endgroup\$ – Epic Boss Dec 30 '17 at 22:25
  • \$\begingroup\$ That’s fair. But as long as you don’t deal with strings (C++ has some weird features related to strings), and do arithmetics and array manipulations, c/c++ or java are quite practical. and there’s always google (and stack overflow) to help whenever you are in trouble. :) btw, I’ve seen the website, quite an interesting challenge. \$\endgroup\$ – Gürkan Çetin Dec 30 '17 at 22:33
  • \$\begingroup\$ The problem is I looked at C++ (as I know more of it than Java) and instantly I realised it was beyond me lol. \$\endgroup\$ – Epic Boss Dec 31 '17 at 9:39

Your Answer

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

Browse other questions tagged or ask your own question.