Show Posts

This section allows you to view all posts made by this member. Note that you can only see posts made in areas you currently have access to.

Messages - dividee

Pages: [1]
Has anyone done a CFFI wrapper for BearLibTerminal with PyPy? 

Sorry for the late reply. I did a CFFI wrapper for bearlibterminal a while ago, but never published it. I just uploaded it, if you want to try it out.

Just replace with the cffi version and it should work. It's only a little faster in CPython, but vastly faster in pypy.

Programming / Re: Dijkstra Maps... What have I done!?
« on: October 12, 2016, 08:27:58 PM »
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.

Programming / Re: Dijkstra Maps... What have I done!?
« on: October 11, 2016, 08:59:53 PM »
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).

If anyone is interested, I ported the Omni samples to Python. I just updated them for 0.14.8. Most of the time, the translation from C++ is quite literal. It runs in both Python 2.7 and 3.5 (and probably others). And also on pypy 5.3, although it's very slow on pypy because of ctypes...

Here is the link:

You should be able to just download or clone the repository and run the samples in the Python directory. You can either run each sample individually or for the whole thing.

Pages: [1]