Using Heap’s Algorithm to Brute Force a Puzzle in Myst IV: Revelation

December 16th, 2024

I have been playing through Myst IV: Revelation recently. In it, I came across a puzzle. There was an interface upon which I could enter 5 symbols, of which there were 8 choices for each. I had already narrowed down the possibilities to 5 of those 8 symbols, and I knew that the answer would be some permutation of them (aka, that no symbol would be repeated).

I had already tried all the obvious things that came to mind and was not finding much luck. Looking back, after finding the actual solution, the actual solution was one of the things I had explicitly written down as something I had tried in my notes, but I must have made a mistake, and so I never decided to try it again as my notes said I had already tried it. Oops. In any case, at the time, I was at the end of my wits, and I decided to brute-force it. (I was determined not to look up any solutions – I’m not a cheater!)

Read the rest of this entry »

Tags: , , , ,
Posted in Technology | No Comments »

Can you Use Slang with WebGL?

December 9th, 2024

I recently learned about Shader Slang, having appeared on Khronos’s home page as a Khronos-sponsored project, which is apparently a recent development. It appears to be designed mostly for desktop graphics APIs, and particularly recent hyper-explicit APIs like DX12 and Vulkan. WebGL uses GLSL, and GLSL isn’t on the list of supported targets (and OpenGL is described as “only limited support”), but… can I still use Slang?

Short answer: Yes.

Read the rest of this entry »

Tags: , ,
Posted in Game Development | No Comments »

Use Lists for Reliable Messaging in Valkey/Redis

December 2nd, 2024

One of the supported data stores for my game’s backend is Valkey or Redis. Data storage is straightforward, but real-time notifications of updates to games is less so. My initial plan had been to use Valkey’s pub/sub functionality, but reliability has been top of mind for me, and there is a problem with pub/sub in this case.

Suppose that there are two game servers running. In my architecture, players can be connected to any server and play the same game – there is no need for players of the same game to be connected to the same server. There is a temporary blip in connectivity from one of the game servers to Valkey. Meanwhile, the player makes a move on the other game server. Valkey gets the updated data, and the game server issues a publish to Valkey, but with the first game server being disconnected at the moment, there is no subscription to receive the message. The first game server then reconnects, and due to ioredis’s auto-resubscribe functionality, seamlessly resubscribes. The server doesn’t notice anything has gone wrong. But the message has been dropped, and one of the players doesn’t see an update. This isn’t good.

I was toying with the idea that upon Valkey reconnect, a game server could poll all the games it currently has players on to see if any games have changed in the mean time. However, that could be a lot of games, and it would be best not to flood Valkey with activity immediately after a reconnect.

Instead, I was looking for a reliable alternative to pub/sub. The answer is easy: lists.

Read the rest of this entry »

Tags: , ,
Posted in Technology | No Comments »

Experiences Drinking from the Firehose

November 25th, 2024

For about a year now, I’ve been running a service consuming and archiving the contents of the Bluesky firehose. I had a reason for this, but I haven’t gotten around to actually using the data for that purpose yet, so I’ll hold off on explaining that for now. But in the mean time, I figured I’d collect the data, and the operational experience in doing so has been somewhat interesting to me.

First, some background: Bluesky is a social network similar to Twitter. Users post short messages, consisting of text, photos, or videos. Posts can be in reply to other posts. Users can like posts. Users have a profile, and can follow or block other users. There is more to it, but this is 90% of the core functionality.

Unlike Twitter, Bluesky is (mostly) decentralized. Bluesky calls its architecture ATProto. In ATProto, user data is stored authoritatively in “repositories” on Personal Data Servers (PDSes). Repositories contain records. Records can be freely created or deleted by the user owning the repository. Users are identified by Decentralized Identifiers (DIDs). In practice, everyone uses the PLC (“placeholder”) DID method, which relies on a central server at https://plc.directory. The PLC DID server associates a user with their PDS.

All data in a PDS is freely accessible. Any part of a repository may be fetched at any time; a repository may be fetched in its entirety all at once; and it is also possible to subscribe for all changes on a PDS regardless of repository.

Read the rest of this entry »

Tags: , , , , , , , , , , , , , ,
Posted in Technology | No Comments »

Using FoundationDB Without the Package

November 18th, 2024

Huge disclaimer: I don’t recommend running FoundationDB in production this way. This is mostly for if you want to do some testing.

Suppose you have come into possession of some FoundationDB binaries. (For example, having built FoundationDB from source and peeking in the build/bin directory.) The documentation only describes how you use FoundationDB installed system-wide from a package. This is a smart way to run it for production workloads, but when you’re just testing, that’s a big commitment.

To get a cluster running, there’s a couple things you’ll need:

  • A cluster file.
  • A data directory.
  • A log directory.
  • (If using fdbmonitor) a configuration file.

The packaging deals with all this for you, but if we’re going without the packaging, you’ll need to deal with some of these yourself.

Read the rest of this entry »

Tags:
Posted in Technology | No Comments »

ICANON Splits Your Lines

November 11th, 2024

I don’t think anyone would be particularly surprised to hear that the terminal driver, with all of its rich legacy, has some quirks that are not necessarily obvious. While attempting to demonstrate something else in a draft post, I came across this handy, but unexpected, behavior.

Suppose you call read on stdin with a reasonably large buffer size. Your language’s standard library might do this for you, for example, when you tell it to read a line. In that case, you’d expect it to give you everything up ’till the new-line, then stow away the rest internally for the next time you ask to read a line. That’s because when you read a file, or a pipe, or nearly any kind of file-like thing, it will hand you all the data it’s got, which could consist of multiple lines.

At a TTY, how do you end up with multiple lines? Simple: If you weren’t reading for some time, multiple lines could have been entered in that time. Say, the program was sleeping, during which time you enter two lines, and then the program wakes and does a read. By analogy with other devices, you might expect it to return all completed lines (e.g. everything not still available for editing) up to the buffer size you specify, right?

In a normal terminal mode, surprisingly (to me), no! You will be fed one line at a time.

Read the rest of this entry »

Tags: , ,
Posted in Technology | No Comments »

In-Process Performance Counters on Linux

November 4th, 2024

perf stat is a great boon to understanding a program’s performance. It lets you set up performance counters before running a program, and then shows you the resulting performance counter metrics after running.

Sometimes it can be more helpful to instrument just a part of a program’s execution, rather than the entire program’s execution. In my most recent case, what I wanted to measure was simple: The number of instructions executed.

libjevents, part of Andi Kleen’s pmu-tools project (also home of the indispensable toplev tool), provides a helpful abstraction for doing so. The “self profiling” section of the README explains how it’s done.

Read the rest of this entry »

Tags: , , ,
Posted in Technology | No Comments »

socat for Protocol Snooping

October 28th, 2024

While doing some debugging on my WebSocket implementation, I really wanted to snoop on some traffic going between the client and server. There’s are standard ways to snoop on traffic at the operating system level, for example tcpdump and Wireshark. Those can be a little heavy-weight though. If you control where you’re connecting to, there are easier options.

socat is a “Swiss army knife” for plumbing network streams together. One of the simplest uses of it is to have it listen, and then when it receives an incoming connection, to connect somewhere else and pipe traffic back and forth:

socat tcp-listen:8080,bind=localhost tcp:example.com:80

Read the rest of this entry »

Tags: , , , ,
Posted in Technology | No Comments »

Skybox or Skyplane?

October 21st, 2024

One of the more obvious ways to handle a background in a game is to have a very large box surrounding the player – the skybox. Along with that, you might have a ground or water plane that similarly extends out a great distance.

Problem is, you want to use the depth buffer as best as you can. To do that, you want to set the far plane as near as possible. If you need to set the far plane out really far to accommodate your ground and skybox, you’re wasting a ton of the representable range of the depth buffer. And if you try to get around this by making the skybox and ground plane end closer to the eye, its visibly squarish nature begins to become unsightly.

There’s an easy solution to this, at least conceptually. Rather than trying to make the skybox and ground real objects in space, make them a quad that appears at the very back of NDC space. It can be the last thing you draw, filling in any gaps not covered by other objects. In this role, you don’t care if it writes a sensible depth that can occlude other objects (in fact, you never do really want it to occlude anything else) – just shove it all the way into the back.

Read the rest of this entry »

Tags:
Posted in Game Development | No Comments »

Tracking Down Compiler Issues with C-Reduce

October 14th, 2024

When I first came across the issue described in the previous post, I was baffled. I tried to reduce the problem, but whenever I tried to manually copy out bits I thought could be the problem, the problem went away. The “building up” solution not working, I started to try at the “breaking down” solution, starting from the full code that demonstrated the problem and deleting irrelevant code. But this was in a file more than a thousand lines long, and the broken code had many dependencies on other parts of this file, making stripping it down difficult.

But I had a tool in my toolbox that could help. I’ve been a fan of delta debugging for a long time. With delta debugging, you define an “interestingness” criterion, and provide this, along with a large but interesting input to a reducer tool, and it will attempt to reduce the code to the smallest example that is still interesting per the provided criterion.

Read the rest of this entry »

Tags: , ,
Posted in Technology | No Comments »

« Older Entries