Dijkstra, and Doing Things The Hard Way (Pt.1)

I can remember quite clearly the first time I came across Dijkstra’s Algorithm. It was in xkcd 342, and at the time (bearing in mind I was about 12) it seemed like the most effortlessly cool computer science-y thing (I was a weird kid. The kid bit has stopped being true now.).

Looking back on that comic, I realise that actually, I don’t really understand that panel. Why is Dijkstra better for memory usage than A*?  Surely, since A* prioritises likely routes, it needs to hold less in memory?

Anyway, I came to this realisation and promptly decided that I need to implement both in Python to get a better idea of how they work. And so here we are.

The “Doing Things The Hard Way” part of the title refers to a philosophy I’ve developed over a few years of half-heartedly writing code: I want to do something myself before I use a library. There are definitely pathfinding and terrain-generating libraries out there, but what would I learn if I used them? A lot about those libraries, relatively little about the underlying maths and code.

Warning: this post is a stream-of-consciousness style post. I’m writing it at the same time as my code. It may ramble.

My work so far has got me:

  • a class of maps, which use an algorithm I wrote to define terrain height (Doing It The Hard Way)
  • a function which takes that map and turns it into a Dict, where mapdict(xCoord,yCoord) = terrainHeight
  • a Breadth First Search function.
figure_1.png
Figure 1: A Terrain Map (Darker is lower)

The Breadth First engine operates as follows:

  1. Mark the current square as visited.
  2. Number the coordinates at (x,y+1),  (x+1,y),  (x,y-1),  (x-1,y) with increasing integers (the node number).
  3. Move to the lowest-numbered unvisited square.
  4. Start again.

This gives an outwards spiral pattern from the start, as seen here:

figure_2.png
Figure 2: the breadth-first search result

This is the result of about six hours of coding, by the way. Anyway, I shall now crack on.

Implementing a ‘came-from’ log

A ‘came-from’ log simply keeps track of which coordinate was current during step 2 above. So, if we started at (50,50), then (50,51), (51,50), (50,49) and (49, 50) would all have a ‘came-from’ value of 50. Simple, right? Just another dictionary; every key is the coordinates of a square, and every value is the came-from.

Would it were so.

I’ve implemented this; but it’s broken my breadth-first searcher, which now stops after moving to node 1. Logging shows that it can’t find node 2, i.e. the node directly to the right of node 0.

(By the way, a node is another term for a point to which a set of coordinates refer. In the above example, (50,50) is node 0, (50,51) is node 1, and so on.)

Eventually I figured it out – laziness with copy and paste. The function which marks neighbouring nodes was marking the wrong neighbouring node. Ouch.

Anyway, the ‘came-from’ is now implemented. It’s useful because it allows us to back-track from a certain point to the origin.

Testing reveals that it… works! Hooray!

Early Exit

It’s exactly what it sounds like – if the node being examined is the target, it stops examining. Implementing that is really easy; just break out of the breadth-first loop, which now looks like this:

### Breadth-first searching with early exit
nextNode = 0
while nextNode != -1:
    nextNode = -1
    for sublist in nodeNumbers:
        if nodesVisited in sublist:
            nextNode = ([nodeNumbers.index(sublist),sublist.index(nodesVisited)])
            exit

    if nextNode != -1:
        nodeX, nodeY = nextNode
    #print("Moving to {0}".format(nextNode))

    nodeNumbers[nodeX][nodeY] = nodesVisited
    nodesVisited += 1
    markNeighbours()

    if nodeX == targetX and nodeY == targetY:
        nextNode = -1
        print("Target found!")

nodeNumbers, by the way, is a dictionary, where a key (nodeX,nodeY) refers to the number assigned to that node.

Movement Costs

This is terrain which I’m notionally modelling. The implication is that climbing a hill is harder than walking on the level. Fortunately, Dijkstra’s Algorithm allows for movement costs (also called edge costs.) So let’s implement it.

First thing is to create another dictionary, nodeCost. This will hold the lowest-cost path to that node.

Now, I think that the best way to calculate that is, for a given node:

  1. Set a currentCost variable to the nodeCost of the current node
  2. For each neighbour, add (nextNodeTerrainHeight-currentNodeTerrainHeight) to currentCost, and if the result is lower than (nextNodeCost), write it to nodeCost.
  3. Move on.

Implement it, and… list index out of range errors. Part of the problem is that I’m using two main types of storage for storing various things relevant to a set of coordinates. One of them is a dict, where the key (a tuple containing the x and y coordinates) corresponds to a value. The other is a list of lists, where list[x][y] holds a value. Keeping track of which variable is of which type is tough.

At this point, I gave up. We take up the narrative thread the following morning…

Right, let’s see. I can fix the list index errors – typo – but now I’m seeing 'int' object is not subscriptable. Irritatingly, here’s the line of code throwing the exception:

if nodeCost[nodeX][nodeY+1] > 0 and nodeCost[nodeX][nodeY+1] < currentCost+mapdict(nodeX,nodeY+1):

I mean, that’s spaghetti. Refactor it to:

        currentNodeCost = nodeCost[nodeX][nodeY+1]
        if currentNodeCost > 0 and currentNodeCost < currentCost + mapdict(nodeX,nodeY+1):
            currentNodeCost = currentCost + mapdict(nodeX,nodeY+1)

and the error moves to this line:

currentNodeCost = nodeCost[nodeX][nodeY+1]

So, there’s an issue with nodeCost. I did a search, and found that although I was defining it, I was then overwriting it with an integer. Oops. That’s why I need better commenting, I think. If I write comments for my code, it helps me to keep straight in my head why I’m doing what I’m doing.

After that, astonishingly, it works, sort of. Or at least, it runs. So no syntax errors. Unfortunately, printing a heatmap of the nodeCost list to screen shows that every single entry is -1  (the value I initialised it to).

After a bit more searching… well, that’s embarrasing. Move a line of code, and it’s working, sort of…

figure_3.png
Figure 3: movement costs.

I think that the reason that the graph looks so uniform is that there’s only a range of 0-9, but the graph is 50×50. That probably means that there’s very little variance. I’ll tackle that in a second, but first I need to check something.

I need to change the way that the ‘came-from’ works – now, I’ll need to write the ‘came-from’ every time we also change the movement cost. The idea is that once I get to the target, I can examine the lowest-cost route back to the target.


Thus ends part one. I’ll write up part two as I get to it, though I’m not sure when that’ll be.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s