while len(nodes_to_visit) != 0:
        cur = nodes_to_visit[0]
#        print("cur.idx: ",cur.idx)

        if cur.idx == goal_idx:
            path_length = cur.path_length
            break

        nodes_to_visit.pop(0)

        row = cur.idx / w
        col = cur.idx % w

        nbrs[0] = (diag_ok and row > 0 and col > 0) and cur.idx - w - 1 or -1
        nbrs[1] = (row > 0) and cur.idx - w or -1
        nbrs[2] = (diag_ok and row > 0 and col + 1 < w) and cur.idx - w + 1 or -1
        nbrs[3] = (col > 0)  and cur.idx - 1 or -1
        nbrs[4] = (col + 1 < w) and cur.idx + 1 or -1
        nbrs[5] = (diag_ok and row + 1 < h and col > 0) and cur.idx + w - 1 or -1
        nbrs[6] = (row + 1 < h) and cur.idx + w or -1
        nbrs[7] = (diag_ok and row + 1 < h and col + 1 < w) and cur.idx + w + 1 or -1

        # print("nbrs: ",nbrs)
        heuristic_cost = float()

        for i in range(8):
            if nbrs[i] >= 0:
                new_cost = costs[cur.idx] + weights[nbrs[i]]
                if new_cost < costs[nbrs[i]]:
                    if diag_ok:
                        heuristic_cost = linf_norm(nbrs[i] / w, nbrs[i] % w, goal_idx / w, goal_idx % w)
                    else:
                        heuristic_cost = l1_norm(nbrs[i] / w, nbrs[i] % w, goal_idx / w, goal_idx % w)

                    priority = new_cost + heuristic_cost
                    nodes_to_visit.append(Node(nbrs[i], priority, cur.path_length + 1))
                    costs[nbrs[i]] = new_cost
                    paths[nbrs[i]] = cur.idx

#    print(paths)
    path2D = []

    i = goal_idx
    while i != start_idx:
        path2D.append([int(i/w),int(i%w)])
        i = paths[i]
    path2D.append([int(start_idx/w),int(start_idx%w)])

    return path2D