blog

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

prim-rlib.py (3475B)


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