If you’ve ever tried making your own roguelike, you’ve likely encountered all sorts of strange-looking 1960s algorithms for doing geometry. Bresenham’s line algorithm is the most famous, but you often see people talking about “DDA lines” among other things. Hopefully, you found your way to the excellent Red Blob Games article on the subject, which describes a modern implementation in detail, with lovely interactive examples.

A line algorithm used to menace an innocent watervine farmer

Perhaps this left you with unanswered questions. These vintage functions look so different from each other, but they all seem to do the same thing!

This post is structured as an ahistorical journey back through time. We start with the floating point algorithm given by Red Blob, which is optimal on modern computers, and end at Bresenham’s 1962 algorithm which uses pure integer arithmetic, as was optimal on the hardware of the day. We can then consider the other functions as steps along our imagined refactoring process, replacing floats piece by piece with integers.

The aim is to present these functions in a unified style so they can be easily compared, and to try and give a little intuition as to what is going on with the geometry.

PureRng, my newest creation, is a random number generator library for rust. The twist is that each generator gets consumed after outputting a single value. To get a new value you must instantiate a new generator, with a new seed. A nice API is provided to ensure this isn’t as much hassle as it sounds - a hash function is employed to generate seeds from arbitrary data.

Below is my minimal NixOS configuration for a Raspberry Pi 4B. It includes everything needed, ready to be loaded from a generic flake.nix.

First enable binfmt on your build machine:

boot.binfmt.emulatedSystems = [ "aarch64-linux" ];

Then build the SD card image with:

nix build '.#nixosConfigurations.YOUR_HOSTNAME.config.system.build.sdImage'

…and rebuild remotely with:

nixos-rebuild switch --flake .#YOUR_HOSTNAME --target-host RASPI_IP --use-remote-sudo

Below is the configuration.nix, with notes on how this all works after the fold:

{ lib, pkgs, modulesPath, ... }:
{
  imports = [
    # This module installs the firmware
    "${modulesPath}/installer/sd-card/sd-image-aarch64.nix"
  ];

  nix.settings = {
    # This is needed to allow building remotely
    trusted-users = [ "YOUR_USERNAME" ];

    # The nix-community cache has aarch64 builds of unfree packages,
    # which aren't in the normal cache
    substituters = [
      "https://nix-community.cachix.org"
    ];
    trusted-public-keys = [
      "nix-community.cachix.org-1:mB9FSh9qf2dCimDSUo8Zy7bkq5CX+/rkCWyvRCYg3Fs="
    ];
  };

  nixpkgs = {
    hostPlatform = "aarch64-linux";
    config = {
      allowUnfree = true;
    };
  };

  # These options make the sd card image build faster
  boot.supportedFilesystems.zfs = lib.mkForce false;
  sdImage.compressImage = false;

  networking = {
    # Set your hostname
    hostName = "YOUR_HOSTNAME";
    useNetworkd = true;
  };

  # Replace networkd with NetworkManager at your discretion
  systemd = {
    network = {
      enable = true;

      networks."10-lan" = {
        # This is the correct interface name on my raspi 4b
        matchConfig.Name = "end0";

        networkConfig.DHCP = "yes";
        linkConfig.RequiredForOnline = "routable";
      };
    };
  };

  # Add your username and ssh key
  users.users.YOUR_USERNAME = {
    isNormalUser = true;
    extraGroups = [ "wheel" ];
    openssh.authorizedKeys.keys = [ "YOUR_SSH_PUBLIC_KEY" ];
  };

  # Our user doesn't have a password, so we let them
  # do sudo without one
  security.sudo.wheelNeedsPassword = false;

  services = {
    openssh.enable = true;
  };

  # Set your timezone
  time.timeZone = "YOUR_TIMEZONE";

  environment.systemPackages = with pkgs; [
    libraspberrypi
    raspberrypi-eeprom
  ];

  hardware.enableRedistributableFirmware = true;

  system.stateVersion = "24.11";
}

Some notes:

Here’s how to do it:

function current_dir() {
    local current_dir=$PWD
    if [[ $current_dir == $HOME ]]; then
        current_dir="~"
    else
        current_dir=${current_dir##*/}
    fi
    
    echo $current_dir
}

function change_tab_title() {
    local title=$1
    command nohup zellij action rename-tab $title >/dev/null 2>&1
}

function set_tab_to_working_dir() {
    local result=$?
    local title=$(current_dir)
    # uncomment the following to show the exit code after a failed command
    # if [[ $result -gt 0 ]]; then
    #     title="$title [$result]" 
    # fi

    change_tab_title $title
}

function set_tab_to_command_line() {
    local cmdline=$1
    change_tab_title $cmdline
}

if [[ -n $ZELLIJ ]]; then
    add-zsh-hook precmd set_tab_to_working_dir
    add-zsh-hook preexec set_tab_to_command_line
fi

Not actually the running process, but the last command line. This does unfortunately add a couple of milliseconds of lag but it’s fairly imperceptible. If you can make this happen faster, please comment on the gist.

Mole with hard hat - Stable Diffusion 2024

A quick note on the mullvad exit node integration feature offered by tailscale.

Tailscale doesn’t allow you to select a different UDP port for the connection to the mullvad node! It’s hardcoded to port 51820.

This is in contrast to the official mullvad client, which lets you use port 53 or a custom port of your choice.

If you’re using this feature in the mullvad client to tunnel out of a network which blocks common VPN ports like 51820, the tailscale integration won’t work! And there will be nothing you can do about it. Tailscale’s relay network doesn’t come into play here, the client just seems content to leave your machine unable to route any packets at all. Presumably there is debug logging to be found somewhere.

There’s an issue open on the tailscale client github repo - go and vote for it so I can tunnel out via mullvad’s servers when I’m in the library rather than a spare VPS.