Skip to content

Instantly share code, notes, and snippets.

@mdamien
Forked from anonymous/_idea
Created January 24, 2017 23:58
Show Gist options
  • Save mdamien/ed0bcbff9202dabbec78858c5fe7723c to your computer and use it in GitHub Desktop.
Save mdamien/ed0bcbff9202dabbec78858c5fe7723c to your computer and use it in GitHub Desktop.
simulate roads created by people trying to get from point A to point B
rules:
- each turn, everybody is assigned a position to go if they don't have already somewhere to go
- each time they go over a "block", it becomes easier for others to use it
# Dijkstra's algorithm for shortest paths
# David Eppstein, UC Irvine, 4 April 2002
# http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/117228
class priorityDictionary(dict):
def __init__(self):
'''Initialize priorityDictionary by creating binary heap
of pairs (value,key). Note that changing or removing a dict entry will
not remove the old pair from the heap until it is found by smallest() or
until the heap is rebuilt.'''
self.__heap = []
dict.__init__(self)
def smallest(self):
'''Find smallest item after removing deleted items from heap.'''
if len(self) == 0:
raise IndexError("smallest of empty priorityDictionary")
heap = self.__heap
while heap[0][1] not in self or self[heap[0][1]] != heap[0][0]:
lastItem = heap.pop()
insertionPoint = 0
while 1:
smallChild = 2*insertionPoint+1
if smallChild+1 < len(heap) and \
heap[smallChild] > heap[smallChild+1]:
smallChild += 1
if smallChild >= len(heap) or lastItem <= heap[smallChild]:
heap[insertionPoint] = lastItem
break
heap[insertionPoint] = heap[smallChild]
insertionPoint = smallChild
return heap[0][1]
def __iter__(self):
'''Create destructive sorted iterator of priorityDictionary.'''
def iterfn():
while len(self) > 0:
x = self.smallest()
yield x
del self[x]
return iterfn()
def __setitem__(self,key,val):
'''Change value stored in dictionary and add corresponding
pair to heap. Rebuilds the heap if the number of deleted items grows
too large, to avoid memory leakage.'''
dict.__setitem__(self,key,val)
heap = self.__heap
if len(heap) > 2 * len(self):
self.__heap = [(v,k) for k,v in self.items()]
self.__heap.sort() # builtin sort likely faster than O(n) heapify
else:
newPair = (val,key)
insertionPoint = len(heap)
heap.append(None)
while insertionPoint > 0 and \
newPair < heap[(insertionPoint-1)//2]:
heap[insertionPoint] = heap[(insertionPoint-1)//2]
insertionPoint = (insertionPoint-1)//2
heap[insertionPoint] = newPair
def setdefault(self,key,val):
'''Reimplement setdefault to call our customized __setitem__.'''
if key not in self:
self[key] = val
return self[key]
def Dijkstra(G,start,end=None):
"""
Find shortest paths from the start vertex to all vertices nearer than or equal to the end.
The input graph G is assumed to have the following representation:
A vertex can be any object that can be used as an index into a dictionary.
G is a dictionary, indexed by vertices. For any vertex v, G[v] is itself a dictionary,
indexed by the neighbors of v. For any edge v->w, G[v][w] is the length of the edge.
This is related to the representation in <http://www.python.org/doc/essays/graphs.html>
where Guido van Rossum suggests representing graphs as dictionaries mapping vertices
to lists of outgoing edges, however dictionaries of edges have many advantages over lists:
they can store extra information (here, the lengths), they support fast existence tests,
and they allow easy modification of the graph structure by edge insertion and removal.
Such modifications are not needed here but are important in many other graph algorithms.
Since dictionaries obey iterator protocol, a graph represented as described here could
be handed without modification to an algorithm expecting Guido's graph representation.
Of course, G and G[v] need not be actual Python dict objects, they can be any other
type of object that obeys dict protocol, for instance one could use a wrapper in which vertices
are URLs of web pages and a call to G[v] loads the web page and finds its outgoing links.
The output is a pair (D,P) where D[v] is the distance from start to v and P[v] is the
predecessor of v along the shortest path from s to v.
Dijkstra's algorithm is only guaranteed to work correctly when all edge lengths are positive.
This code does not verify this property for all edges (only the edges examined until the end
vertex is reached), but will correctly compute shortest paths even for some graphs with negative
edges, and will raise an exception if it discovers that a negative edge has caused it to make a mistake.
"""
D = {} # dictionary of final distances
P = {} # dictionary of predecessors
Q = priorityDictionary() # estimated distances of non-final vertices
Q[start] = 0
for v in Q:
D[v] = Q[v]
if v == end: break
for w in G[v]:
vwLength = D[v] + G[v][w]
if w in D:
if vwLength < D[w]:
raise ValueError("Dijkstra: found better path to already-final vertex")
elif w not in Q or vwLength < Q[w]:
Q[w] = vwLength
P[w] = v
return (D,P)
def shortestPath(G,start,end):
"""
Find a single shortest path from the given start vertex to the given end vertex.
The input has the same conventions as Dijkstra().
The output is a list of the vertices in order along the shortest path.
"""
D,P = Dijkstra(G,start,end)
Path = []
while 1:
Path.append(end)
if end == start: break
end = P[end]
Path.reverse()
return Path
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def __add__(self, other):
if not isinstance(other, Point):
return NotImplemented
return Point(self.x + other.x, self.y + other.y)
def __eq__(self, other):
if not isinstance(other, Point):
return NotImplemented
return self.x == other.x and self.y == other.y
def __hash__(self):
return self.x*1000000 + self.y
def __str__(self):
return '{},{}'.format(self.x, self.y)
def shortestPath(G,start,end):
"""
Find a single shortest path from the given start vertex to the given end vertex.
The input has the same conventions as Dijkstra().
The output is a list of the vertices in order along the shortest path.
"""
D,P = Dijkstra(G,start,end)
Path = []
while 1:
Path.append(end)
if end == start: break
end = P[end]
Path.reverse()
return Path
def to_graph(grid):
G = dict()
for y, row in enumerate(grid):
for x, block in enumerate(row):
edges = {}
for offx, offy in (-1, 0), (1, 0), (0, -1), (0, 1): #, (-1, -1), (1, 1), (-1, 1), (1, -1):
p = Point(x + offx, y + offy)
if p.x < 0 or p.y < 0 or p.x >= len(row) or p.y >= len(grid):
continue
try:
# w = 1000 - grid[y][x][0]
w = 1 / (grid[y][x][0] + 10)
edges[str(p)] = w
except IndexError:
pass
G[str(Point(x, y))] = edges
return G
def faster_path(G, x, y, dest_x, dest_y):
path = shortestPath(G, str(Point(x, y)),
str(Point(dest_x, dest_y)))
if len(path) < 2:
return 0, 0
start, end = path[:2]
sx, sy = [int(x) for x in start.split(',')]
ex, ey = [int(x) for x in end.split(',')]
return ex - sx, ey - sy
if __name__ == '__main__':
from pprint import pprint as pp
# example, CLR p.528
G = {'s': {'u':10, 'x':5},
'u': {'v':1, 'x':2},
'v': {'y':4},
'x':{'u':3,'v':9,'y':2},
'y':{'s':7,'v':6}}
grid = [
[(0,), (4,), (0,)],
[(0,), (4,), (4,)],
[(0,), (0,), (0,)],
]
G = to_graph(grid)
pp(G)
print(Dijkstra(G, str(Point(0, 0))))
print(shortestPath(G, str(Point(0, 0)), str(Point(2, 2))))
# two things to show: people positions + block resistance
# one easy thing: each block is
# - (block_smoothness, peoples)
# and people are just (goal_x, goal_y)
# let's do something minimal, create a grid with nobody
# let's add people
# grid[y // row][x // column]
import random, time, os
import dijkstra
WIDTH = 200
HEIGHT = 60
def maybe_add_somebody():
if random.random() > 0.9995:
return [(random.randint(0, WIDTH - 1), random.randint(0, HEIGHT - 1))]
return []
def grid_print(grid):
for row in grid:
for block in row:
# color it to make it fun !
# limit precision too !
l = block[0]
c = ' '
if l == 2:
c = '\''
elif l == 3:
c = '"'
elif l > 3:
if l > 11: l = 11
c = l - 2
if len(block[1]) > 0:
c = '|'
print(c, end='')
print()
def direct_path(grid, x, y, dest_x, dest_y):
# compute movement to do to get to the target
# without taking into account block resistance
offx = 0
if x != dest_x:
if x > dest_x:
offx = -1
else:
offx = 1
offy = 0
if y != dest_y:
if y > dest_y:
offy = -1
else:
offy = 1
return offx, offy
def move_people(grid):
G = dijkstra.to_graph(grid)
new_peoples = []
for y, row in enumerate(grid):
for x, block in enumerate(row):
for (dest_x, dest_y) in block[1]:
# offx, offy = direct_path(grid, x, y, dest_x, dest_y)
offx, offy = dijkstra.faster_path(G, x, y, dest_x, dest_y)
### if we are on the target, set new goal
if offx == 0 and offy == 0:
dest_x = random.randint(0, WIDTH - 1)
dest_y = random.randint(0, HEIGHT - 1)
### detect bad directions
new_x = x + offx
if new_x < 0 or new_x >= WIDTH:
print('error: new_x=', new_x)
new_x = x
new_y = y + offy
if new_y < 0 or new_y >= HEIGHT:
print('error: new_y=', new_y)
new_y = y
new_peoples.append((new_x, new_y, (dest_x, dest_y)))
block[1] = []
for x, y, dest in new_peoples:
try:
grid[y][x][0] += 1
grid[y][x][1].append(dest)
except IndexError:
print('error: y=', y, ' x=', x)
import pudb;pudb.set_trace()
grid = [ [ [
1, maybe_add_somebody()
] for _ in range(WIDTH)
] for _ in range(HEIGHT)]
step = 0
while True:
os.system('clear')
print(step)
grid_print(grid)
move_people(grid)
time.sleep(0.1)
step += 1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment