1

I'm approaching the world of pathfinder algorithms so I have started playing with the two most famous A* and Dijkstra.

I'm developing algorithms in Python and the graph is a dictionary of dictionary:

{Node:{(Node1:weights1),(Node2:weights2),..}

My space is a chessboard of 640x480 and these are all the possible paths that it is possible to follow:

paths

This is my implementation of the algorithms:

def Manhattan(node1, node2):
    j1 = node1%640
    i1 = (node1-j1)/640
    j2 = node2%640
    i2 = (node2-j2)/640
    return np.abs(j1-j2) + np.abs(i1-i2)

def Astar(graph, start, end):
    A = [None] * (640*480)
    queue = [(0, 0, start, ())]
    while queue:
        fscore, path_len, v, sortPath = heappop(queue)
        sortPath = (v, sortPath)
        if v == end : break
        for w, edge_len in graph[v].items():
            new_cost = path_len+edge_len
            if A[w] is None or new_cost < A[w]:
                A[w] = new_cost
                heappush(queue, (new_cost + Manhattan(w,end), new_cost, w, sortPath))

    # to give same result as original, assign zero distance to unreachable vertices             
    return [0 if x is None else x for x in A],sortPath


def Dijkstra(graph, start, end=None):
    A = [None] * (640*480)
    queue = [(0, start, ())]
    while queue:
        path_len, v, sortPath = heappop(queue)
        sortPath = (v, sortPath)
        if v == end : break
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w, sortPath))

    # to give same result as original, assign zero distance to unreachable vertices             
    return [0 if x is None else x for x in A],sortPath

As far as I know, the A* algorithm (if the heuristic function makes sense; I have used Manhattan because it is not possible to go in diagonal) should be faster than Dijkstra because it should avoid expanding the not interesting nodes.

In my case Dijkstra runs in 0.28 s while A* in 1 s. And the explored nodes for both the algorithms are exactly the same:

Dijkstra:

dijkstra exploration

A*:

a-star exploration

Am I doing something wrong with the A* implementation? The difference in the running time, should it be because for the heuristic function I convert each time from linear index to matrix row, column? Any help is greatly appreciated!

BugsFree
  • 540
  • 1
  • 6
  • 24
  • @Coldspeed https://stackoverflow.com/a/1332478/1377097 – beaker Jun 20 '17 at 14:32
  • @Coldspeed: Yes you are completely wrong. Dijkstra's is BFS that works on weighted graphs. A\* is Dijkstra's that includes a distance heuristic. – BlueRaja - Danny Pflughoeft Jun 20 '17 at 17:45
  • Couple of remarks: 1. If Dijkstra and A* expand the same set of nodes is normal than Dijkstra's algorithm is faster. How much faster it will depend on the calculation time of the heuristic function. 2. I haven't looked at the code but I hardly doubt both algorithms will expand the same nodes in this kind of search space. Review your implementation of A* and Manhattan distance. – FrankS101 Jun 26 '17 at 12:28
  • I strongly suggest that you implement one search function, that accepts two functions as arguments (g and h). for Dijkstra, simply have *h* return 0 for every 2 states, and for A*, invoke the Manhattan distance. This will make sure you are actually performing A* and Dijkstra, and not a faulty version of one of those. – Ori Aug 02 '17 at 20:29

0 Answers0