the biggest problem I see is the sort call each step which is O(n log n)

I suggest using the heapq so it will be reduced to O(log n) per insert and pop saving you a factor of n

you will need to add the steps as lists with the sort key (the path["cost"] + computeOffset(path["steps"][-1], end) as first and then the tuple so natural ordering will be used

paths = []
heapq.heappush(paths, [0,{
    "cost": 0,
    "steps": [start]
}]
while True:
    if len(paths) == 0:
        return False
    best = heappop(paths)[1]
    

and to insert:

heapq.heappush(heap, [cost + computeOffset(steps[-1], end),
                      {
                          "cost": cost,
                          "steps": steps
                      })

(I have no idea if I indented this correctly...)

the biggest problem I see is the sort call each step which is O(n log n)

I suggest using the heapq so it will be reduced to O(log n) per insert and pop saving you a factor of n

you will need to add the steps as lists with the sort key (the path["cost"] + computeOffset(path["steps"][-1], end) as first and then the tuple so natural ordering will be used

paths = []
heapq.heappush(paths, [0,{
    "cost": 0,
    "steps": [start]
}]
while True:
    if len(paths) == 0:
        return False
    best = heappop(paths)[1]
    

and to insert:

heapq.heappush(heap, [cost + computeOffset(steps[-1], end),
                      {
                          "cost": cost,
                          "steps": steps
                      }])

(I have no idea if I indented this correctly...)