![[info]](http://l-stat.livejournal.com/img/userinfo.gif){kind=small}
Incentive, here I come!
For the curious, the interpreter is downloadable here, and I've put the main runtime interface headers behind an lj-cut just to give you the flavor of the thing.
To be truthful, I finished all that over a week ago. Since then I've been working on the next step: a map editor for my next game, the game that will also use that scripting engine. I'm using the working title Praetor, so you'll probably catch me referring to that. I'll post more about that thing later, but the quick summary is that it's a collectible card game played out using armies deployed on a hexagonal playing board. Cells on the playing board have various terrains, and as you progress through the game you'll face opponents on different boards--so a map editor to lay out that terrain was essential. Here's a sample of what it lets you create:
The editor has a small amount left to do, but it's not a big project and is almost wrapped up already. Importantly, a lot of its code is content that will be shared with the game itself: one third is raw game-engine code, one third is common Banshee-based map-rendering code, and one third is specific to the editor itself. Should help me get the game itself running a little faster than if I had to rewrite all that from scratch.
( Oh, and here's that header, for the truly curious. )
The result is that you can actually run simple scripts now: global variables and local variables all work, mathematical expressions are properly evaluated, and even things like += and -- are compiled and interpreted properly. Yay!
There's still a lot to go: in particular classes, methods, namespaces and array object references are still pending. Oh, and things that involve jumping around at runtime: if/else, for loops, trinary operator, logical-or/-and etc. But things are looking good.
For the die-hard curious out there, I'm posting my current ( bytecode description ) I'm filling in the docs as I go, so this describes accurately what the script does today--but it lacks several bytecodes that will be necessary to finish this thing off.
( Interpreter Notes )
type_a ::= type_b ";" | [type_c]* type_d
A simplistic parser that recognizes such a definition would look roughly like this:
bool parse_type_a (sourcedata &in)
{
pos = in.tellPosition();
// See if we have a type_b followed by a semicolon
if (parse_type_b (in)) {
if (parse_token (in, SEMICOLON)) {
return true;
}
in.setPosition (pos); // didn't pan out; rewind try the other form
}
// Didn't have that; see if we have a series of type_c's followed by a type_d
while (parse_type_c (in)) {
;
}
if (parse_type_d (in)) {
return true;
}
in.setPosition (pos);
return false;
}
Notice that, on failure, we didn't scream and complain: if parse_type_b doesn't see a type_b syntax coming up next on the stream, then it's not a big deal. All it does is return false, indicating that we didn't see a type_b coming up--and importantly, we didn't advance the stream at all. (Notice that we might've successfully pulled a type_c or two off the stream, then failed to find a type_d following on. Gotta put those type_c's back.)
With an adequately complex grammar (like the one we're using for parsing C-like expressions), you can imagine how quickly this turns into a deep recursive stack. In practice, this is exactly how the recursive descent parser works: having defined the grammar very precisely, we write methods that exactly parse each basic type, and allow them to recurse pretty deeply. It's quite simple to implement, but can be unpleasant to debug; helps to add a tracing facility to show where you are in the parsing stack.
In the parsing stage, we'll just write enough code to properly walk the script all the way through--doing nothing at all, just scanning through. By the time the parsing stage is done, the compiler will be able to detect and report all manner of syntax errors while silently accepting all properly-formatted scripts. The compiler will not, however, do anything else useful at all. This is the last stage we can really accomplish without giving some serious thought to how the interpreter is going to work.
The generation stage will be much harder: that's where we insert code into the existing parser to make the compiler actually generate some kind of machine-usable bytecode output. And that's when things get really fun.
I've just about finished my parser; it handles everything except flow control (for/do/while/if/else etc) and array initialization. When I've got that stabilized a little bit, I'll post in more detail about how that parser works, then move on to the interpreter and bytecode generator. Good geek stuff coming up!
The traditional way to lay this out is through BNF format, and to make use of YACC ("yet another compiler compiler"). Again I'm going to skip over that thing and just roll the code myself, but writing out some BNF-like form for the language is essential--especially when you plan to use a recursive descent compiler, since the methods you write will almost exactly follow the BNF assignment statements.
A first cut at the grammar for Dualscript is below. I've smoothed out a few things in the language since I posted earlier: added a keyword here or removed one there, eliminated class-scope methods and data variables, and so forth. The result is a pretty simplistic scripting language that has a certain degree of agreeable symmetry. There are probably some significant errors below--in particular I've omitted the array definition syntax and I'm not happy with postfix_expr through postfix_operator, so I may need to rework those. But it's time for bed now, so this is going to have to suffice.
( BNF hides behind cut )
A clever tokenizer won't run too far ahead of the actual compiler: that's called a streaming tokenizer, and it's marginally more complex than a tokenize-everything-and-remember-it-all-a
The basic tokenization loop looks more or less like this:
as long as there's content left in the input script {
skip whitespace (including EOLs)
if we hit "//", skip to the end of the line and restart this loop
if we hit "/*", keep reading until we hit "*/" then restart this loop
if we ran into the end of the script, quit now
if the next char is a digit, look for number sequences
don't forget to look for hex and octal radixes ("0x5E13", "0777")
don't forget to look for decimals and exponents ("15.37", "27e+5")
remember to look for special cases ("0", "0.3" which look octal-ish)
see if the next 3 characters match a 3-character token (like ">>=");
if so, record that token into our output and restart this loop
likewise, see if the next 2 characters match a 2-character token ("+=", "<<")
likewise, see if the next character matches a 1-character token (":", ";" etc)
if the next character is an apostrophe, crack character sequences like 'x'
remember to handle encodings like '\t' for tab, '\n' for newline etc
and of course '\x7f', '\127', '\035' should be supported too
if the next character is a quotation mark, try to pull a whole string
this is pretty easy--just skip the ", then keep reading until hit another one
again, look for \ prefixes, and don't be fooled by \"
okay, the next word must be plain text--either a keyword or something like a variable.
scan forward until we run out of legal characters for either, and accumulate the text.
then match against known keywords ("for", "return" etc)
}
And that's it. No magic involved--just some simple text cracking. The result is that we can stop worrying about the text file that the user supplied; instead, we have a much more programmatically accessible array of tokens. The compiler will start pawing through those tokens to get its work done--in the next post.
| "In the beginning, the Matrix was designed as a utopia for humans, but some say we lack the programming code to create a perfect world." -Agent Smith, Matrix |
Yes, it's time to design a scripting language, complete with an interpreter. I'm doing this as part of another project--will get to that later--but it's a fun little self-contained project all on its own.
The first step in the project is to be sure you really need it. Adding a scripting language to a system can make it extremely flexible and powerful, but even the blunt approach I'm going to cover here is a good amount of work. If you can get by without it, by all means use a less general-purpose solution.
Okay, you passed that hurdle: you want a script after all--and by the same process, you've decided that downloading and incorporating a public Javascript engine or calling out to a Perl interpreter isn't doing it for you either. You need something new--some tricky new syntactical feature, integration with your home-rolled application or something you can sell without licensing problems. So a new scripting language and interpreter it will be.
Next step is to figure out what kind of syntax your language will provide. I've just finished a write-up of the major features of my next project, Dualscript. And I'll even put it behind a cut, because it's about 500 lines. Next up: posts about the bytecode, tokenizing, the recursive-descent parser and putting together a stack-based interpreter.
( Dualscript Language Summary )
I've been a big fan of the Danger Hiptop cell phone, and have made a decent wage writing games for it. But writing in Java hurts my pride, and when my third Hiptop in a row died a hardware death I decided it was time to rethink my choice of platform. See, the Hiptop just doesn't seem to be going anywhere. After about four years now, their hardware has changed slightly: a two-directional wheel has replaced the one-directional one, and the screen resolution is better. The camera is maybe 1.6 megapixels instead of 1.0. Wow. But it still doesn't have anything more than rudimentary bluetooth, doesn't have any kind of GPS, its CPU-power-to-display-pixels ratio is *decreasing*, and its radio... god help me, but GPRS connectivity sucks even when it actually works. Four years, and they haven't done anything about some fundamental problems. |  |
So I've swapped brands, and am now one of the herd playing with an iPhone. It's a new world, baby. Looking forward to picking up some Objective-C, learning some xCode, and capitalizing on the latest fad.
Isaac and Mom are off at their own testing right now; they should be back soon in fact. Ike's aiming to get the first bit of black on his belt as he pre-tests for 1st degree; Tara's working on her red belt. All fun. :)
In other news, NaNoWriMo is finally over. Since I can't write my way out of a wet paper bag, I don't plan to return to the jokingly-referred-to-as-a-manuscript for edits or anything, so I figured I'd just post it here. Have fun, and if you laugh yourself sick at my lack of writing prowess, don't say I didn't warn you.
Dust - Richard's NaNoWriMo book from 2007
I actually finished the VNC client; it turned into a nicely polished application, and works surprisingly well. I packed it with little things to help clean up the remote-manipulation experience while working on a high-latency link: it manages your cursor locally so there's no visible lag to cursor movement, batches up cursor- and keystroke- transmission to minimize bandwidth consumption, has a clever popup/overlay typing editor that shows you your keystrokes so that you can easily edit text without waiting 2 seconds for a screen refresh to find out what you actually typed, and so on. No question, it's the best VNC app I've ever seen for a cell phone. :)
Sadly, Danger shot it down:
| Dear Random Software, After careful evaluation, we do not believe this application to be a candidate for Catalog inclusion. If you have any questions, please feel free to contact me. |
...and that's that. No justification, no explanation, no apologies--just "you wasted your time and we won't tell you why." Unprofessional.
I've since had a fairly lengthy conversation with a different person at Danger, who described his understanding for the limitation: a combination of high bandwidth and low demand. Big surprise there.
Anyway, time to move on to the next product. Mmmmm... maybe I should dust off Chess Club and resubmit it. Remember this one?
It was shot down for third-party server interaction. BUT, I've heard (from Danger themselves) that this wall is crumbling; there's already one app in the catalog that talks to third-party servers and has a recurring charge (to cover the ongoing network usage). The app itself is pretty nice, and it's possible that this time around it will get approved.
Problem is, ICC has changed their "guest" policy since I wrote that thing--you can no longer login as a guest indefinitely, which is going to be a ship-stopper for my client. I hate to say it, but if I want to ship this thing I'm going to have to port it to work with FICS (the Free Internet Chess Server) as well. That's a lot of work, but not impossible.
That last feat is pretty fun, and is the basis of a new program I just finished for my cell phone: a VNC client. The idea is, with two clicks on my cell phone I can now connect to my desktop machine and see its display right there on the phone; I can type and the remote computer sees the keystrokes, and I can roll the trackball and watch the mouse cursor move. Basically, if you don't mind the brain-numbing latency (1-5 seconds for a full screen refresh), you can take over a remote machine very nicely.
Here's a few obligatory pics:
I've just submitted the application to the makers of my cell phone, as the first step in getting their business development and QA departments to look the application over. The quality of the application is very high--I'm pretty proud of it, actually--but I'm guessing there's only about a 50% chance that the app will get approved. There are two likely hangups: it doesn't work on older versions of the phone (requires a trackball, and old phones don't have one), and it uses a lot of network bandwidth (something carriers don't like--and if carriers don't like it, well, it's dead in the water).
On the other hand, having a good VNC client brings the Sidekick closer to feature-parity with other data-targetted PDAs out there. Who knows?
Yet another exciting day: I tested for black belt this morning. The whole process took just under three hours--though half of it I was just standing by watching the junior members test, and helping out only by holding boards for breaking or playing attacker for self-defense tests.
The test went quite well, I think. The patterns went smoothly--didn't get called to repeat any, and several instructors complimented me on them later. Self-defense likewise was straight-forward, though we took them a little gently in deference to the exceptionally hard floors (the test was held in a local high school gym). I had only two rounds of sparring, one attacker each--drew strong opponents both times, and did much better than I'd expected. Breaking was great: nailed all my breaks on the first try, including the four-board one. I know the terminology cold, so I wasn't worried about that part.
Basically a much less painful test than I'd feared. Sa Bum Nim runs a very vigorous class, when the frequent refrain of "compared to this, testing will be easy." I don't know if it was really easy, but I certainly wasn't as tired after the 3-hour test as I am after a normal 1-hour class.
We'll find out the results of the test in two weeks, and if I passed (I'm pretty confident that I did), there's a ceremony in late May where new belts are awarded. Here's hoping I get to move on to learning some new patterns!
Update: the lists of test results were posted today, and indeed I passed. The ceremony where I'll receive my actual black belt will be held on the 19th--just a week from now.
So, here's hoping for better luck this time:
This tasty little thing has about twice the horsepower of my old car, weighs in at 100 pounds lighter, and has so much torque that you can bark the tires at 60mph if you slam the accelerator. Its handling is phenomenal--the comparison to steering a go-kart is well-deserved. It practically begs you to drive like an asshole.
In fact, I think I'll go for a drive now. :)
Isaac did an amazing job. First off, he handled that huge crowd so well! The tournament was at the "main school"--a building we've been to only once before, and which is full of weird twisty passages and crammed with spectators and participants. But he paid attention, found out where he needed to be, and did his thing in the tournament without any help or instructions from us at all.
Tara arrived from church about 20 minutes before the childrens' competition began. We got a few photos of Isaac doing his pattern: he scored 9's and 9.5's, and ended up with 3rd place in his division. It was hilarious to see his jaw drop when they called his name for a trophy.
When it came time for Isaac's division to spar, Nathaniel and I wandered around the building and arrived outside a door right next to where they were fighting. Got a few video clips and some stills, but sadly his back was to us and there were occasional spectators in the way. Isaac lost his first match 2pts-3pts, then won his second 3pts-1pt. He ended up with a 3rd-place finish there as well, so he now has two trophies on the mantle. (Need to put up a shelf in his room.)
When Isaac was finished, Tara took the boys back to the house and I stuck around for the adult competition. The pre-black-belt division was too large so they split us up; I ended up in a different division from the others against whom I'd expected to compete. I took first in patterns and third in sparring--the former doesn't mean much as the others in my division had a lot of stage fright, but I struggle with sparring so I'm pretty proud of the latter.
Since Michael had a birthday Saturday and Isaac won trophies Sunday, Nathaniel got to pick where we went to dinner to celebrate. :)
I'm targetting the server-side binary first, and the initial step there is to come up with a card compiler. That is, here on my machine I'm going to be producing a series of text files (and their associated images) that describe individual cards in the game. Here's a sample for what the cards will look like during the actual game play (click for larger version):
This particular card talks about a Medusa, which is just a convenient sample. (My son is reading a book about greek mythology, and he suggested it.) The relevant stats for this thing (which don't match the picture--sorry) are:
- It gets 1 AP per turn, and can have 3 maximum.
- It's slow: it can only move two squares per AP expenditure.
- It can't attack often: it has to use up 2 APs to attack.
- It can attack you up even if you're standing a square or two away.
- If it does attack you, you're screwed: you can't defend.
- Anyone hit by a Medusa gains the Rooted (can't move) and Harmless (can't attack) attributes.
( Read more... )
I've also written a specification for the dedicated server process that will be running full-time on the web site to manage this. I've thrown out peer-to-peer networking along with all its complications, and am going with a full client/server approach instead. This was primarily motivated by the complications of trying to play a correspondence game when there's no guarantee that you and your opponent will ever both be online simultaneously, but that's kind of a cop out: truth is client/server is simply easier to deal with overall.
Anyway, for those who have incurable insomnia, here's the better part of the web server design. ( Read more... )
( See their game summary... )
This was the final pre-test before black, so I don't have to test again until March '07 when I'll be trying for 1st-degree black. :)
