Principle:CARLA simulator Carla Road Network Graph Construction

Knowledge Sources	CARLA Simulator CARLA Documentation Bast et al., "Route Planning in Transportation Networks", Algorithm Engineering, Springer, 2016 OpenDRIVE Specification, ASAM, Rev. 1.6, 2021
Domains	Graph Theory, Road Networks, Autonomous Driving
Last Updated	2026-02-15 00:00 GMT

Overview

Road Network Graph Construction is the process of converting a CARLA map's road topology -- defined by OpenDRIVE lane segments -- into a weighted directed graph suitable for pathfinding algorithms. The resulting networkx.DiGraph encodes the connectivity of the road network, where nodes represent waypoint positions and edges represent drivable road segments annotated with distance, road type, and intersection status.

Description

CARLA maps are internally described using the OpenDRIVE standard, which defines roads, lanes, junctions, and their geometric properties. However, OpenDRIVE's representation is designed for continuous geometry, not discrete graph search. The GlobalRoutePlanner bridges this gap through a four-phase construction pipeline:

1. _build_topology(): Queries the CARLA map for its topology -- a list of (start_waypoint, end_waypoint) pairs representing minimal lane segments. Each segment is interpolated at the configured sampling resolution to produce a dense sequence of waypoints. The result is a dictionary mapping segment indices to their entry/exit waypoints and interpolated path.

1. _build_graph(): Converts the topology dictionary into a networkx.DiGraph. Each unique waypoint position becomes a node (identified by (road_id, section_id, lane_id)). Directed edges connect entry to exit waypoints within each segment, weighted by Euclidean distance. Exit-to-entry connections between consecutive segments form the road continuity.

1. _find_loose_ends(): Identifies dangling exit waypoints that lack outgoing connections (e.g., at the edges of the mapped area or due to discretization artifacts). For each loose end, the method queries waypoint.next() to find the closest continuation and adds a bridging edge.

1. _lane_change_link(): Augments the graph with lateral edges representing legal lane changes. For each edge in the existing graph, if the underlying waypoint allows a left or right lane change, a new edge is added connecting the current segment to the adjacent lane's corresponding segment, annotated with RoadOption.CHANGELANELEFT or RoadOption.CHANGELANERIGHT.

Usage

Use road network graph construction when you need to:

• Compute shortest or fastest routes between arbitrary locations in a CARLA map
• Analyze road network connectivity (e.g., identify unreachable areas, count intersections)
• Provide a route backbone for local planners and behavior agents
• Study lane-change opportunities and their impact on routing

Theoretical Basis

Graph Representation of Road Networks

A road network is modeled as a weighted directed graph G = (V, E, w) where:

• V = set of nodes, each corresponding to a waypoint at a specific (road_id, section_id, lane_id)
• E = set of directed edges, representing drivable connections between waypoints
• w: E -> R+ = edge weight function, typically Euclidean distance between node positions

Edge Types

Edge Type	RoadOption	Description
Lane segment	LANEFOLLOW	Connects entry to exit of a single lane segment
Segment continuation	LANEFOLLOW	Connects exit of one segment to entry of the next
Left lane change	CHANGELANELEFT	Lateral connection to the adjacent left lane
Right lane change	CHANGELANERIGHT	Lateral connection to the adjacent right lane
Loose-end bridge	LANEFOLLOW	Artificial connection to fix dangling endpoints

Sampling Resolution

The sampling resolution parameter r (in meters) controls the density of interpolated waypoints along each lane segment. A smaller r produces a finer graph that more closely follows road curvature but increases graph size and construction time:

For each topology segment (wp_start, wp_end):
    path = [wp_start]
    current = wp_start
    while distance(current, wp_end) > r:
        current = current.next(r)
        path.append(current)
    path.append(wp_end)

Typical values range from 1.0 m (high fidelity) to 4.0 m (fast construction). The default in CARLA agents is 2.0 m.

Complexity

For a map with N lane segments and average segment length L meters with sampling resolution r:

• Number of nodes: O(N * L / r)
• Number of edges: O(N * L / r) for lane-following + O(N) for lane-change links
• Construction time: O(N * L / r) -- dominated by waypoint interpolation

Related Pages

Implemented By

• Implementation:CARLA_simulator_Carla_GlobalRoutePlanner_Init