Dijkstra Maps... What have I done!?

[doulos05]

So, I'm attempting to use a Dijkstra map/heat map in my game (since that's obviously the easiest way to handle monster AI movement). But I've done something horribly, horribly wrong. In a 12x12 empty room, it takes 80 seconds to run. Since it's the heat centered on the player, it's going to have to update pretty much every turn. The problem is definitely that I'm visiting nodes too often (it takes 8,000 iterations to do an empty 8x8 room and I don't want to even consider how many it takes for a 12x12, but I estimate it to be about 41,500 or so). Below is the function (written in Python). I've pulled this out of a Map class, but before I try optimizing the data structure of the tiles or their storage, I want to cut the number of visits down to what it's supposed to be (a bit less than half what it is now if I'm reading the O() notation on Dijkstra's correctly. How can I fix this?

Code: [Select]

    def heatmap(self, source_x,source_y):
        l_open = []
        source = self.lookup(source_x,source_y)
        if source: l_open.append(source)
        start = True
       
        while l_open:
            cell = l_open.pop()
            cell.visited = True
            neighbors = []
            addrs = self.get_neighbor_addrs(cell.x,cell.y)
            for addr in addrs:
                c = self.lookup(addr[0],addr[1])
                if c:
                    if c is not cell and not c.blocked:
                        neighbors.append(c)
            if start:
                start = False
                cell.previous = cell
                cell.value = 0
                for neighbor in neighbors:
                    neighbor.previous = cell
                    l_open.append(neighbor)
               
            else:
                neighbors.sort(key=lambda x: x.value)
                cell.previous = neighbors[0]
                cell.value = neighbors[0].value + 1
                for neighbor in neighbors:
                    if cell.value < neighbor.value:
                        if not neighbor in l_open:
                            l_open.append(neighbor)

        return self.render(0,self.width, 0,self.height,True)
*The only changes made to this code was the removal of variables and print() commands I was using to track the output.

[Tzan]

I see where you are setting " cell.visited = True ".
But I dont see where you are testing this to prevent running over those cells again.

[doulos05]

I see where you are setting " cell.visited = True ".
But I dont see where you are testing this to prevent running over those cells again.

But shouldn't I still check each one to verify that the current cell isn't a better path?

When I was using .visited, the map sometimes ended up looking like this:

Code: [Select]

9 8 4 5 6
8 7 3 4 5
7 6 2 3 4
6 1 1 1 3
5 1 0 1 2
4 1 1 1 2
3 2 2 2 2
Because I'm not using a priority queue, it just pops the first one, which leads to trails around the map.

[Gornova]

hi! I've done something similar in the past (with Java), maybe can inspire you: https://github.com/Gornova/Wargame

[tuturto]

If I read your code correctly, you shouldn't be adding neighbour to l_open, if it already has a value associated to it. So instead of:

Code: [Select]

9 8 4 5 6
8 7 3 4 5
7 6 2 3 4
6 1 1 1 3
5 1 0 1 2
4 1 1 1 2
3 2 2 2 2
You want (player or goal located at 0):

Code: [Select]

4 4 4 4 4
3 3 3 3 3
2 2 2 2 2
2 1 1 1 2
2 1 0 1 2
2 1 1 1 2
2 2 2 2 2
After this path finding is simply just going towards smallest number.

[Tzan]

I've never made a Dijkstra Map before, but I have done A*.

In A*
When you enter a new cell, that is already the shortest path that could exist to that point.
In A* you have the exact cost of the current path + an underestimate of the remaining distance.

I spent a lot of time with graph paper doing it by hand to really see what was happening, before coding it.

Like I said I have never done Dijkstra, so things may work different there.
I spotted that unused bool so I expect that's a problem.
Looks like tuturto has a good idea to try.

[dividee]

If your not using a priority queue (or a minimum search), it's not Dijkstra. In Python, a priority queue is easy to implement using the heapq module.

I took the liberty to simplify and modify your code to something that looks more like Dijkstra's algorithm. I didn't test it as I don't have access to your data structures, so there are very probably some bugs, but it should be a better starting point:

Code: [Select]

from heapq import *

    def heatmap(self, source_x,source_y):
        l_open = []
        source = self.lookup(source_x,source_y)
        if source: l_open.append((0,source,source)) # (value, cell, previous)
       
        while l_open:
            value, cell, previous = heappop(l_open)
            if cell.visited: continue
            cell.visited = True
            cell.previous = previous
            cell.value = value

            for x,y in self.get_neighbor_addrs(cell.x,cell.y)
                c = self.lookup(x,y)
                if c and not (c.visited or c.blocked):
                    heappush(l_open, (value + 1, c, cell))

        return self.render(0,self.width, 0,self.height,True)
As long as the cell cost is constant, Dijkstra and BFS are equivalent; Dijkstra becomes interesting when the cost is variable (but it should not be negative).

[doulos05]

Oh my god! Not only did that fix it, it runs about 100x faster.

But more importantly, because you tweaked code I had already written, I know how it works. I KNOW HOW IT WORKS!

For 10 years, I've poked at A* and Dijkstra maps without grokking what was happening well enough to implement it in code. But now i do. You, sir, are a God among men. May the @ always sing your praises until the heat death of the universe.

[dividee]

Thank you for the high praise, I'm glad I could help you grok it

The main difference when compared to the classic presentation of the algorithm is that we don't have an operation to decrease the priority of an item in the priority queue.
So instead of comparing the length of a new candidate path to a previous value, we allow a cell to be pushed multiple times in the priority queue and the extract-min operation (heappop) guarantees us that the first one we'll pop will be the best one. The other ones will be rejected by the "if cell.visited:continue" check.