Curves and web servers

2025-Apr-06 (3146 words)

Last week, we started to think about curves. This week, we’ve mostly finished the curves in roads. There is still one thing to be done, which is reducing the radius of the curve to make it fit the space available, but this should not be too difficult, so can wait a bit.

However, to complete the curves, we had to add a clockwise argument to the draw_arc function.

const direction: f32 = if (clockwise) -1 else 1;

var angle: f32 = start;
const sweep: f32 =
    if (clockwise)
        @mod(start - end, std.math.tau)
    else
        @mod(end - start, std.math.tau);

const segments: usize =
    @max(3, @as(usize, @intFromFloat(num * sweep / std.math.tau)));

The important thing here is that the number of segments to draw should be related to the angular sweep from the start angle to the end angle. Once that is calculated, the way we draw the arc is pretty much the same as before.

The CurveUpdateRequired component feeds into the update_curves_system that does all the fun stuff.

fn update_curves_system(iter: *const ng.SystemIterator) void {
    for (iter.entities) |entity| {

First we iterate over all the entities that match this system.

const node = entity.get(com.Node) orelse continue;

const curve = entity.getPtr(com.Curve) orelse continue;

Then we get the node and a mutable curve components from this entity, otherwise we continue to the next entity.

const radius: ng.Vec2 = @splat(curve.radius);

const from_link = curve.from.get(com.Link) orelse return;
const from = if (from_link.start == entity) from_link.end else from_link.start;

const to_link = curve.to.get(com.Link) orelse return;
const to = if (to_link.start == entity) to_link.end else to_link.start;
const from_node = from.get(com.Node) orelse return;
const to_node = to.get(com.Node) orelse return;

We get a bunch of information from the curve. The from and to links are obtained. Note, that the curve could be at the start or end of each link, so we check the start field of the link and use that or the end field.

Finally, we get the Node component for the from and to entities.

At this point, we have all the data we need and we can get to the fun math bit.

const dfrom = ng.normalize(from_node.pos - node.pos);
const dto = ng.normalize(node.pos - to_node.pos);

const a = ng.atan2(dfrom);
const b = ng.atan2(dto);
const c = @mod(a - b, std.math.tau);

dfrom is the normalized vector that points from the from_node to the current node. dto is similar for the current node to the to_node. With these, we can calculate their angles using atan2 on these vectors. And with these angles, we can determine how much these angles ‘curve’.

const side: ng.Vec2 = if (c > std.math.pi) .{ 1, 1 } else .{ -1, -1 };

If the angle curves more than ‘pi’ then we use one or the other side.

const from_a = node.pos + ng.Vec2{ dfrom[1], -dfrom[0] } * radius * side;
const from_b = from_node.pos + ng.Vec2{ dfrom[1], -dfrom[0] } * radius * side;

const to_a = node.pos + ng.Vec2{ dto[1], -dto[0] } * radius * side;
const to_b = to_node.pos + ng.Vec2{ dto[1], -dto[0] } * radius * side;

We then compute two positions per side, from_a and from_b are based on the current node position, the dfrom vector, the radius and the side; to_a and to_b are computed the same way. This gives us two points per line on the correct side of the line, based on the radius of the curve. This allows us to compute the line intersection of these two lines to determine the position of the center of the curve.

curve.center = ng.line_intersection(from_a, from_b, to_a, to_b);

From here, it is really simple. We need to determine where the straight line of the link will be. We can get this point based on the center point of the curve, the tangent of the incoming line, and the side that this is on.

const from_tangent = ng.Vec2{ -dfrom[1], dfrom[0] };
const to_tangent = ng.Vec2{ -dto[1], dto[0] };

const end_link = curve.center + from_tangent * radius * side;

With all this information, we can determine the final parameters for the curve.

curve.start_angle = ng.atan2(from_tangent * side);
curve.end_angle = ng.atan2(to_tangent * side);
curve.clockwise = side[0] < 0;
curve.width = from_link.width;
curve.style = from_link.style;
curve.offset = ng.distance(end_link - node.pos);

entity.remove(com.CurveUpdateRequired);

The curve offset is just the distance from the end_link to the node.pos. And of course, given that we’ve updated the Curve of the entity, we can remove the CurveUpdateRequired component from this entity.

This week, I’ve added a number of new components:

LaneKind
LinkStyle
Junction
OnLink

LaneKind is an enumerated type that describes the different possible types of a lane.

LinkStyle is effectively an array of LaneKind and widths, that determines how different lanes of a link should be drawn and therefore what vehicles are allowed on different lanes. This is used when drawing lanes at the moment.

Junction is an array of links that define the arms that go into a given junction. Remember that Curve is used for nodes that have two links going to it, and Junction is used for nodes that have more than two links.

OnLink is a component that should be able to be placed on a vehicle entity when it is on a link. It encodes the link and the lane that this vehicle is within. This isn’t used at the moment, and I don’t think it is complete yet.

An example of a LinkStyle is used in the code today, using the add_lane function.

const s1 = ng.new();
add_lane(s1, .sidewalk, 2.0);
add_lane(s1, .kerb, 0.1);
add_lane(s1, .traffic_down, 3.2);
add_lane(s1, .center_line, 0.1);
add_lane(s1, .traffic_up, 3.2);
add_lane(s1, .kerb, 0.1);
add_lane(s1, .sidewalk, 2.0);

Here we have a link that has a sidewalk, a kerb, a traffic lane, a center line, another traffic lane, another kerb, and another sidewalk. All very self-explanatory. You can probably see how an editor could be easily built that allows the configuration of such styles to be built.

The add_lane function itself is pretty simple:

fn add_lane(entity: ng.Entity, kind: com.LaneKind, width: f32) void {
    const int_width = to_width(width);
    if (entity.getPtr(com.LinkStyle)) |style| {
        if (style.num_lanes < com.max_lanes) {
            style.kind[style.num_lanes] = kind;
            style.width[style.num_lanes] = int_width;
            style.total_width += int_width;
            style.num_lanes += 1;
        }
    } else {
        var style: com.LinkStyle = undefined;
        style.num_lanes = 1;
        style.kind[0] = kind;
        style.width[0] = int_width;
        style.total_width = int_width;

        entity.set(style);
    }
}

There are two cases to deal with. The first when the entity already has a LinkStyle, where we just add a lane based on the num_lanes field of the component. The second is where the entity does not have a LinkStyle, where we just set a LinkStyle on the entity with a single lane with the correct lane information.

One important aspect of this is that the style doesn’t enforce the width of the link. The link itself still has a width. This is because in many locations, the width of the right of way is typically wider than the lanes. This allows roads to be widened at a later date without requiring any additional land. For example, major roads are typically built within a right of way that is much wider than originally built road. Later, when the road is widened, no additional land is required as the additional lanes can be fit within the existing width of the right of way.

One side effect of the above changes is that the ComponentField struct in the ECS needs to encode an array_len and type_id fields, as well as the additional of a Component kind to the ComponentFieldKind enum. This allows the LinkStyle information to be encoded correctly.

This also meant that instead of just using a single switch on the field.type in the register_component function, we created a get_component_field_kind function, that also returns the array and component information as necessary.

The other big change this week was the creation of a web server within the program. Why create a web-server? Well, firstly, it really makes introspection of the system very easy. If we have the ability to look at an entity’s components and perhaps later even change them, we can debug the program as it is running in real time. Logically, this could also allow a ‘stats’ view on the game when it is running. Wouldn’t it be cool to have a webpage that could be viewed on another device, or another monitor, that shows the population, demand levels, urgent issues that need dealing with, and graphs showing the change in various values.

At the moment, we just have a simple proof of concept web server that can expose the list of all entities, components, and systems. To do this, we are using the zig standard http library. Some say that it is slow and inefficient, but I’ve not noticed that, probably because I’ve incorporated it in to a Thread.Pool for actually processing requests.

pub fn init() !void {
    gpa = std.heap.GeneralPurposeAllocator(.{}){};
    allocator = gpa.allocator();

The init function of the ng.http module, first creates it’s own allocator. Why? Well, we will use this allocator to create the thread pool, and because http connections can be kept alive after a single request has completed, there is no simple way to kill the active threads in the thread pool at program completion. The typical way to use the Thread.Pool is to create a pool, spawn a bunch of tasks to the pool, and then deinit the pool. The problem is that deinit’ing the pool causes all the threads to be joined, which could be a very long time if we have a web browser that just made a request and has kept the connection alive in anticipation of another request about to the made by the user later.

    try pool.init(.{
        .allocator = allocator,
    });

    for (pool.threads) |thread| {
        thread.detach();
    }

We just create the pool, with our local allocator, and then iterate through all the pool’s threads and detach them. This allows the program to exit without having to join the threads.

pub fn deinit() void {
}

The deinit function is empty. Oh no! We are not freeing the memory allocated to the thread pool. Yeah, but we also don’t care that much. The memory allocated to this is very tightly bound, and we trust that the standard library is not leaking memory. Therefore, we can just think ‘yeah, all good here’, not check that the allocator is not leaking, and be happy.

The other block of memory that is allocated at the start is the paths global. This is a `StringHashMap(RequestFunction) that maps a string to a callback function. In the init function, we just add a bunch of paths:

    try paths.put("/", do_index);
    try paths.put("/index.html", do_index);
    try paths.put("/entity", do_entity);
    try paths.put("/component", do_component);
    try paths.put("/system", do_system);

Yeah, that hash map is not free’d either. But it is static for the lifetime of the program.

The web server itself is run in a separate thread.

    http_server_thread = try std.Thread.spawn(.{}, server, .{});
    try http_server_thread.setName("http server");
    http_server_thread.detach();

We detach that thread as well, so that we can just exit whenever we want.

The server function is very simple.

fn server() !void {
    const addr = try std.net.Address.parseIp("127.0.0.1", 4237);
    log.debug("listening at http://{}/ ({})", .{ addr, thread_id });

    var listener = try addr.listen(.{
        .reuse_address = true,
    });

    while (true) {
        const connection = try listener.accept();

        try pool.spawn(process_connection, .{connection});
    }

    listener.deinit();
}

We first create an Address based on parsing an IP address. We use the localhost IPv4 address for security reasons, and the port 4237 which is just a random number.

Then we create a listener, allowing the reuse_address flag to be set. This effectively does a socket, bind, and listen calls.

Then we just enter an endless loop, accepting a connection and spawning the resultant connection off into the thread pool, using the function process_connection. And we have a web-server.


fn process_connection(connection: std.net.Server.Connection) void {
    var buffer: [64 * 1024]u8 = undefined;

    defer connection.stream.close();

    var http_server = std.http.Server.init(connection, &buffer);
    while (true) {
        var request = http_server.receiveHead() catch |err|
            {
                log.err("http request {}", .{err});
                return;
            };

        process_request(&request) catch |err|
            {
                log.err("process request {}", .{err});
                return;
            };
    }
}

The process_connection function inits an http.Server object based on the connection and a static buffer on the stack. This buffer is used to process the headers of a request. 64kB is probably overkill here, but each thread is initialized with 16MB, so I’m not worried about stack overflow here.

We then call the receiveHead function on the http_server. This parses the request header and returns the request. We can then process this request and loop around again. Obviously, if something fails, then we return, closing the connection’s stream as we return.

At this point, we’ve got an http request. We just have to map it to a function that generates an appropriate response. This is where process_request comes in.

fn process_request(request: *std.http.Server.Request) !void {
    number_requests += 1;

    const uri = try std.Uri.parseAfterScheme("http", request.head.target);
    var path_buffer: [256]u8 = undefined;
    const path = std.Uri.percentDecodeBackwards(&path_buffer, uri.path.percent_encoded);

    var response = Response.init(allocator);
    defer response.deinit();

    if (paths.get(path)) |fun| {
        fun(request, &uri, &response);
    } else {
        do_404(request, &uri, &response);
    }

    request.respond(response.buffer.items, .{
        .status = response.status,
        .extra_headers = response.headers.items,
    }) catch |err|
        {
            log.err("request response {}", .{err});
        };

    log.debug("{s} \"{}\" {d:0>3} {} ({})", .{
        @tagName(request.head.method),
        std.zig.fmtEscapes(request.head.target),
        @intFromEnum(response.status),
        response.buffer.items.len,
        std.Thread.getCurrentId(),
    });
}

First we do some accounting, incrementing the number of requests we’ve received. Then we parse the uri of the request.head.target. This is the bit after the GET in the HTTP header. We want the path. The target however is ‘percent encoded’, meaning things like %49 means the character 1. To decode these, we use the percentDecodeBackwards giving it a buffer from the stack.

We have our own Response object, and we create an instance of this. The path that we got from above, we check if it was registered in the paths hash map. If we found a function, we call it with the request, the uri, and the response object. Otherwise, we call a do_404 function with the same parameters.

Finally, we call the request.respond function using the information collected in out response object. And then we log the request.

The target functions are pretty simple.

fn do_404(
    request: *std.http.Server.Request,
    uri: *const std.Uri,
    response: *Response,
) void {
    _ = uri;

    response.set_html();
    response.append(html_header);
    response.append(header_div);
    response.print(http_404_response_text, .{request.head.target});
    response.append(html_footer);
    response.set_status(.not_found);
}

const http_404_response_text =
    \\Invalid request {s}
    \\
;

The do_404 function just says, this is an html response, appending the common html_header, header_div, uses a print function to template the request’s target into the response, and then appends the html_footer. Finally, we set the .not_found status (404). That’s it.

The entity path does a little more than this.

var iter = ng.entity_iterator();
while (iter.next()) |entity| {
    const eid: u32 = @bitCast(entity);
    response.print("<a href=\"/entity?eid={}\">{}</a><br>\n", .{ eid, entity });
}

We have an entity_iterator function exposed by the ecs module that allows us to iterate over all entities. We can then build a list of entities in a list.

Obviously, if we click on one of those links, we have to do something.

var optional_query = parse_query(allocator, uri.query);

if (optional_query) |*query| {
    defer query.deinit();

    if (query.get("eid")) |eid_str| {
        if (parse_int(u32, eid_str)) |eid| {
            const entity: ng.Entity = @bitCast(eid);
            response.print("<b>{}</b><br>\n", .{entity});

            var component_iter = ng.component_iterator();
            while (component_iter.next()) |component| {
                if (component.get_data(entity)) |data| {
                    response.print("<b>{s}</b><br>\n", .{component.name});
                    response.print("{any}<br>\n", .{data});
                }
            }
        }
    }
}

This attempts to parse the uri.query field, which can be optional and therefore returns an optional query object. If we have an query object, then we attempt to get the eid field. If that works, then we parse the string as a u32, and then @bitCast that to an Entity. With that entity information, we can then iterate though all known components, attempting to get_data for that entity for each component. If we have some data, then we can print the component name, and its data.

We could also parse the data returned and print the individual fields of this component data, but that is a project for a later time.

The do_component and do_system functions work in a very similar way.

There are a couple of things that need to be considered before going too far away from this code. Firstly, it might make sense to process these http requests in a system rather than in a separate thread. Logically, we have a bunch of race-conditions in the current code. This is probably something that I will fix next week. This would require a new component that encodes a request and response.

-------------------------------------------------------------------------------
Language                     files          blank        comment           code
-------------------------------------------------------------------------------
Zig                             32           2091           1739          15455
-------------------------------------------------------------------------------

We are up to 15455 lines of code. An additional 885 lines of code for this week. More than last week, but still pretty low. I have been thinking about how the simulation of the world will happen, so I might spend some time working on starting to build this up. The current thoughts are that we have a bunch of entities with the Person component. These have one or move Skills, that encode the skills that a person has. Each person can have say 16 skills and each skill can go from 1 to 255. This means that we need a Skill enumeration for each skill. Obviously, we need to give each person a name, sex, age, and health. I’m sure there will be other components that make sense.

One thing that might be useful here is to have a Random component that is just a random 128-bit integer. We can then take a subset of this value to use for various things. When two persons create a new baby person, their random value would be a random selection of bits from the father and the opposite selection of bits from the mother. If we use these bits to drive visual characteristics like eye color, hair color, height, etc., then we can have children looking similar one or both of their parents.

A Process is just a set of inputs, skills required, and outputs. A person that performs a process would transform the inputs to the outputs based on how close their skill is to 255. If they have a very low skill, then the process may be very inefficient. If it is 255, then it the process would be very efficient. Obviously, as persons perform a process, their skill level for the skills they use will increase. This allows the encoding of apprenticeships, but also education. A person who is at school will learn skills without producing anything.

We can also default the set of skills that a person has based on their Random value.

Obviously, if we have persons that can be educated, we need schools, and they need to have persons attending them. Therefore, we need to have a component that encodes AttendingSchool. If the person is too old to be in education, then they’d have EmployedBy. This obviously then requires that we have School and Company components on entities.

Let’s see if we can build this next week, and then also drive a few new webpages to expose some summary information from the simulation.

« Roads, junctions, curves

Names »

Fourth, Game