blog

Personal blog
git clone git://git.laack.co/blog.git
Log | Files | Refs

prim-rlib.py (3650B)

      1 import pyray as pr
      2 import statistics
      3 import heapq
      4 import random
      5 import math
      6 import time
      7 
      8 for _ in range(0,10):
      9     VERTICES = 2500
     10     EDGES = 25000
     11     RADIUS = 5
     12 
     13     pr.init_window(5120,1440, "prim")
     14 
     15     class Vertex():
     16         def __init__(self, x, y):
     17             self.x = x
     18             self.y = y
     19             self.visited = False
     20         def draw_vertex(self):
     21             if self.visited:
     22                 pr.draw_circle(int(self.x),int(self.y), RADIUS, pr.WHITE)
     23             else:
     24                 pr.draw_circle(int(self.x),int(self.y), RADIUS, pr.GRAY)
     25     class Edge():
     26         def __init__(self, v1, v2):
     27             self.v1 = v1
     28             self.v2 = v2
     29             self.dist = math.sqrt(((v1.x - v2.x) ** 2) + ((v1.y - v2.y) ** 2))
     30         def draw_edge(self, c):
     31             pr.draw_line(int(self.v1.x), int(self.v1.y), int(self.v2.x), int(self.v2.y), c)
     32 
     33         def __lt__(self,otr):
     34             return self.dist < otr.dist
     35 
     36 
     37     graph = {}
     38 
     39     for i in range(0,VERTICES):
     40         x = random.random() * 5120
     41         y = random.random() * 1440
     42         graph[Vertex(x,y)] = []
     43 
     44 
     45     edge_list = []
     46     keys = list(graph.keys())
     47 
     48     for i in range(0,EDGES):
     49         k1 = None
     50         k2 = None
     51         while k1 == k2:
     52             k1 = random.choice(keys)
     53             k2 = random.choice(keys)
     54 
     55         edge = Edge(k1,k2)
     56         graph[k1].append(edge)
     57         graph[k2].append(edge)
     58         edge_list.append(edge)
     59 
     60 
     61     edge_heap = []
     62     visited_vertices = set()
     63 
     64 
     65     start = random.choice(keys)
     66     start.visited = True
     67     visited_vertices.add(start)
     68     for edge in graph[start]:
     69         heapq.heappush(edge_heap, edge)
     70 
     71 
     72     first = True
     73 
     74     to_draw_vert = []
     75     to_draw_edge = []
     76 
     77     texture = pr.load_render_texture(5120,1440)
     78 
     79     fts = []
     80 
     81     while True:
     82 
     83         pr.begin_texture_mode(texture)
     84 
     85         if first:
     86             start = time.monotonic_ns()
     87             pr.clear_background(pr.BLACK)
     88 
     89             for edge in edge_list:
     90                 edge.draw_edge(pr.DARKGRAY)
     91             first = False
     92             end = time.monotonic_ns()
     93             print("first frame (ns): ", end - start)
     94 
     95             for vertex in graph:
     96                 vertex.draw_vertex()
     97 
     98         start = time.monotonic_ns()
     99         for edge in to_draw_edge:
    100             edge.draw_edge(pr.WHITE)
    101         for vert in to_draw_vert:
    102             vert.draw_vertex()
    103         pr.end_texture_mode()
    104         end = time.monotonic_ns()
    105         fts.append(end - start)
    106 
    107         to_draw_vert = []
    108         to_draw_edge = []
    109 
    110 
    111         item = None
    112         while edge_heap:
    113             candidate = heapq.heappop(edge_heap)
    114             if (candidate.v1 in visited_vertices) != (candidate.v2 in visited_vertices):
    115                 item = candidate
    116                 break
    117 
    118         if item is None:
    119             break
    120 
    121         new_vertex = item.v2 if item.v1 in visited_vertices else item.v1
    122         visited_vertices.add(new_vertex)
    123         new_vertex.visited = True
    124 
    125         to_draw_vert.append(new_vertex)
    126         to_draw_edge.append(item)
    127 
    128         for edge in graph[new_vertex]:
    129             if not edge.v1 in visited_vertices or not edge.v2 in visited_vertices:
    130                 heapq.heappush(edge_heap, edge)
    131 
    132         source_rec = pr.Rectangle(0, 0, 5120, 1440)
    133         dest_rec = pr.Rectangle(0, 0, 5120,1440)
    134 
    135         pr.begin_drawing()
    136         pr.draw_texture_pro(texture.texture, source_rec, dest_rec, pr.Vector2(0, 0), 0, pr.WHITE)
    137         pr.end_drawing()
    138 
    139 
    140     print("Average frame time (ns): " + str(sum(fts) / len(fts)))
    141     print("Std. deviation frame time (ns): " + str(statistics.stdev(fts)))
    142 
    143     pr.unload_render_texture(texture)
    144     pr.close_window()