Walking Your Frog to the Library

Typing in VR has always been a painful experience. Aim a virtual laser at a keyboard nearly the width of your vision from too far away to be precise. If you're lucky you get two lasers instead of one, and can hunt and peck twice as fast. But be careful: moving quickly means missing letters, which means trying to point between letters extremely precisely with your extremely imprecise laser to go back, or mashing the virtual arrow keys just a few… more…… times……… while trying to look at the desktop, allowing your aim away to drift away. The controller movement from pulling the trigger to click causes your laser to jump downward, meaning you either miss, or the runtime has to freeze your cursor in place for a moment to try to compensate. This results in the opposite problem, causing the cursor to teleport a bit after you press the key and messing up your travel to the next key.

Typing on a smartphone has always been a painful experience. I never learned T9; people tell me it was great. Tactile feedback must have been nice. For me, my first mobile typing experience was an iPod touch (remember those?) and an autocorrect system which can best be described as "technically better than nothing". Hunt and peck, with two lasers thumbs, while looking away from buttons you can't feel…

One solution to this problem was the introduction of swipe input: rather than individual key inputs, allow the user to draw the path between the letters in the word. The original Swype patent¹ was filed in 2003 and variations of the system have since been added as first-party features to every major mobile platform.

Analogous problems beg analogous solutions, and bringing something similar to VR isn't a novel idea. Meta added a hand-tracking swipe keyboard to the Quest in v56 back in 2023. For PCVR, controllers are still the preferred input method for most games. So, I set out to to create a swipe keyboard for SteamVR.

How hard could it be?

A prototype called BetterKeyboard

Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.

jwz

When exploring a new space it's helpful to get something, anything working as quickly as possible. All the assumptions you have about how something works or how a solution should feel are probably wrong. Solving the problem in the dumbest way possible can eliminate a lot of these assumptions very quickly.

So I wrote a regex.

Actually, I wrote some code that wrote a regex. (That's three problems, for those keeping score.) The way to convert a swipe to letters seemed pretty obvious: look at all the points along the path from start to finish², figure out which keys it touched, and then look through the dictionary for words that have the matching letters in that order.

It can't be every key along the path since it crosses over all the keys between the ones the user meant to hit. The original Swype algorithm tries to detect sharp angles, which tells you which keys the user was actually aiming at. Seems like a pretty good idea, let's do that. Doing this reliably ended up being an ongoing battle, but it was working Well Enough at this stage.

So now after a swipe (say for "potato") we have a regex that looks something like this:

   ^p.*t.*a.*t.*o$

Match that against every word in english and tada, suggestions.

For the small example vocabulary I was using at the time, this actually worked remarkably well and allowed me to move on to building out the UI and exploring how it felt to use in VR. Long term though, it's not nearly robust enough. Users don't draw perfectly straight paths, they don't always draw sharp corners, and they don't always even hit the first and last keys they intended.

Dog Frog walking

After spending quite a long time thinking about the problem of picking out the letters that a path "meant" to hit and getting nowhere in particular, inspiration arrived:

Instead of turning a path into letters, why not turn letters into paths?

I wasn't looking for a text comparison algorithm after all, but a path comparison algorithm. This is a well-studied area. A very brief research session later I found an ideal match: Fréchet distance.

More specifically, discrete Fréchet distance. Even more specifically, the algorithm described in a conveniently-timed 2024 paper by Nis Meinert³. This optimized version runs in linear memory, ideal for working over arbitrary user input. This also avoids any dynamic allocation, speeding things up further. Reference implementations are available, which made implementing it as a Godot extension trivial.

The standard description of the Fréchet distance is thus: Imagine a person walking their dog on a leash. The dog is a free to be a dog and wander a bit off the path walked by the owner, but neither of them ever reverse course. The Fréchet distance is the longest the dog ever stretches the leash during the walk.

Discrete Fréchet is more like a frog walking another frog: instead of walking smoothly along a path, each of them hop from point to point. It's best to not think about the metaphor too much.

Teaching a frog to read

Applying Fréchet to swipe input, then, relies on the observation that each word has a fairly unique journey across the keyboard. If you take the path that the user draws and calculate the Fréchet distance to an ideal path representing each word in your vocabulary, the one with the lowest distance should be the word that the user meant.

Generating ideal paths is very straightforward: create a line consisting of the centerpoint of each key in the order they appear in the word. For this application, sampling the user input at a (nearly) fixed cadence produces the best results for angle detection. Since we know this cadence, we can then interpolate the ideal path to have points at roughly the same distance to give Fréchet an ideal comparison surface. The only downside of this approach is the sheer number of points; it uses quite a lot of memory without additional optimization.

There are a couple places where this approach falls over and requires supplementation with other metrics:

• Identical paths: "ah"/"agh" traverse exactly the same points.
• Technically different, but appear identical to Fréchet due to overlapping points: with "to"/"too" the latter has a zero-length segment.

Most of the exceptions consist of fairly short words; the chances of identical traversal fall off dramatically with number of letters. The actual difficulties come instead from the inherent inaccuracy of user input, especially in VR. The act of drawing in midair with an unsupported hand and no tactile feedback leads to extremely shaky and inaccurate lines, which are often more similar to words that the user didn't intend at all than the one they were aiming for.

The lines are so shaky in fact that some amount of smoothing became necessary. For this I'm currently feeding input through the eternally useful 1€ Filter⁴.

Caffienating your frog

Fréchet works surprisingly well on its own, but even the optimized version of the algorithm is too slow to actually apply to every single word each swipe. A few hundred milliseconds is the limit before the user starts feeling like the keyboard is slowing them down between each word.

The most effective single optimization has been to treat the first and last points as a filter, discarding any words that don't have endpoints in roughly the appropriate spots on the keyboard. This can't be the exact letters as users will often miss by a key or so due to rapidly adjusting their position after finishing the previous word, or overshoot the last key as they start releasing the trigger. Instead, the start and end are treated as clusters of keys: if the user started on "s" they could have meant any of "w", "a", "s", "d"¸ etc. This reduces how effective the optimization is at speeding up results, but is necessary to avoid discarding valid suggestions and is still a massive improvement over checking every single word.

There are lots of other tiny optimizations that all add up to a speedy experience, but this article is long enough already.

Future research directions

An interesting realization during development was that the words I expected to be slow were almost never the words that were actually slow. Intuitively you'd expect longer words to be much worse with the linear Fréchet, but in fact the layout of the keyboard matters much more. Short words can have very long paths in a layout like QWERTY which was specifically designed to keep common letters far apart. This raises at least two questions for further exploration:

• What is the impact of layout on average swipe comparison time?
• Does average comparison time correlate with suggestion accuracy? Negatively or positively?

My intuition is that QWERTY may actually be an ideal swipe layout for the same reason it was ideal for preventing typewriter jams: positioning the most common letters chaotically lowers the chance of words having very similar paths. On the other hand, since each pair of letters remains in the same position, maybe it doesn't have an impact at all.

Reflections on problem solving

I had a beta tester call the swipe algorithm "uncanny", which is about as validating as I could have hoped for. Choosing a more traditional algorithm over machine learning in 2026 may seem strange to a lot of people, and I was very aware of that as I was making it. ML just wasn't feasible as a one-person startup: no one shares their data sets⁵, and I didn't have the resources to go have a bunch of actual humans swipe and label data for me. Sometimes you just have to choose the tool you can actually operate, even if another one seems to be a better fit for the job.

The other lesson from this project is that sometimes the best solutions come from taking a step back and looking the problem from another direction. Or six other directions. It took me far longer than I would have liked to arrive at the working algorithm, but the time was well spent because the entire product would be useless if it were even slightly less good. Sometimes moving faster is not better, and time invested in thinking is much more valuable than time spent cranking out code that ultimately solves the wrong problem. Now more than ever it's important to know when to do which thing⁶.

And now the ad break!

All of the above research has been applied to some development, in Liminetics' second product Scribeam. On top of swipe input, it aims to solve as many of the pain points of VR keyboards as possible:

• Integrates directly with the VRChat chatbox.
• Instead of being huge for larger aim targets, it's small and spawns at the tip of your controller for more precise movements.⁷
• Instead of having to shift your position to where the keyboard is to type with both arms, you can summon it right where your arm is, flick your wrist a few times, and put it away again.
• Makes use of the variety of inputs VR controllers provide with fully customizable SteamVR Input support
• Works alongside your existing desktop overlay tools when you need to control your PC.

The roadmap includes things like custom macropads, racing/flying simulator mode, and more game chat integrations.

If you found this work interesting and would like to support future research into improving social VR, or you're a social VR user who has used a keyboard even one time and knows exactly the pain I'm talking about, Scribeam is coming soon on Steam. If you're a developer, streamer, or The One In The Friend Group Who Explains VR, you may also like VRInputSpy. It allows you to capture or stream SteamVR input in real time as you play, rendered on the controller models in-headset or to OBS.

Even if all you can do is share this article, it's greatly appreciated. Liminetics is a fully bootstrapped company dedicated to improving social VR, and we're just getting started. Thanks for reading!