I use lambda calculus to understand natural language meaning and language change.
322 stories
·
90 followers

Terminal Phase: building a space shooter that runs in your terminal

1 Comment

Yeah you read (and saw, via the above gif) that right! A space shooter! That runs in your terminal! Pew pew pew!

Well it's most of one, anyway. It's a prototype that I built as a test program for Spritely Goblins.

I've satisfied the technical needs I had in building the program; I might still finish it as a game, and it's close enough where making a satisfying game rather than just a short demo is super feasible, but I've decided to see whether or not there's actually enough interest in that at all by leaving that as a milestone on my Patreon. (We're actually getting quite close to meeting it... would be cool if it happened!)

But what am I, a person who is mostly known for work on a federated social web protocol, doing making a game demo, especially for a singleplayer game? Was it just for fun? It turns out it has more to do with my long term plans for the federated social web than it may appear.

And while it would be cool to get something out there that I would be proud of for its entertainment value, in the meanwhile the most interesting aspects of this demo to me are actually the technical ones. I thought I'd walk through what those are in this post, because in a sense it's a preview of some of the stuff ahead in Spritely. (Now that I've written most of this post, I have to add the forewarning that this blogpost wanders a lot, but I hope all the paths it goes down are sufficiently interesting.)

Racket and game development

Before we get to the Spritely stuff, I want to talk about why I think Racket is an underappreciated environment for making games. Well, in a certain sense Racket been advertised for its association with game-making, but in some more obscure ways. Let's review those:

  • Racket has historically been built as an educational teaching-programming environment, for two audiences: middle schoolers, and college freshmen. Both of them to some degree involve using the big-bang "toy" game engine. It is, by default, functional in its design, though you can mix it with imperative constructs. And yet maybe to some that makes it sound like it would be more complicated, but it's very easy to pick up. (DrRacket, Racket's bundled editor, also makes this a lot easier.) If middle schoolers can learn it, so can you.
  • Along those lines, there's a whole book called Realm of Racket that's all about learning to program by making games. It's pretty good!
  • Game studio Naughty Dog has used Racket to build custom in-house tools for their games.
  • Pioneering game developer John Carmack built prototypes for the Oculus Rift using Racket. (It didn't become production code, though John's assessments of Racket's strengths appear to align with my own largely; I was really pleased to see him repost on twitter my blogpost about Racket being an acceptable Python. He did give a caveat, however.)

So, maybe you've already heard about Racket used in a game development context, but despite that I think most people don't really know how to start using Racket as a game development environment. It doesn't help that the toy game engine, big-bang, is slowed down by a lot of dynamic safety checks that are there to help newcomers learn about common errors.

It turns out there are a bunch of really delightful game development tools for Racket, but they aren't very well advertised and don't really have a nice comprehensive tutorial that explains how to get started with them. (I've written up one hastily for a friend; maybe I should polish it up and release it as its own document.) Most of these are written by Racket developer Jay McCarthy, whom I consider to be one of those kind of "mad genius hacker" types. They're fairly lego-like, so here's a portrait of what I consider to be the "Jay McCarthy game development stack":

  • Lux, a functional game engine loop. Really this is basically "big-bang for grown-ups"; the idea is very similar but the implementation is much faster. (It has some weird naming conventions in it though; turns out there's a funny reason for that...)
  • By default Lux ships with a minimal rendering engine based on the Racket drawing toolkit. Combined with (either of) Racket's functional picture combinator libraries (pict or the 2htdp/image library), this can be used to make game prototypes very quickly, but they're still likely to be quite slow. Fortunately, Lux has a clever design by which you can swap out different rendering engines (and input mechanisms) which can compose with it.
  • One of these engines is mode-lambda which has the hilarious tagline of "the best 2d graphics of the 90s, today!" If you're making 2d games, this library is very fast. What's interesting about this library is that it's more or less designed off of the ideas from the Super Nintendo graphics engine (including support for Mode-7 style graphics, the graphic hack that powered games like the Super Nintendo version of Mario Kart). Jay talks about this in his "Get Bonus!" talk from a few years ago. (As a side note, for a while I was confused about Get Bonus's relationship to the rest of the Jay McCarthy stack; at 2018's RacketCon I queried Jay about this and he explained to me that that's more or less the experimental testing grounds for the rest of his libraries, and when the ideas congeal they get factored out. That makes a lot of sense!)
  • Another rendering engine (and useful library in general) is Jay's raart library. This is a functional picture library like pict, but instead of building up raster/vector graphic images, you're building up ascii art. (It turns out that ascii art is a topic of interest for me so I really like raart. Unsurprisingly, this is what's powering Terminal Phase's graphics.)

As I said before, the main problem with these is knowing how to get started. While the reference documentation for each library is quite good, none of them really have a tutorial that show off the core ideas. Fortunately each project does ship with examples in its git repository; I recommend looking at each one. What I did was simply split my editor and type in each example line by line so I could think about what it was doing. But yeah, we really could use a real tutorial for this stuff.

Okay, so 2d graphical and terminal programs are both covered. What about 3d? Well, there's really two options so far:

  • There's a very promising library called Pict3d that does functional 3d combinators. The library is so very cool and I highly, highly recommend you watch the Pict3d RacketCon talk which is hands down one of the coolest videos I've ever seen. If you use DrRacket, you can compose together shapes and not only will they display at the REPL, you can rotate around and view them from different angles interactively. Unfortunately it hasn't seen much love the last few years and it also mostly only provides tools out of the box for very basic geometric primitives. Most people developing 3d games would want to import their meshes and also their skeletal animations and etc etc and Pict3d doesn't really provide any of that yet. I don't think it even has support for textures. It could maybe have those things, but probably needs development help. At the moment it's really optimized for building something with very abstract geometry; a 3d space shooter that resembles the original Star Fox game could be a good fit. (Interestingly my understanding is that Pict3d doesn't really store things as meshes; I think it may store shapes in their abstract math'y form and raytrace on the GPU? I could be wrong about this.)
  • There's also an OpenGL library for Racket but it's very, very low level. (There's also this other OpenGL library but I haven't really looked at it.) However raw OpenGL is so extremely low level that you'll need to build a lot of abstractions on top of it to make it usable for anything.

So that covers the game loop, input, display.

That leaves us with audio and game behavior. I'll admit that I haven't researched audio options sufficiently; rsound seems like a good fit though. (I really need a proper Guix package of this for it to work on my machine for FFI-finding-the-library reasons...)

As for game behavior, that kind of depends on what your game is. When I wrote Racktris I really only had a couple of pieces of state to manage (the grid, where the falling piece was, etc) and it was fairly easy to do it using very basic functional programming constructs (really you're just creating a new version of these objects every time that a tick or input happens). As soon as I tried moving to a game with many independently operating objects doing their own thing, that approach fell apart.

The next thing I tried using was Racket's classes and object system. That was... okay, but it also felt like I was losing out on a lot. Previously I had the pleasant experience that "Woo, yeah! It's all functional!" A functional game engine is nice because returning to a prior snapshot in time is always possible (you can trivially make a game engine where you can rewind time, for instance; great for debugging) and it's much easier to poke and prod at a structure because you aren't changing it, you just are getting it back. Now I lost that feature.

In that conversation I had with Jay at RacketCon 2018, he suggested that I look at his DOS library for game behavior. I won't as quickly recommend this one; it's good for some game designs but the library (particularly the DOS/Win part) is fairly opinionated against objects ("processes") communicating with each other on the same tick; the idea is that each processes only can read what each other wrote on the previous tick. The goal here as I understand it is to eliminate an entire class of bugs and race conditions, but I quickly found that trying to work around the restrictions lead me to creating terrible hacks that were themselves very buggy.

This became really clear to me when I tried to implement a very simple wild west "quick draw" game a-la the Kirby quick draw and Samurai Kirby type games. (All this happened months back, when I was doing the anniversary animation I made earlier this year.) These are very simple games where two players wait for "Draw!" to appear on the screen before they press the button to "fire their gun". Fire first, you win. Fire second, you lose. Fire too early, you lose. Both fire at the same time, you draw. This is a very simple game, but trying to build it on top of DOS/Win (or my DOS/Hurd variant) was extremely hard to do while splitting the judge and players into separate objects. I ended up writing very contorted code that ultimately did communicate on the same tick, but via a layered approach that ended up taking me an hour to track down all the bugs in. I can't imagine scaling it up further.

But DOS had some good ideas, and I got to thinking about how to extend the system to allow for immediate calls, what would it look like? That's when I hit a series of epiphanies which resulted in a big rewrite of the Spritely Goblins codebase (which turned out to make it more useful for programming game behavior in a way that even fits very nicely into the Lux game loop). But I suppose I should really explain the what and why of Spritely Goblins, and how it fits into the larger goals of Spritely.

Terminal Phase and Spritely Goblins and stuff

Spritely Goblins is part of the larger Spritely project. Given Spritely's ambitious goal of "leveling up" the fediverse by extending it into the realm of rich and secure virtual worlds, we have to support distributed programming in a way that assumes a mutually suspicious network. (To get in the right mindset for this, maybe both watch my keynote and Mark Miller's keynote from the ActivityPub conference.) We really want to bake that in at the foundation of our design to build this right.

Thus Spritely Goblins is an asynchronous actor-ish distributed programming system on top of Racket. Kind of like Erlang, but with a focus on object capability security. Most of the good ideas have been taken from the E programming language ("the most interesting programming language you've never heard of"). The only programming environments I would consider viable to build Spritely on top of are ones that have been heavily informed by E, the best other candidate being the stuff Agoric is building on top of Javascript, such as their SwingSet architecture and Jessie (big surprise, since the folks behind E are mostly the folks behind Agoric), or some other more obscure language environments like Monte or, yes, Goblins. (Though, currently despite hanging out in Racket-land, which drinks deeply into the dream of everyone building their own languages, Goblins is just a library. If you want to run code you don't trust though, you'll have to wait until I release Spritely Dungeon, which will be a secure module / language restriction system for Racket. All in due time.)

Spritely Goblins already has some interesting properties:

  • All objects/actors are actually just procedures, waiting to be invoked! All "state" is merely the lexical scope of the enclosed procedure. Upon being invoked, a procedure can both return a value to its invoker (or in asynchronous programming, that fulfills the promise it is listening to) as well as specify what the next version of itself should be (ie, what procedure should be called the next time it handles a message).
  • Objects can only invoke other objects they have a reference to. This, surprisingly, is a sufficient security model as the foundation for everything we need (well, plus sealers/unsealers but I won't get into those here). This is the core observation from Jonathan Rees's A Security Kernel Based on the Lambda Calculus; object capability security is really just everyday programming via argument passing, which pretty much all programmers know how to do. (This applies to modules too, but more on that in a future post.)
  • In most cases, objects live in a "vat". This strange term from the object capability literature really means an event loop. Objects/actors can send messages to other objects in other vats; for the most part it doesn't matter where (on what machine, in what OS process, etc) other objects are when it comes to asynchronous message passing.
  • When asynchronous message passing, information is eventually resolved via promises. (Initially I had promises hidden behind coroutines in the core of the system, but it turns out that opens you to re-entrancy attacks if you aren't very careful. That may come back eventually, but with great care.)
  • While any object can communicate with any other object on any vat via message passing, objects on the same vat can do something that objects on separate vats can't: they can perform immediate calls (ie, something that looks like normal straight-ahead programming code, no coroutines required: you invoke the other object like a procedure, and it returns with a value). It turns out this is needed if you want to implement many interesting transactional things like financial instruments built on top of pure object capabilities. This also is nice for something like a game like Terminal Phase, where we really aren't doing anything asynchronous, are running on a fixed frame rate, and want to be deterministic. But a user should remember that (for important reasons I won't get into in this post) that immediate calls are strictly less universal than asynchronous message passing, since those can only be done between objects in the same vat. It's pleasant that Goblins can support both methods of development, including in an intermixed environment.
  • There is actually a lower level of abstraction than a vat, it turns out! This is something that is different than both E and Agoric's SwingSet I think and maybe even mildly novel; all the core operations (receiving a message, spawning an actor, etc) to operate on the actormap datastructure are exposed to the user. Furthermore, all of these operations are transactional! When using the lower-level actormap, the user receives a new actormap (a "transactormap") which is a delta to the parent actormap (either another transactormap or the root protected weak-hashtable actormap, a "whactormap").
  • This transactionality is really exciting. It means that if something bad happens, we can always roll back to a safe state (or rather, never commit the unsafe state at all). In the default vat, if a message is received and an uncaught exception occurs, the promise is broken, but all the effects caused by interactions from unhandling the message are as if they never occured. (Well that is, as long as we use the "become this procedure" mechanism in Goblins to manage state! If you mutate a variable, you're on your own. A Racket #lang could prevent your users from doing such naughty things if you so care.)
  • It also means that snapshotting an actormap is really easy. Elm used to advertise having a "time traveling debugger" where they showed off Mario running around, and you could reverse time to a previous state. Apparently this was removed but maybe is coming back. Anyway it's trivial to do such a thing with Goblins' actormap, and I built such a (unpublished due to being unpolished) demo.
  • Most users won't work with the actormap though, they'll work with the builtin vat that takes care of all this stuff for them. You can build your own vat, or vat-like tools, though.

Anyway, all the above works and exists. Actors can even speak to each other across vats... though, what's missing so far is the ability to talk to other objects/vats on other machines. That's basically what's next on my agenda, and I know how to do it... it's just a matter of getting the stuff done.

Well, the other thing that's missing is documentation. That's competing for next thing on the agenda.

But why a synchronous game right now?

If the really exciting stuff is the distributed secure programming stuff, why did I stop to do a synchronous non-distributed game on top of Spritely Goblins? Before I plowed ahead, given that the non-distributed aspects still rest on the distributed aspects, I wanted to make sure that the fundamentals of Spritely Goblins were good.

A space shooter is simple enough to implement and using ascii art in a terminal meant I didn't need to spend too much time thinking about graphics (plus it's an interesting area that's under-explored... most terminal-based games are roguelikes or other turn-based games, not real time). Implementing it allowed me to find many areas that could be improved usability-wise in Goblins (indeed, it's been a very active month of development for Goblins). You really know what things are and aren't nice designs by using them.

It's also a great way to identify performance bottlenecks. I calculated that roughly 1 million actor invocations could happen per second on my cheapo laptop... not bad. But that was when the actors didn't update themselves; when it came to the transactional updates, I could only seem to achieve about 65k updates per second. I figured this must be the transactionality, but it turns out it wasn't; the transactionality feature is very cheap. Can you believe that I got a jump from 65k updates per second to 680k updates per second just by switching from a Racket contract to a manual predicate check? (I expected a mild performance hit for using a contract over a manual predicate, but 10x...?) (I also added a feature so you can "recklessly" commit directly to the actormap without transactions... I don't recommend this for all applications, but if you do that you can get up to about 790k updates per second... which means that transactionality adds only about a 17% overhead, which isn't even close to the 10x gap I was seeing.) Anyway, the thing that lead me to looking into that in the first place was doing an experiment where I decided I wanted to see how many objects I could have updating at once. I might not have caught it otherwise. So making a game demo is useful for that kind of thing.

I feel now that I've gotten most of the churn out of that layer of the design out of the way so that I can move forward with the design on the distributed side of things next. That allows me to have tighter focus of things in layers, and I'm happy about that.

What's next?

So with that out of the way, the next task is to work on both the mutually suspicious distributed programming environment and the documentation. I'm not sure in which order, but I guess we'll find out.

I'll do something similar with the distributed programming environment as well... I plan to write something basic which resembles a networked game at this stage to help me ensure that the components work nicely together.

In the meanwhile, Terminal Phase is very close to being a nice game to play, but I'm deciding to leave that as a funding milestone on my Patreon. This is because, as far as my technical roadmap has gone, Terminal Phase has performed the role it needs to play. But it would be fun to have, and I'm sure other people would like to play it as a finished game (heck, I would like to play it as a finished game), but I'd like to know... do people actually care enough about free software games? About this direction of work? Am I on the right track? Not to mention that funding this work is also simply damn hard.

But, at the time of writing we're fairly close, (about 85% of the way there), so maybe it will happen. If it sounds fun to you, maybe pitch in.

But one way or another, I'll have interesting things to announce ahead. Stay tuned here, or follow me on the fediverse or on Twitter if you so prefer.

Onwards and upwards!

Read the whole story
beslayed
1858 days ago
reply
terminal old-school space shooter as preparation for lisp-driven MUDs and distributed social networks
739 days ago
hi there, thanks for your post. it's help for me. http://bit.ly/nulalegends
Share this story
Delete

leah blogs: Ken Thompson's Unix password

2 Comments and 11 Shares

Somewhere around 2014 I found an /etc/passwd file in some dumps of the BSD 3 source tree, containing passwords of all the old timers such as Dennis Ritchie, Ken Thompson, Brian W. Kernighan, Steve Bourne and Bill Joy.

Since the DES-based crypt(3) algorithm used for these hashes is well known to be weak (and limited to at most 8 characters), I thought it would be an easy target to just crack these passwords for fun.

Well known tools for this are john and hashcat.

Quickly, I had cracked a fair deal of these passwords, many of which were very weak. (Curiously, bwk used /.,/.,, which is easy to type on a QWERTY keyboard.)

However, kens password eluded my cracking endeavor. Even an exhaustive search over all lower-case letters and digits took several days (back in 2014) and yielded no result. Since the algorithm was developed by Ken Thompson and Robert Morris, I wondered what’s up there. I also realized, that, compared to other password hashing schemes (such as NTLM), crypt(3) turns out to be quite a bit slower to crack (and perhaps was also less optimized).

Did he really use uppercase letters or even special chars? (A 7-bit exhaustive search would still take over 2 years on a modern GPU.)

The topic came up again earlier this month on The Unix Heritage Society mailing list, and I shared my results and frustration of not being able to break kens password.

Finally, today this secret was resolved by Nigel Williams:

From: Nigel Williams <<a href="mailto:nw@retrocomputingtasmania.com">nw@retrocomputingtasmania.com</a>>
Subject: Re: [TUHS] Recovered /etc/passwd files

ken is done:

ZghOT0eRm4U9s:p/q2-q4!

took 4+ days on an AMD Radeon Vega64 running hashcat at about 930MH/s
during that time (those familiar know the hash-rate fluctuates and
slows down towards the end).

This is a chess move in descriptive notation, and the beginning of many common openings. It fits very well to Ken Thompson’s background in computer chess.

I’m very happy that this mystery has been solved now and I’m pleased of the answer.

[Update 16:29: fix comment on chess.]

NP: Mel Stone—By Now

Read the whole story
beslayed
1865 days ago
reply
.
popular
1888 days ago
reply
Share this story
Delete
1 public comment
jepler
1889 days ago
reply
ha!
Earth, Sol system, Western spiral arm

Pacman in 512 bytes

2 Shares

Pillman is Oscar "Nanochess" Toledo's reimplementation of Pacman ("a game about a yellow man eating pills") in 512 bytes -- small enough to fit in a boot sector -- written in 8088 assembler. (via Four Short Links)

Read the whole story
beslayed
1980 days ago
reply
Share this story
Delete

NewPipe represents the best of FOSS

1 Comment

NewPipe is a free and open-source Android application for browsing & watching YouTube. In my opinion, NewPipe is a perfect case-study in why free & open source software is great and how our values differ from proprietary software in important ways. There’s one simple reason: it’s better than the proprietary YouTube app, in every conceivable way, for free.

NewPipe is better because it’s user-centric software. It exists to make its users lives better, not to enrich its overseers. Because of this, NewPipe has many features which are deliberately omitted from the proprietary app, such as:

  • No advertisements1
  • Playing any video in the background
  • Downloading videos (or their audio tracks alone) to play offline
  • Playing videos in a pop-up player
  • Subscribing to channels without a YouTube account
  • Importing and exporting subscriptions
  • Showing subscriptions in chronological order
  • It supports streaming services other than YouTube!2

YouTube supports some of these… for $12/month. Isn’t that a bit excessive? Other features it doesn’t support at all. On top of that, YouTube is constantly gathering data about you and making decisions which put their interests ahead of yours, whereas NewPipe never phones home and consistently adds new features that put users first. The proprietary app is exploitative of users, and NewPipe is empowering users.

There are a lot of political and philosophical reasons to use & support free and open source software. Sometimes it’s hard to get people on board with FOSS by pitching them these first. NewPipe is a great model because it’s straight up better, and better for reasons that make these philosophical points obvious and poignant. The NewPipe project was started by Christian Schabesberger, is co-maintained by a team of 6, and has been contributed to by over 300 people. You can donate here. NewPipe represents the best of our community. Thanks!

  1. Support your content creators with tools like Liberapay and Patreon! 

  2. At least in theory… basic SoundCloud support is working and more services are coming soon. 

Read the whole story
beslayed
2079 days ago
reply
.
Share this story
Delete

Saturday Morning Breakfast Cereal - Psyops

1 Comment and 8 Shares


Click here to go see the bonus panel!

Hovertext:
Also cats love you with an undying loyalty but don't know how to express it.


Today's News:
Read the whole story
beslayed
2118 days ago
reply
.
Share this story
Delete

Saturday Morning Breakfast Cereal - Unfinished Business

1 Comment and 6 Shares


Click here to go see the bonus panel!

Hovertext:
Tiny apartment. Working for other people all the time. Often cold and malicious. My God... this is where genies come from.


Today's News:
Read the whole story
beslayed
2119 days ago
reply
.
Share this story
Delete
Next Page of Stories