def a_search(kaart, goal):
    path = []
    frontier = PriorityQueue()
    nei = []
    frontier.put((heuristic(start, goal), start))
    came_from = {}
    came_from[start] = None
    rows = len(kaart)
    columns = len(kaart[0])
    old = None
    visited = []
    flagM = 0
    cost_so_far = {}
    cost_so_far[start] = 0
    flag = True


    while not frontier.empty():

        if len(nei) > 1:
            if flag is True:
                flag = False
                a = nei[0]
                frontier.put(nei[1])
            else:
                flag = True
                a = nei[1]
                frontier.put(nei[0])
        elif len(nei) == 1:
            a = nei[0]
        else:
            a = frontier.get()
        nei.clear()
        current = a[1]
        prio = a[0]
        print("Start = " + str(current))
        if current[0] - 1 >= 0 and kaart[current[0] - 1][current[1]] != "*" and (current[0] - 1, current[1]) not in came_from.keys():
            next = (current[0] - 1, current[1])
            came_from[(current[0] - 1, current[1])] = current
            flagM += 1
            new_cost = cost_so_far[current] + 1
            if next not in cost_so_far or new_cost < cost_so_far[next]:
                cost_so_far[next] = new_cost
                priority = new_cost + heuristic(next, goal)  # g(n) + h(n)
                came_from[next] = current
                print(str(priority) + "    " + str(next))
                if prio == priority:
                    nei.append((priority, next))
                else:
                    frontier.put((priority, next))
        if current[0] + 1 < rows and kaart[current[0] + 1][current[1]] != "*" and (current[0] + 1, current[1]) not in came_from.keys():
            next = (current[0] + 1, current[1])
            came_from[(current[0] + 1, current[1])] = current
            flagM += 1
            new_cost = cost_so_far[current] + 1
            if next not in cost_so_far or new_cost < cost_so_far[next]:
                cost_so_far[next] = new_cost
                priority = new_cost + heuristic(next, goal)  # g(n) + h(n)
                came_from[next] = current
                if prio == priority:
                    nei.append((priority, next))
                else:
                    frontier.put((priority, next))


            print(str(priority) + "    " + str(next))
        if current[1] + 1 < columns and kaart[current[0]][current[1] + 1] != "*" and (current[0], current[1] + 1) not in came_from.keys():
            next = (current[0], current[1] + 1)
            came_from[(current[0], current[1] + 1)] = current
            flagM += 1
            new_cost = cost_so_far[current] + 1
            if next not in cost_so_far or new_cost < cost_so_far[next]:
                cost_so_far[next] = new_cost
                priority = new_cost + heuristic(next, goal)  # g(n) + h(n)
                came_from[next] = current
                if prio == priority:
                    nei.append((priority, next))
                else:
                    frontier.put((priority, next))
            print(str(priority) + "    " + str(next))
        if current[1] - 1 >= 0 and kaart[current[0]][current[1] - 1] != "*" and (current[0], current[1] - 1) not in came_from.keys():
            next = (current[0], current[1] - 1)
            came_from[(current[0], current[1] - 1)] = current
            flagM += 1
            new_cost = cost_so_far[current] + 1
            if next not in cost_so_far or new_cost < cost_so_far[next]:
                cost_so_far[next] = new_cost
                priority = new_cost + heuristic(next, goal)  # g(n) + h(n)
                came_from[next] = current
                if prio == priority:
                    nei.append((priority, next))
                else:
                    frontier.put((priority, next))
            print(str(priority) + "    " + str(next))
        if current not in came_from.keys():
            came_from[current] = old
        if kaart[current[0]][current[1]] == "D":
            break
        visited.append(current)
        old = current



    x = goal
    while x != start:
        path.append(x)
        x = came_from[x]
    path.append(start)
    return path