Tracks are generated from Voronoi diagrams created via Voronout.

Every diagram is a collection of regions in a two-dimensional space.

Each region is concerned with a point P in that space. A region's dimensions is determined by the idea that it contains all points closer to its own P than any other region's P.

A set of region points SP can easily produce a diagram whose regions vary in size:

With region size variance comes variance in the length of any region R's " border " with one of its neighbors:

A Track sees the set of all borders in a diagram as a collection of edges, each edge between two points. It doesn't want that entire set, because each point - each node - can be reached from every other point through multiple different " paths " from edge to edge .

What it wants is a subset of those edges where a start and an end can be picked such that, if going from edge to edge was restricted by limited resources, it would be very likely to go from start and run out of resources before getting to end.

(Finding and traveling on a path where you could get from start to end would be more of a challenge.)

That subset would be a set of edges where every node cannot be reached from every other node.

TrackGenerator.generateTrack() creates that set using the following parameters:

diagram_width: int,
diagram_height: int,
num_diagram_regions: int,
length_min_quantile: float,

(See source for all parameters.)

diagram_width, diagram_height, and num_diagram_regions are used to generate the Voronoi diagram:

voronoi_points = tuple(Point(x = random.random(), y = random.random()) for _ in range(num_diagram_regions))
..
voronoi_diagram = VoronoiDiagram(basePoints = voronoi_points, planeWidth = diagram_width, planeHeight = diagram_height)

In this case,

diagram_width = 600
diagram_height = 600
num_diagram_regions = 18,
length_min_quantile = 0.50

and

voronoi_points = (
    Point(x= 0.9463, y= 0.6669), 
    Point(x= 0.4353, y= 0.5272), 
    Point(x= 0.4222, y= 0.5968), 
    Point(x= 0.9876, y= 0.5229), 
    Point(x= 0.5794, y= 0.964), 
    Point(x= 0.5983, y= 0.0106), 
    Point(x= 0.687, y= 0.1437), 
    Point(x= 0.4132, y= 0.2723), 
    Point(x= 0.0361, y= 0.1436), 
    Point(x= 0.062, y= 0.2417), 
    Point(x= 0.8191, y= 0.4291), 
    Point(x= 0.5383, y= 0.8066), 
    Point(x= 0.5011, y= 0.365), 
    Point(x= 0.3063, y= 0.9677), 
    Point(x= 0.9008, y= 0.0296), 
    Point(x= 0.2748, y= 0.7383), 
    Point(x= 0.8428, y= 0.0683), 
    Point(x= 0.1703, y= 0.0407)
)

Voronout creates the diagram in a 2-D space where 0 <= x <= 1 and 0 <= y <= 1, with (x = 0, y = 0) in the upper-left, then scales the diagram's coordinates on x*=diagram_width and y*=diagram_height.

Voronout is a wrapper around SciPy's Voronoi diagram generation that that translates its output into more easily parsible data.

Any adjustment to the generated diagram is best done by whomever generates the diagram.

In TrackGenerator's case, the adjustment is removing all node " overlaps ". The diagram generated by voronoi_points illustrates the necessity of this:

(The overlap's in the center, where it looks like four edges are meeting - that's actually where two edges are meeting overlapping with where another two edges are meeting.)

How overlaps are identified:

JUNCTION_RADIUS = 3
..
@staticmethod
def _junction_intersection_check(junction_1: Point, junction_2: Point, junction_diameter: float) -> bool:
    return Point.distance(p1 = junction_1, p2 = junction_2) <= junction_diameter
..
for (voronoi_diagram_vertex_id, voronoi_diagram_vertex) in voronoi_diagram_vertices.items():
    for (other_voronoi_diagram_vertex_id, other_voronoi_diagram_vertex) in voronoi_diagram_vertices.items():
        if voronoi_diagram_vertex_id != other_voronoi_diagram_vertex_id and voronoi_diagram_vertex_id not in voronoi_diagram_vertex_replacements and other_voronoi_diagram_vertex_id not in voronoi_diagram_vertex_replacements:
            vertices_intersect = TrackGenerator._junction_intersection_check(junction_1 = voronoi_diagram_vertex, junction_2 = other_voronoi_diagram_vertex, junction_diameter = JUNCTION_RADIUS * 2)
            if vertices_intersect:
                vertex_to_keep = random.choice([voronoi_diagram_vertex_id, other_voronoi_diagram_vertex_id])
                vertex_to_replace = other_voronoi_diagram_vertex_id if vertex_to_keep == voronoi_diagram_vertex_id else voronoi_diagram_vertex_id

                voronoi_diagram_vertex_replacements[vertex_to_replace] = vertex_to_keep

(Since voronoi_diagram_vertex and other_voronoi_diagram_vertex are so close together already, either one could resolve the overlap.

random.choice just adds variation to how the resolution happens.)

voronoi_diagram_vertex_replacements is checked when we're converting the diagram into the basis of a Track:

edge_vertex_0 = voronoi_diagram_vertex_replacements.get(voronoi_diagram_edge.vertex0Id, voronoi_diagram_edge.vertex0Id)
edge_vertex_1 = voronoi_diagram_vertex_replacements.get(voronoi_diagram_edge.vertex1Id, voronoi_diagram_edge.vertex1Id)

edge = EdgeVertexInfo(vertex_0_id = edge_vertex_0, vertex_1_id = edge_vertex_1)

The Track basis consequently starts with those overlaps resolved:

(Resolution resulted in the four edges actually meeting at one point.)

The next removal to be done is " contraction ".

" Contraction " takes two vertices and replaces one with the other, like the previous overlap logic.

The difference is that contraction is done in terms of the edges instead of the vertices.

Eligibility for contraction is determined like so:

edges_and_lengths = {}

for voronoi_vertex_id in voronoi_diagram_vertices:
    ..
        ..
            ..
                edge_vertex = voronoi_diagram_vertices[vertex_on_edge_id]
                other_edge_vertex = voronoi_diagram_vertices[other_edge_vertex_id]
                ..
                distance_between_vertices = GraphOps.scaled_graph_point_distance(graph = connections, p1 = edge_vertex, p2 = other_edge_vertex)
                ..
                if distance_between_vertices > 0.0:
                    edges_and_lengths[voronoi_edge_id] = distance_between_vertices

diagram_edge_lengths = numpy.array(tuple(edges_and_lengths.values()))
diagram_edge_min_acceptable_length = numpy.quantile(a = diagram_edge_lengths, q = length_min_quantile)
..
# Use this to track edges already contracted - make sure we don't process them again.
affected_by_contraction = []
..
for edge_id in edge_ids:
    if edge_id not in affected_by_contraction:
        latest_edge = GraphOps.edges_by_id[edge_id]
        latest_edge_length = latest_edge.edge_length

        # Contract an `edge` if it fits the criteria or if it's too small.
        can_be_contracted = TrackGenerator._edge_can_be_contracted(graph = connections, `edge` = latest_edge)
        edge_length_under_minimum = latest_edge_length < diagram_edge_min_acceptable_length

        if can_be_contracted or edge_length_under_minimum:
            ..

An edge will be contracted if its length is < the {length_min_quantile * 100}th quantile of the lengths of all diagram edges, or if TrackGenerator._edge_can_be_contracted() returns True.

@staticmethod
def _edge_can_be_contracted(graph: Graph, edge: GraphEdge) -> bool:
    ..
    all_zero_neighbors_lonely = (num_0_lonely_neighbors and len(num_0_lonely_neighbors) == len(num_0_neighbors_not_1))
    all_one_neighbors_lonely = (num_1_lonely_neighbors and len(num_1_lonely_neighbors) == len(num_1_neighbors_not_0))

    lonely_threshold = 1.0

    # The likeliness of being possibly eligible for contraction is inversely proportional to the number of non-lonely neighbors.
    zero_adjustment = 0.50 if all_zero_neighbors_lonely or not num_0_neighbors else 1 / len (num_0_neighbors)
    one_adjustment = 0.50 if all_one_neighbors_lonely or not num_1_neighbors else 1 / len (num_1_neighbors)

    lonely_threshold-=zero_adjustment
    lonely_threshold-=one_adjustment

    lonely_determinant = random.random()

    if lonely_determinant > lonely_threshold:
        # Eligibility for contraction: " Does the node with at least one non-lonely neighbor have < MAX_NEIGHBORS_DEFAULT_CONTRACTION neighbors?"
        relevant_num_neighbors = len(num_1_neighbors) if all_zero_neighbors_lonely else len(num_0_neighbors)
        relevant_less_than_max = relevant_num_neighbors < MAX_NEIGHBORS_DEFAULT_CONTRACTION

        edge_length = edge.edge_length

        # If relevant_less_than_max, it's much more likely that the `edge` can be contracted.
        contraction_min = max(1 - edge_length, 0.50) if relevant_less_than_max else edge_length + (1 / relevant_num_neighbors)
        contraction_determinant = random.random()

        return contraction_determinant > contraction_min
    else:
        return False

An edge E will be contracted if either

• its length is < the {length_min_quantile * 100}th quantile of the lengths of all diagram edges
• if TrackGenerator._edge_can_be_contracted() chooses it to be contracted

_edge_can_be_contracted's choice criteria:

• Are one or both of its two vertices " lonely "?
  • " lonely " = only forms an edge with the other vertex in the edge being considered
• How few vertices do each of the two vertices make an edge with, not counting the other vertex in the edge?
  • Of those two vertices, which one's " make an edge " count is the lesser?

The fewer vertices that those of E make other edges with, the more likely E is to be chosen for contraction.

If E is chosen, then its vertices A and B are evaluated.

Whichever one of the two makes more edges with " lonely " vertices becomes VR. The other becomes OV.

The set of vertices that make edges with VR are VTR.

Each VT in VTR is connected to OV, and then the edge (VR, OV) is deleted:

Every edge in the diagram is checked like this, unless it was previously reconnected as a (VT, OV) edge.

(That " don't process an already reconnected edge " also applies to VTR reconnections.

Having an edge only be reconnectable once allows for the benefits of contraction while minimizing changes done to the original shape of the Track.)

When creating a (VT, OV) edge, we check if it would intersect with any other existing edge (including other (VT, OV) edges).

If it would, we calculate the intersection point IP and add the edge (IP, OV) instead:

After processing all edges in the diagram:

Sections of the diagram before contraction

and after

show contraction remvoing shorter edges between vertices and creating longer ones.

The last removal to be done is the deletion of the diagram's edges containing subsets that make cycles:

A cycle is a set of edges that could be repeatedly traveled without eventually having to go to another edge not in the cycle.

Cycles would facilitate paths through which traveling from start to end on finite resources could not succeed, but they wouldn't do so in an interesting way.

Removing those " boring " cycles is just a matter of deleting every edge that is both part of a cycle and would not leave a subset of edges disconnected from others if it was removed:

Handling the cycles results in the desired subset of edges, where start and end could be easily picked such that on finite resources, one path would reach end and the others wouldn't.