Qwerty War released

It’s actually been up for a while now at http://www.qwertywar.com/.

As is typical of software, final cleanup took me longer than expected, a week perhaps. One problem still irks me: it’s too slow. While it runs reasonably well on my desktop machines, not so much on my my high-resolution devices. And this after already spending a day or two profiling and optimizing.

Poor performance on the tablets and phones doesn’t bother me too much, since it’s a typing game, and who would play with a touchscreen anyway? My high-dpi Lenovo laptop, however, also does badly. I suspect the problem is partly thanks to poor Nvidia support on Linux.

Still, the performance problems surprised me because it just doesn’t seem like there really is all that much happening on the screen. The game draws a few shapes and renders a handful of different 32×32 sprites in maybe a few dozen different positions.

Sometimes, though, you just need to call something good enough and go play Qwerty War.

Comefrom0x10: unary minus

In the original Comefrome0x10 grammar, I skipped unary minus. In retrospect, its presence has important consequences that I should have considered earlier, so unary minus made me reverse a couple decisions.

Line continuation

Comefrom0x10 uses newlines to delimit statements, which is fairly common in modern languages. What is not so common is that a standalone expression has a side effect: it writes to program output, as in PowerShell. This makes hello world succinct:

'hello world'

Prior to adding the unary minus operator, I allowed line continuation if an operator started a line, so these would be equivalent:

x = 2 + 3

x = 2
  + 3

But unary minus causes problems. These lines could be either “3 - 2” or “print 3; print -2“:

3
-2

I could continue to allow operators at the end of a line to indicate line continuation, but I’ve never liked end-of-line line markers for continuation as they are too hard to see. Comefrom0x10, therefore, now has no facility at all for line continuation. I will figure it out when I have a burning need.

Concatenation

Unary minus causes a second problem, when interacting with cf0x10’s concatenation behavior.

In cf0x10, space is the concatenation operator: “'foo' 'bar' is 'foobar' # true“. Originally, I allowed the concatenation space to be optional, so “name'@'domain” would be equivalent to “name '@' domain“.

Enter unary minus. In most languages, all three of these expressions mean “a minus b”, but in the original cf0x10 grammar, they could indicate either concatenation with negative b or subtraction:

a -b
a-b
a - b

Other languages do allow space concatenation, but normally only for literals. In Python, for example:

>>> 'a' 'b'
'ab'
>>> a, b = 'a', 'b'
>>> a b # ILLEGAL in Python, but LEGAL in cf0x10
SyntaxError: invalid syntax

In css, space is even an operator and “-” can appear at the beginning of an identifier. The css grammar, avoids ambiguity, however, by making “-” mathematical only when followed by a number, as in “-2px” versus “-moz-example“; “--foo” is illegal. Css gets away with this because it has no variables, making the operand’s type known during parsing.

Since the cf0x10 parser cannot know operand types, Comefrom0x10 has two options. It could decide whether to subtract or concatenate at runtime, or it could make the grammar a bit less forgiving of how you use spaces. Spacing is already significant, so, on balance, I think that making the spacing rules restrictive is the more clear:

a -b # concatenation
a-b # subtraction
a - b # subtraction
a- b # syntax error

The rules are that concatenation requires at least one space and unary minus cannot be followed by a space.

Comefrom0x10: day 5

A few days have passed building a brand new language. About a day and a half getting most of the grammar worked out and another day and a half building the guts of the interpreter. But now cf0x10 programs can basically run, albeit with a limited set of operators and without entirely correctly scope resolution.

Of course, I spent much of the time on the interpreter working out the ideal semantics for the comefrom statement, a much neglected field of computer science. The natural question is, “what happens when more than one statement comes from a single other statement?”

In Intercal, this is simply an error. Though that might seem like a cowardly evasion, it can simply be credited to Intercal’s being a lower-level language: the Intercal programmer needs to handle these situations explicitly by abstaining and so forth.

Comefrom0x10, on the other hand, is a high-level language designed to minimize runtime errors, so Comefrom0x10 has well-defined semantics for all variations of coming from a place.

First, eligible comefroms receive control in the order they appear in the source. Alone, however, this rule causes trouble breaking out of blocks. Consider this program that prints the Fibonacci sequence up to ten thousand:

fib
  b = 1
  comefrom fib
  a
  next_b = a + b
  a = b
  b = next_b

  comefrom fib if a > 10000

If the first comefrom took precedence, the loop would never end. Changing the first line to “comefrom fib if a < 10000” would fix the problem, but require reconfiguring how the variables a and b get swapped. I think the existing version is more clear: last-first wins allows a common idiom of placing your exit conditions at the end of a block.

The first exception to source order, therefore, is that when multiple comefroms are eligible within the same block, the last one wins.

There are other exceptions, but that’s another article.

Comefrom0x10: day 1

Today, I am finally creating a language.

Inspired by Come Here and Come From, Comefrom0x10, pronounced “Come from sixteen”, will be a modern language based entirely around the much-maligned “come from” control structure.

I am writing the first interpreter in Python. I was hoping to have a grammar worked out by the end of day one, but failed to make significant progress. Originally, I thought I would use a parsing expression grammar, but soon reverted to Backus-Naur. The trouble is that I want cf0x10 to include syntactic indentation (as it’s a modern, Pythonic language). This means that I need indent and dedent constructions, which parsing expression grammars can’t easily express.

So, I decide to switch to lalr. As a bonus, using lalr, will, of course, let people easily build million-line cf0x10 programs without worrying about slow compile times.

The Python parser generator landscape is surprisingly bleak. Many of the parser generators available are abandoned or half-assed. Ply seems to be the only real contender. There are two main problems with Ply: first, its mechanism of embedding grammar specification within docstrings makes the parser obnoxiously verbose; second, it doesn’t provide an obvious way to generate a parser that does not require installing Ply.

Ply has a very strong point though: it provides outstanding debug output for diagnosing problems with your grammar. I’ll just live with the verbosity; I might try PlyPlus if it gets too annoying. As far as removing the Ply dependency goes, I’ll wait until the Enterprise customers for cf0x10 want to fork out money to fund writing a build script so I can use the generated parse table without depending on Ply.

Ply’s scanner generator has the usual Lex push and pop state capabilities, plus it makes saving arbitrary lexer state easy. I, therefore, spend a good deal of day one trying to avoid hand-writing a lexer. As usual, this is a waste of time.

The insurmountable problem is that Ply helpfully stops you from providing regexes that match an empty string, presumably assuming they would cause infinite loops. In addition to syntactic indentation, Comefrom0x10 uses syntactically significant blank lines and without either a facility for pushback or empty-matching regex, it is very hard to write a sensible grammar. But that’s another article.

So finally, I just decide to hand-write the lexer and begin to make progress near the end of day one.

Qwerty War: day 5

On day five, I plan to get the leaderboard persistence built and deployed: the only part of the project that requires a database back end. I figure that I’ll build this with Django and deploy on Heroku.

So I switch from JavaScript to Python and naturally this requires that I instate my traditional key customization that maps shift+space to underscore. Previously, I’ve used xmodmap, but the going wisdom around the Internet is that xkb is the newer, better way to do things.

hours pass

I can finally type underscores without over-extending my pinky, so I turn back to the problem of Django. Django normally uses a great many subdirectories to organize things and make them portable, which is great for medium to large applications, but annoying for something as small as Qwerty War. The article Django as a micro-framework is a good start to really stripping Django down, but it’s significantly out of date. To bring it up to date with Django latest, the main thing to realize is the django-admin command line should now read thus:

django-admin runserver --settings settings --pythonpath .

From there, you’ll find there are a series of errors that are all pretty self-explanatory and easily fixed. I skip most middleware, but keep the csrf and clickjacking parts.

Soon enough, Django is serving up my static files: I haven’t built any database stuff yet, but I figure I should try deplying the static bits on Heroku. First hurdle: Heroku wants me to install its command-line tool by piping stuff from wget into a shell. The script would install Heroku’s apt repository and go from there.

Isn’t the whole deployment done with git anyway? Why do I need the heroku command line interface? Much less another dpkg repo. It turns out this is easy enough, if undocumented

  1. Add an ssh public key to your account via the Web gui
  2. Use the Web gui to create a project
  3. Push to the project using the funky-looking location git@heroku.com:[appname].git

Mercurial, of course, does not speak Git natively, so I decide to try to the hg-git extension. Its homepage says to install via the old easy_install. Not an auspicious start, but ok, I just try pip instead, and in Pythonic fashion, it just works.

So far, so good. The first push via hg-git succeeds, but naturally, the app fails to start on Heroku, as I haven’t yet created a Procfile or wsgi.py. I add them, push again, and… nothing. Mercurial reports there are no changes to push. Did my first push really work at all? I figure I’ll try cloning the repo from Heroku to check, using actual Git…. time passes (but much less than spent on xkb) …I figure the problem is that either hg-git or Heroku or both dislike that I pushed some rather large files. In particular, I included a full history of my edits to the binary blobs that are audio files, plus the originals in .wav and .flac format.

Fair enough, pushing all that stuff is pretty wasteful anyway. I abandon the hg-git extension and opt for a simple shell script that deploys via Git proper. It works, so on day five, I at least have a deployable application, if still very much in development mode and without a database.

Qwerty War: day 4

On day four, I add sound effects. There are only a two essential types of sounds:

  • Gunshot when the player fires
  • Explosion when an enemy blows up

I could add some other effects, such as bullets whizzing by; a sound when powerups appear would be nice and maybe an alarm when health gets low. The original has music, but I think that is over-achieving for this little project.

There are a plenty of free explosion and gunshot sounds online; I pick some from freesound.org, and tweak and cut them in Audacity.

I’m playing all sounds with the Web Audio api. To make them interesting, I add a few variations that may actually be more trouble then they are worth: decreasing volume and delay depending on distance from the player.

What does turn out to be important is not playing too many explosions at once; many simultaneous explosions cause clipping and many very close together just sound like noise, so I introduce a brief delay between explosions when the player hits a bomb. This turns out to be a nice effect. Even with this, though, many explosions simply add up to too loud and still clip, so I use Web Audio to insert a compressor and that mostly gets levels under control.

Next problem is that the gunshots contain some hissing noise as they fade out; it is barely noticeable for a single shot, but becomes irritating when many shots are happening close together. A low-pass filter on the tail of the sounds cleans it up.

Once all the explosion sounds are working, I realize I have a performance problem. At first, I think that Web Audio is causing it, but a few minutes with a profiler tell me that it actually is drawing all the explosion animations when a large bomb goes off. I hadn’t noticed it before only because I did not have so many enemies on the screen at once.

Well, optimization will be a problem for day five.

Qwerty War: days 2 and 3

For day 2 of the Qwerty War project, I wanted to get all the visuals roughed in, though without final sprites for the player and enemies. It turns out this actually took two days.

I considered doing the whole thing by moving divs about the screen, or even svg everywhere, but the obvious choice is canvas, so best not to overthink it.

User controls – word input, health meter and score – are still regular html elements overlaid on the canvas. At first, I thought I would do the same with the enemy words: reposition the table cells from day one’s text-only version to follow sprites around, but soon decided drawing the text with canvas api would be simpler.

More structural changes came from the rework necessary to allow for delay while bullets reached the targets. This may not have been strictly necessary: originally, I planned to keep reactions instantaneous. When the player shoots, for example, the enemy would explode immediately. I would then animate the bullet motion toward the enemy. Since the bullet would whiz over in less than a tenth of second, the delay would not be noticeable.

As I was starting, though, this felt wrong. The code made more sense if I associated the explosion with a bullet impact, rather than the shot. If I’m inclined in the future, this should allow features like slow motion.

Bullets are the only effect not built with sprites: they are just lines with gradients to fade out toward the shooter. The “collision detection”, if you can call it that, is easy. Since every moving element is arranged radially from the player, it’s a simple matter of checking whether the bullet traveled far enough to hit its target, which causes the target to explode.

Explosions, of course, are the fun part. The nifty http://explosiongenerator.com/ gives me the look I want. There are three levels of enemies in the game, from words length three up to five, so I just need an explosion per enemy type. Stopping the explosion a few frames from the end gives a nice debris and blood splatter to paint on the background. By randomizing the rotation of each explosion and its ending frame, just three explosions look pretty organic.

Explosion generator gives you a download full of .png images; I used ImageMagick to combine them into a single image suitable for animation:

montage images/explosion0{000..191..4}.png -geometry +0+0 -tile 12x4 -background none explosion1.png

That squirly brace stuff is a handy shell trick to pick every fourth image from a desired range. From there I just use JavaScript to animate these frames.

So far, the game on day 3 looks pretty good, but a few details bother me:

  • Enemies run over each other, sometimes obscuring the words you need to see. This also happens in the original Qwerty Warriors. It’s not too much of a problem – you could even say it makes you think a little more strategically about who to shoot – but it seems unpolished. Would be nice to put in collision detection so enemies don’t run each other over.
  • The end is abrupt. It might be a neat effect to finish animating all bullets in flight and explosions after the player dies.
  • Bullet animations are not entirely satisfying. They are functional, but not exciting.
  • As I was testing, I realized muzzle flashes are a nice feature to show you who is shooting at you. I put them in as just one extra sprite for each of the player and enemy types, flash on or off, but there probably should be a few frames to that animation.
  • The bullet trail extends through the shooter. I mentally justify that by saying it’s the stuff coming out of the rear of a rocket or something, but actually it just looks odd.

Nonetheless, it looks decent and is becoming fun to play. Day four will be for sound effects.

Qwerty War: day 1

“Qwerty War” is what I’m calling a small typing game inspired by Qwerty Warriors.

The concept is that you are a keyboard-slinging warrior surrounded by never-ending waves of enemies. There is no escape, but you’ll take as many of them down with you as you can. Qwerty Warriors is my favorite typing game; since it surrounds you with enemies, it has an intensity that other typing games lack. Its remake, Qwerty Warriors 2, by contrast, only sends enemies in from the top, typical for typing games, and boring.

The original is built in Flash and often syndicated on shady sites who make their money via ads for scareware and other garbage. So my own Qwerty War will be an open source JavaScript only game.

On day one of this project, my goal is to get a text-only version working with all components. In the text only version, a table of “word” and “range to enemy” replaces the visual of enemies encircling the player, but it contains all the actual gameplay components. There is no reason for a typing game not to be accessible to the blind, so the text only version will remain as a fallback to the final graphical version, build on html canvas.

The final version will include a server-side component for saving the leaderboard, but the game itself runs entirely in the front end. After day 1, it is playable, if a bland. Source is on Bitbucket.

Android List

Some time ago, I wrote a shopping list app as an exercise to learn Android programming. I do not plan to maintain this or enhance it, but the code is now available.

It is just a couple simple list views. One view adds items to the list. All items ever added remain in that view, the inventory. The other view is the actual shopping list. Tapping an item in the inventory moves it to the shopping list; tapping it in the shopping list moves it back to inventory.

A right or left swipe switches between the views, which brings up an annoying factoid: the Android api does not have built-in swipe detection. Creating your own gesture detector is easy; 30 seconds on Google finds as many slightly different implementations as you could care to see. Nevertheless, swiping is a simple, common need. A side-to-side swipe detector and a zoom detector would probably cover almost every application.

This illustrates another reason to like Python:

Fans of Python use the phrase “batteries included” to describe the standard library, which covers everything from asynchronous processing to zip files.