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)))