|
play | source |
This is a game project that was done as part of the 2010 International Lisp Games Expo by me, Eric Bergstrome (ericbb on irc).
The game is a top-down shooter in which a triangle navigates a map of squares and shoots circles with a laser. The circles charge the triangle on sight and the game is ended either successfully, when the triangle eliminates all circles, or unsuccessfully, when a circle reaches the triangle. It was written in the final four days of the expo.
The preceeding twenty-six days were used to create the interactive Lisp programming system that was used to host the game and its development.
The system is comprised primarily of a virtual machine, written in Javascript, and a compiler for a Lisp dialect written in the language itself, which targets the machine code of the virtual machine.
The virtual machine is designed to support concurrency constructs like those found in Erlang. For example, there are primitive functions, "spawn", "spawnlink", "link", "kill", "exit", and "send". The "receive" feature is supported by a dedicated instruction in the machine code. Independent processes are scheduled to run concurrently.
Browser features like input events, DOM inspection and modification, and asynchronous HTTP communication are imported into the system.
Questions and comments are welcome: norstrulde@gmail.com.
The basic project goal was to make a game in 30 days using Lisp. To suit my own interests, I decided that my game would be a top-down shooter built using a Lisp of my own making and I decided that the whole thing would run within the browser.
Something that was on my mind at the outset of the project was the fact that I had consistently found the code for successful games to be made of simple stuff. I saw an emphasis on consistency and pragmatism and what seemed to be a de-emphasis on cleverness.
So I went into the expo with the goal of making a new language but not getting stuck in any mires of complexity. I suppose I decided to adopt the Worse is Better approach to design.
Current source line counts are 1966 lines of Lisp code and 1938 lines of Javascript code. There are 795 lines of html and 80 lines of css. There is also a 33 line webserver I wrote in Go to support development.
I worked on the project every day for 30 days straight and, since the expo deadline had been extended, I did some small bug fixing and tweaks after the original deadline.
The tools I used included:
Using existing designs. I tried not to be inventive. The virtual machine and compiler are based on designs from Paradigms of Artificial Intelligence Programming (PAIP) and the multiprocessing is based on beautifully simple descriptions found in Programming Erlang. Without those two books, there would have been no hope of me getting as far as I did with the language.
Working every day and keeping a log. I decided on day one to keep a daily log. This encouraged me to make sure I had something to write in the log by the end of each day. It took commitment to the project but it also meant that I suffered very little from mental "cache misses".
Hanging out on IRC. To anyone thinking about doing a small self-directed game project: join a community of hackers like #lispgames and your project will be twice as fun.
Getting caught up in the language design aspect. I had a great time toying around with my little Lisp.
Getting caught up in the language design aspect. It could have been worse -- I did manage to finish a couple of simple games after all -- but my goals going in were shifted more toward game development than what ended up happening. There were two key events: the moment I realized that I could get a self-hosting system and the moment I decided to implement message-passing concurrency. Neither of those goals were part of my initial plan but I couldn't resist. So I have a self-hosted compiler and a cool concurrency system but the games would probably have been better if I had stuck with simpler designs.
Last-minute performance optimization. Certainly, premature optimization is much worse but the few frustrating moments I had in this project were generally during the last two day crunch when I realized that things I really wanted to do were bogging down even in Chrome. Because I was running out of time, I wanted to push forward with features but what I really should have done was get myself some timing statistics.
Generally, I was a little slow deciding to make support tools. It can be a fine balance determining when to step back and automate and when to just push on. In optimization tools and server maintenance tools I waited a bit too long.
Under-use of git. I get a lot more mileage from git when I use it better. There were a few times when I had to back out a fair bit of work simply because I forgot to use small commits or branches.
The biggest risks I took revolved around exciting language features. These turned out to use up a lot of time but also really paid off in making the project fun.
I kept game development risks down pretty well because I knew I didn't have much time. For the shooter, I used a few small geometry hacks that I knew would be fairly easy for me and avoided commiting to anything fancy in the artistic department, which I knew could have been large time-sinks without making the game much more fun.
One other risk I avoided was tackling multiplayer. I did start looking into using node.js on my Linux server but no easy wins presented themselves in terms of game design so I abandoned those ambitions fairly quickly.
Generally, I added language features and cut game features. As I've said already, these changes to the plan were neither clearly good nor clearly bad choices. Given the nature of the project, I let my own interests drive directional changes on the fly. The only real constraints were that I had to have an actual game by the deadline and it had to be written in Lisp. I didn't do a lot of planning anyway.
I need to be more attentive to how I'm using git. When I tackle some experimental idea, I really need to think about opening a branch. And I still forget sometimes to keep commits self-contained.
There is a certain point at which a language really takes off. For my language, the moment I finished quasiquote expansion and started writing the essential macros of Lisp there was an explosion of Lisp code that became possible and the language really came alive.
A self-hosting language can be a mind-bending thing. The interdependencies start to run deep and hide themselves if you are not careful. The way I bind macros into the global environment is still buggy and something I worked around. My next self-hosted system I do will definitely take into account some things I learned this time around.
Game expos are great fun. This is the first one I have done and it won't be the last.
Here is a daily log of my work on this project.
Got enemies to chase when they can see the player and to die when the laser hits them. Sometimes, they don't die when they should -- pesky circles -- and that's a bug; but I'm out of time and must release it as is.
I also spent a fair bit of time today trying to optimize. I didn't have a lot of success but I did get rid of a bad screen flicker problem by buffering draw operations and executing them all -- for a given frame -- within a single JS callback. As it is, the game is not playable within Firefox on my laptop but Chrome and Safari do run it at a decent framerate.
Finished collision detection, made a map, a shootable laser, and inert enemies.
Added polygon drawing methods and started working on tile maps.
Started thinking about graphics. Read about HTML canvas transforms and images. Wrote a little complex-number library and a goofy top-down map editor thing.
Considered doing a server-side version. I think I will do it -- using node.js -- but not until after the expo. Fixed a few concurrency bugs.
Finished pong and added some related examples: you can change the ball color and you can restart the game; both from the REPL.
Split Lisp source into multiple files so compiling and loading is faster for typical small changes. Added lexical environment display to backtraces. Did some thinking about scene graph design. Started making pong.
Housecleaning and some documentation.
Another revision of the site and a few long-overdue workflow improvements.
I wrote a tiny HTTP server in Go which runs locally and allows me to use HTTP PUT to write compiled fasl files directly from the REPL. I also wrote an Emacs function "ebb-sexp-to-clipboard", which I've bound to a key chord so that I can quickly transfer expressions from my editor to the browser textarea without using the mouse. Lastly, I changed the process crash reporting so that a backtrace is included in the report that gets sent to monitoring processes.
Got the loading process into the scheduler loop. Now all lisp code is scheduled uniformly.
Added timeouts to the "receive" form based on how it is done in Erlang. Forgot that the timeout value need not be a compile-time constant. So only literal values are working for now.
Added process linking and exit signals. For example, the REPL now monitors its subprocesses so that if an exception is raised, the subprocess will die and the monitor process will receive a message that indicates which process died and what was the reason.
Added a function (showprocs) which writes the current list of processes with their identifiers and their states; either "running" or "waiting". Since the backtrace function now accepts a PID, you can use the process list to examine a fair bit about what is going on. Still, there is plenty of room for improvement in the introspection department.
Added inter-process messaging. Messages are lists and are matched at the receiving end based on the symbol in the first position. I am trying to emulate Erlang's messaging but I don't intend to do full pattern matching. Processes are identified by symbols and sends are asynchronous.
I reworked the REPL using the new concurrency tools. It is now possible to evaluate an expression that crashes its abstract machine without losing access to the REPL. The reason is that I spawn a new process for each click of the "evaluate" button and if the expression causes a crash, only the new process is affected. It is even possible to examine the stack trace for the crashed process right from the REPL.
Discovered that calling setTimeout at high frequencies can really slow down a javascript program.
Switched from synchronous to asynchronous loading.
Added concurrency primitives: spawn, receive. Spawned processes cannot communicate with each other yet but they can receive messages related to browser events. I put a red box and a green box on the canvas that can be moved with the keyboard.
Took a day to mostly just tidy the code up. I did add a few macros: when, unless, dotimes. I also added the special form, evalwhen.
Now that I'm using fasl files, it's easier to get confused by when things happen. Without evalwhen, it had become impossible to define a macro and then use it in the process of compiling forms appearing later in the same file. This tactic was something I had been using heavily in bringing the system up. Just look at the first few macros of the lisp file. The pattern is still there but works for a different reason. It wouldn't work for newly defined macros or changes to existing macros.
Now that I've added evalwhen, you can achieve the old behavior
using (evalwhen (compile load) ...). Interestingly, you
can define a macro that is only available during compilation by using
(evalwhen (compile) ...). The default behavior is
equivalent to (evalwhen (load) ...). The final alternative,
(evalwhen () ...) is essentially a way to comment out a
body of code.
Fairly major rewrite of the abstract machine. Changed the instruction representation and restructured the central loop. Also, the function that is the entry point into machine execution can now return while the machine is still "running". When called again, the machine will continue where it left off. This feature will be important as I work on concurrency and debugging features over the next few days.
Implemented a backtrace function by reifying machine state, walking the stack and disassembling suspended functions. It doesn't show function names or lisp code but it is still nice to have.
Ran into a tricky situation with macro redefinition and realized that I should probably add an eval-when form to work around the problem.
Compilation is really slow. Seems like I'll need to find some major optimizations if I'm going to have any hope of implementing a real-time game. On the other hand, it's cool that I now have enough work for the system that I can actually notice the delays.
Fixed a fasl loading bug that turned out to be due to "" being a false value in javascript. The bootstrapped version of the compiler can now handle strings without crashing.
Removed the compiler and assembler from the javascript code. The system is now completely reliant on the lisp versions.
Added string support. Translated reader, printer, and disassembler into lisp. Created reader and writer functions for a new -- highly inefficient -- fasl format.
Added a couple more alist-related functions. Specifically, "new", "clone", and "set_".
Realized that the language can now express its own compiler! So, of course, I translated the compiler into my new lisp and got it to produce code that successfully executed on the abstract machine. This possibility was something that caught me by surprise. Now I am thinking about creating an object file format ("fasl" in lisp parlance) so I can drop the javascript version of the compiler.
Wrote a disassembler after revising the code I use to generate and display instructions. The disassembler can be used to show the abstract machine code for a given function value. It can also be used to see the abstract machine code for lambda expressions defined within a given function.
For example: Use (dis chain) first to see the code for the chain function. At instruction 2, there is a FN instruction. So you can call (dis chain 2) to see the code for that lambda expression. You can continue further since the displayed code shows a FN instruction at instruction 1. Call (dis chain 2 1) to see the code for the associated lambda. In this way, all code can be inspected.
I also wrote some functions for using association lists in a way similar to how I use javascript objects. I haven't added a clone function, but it is clear how that can be done. I added a macro so that:
(_ foo bar (baz (cons 1 2) 4))
does something like the javascript code:
foo.bar.baz(cons(1, 2), 4);
Removed the moveable box that I created on the first day. It was implemented using javascript. Soon I will have interactive lisp code intead.
Added a couple of drawing primitives to lisp. I put an example of their use at the end of the lisp source file.
Attached an event handler to the input box so that you can trigger evaluation by pressing enter.
Worked on the look of the site. Fonts, colors, layout, etc. The site now has two columns. The new right-hand column includes an interactive REPL and lists the lisp code that will grow to define the game.
Big day today!
I completed two of the major remaining language features: quasiquote (aka backtick) and dotted lists (both for literal data and as argument lists).
It is now easy to add macros. I've written some already: define, defmac, cond, and, quasiquote, let, and letrec.
I also wrote some important functions today: list, length, append, map.
Got primitive functions and macros working. I'm not open-coding any primitives yet but I probably will want to do that eventually.
I decided to keep macros in the normal global namespace. To test macroexpansion, you can do this,
> (apply let '(((x 5)) (+ x x))) => ((lambda (x) (+ x x)) 5)
Implemented the "apply" function. Interestingly, I had to change the abstract machine slightly first. The original required that the number of arguments in a call be known at compile time.
All special forms can now be compiled and executed.
Started on the compiler.
Typed in much of the abstract machine code I'm stealing from Norvig's book; translating directly from common lisp into javascript.
Eventually, I'll have to break the loop into chunks so that event handlers get a chance to run. For now it's written to run until hitting a "HALT" instruction.
Reviewed the PAIP scheme abstract machine. Thought about page layout.
Added sexp parsing, which required defining some lisp types. Numbers, symbols, conses, and nil are expressible but functions are not, yet.
Sketched out the loading process. The lisp file is fetched using XHR, "read", "compiled", and "executed". Those quoted steps are just stubs for now.
Added a "reset" button so that I can change the lisp code on the server and press "reset" instead of refreshing the page.
Put some thought into pause/resume and whether to do the parsing in emacs or in javascript.
Added the canvas and enough javascript to be able to move a little box around.
I'm going to make a game for
ILGE 2010.
I'll use a tiny scheme dialect that I'll throw together. It will run in the browser. Graphics will use HTML5 canvas. There may even be sound.
Gameplay will involve running around a map shooting AI bots. View will be top-down.
Coding style will be grungy. Plenty of global variables, plenty of mutable state, no fancy object system, no coroutines, no design patterns. Closures are allowed.
Due 30 Jul 2010.