Skip to content

Road Generation with Prim's Algorithm and MST

Latest
Compare
Choose a tag to compare
@matthewstyler matthewstyler released this 10 Dec 18:38

Updated connected pair generation of building in a town and centroids between town for road generation to use prim's algorithm with a minimum spanning tree. This was originally generating a full graph.

Time improved from O(n^2) to O((V+E)logV). Map generation with roads is significantly faster.

Minimum Spanning Tree
Prim's Algorithm