blog

prim-rlib.py (4763B)

---

 import pyray as pr
 import statistics
 import heapq
 import random
 import math
 import time
 
 fts = []
 first_time = []
 
 
 pr.init_window(5120,1440, "prim")
 texture = pr.load_render_texture(5120,1440)
 
 for _ in range(0,10):
     VERTICES = 2500
     EDGES = 25000
     RADIUS = 5
 
 
     class Vertex():
         def __init__(self, x, y):
             self.x = x
             self.y = y
             self.visited = False
         def draw_vertex(self):
             if self.visited:
                 pr.draw_circle(int(self.x),int(self.y), RADIUS, pr.WHITE)
             else:
                 pr.draw_circle(int(self.x),int(self.y), RADIUS, pr.GRAY)
     class Edge():
         def __init__(self, v1, v2):
             self.v1 = v1
             self.v2 = v2
             self.dist = math.sqrt(((v1.x - v2.x) ** 2) + ((v1.y - v2.y) ** 2))
         def draw_edge(self, c):
             pr.draw_line(int(self.v1.x), int(self.v1.y), int(self.v2.x), int(self.v2.y), c)
 
         def __lt__(self,otr):
             return self.dist < otr.dist
 
 
     graph = {}
 
     for i in range(0,VERTICES):
         x = random.random() * 5120
         y = random.random() * 1440
         graph[Vertex(x,y)] = []
 
 
     edge_list = []
     keys = list(graph.keys())
 
     for i in range(0,EDGES):
         k1 = None
         k2 = None
         while k1 == k2:
             k1 = random.choice(keys)
             k2 = random.choice(keys)
 
         edge = Edge(k1,k2)
         graph[k1].append(edge)
         graph[k2].append(edge)
         edge_list.append(edge)
 
 
     edge_heap = []
     visited_vertices = set()
 
 
     start = random.choice(keys)
     start.visited = True
     visited_vertices.add(start)
     for edge in graph[start]:
         heapq.heappush(edge_heap, edge)
 
 
     first = True
 
     to_draw_vert = []
     to_draw_edge = []
 
     while True:
 
 
         if first:
             start = time.monotonic_ns()
             pr.begin_texture_mode(texture)
             pr.clear_background(pr.BLACK)
 
             edge_times = []
             vertex_times = []
 
             for edge in edge_list:
                 es = time.monotonic_ns()
                 edge.draw_edge(pr.DARKGRAY)
                 ee = time.monotonic_ns()
                 edge_times.append(ee - es)
             for vertex in graph:
                 vs = time.monotonic_ns()
                 vertex.draw_vertex()
                 ve = time.monotonic_ns()
                 vertex_times.append(ve - vs)
             first = False
             pr.end_texture_mode()
             source_rec = pr.Rectangle(0, 0, 5120, 1440)
             dest_rec = pr.Rectangle(0, 0, 5120,1440)
             pr.begin_drawing()
             pr.draw_texture_pro(texture.texture, source_rec, dest_rec, pr.Vector2(0, 0), 0, pr.WHITE)
             pr.end_drawing()
             end = time.monotonic_ns()
             first_time.append(end - start)
 
             print("Edge time avg: " + str(sum(edge_times) / len(edge_times)))
             print("Vertex time avg: " + str(sum(vertex_times) / len(vertex_times)))
 
             continue
 
 
         if len(to_draw_edge) != 0 or len(to_draw_vert) != 0:
             start = time.monotonic_ns()
             pr.begin_texture_mode(texture)
             for edge in to_draw_edge:
                 edge.draw_edge(pr.WHITE)
             for vert in to_draw_vert:
                 vert.draw_vertex()
             pr.end_texture_mode()
             source_rec = pr.Rectangle(0, 0, 5120, 1440)
             dest_rec = pr.Rectangle(0, 0, 5120,1440)
 
             pr.begin_drawing()
             pr.draw_texture_pro(texture.texture, source_rec, dest_rec, pr.Vector2(0, 0), 0, pr.WHITE)
             pr.end_drawing()
             end = time.monotonic_ns()
             fts.append(end - start)
             to_draw_vert = []
             to_draw_edge = []
 
 
         item = None
         while edge_heap:
             candidate = heapq.heappop(edge_heap)
             if (candidate.v1 in visited_vertices) != (candidate.v2 in visited_vertices):
                 item = candidate
                 break
 
         if item is None:
             break
 
         new_vertex = item.v2 if item.v1 in visited_vertices else item.v1
         visited_vertices.add(new_vertex)
         new_vertex.visited = True
 
         to_draw_vert.append(new_vertex)
         to_draw_edge.append(item)
 
         for edge in graph[new_vertex]:
             if not edge.v1 in visited_vertices or not edge.v2 in visited_vertices:
                 heapq.heappush(edge_heap, edge)
 
 
 pr.unload_render_texture(texture)
 pr.close_window()
 
 print("Average frame time (ns): " + str(sum(fts) / len(fts)))
 print("Std. deviation frame time (ns): " + str(statistics.stdev(fts)))
 
 print("Average first frame time (ns): " + str(sum(first_time) / len(first_time)))
 print("Std. deviation first frame time (ns): " + str(statistics.stdev(first_time)))