Robin's Thoughts

Roads, junctions, curves

(1822 words)

I spent most of last week creating a new graphics library for drawing lines, circles, and quadratic bezier curves. This week, I’m ignoring the bezier curve bit whilst drawing roads. This is the problem with going too far ahead with the implementing side of things and not far enough with the thinking side of things.

I want to be able to draw roadways. And paths, canals, railways, and other transport infrastructure. I thought we would be doing this using quadratic bezier curves, just like most other games would do. However, I’m not currently convinced that this is the best way. You see we need to do three different things:

This means that we need to have the concept of nodes, links, and junctions.

How do we connect just two nodes together? We use a curve.

This also means that we can have multiple junction types just by defining different components and then applying them to nodes as required.

Using the ECS system, we can just define a Node, Link, Curve, PriorityJunction, SignalizedJunction, RoundaboutJunction, etc.

To illustrate this, this is the current definition of a curve:

pub const Curve = extern struct {
    from: ng.Entity,
    to: ng.Entity,
    radius: f32,

    center: ng.Vec2 = .{ 0, 0 },
    start_angle: f32 = 0,
    end_angle: f32 = 0,

    offset: f32 = 0,
};

However, let’s not jump ahead too much. Mainly, because the majority of the code required to compute and draw curves is not written yet!

We’ve added the ability to click and drag nodes around. We’ve done that by adding in a map_selected_state and map_selected global states.

The processing of these is very simple. When we press the left mouse button, we do:

.left => {
    const map_pos = state.camera.to_world(event.pos);
    if (find_nearest_node(map_pos)) |entity| {
        state.map_selected = entity;
    } else if (find_nearest_link(map_pos)) |entity| {
        state.map_selected = entity;
    } else {
        state.map_selected = null;
    }
    state.map_selected_click = event.pos;
    state.map_selected_state = .clicked;
},

This finds the nearest node, or link to the position that was clicked on the map and then saves that away in global state. We also note that we just .clicked this.

Later, in the mouse_move function, we can check if we want to drag the node:

if (state.map_selected_state == .clicked) {
    const delta = @abs(state.map_selected_click - event.pos);

    if (delta[0] > 8 or delta[1] > 8) {
        state.map_selected_state = .dragging;
    }
}

We only start dragging if we moved the mouse more than 8 pixels in the x or y direction. This stops the dragging of nodes when you have a low quality mouse that will move a little when you click.

When if we are dragging, we move the node itself.

if (state.map_selected_state == .dragging) {
    const world_position = state.camera.to_world(event.pos);
    if (state.map_selected) |entity| {
        if (entity.getPtr(com.Node)) |node| {
            node.pos = world_position;
        }
    }
}

This just gets the current world position of the mouse and if the map_selected has a Node then we update the position of that node to be that world position. That is the easy part…

    var iter = state.links_query.iterator();
    while (iter.next()) |link_entity| {
        if (link_entity.get(com.Link)) |link| {
            if (link.start == entity) {
                link_entity.set(com.Construction{ .steps = 10 });
                if (link.start.has(com.Curve)) {
                    link.start.set(com.CurveUpdateRequired{});
                }
                if (link.end.has(com.Curve)) {
                    link.end.set(com.CurveUpdateRequired{});
                }
            }
            if (link.end == entity) {
                link_entity.set(com.Construction{ .steps = 10 });
                if (link.start.has(com.Curve)) {
                    link.start.set(com.CurveUpdateRequired{});
                }
                if (link.end.has(com.Curve)) {
                    link.end.set(com.CurveUpdateRequired{});
                }
            }
        }
    }

We then iterate over all links looking to see which links connect with this node. If the start or end is the node we just moved, then we do a couple of things. First, we set the Construction steps to 10, which simulates the time required to rebuild the link given that it has just moved. Next, we check to see if the two nodes, the start and end nodes of the link, have a Curve, and set the CurveUpdateRequired component to that node.

What is a CurveUpdateRequired component? It has no data, and we’ve not discussed it before. The key to this is the code below:

    ng.register_system(
        .{
            .name = "update_curves",
            .phase = .update,
        },
        update_curves_system,
        .{
            com.CurveUpdateRequired,
            *com.Curve,
        },
    );

We have an update_curves_system that will iterate over any entity that has a CurveUpdateRequired component and a Curve component.

fn update_curves_system(iter: *const ng.SystemIterator) void {
    for (iter.entities) |entity| {
        if (entity.getPtr(com.Curve)) |curve| {
            curve.offset = ng.rand() * 10;
        }
        entity.remove(com.CurveUpdateRequired);
    }
}

This is not completed yet, there a lot more math that needs to go into here, but the concept is illustrated. In the update_curves_system, we iterate over all the entities, get a mutable pointer to the Curve and we can then update that we necessary, and we also remove the CurveUpdateRequired component from that entity.

Do you see what’s just happened? We’ve passed a message from one part of the process (the mouse movement code) to another part (the update curves system). Once we’ve dealt with this message, we remove it and we won’t process this again, unless it is set on this device again.

This concept of using the entity component system for passing messages around is really neat. It associates the message with a specific entity. The message can include additional information, for example, I’m considering adding in the two links into this CurveUpdateRequired message to keep the processing low on the processing side. It also allows only processing a limited number of such messages each frame. Do we need to update all the curves in a single loop in a single frame, or could we just do one per frame, or up to 1 ms of work per frame? Probably not. But it is a place to optimize in the future.

Of course, we’ve added code to find the nearest node or link. These are brute force algorithms at the moment, because we don’t need to optimize them yet. For example:

fn find_nearest_node(pos: ng.Vec2) ?ng.Entity {
    var iter = state.nodes_query.iterator();
    var best_entity: ?ng.Entity = null;
    var best_dist: f32 = 0;
    while (iter.next()) |entity| {
        if (entity.get(com.Node)) |node| {
            const dist = ng.distance(node.pos - pos);
            if (dist <= 5 and (best_entity == null or dist < best_dist)) {
                best_dist = dist;
                best_entity = entity;
            }
        }
    }
    return best_entity;
}

The 5 only allows you to select a node within a 5 meter radius circle around the node. This should really be some changeable constant rather than a hard coded special value, but things can be updated later.

I’ve also added the concept of a query into the ECS. This is just like a system, except they are not run automatically every time we progress a frame. Whilst working on this, I noticed that some entities were not being associated with queries (and systems) during the update_system_entities function that goes through all entities that have had their set of components changed, and update the systems and now queries that are associated with.

The problem was that a zig HashMap with a void value, or in other words we were using this as a set, would give us back a value when we called get_data on that component. This was especially annoying because our message component CurveUpdateRequired has a void value and the nodes were not being added to the system. The function has_component_type was therefore changed from using the get_data function to the contains function. This is logically the better function to use anyway, but also fixed this bug.

There were some minor additions to the math library. Mainly a line_intersection function along with some simple dot, distance, distance_squared, lerp, get_curve_position, and distance_to_line functions. These all take Vec2 parameters and do the obvious things. For example, the link intersection does:

pub fn line_intersection(p1: Vec2, p2: Vec2, p3: Vec2, p4: Vec2) Vec2 {
    const det = (p1[0] - p2[0]) * (p3[1] - p4[1]) -
                (p1[1] - p2[1]) * (p3[0] - p4[0]);

    const a = p1[0] * p2[1] - p1[1] * p2[0];
    const b = p3[0] * p4[1] - p3[1] * p4[0];

    const px1 = a * (p3[0] - p4[0]);
    const px2 = b * (p1[0] - p2[0]);

    const py1 = a * (p3[1] - p4[1]);
    const py2 = b * (p1[1] - p2[1]);

    const px = (px1 - px2) / det;
    const py = (py1 - py2) / det;
    return ng.Vec2{ px, py };
}

Looking at this now, we probably need to check if det is zero and handle that case.

-------------------------------------------------------------------------------
Language                     files          blank        comment           code
-------------------------------------------------------------------------------
Zig                             31           1918           1648          14670
-------------------------------------------------------------------------------

We are up to 14670 lines of code, only about 500 more than last week. But in other news, we now have a fridge/freezer that works, and a car that also works. Yah!

Next week, should be all about getting the curves between links calculating and drawing properly. I might then give some consideration to getting vehicles moving along those roads as well. This might require lanes, directional traffic. This probably will require textures to be applied to the links and curves. I doubt we’ll get to junctions just yet, but just getting vehicles moving along a road would be nice. Of course, this then implies that we should decide what to do with roads that have been moved, or it has a Construction component. Can we wait until all vehicles have moved off the road before the construction starts? Better start thinking about how to do that? Should we have an occupied flag on the Link and Curve?

Flags are not normally recommended in an ECS, because you can just have a zero-length component that is applied to the entity that serves the same purpose. However, each time the construction system looks at a link, it has to delay construction based on occupancy, potentially remove the component Occupied only for this component to be added back again in another system in the very same frame. This might work, if we can make the staging system super smart, but I don’t really like super-smart being the backbone of something that can be dumb. Anyway, that’s a decision for the next week or two.

Fourth, Game