IncursionScript and the Accent Compiler Compiler

When I got a few minutes, I spent a bit more time looking at replacing the Accent usage in Incursion.  For the most part, Accent works pretty much the same as yacc or bison, but does so in a much more user friendly way.  Yacc and bison use BNF grammars, where Accent uses an EBNF grammar.  This allows minor use of some of the regular expression syntax to avoid painful rule finagling completely.

This StackOverflow post quotes the type of work you have to do (from another web page), to convert from EBNF to BNF.  Looking at the one off case, it only seems mildly inconvenient, but when you have several variations, it becomes painful.  Especially, if you're considering converting ~100k of rules for parsing IncursionScript.

monster_def:
  MONSTER { theMon->Attr[0] = theMon->Attr[1] =
            theMon->Attr[2] = theMon->Attr[3] =
            theMon->Attr[4] = theMon->Attr[5] = 0;
            CurrAttk = 0; CurrFeat = 0; theRes = theMon; }
  LITERAL<name>  { theMon->Name = name; }
  ':' cexpr3<n>    { theMon->MType[0] = n; }
    ( ',' cexpr3<n2> { theMon->MType[1] = n2; }
    ( ',' cexpr3<n3> { theMon->MType[2] = n3; } )? )?
    '{' (mon_entry)* '}' { theMon++; };

That was the initial part of a monster type definition. Note that the Accent grammar syntax for the left hand side of rules, embeds the parameter name in < and >, whereas bison has a much more limited support and uses [ and ]. Also, the right hand side of a rule can use the previously mentioned aspects of regular expression syntax. In this case ( and )? are used to indicate 0 or 1 occurrences of a match, and additionally + and * can be used similarly to indicate one or more, and none or more matches.  Note also that the parsed parameter values are used directly in the code blocks, without syntactical sugar, where bison requires that n be $n.

Any use of these regular expression syntaxes would when rewritten for bison, require more and more complicated contrivances and would break up the whole rule making the grammar less readable.  In theory, it should be possible to construct a bison grammar that parses the Accent syntax, with a matching lexer, and convert an Accent grammar to a more convoluted bison grammar.  The bison grammar for the Accent syntax isn't hard to do, in fact, the Accent author provides one in their documentation.  The bulk of the work would be in writing some subset of C parsing, to transform the code blocks, and then there's the flexible Accent parameter lists which bison cannot support at all.

Old with dated pre-ANSI code and using a GPLv2 license, requiring a commercial license to be able to be used freely, Accent is a not just a compelling alternative to bison.  It's almost impossible justify downgrading from it, if one ignores the unfortunate license.  But to become something where any inspired player, can open up a script and start modding, it needs to downgrade from it.

Translating the grammar from EBNF to BNF?  Not enough.  Bison doesn't offer the additional support required.  This solution would still require hours of painstaking rewriting of the custom Accent grammar syntax.

The only remaining alternative, is to write an Accent replacement.  Or to enhance bison or byacc, to support EBNF, and the additional functionality.  But then how many hours would that require?  It might be worth downgrading that 90k Accent grammar to a bison grammar after all.  Something to think about it.

That reminds me, I've searched everywhere three times and I can't find my Dragon parsing book.  It's gone.  I imagine it's with all my compact flash usb adapter, my micro sd card, my issue of Dragontales, and the other things I haven't noticed going missing yet.

Incursion progress report

For the most part, Incursion is pretty stable now.  There are still over a hundred "issues", but this is to be expected for an engine of it's depth.  The last work I did on it before the weekend, beyond a fix for a crash which someone kindly reported, was to try and get an example module put together.

That effort stalled, because what Incursion is, is a customised demonstration game, Halls of the Goblin King.

The source code does have pretty solid support for multiple modules, any of which can provide either new dungeons to explore, or new items, effects, classes, races or any other form of content.  But there are places through the code where it just looks at the first module with an accompanying comment saying just look at this, because it's the only module we have right now.

The source has unused support for multiple players, but it's not consistently used throughout the code, and that's ignoring the question of how multiple players in a turn-based game can even be done.

What I spent time on over the weekend, was just trying to better get a picture on more of the scope of the engine.  In order to do this, I started documenting the constants defined in the script, starting with those used for dungeons (see commit #c953cfe on Bitbucket).  These can refer to values, like the minimum and maximum room widths on the x axis, the density of torches in lit rooms and even references to other game content like features, regions, terrain and even other dungeons connected in some way.

The more time I spend learning more and more of Incursion's source code, the more it seems like the best engine to base a fantasy roguelike on, given certain considerations.  One is the expression relating to the last 10% of the project requiring 90% of the work, Incursion simply requires a little more work and some polishing before anyone who simply hopes to write some scripts and to make a unique roguelike, can do so.  Another is that the game must be OGL and as mentioned fantasy.

Even just spending a few idle hours searching for and commenting the usage of constants, while watching Wimbledon over the weekend, the flexibility and depth of the engine appeals to me.  And the work required to make what it can create less same-same, seems less of a burden.  By that, I refer to things like the depth of a dungeon scaling everything, with increasing depth being downward.  If you wanted to make a tower of ascending levels, then that should be a possibility.  And whether depth should imply a fixed scaling at all, should be another matter.

One idea I should note down, in case I forget to write it elsewhere, is to make it possible to hand edit loaded module data, or to hand author some.  This would not be a method of more easier development, but would lead to additional features like live visualisation of changes to things and how it affects level generation and so forth.  Just reloading the scripts isn't as possible, as they are compiled before use.

Imaginary Realities, volume 7, issue 2 released

Get Imaginary Realities volume 7, issue 2, at the usual place.

• Bartering
• Is Structuralism a Viable Critical Lens for Roguelike Games?

Imaginary Realities, volume 7, issue 1 released

Get Imaginary Realities volume 7, issue 1, at the usual place.

• Choosing an Emoting System
• The Dungeon Keeper
• What Do I Do Now?
• The Worlds in Which We Wander

Incursion PDCurses problems

Switching to the wide character API, the main problem was that the way Incursion encoded it's glyphs was incompatible.  Glyphs are encoded in the form 0xBFCC, where B is the index of the background colour, F is the index of the foreground colour and CC is the 8 bit character code.  F was generally put in place by doing F*256.   To increase the size of character codes, required widespread changes and searching and dealing with a variety of integer values which were involved.

The lower level engine also now uses non-representative values for it's glyph codes.  Mapping to character codes is done in each of the UI layers.

Unfortunately there are some teething problems with getting a working set of character codes.  The red question marks in the following image are GLYPH_FLOOR2, but the UTF-16 code chosen is not available in the default DOS console font.

So, what is the font?  Apparently, it's Terminal.

Here is the Terminal character set.

I knocked up a wizard menu option to dump the glyphs out.

Note that there are characters here which are from a proper UTF-16 font.  Take for example ARROW RIGHT, ARROW LEFT, ARROW UP and ARROW DOWN in the fourth and third to last rows.  Where do they come from?  No idea!  Another question is why does the first glyph for PERSON cause a missing space and the first row to be misaligned?  No idea!

One question I have is whether it is possible to detect missing glyphs and dynamically substitute them.  Curses has an API which allows the character at a given coordinate to be queried.  If I write an character unsupported by the current font, and query it back, do I get the code I wrote or the code that gets displayed?

Adding Curses support to Incursion

Incursion as long as I've been playing it, has always used a 2D graphical library to do it's graphics.  Before the open source release, it was Allegro, and after, it became libtcod which uses SDL2 behind the scenes.  But the problem with graphical libraries, is that the interface is presented on the screen as a static image.  And this means that people who can't see good, cannot play.

Would adding a terminal-based interface, like using curses, solve this problem? ...  Possibly.  Until it is using one, and a person who can't see good tries it out with their screen reader, I'm not sure it's possible to know for sure.

I use the premier operating system, Windows.  I know it's premier because the latest version does edgy shit, like cram a cheap looking tablet interface on the top of the new versions, and everyone not using a tablet gets a constrained and simple interface that doesn't do half of what it used to.  On Windows, we don't have a native terminal program that handles ANSI escape codes.  This is typically how terminals are implemented.  What we do have is a DOS console that does it's own special thing.

Shitty Windows 8 tablet UI

Fortunately, many many years ago, someone wrote a cross-platform curses implementation by the name of PDCurses, that has the bizarrely arcane and complex API that all curses programmers are familiar with, and that makes a DOS console look like it was doing all the nice stuff a Linux terminal window would otherwise do.  PDCurses is dated, but compiles easily, and integrates with little difficulty into existing projects.

The original PDCurses 3.4

Don't confuse it with the confusingly named PDCurses for "real" windows, which has had more recent work done on it.  This does not work in the DOS console, and opens a new window, where it does whatever it does.  Honestly, I have no idea whatever it is doing.  It maybe does it graphically?  The web page lists lots of changes, but isn't clear about whether this is a suitable replacement for the original PDCurses.

PDCurses for "real" windows

Besides allowing the tools (like screen readers) which people who can't see good use to access the console data, there are other advantages.  When people are playing in a Linux terminal, they can capture the data the terminal receives and displays.  This is an interleaved mix of ANSI escape codes and text.  It can be played back, to watch someone else playing.  On Windows, by using PDCurses, something like termrec polls the DOS console by the same Windows API that screen readers use, and recreates something resembling the best kind of low quality interleaved mix of ANSI escape codes and text that can be approximated from the data available.

I'm 90% of the way to implementing the Incursion curses UI.  It's completely untested, and based on Incursion's internal console implementation, it was likely the original implementation used curses.  There are few issues remaining before it can be tested.  Something that libraries like libtcod, SDL and Allegro do, is provide a higher level file system API.  This needs to be replaced.  And then there's the issue of how curses handles colours.  This is a complicated mess.  But I'm sure it's a solved problem that others can shine some light on, so I'll ask about it on the roguetemple forums.

At this point, I'm wondering if it would be better to implement a telnet server, and to have Incursion serve the stream of interleaved ANSI escape codes and text that Linux terminals expect.  Then anyone who plays it could use Putty to do so.

How did people ever complete Incursion?

Sometimes when I fix a bug, I wonder how people ever completed Incursion. Take this one for example.

The definition:

struct EventInfo {
    EventInfo& operator=(EventInfo &e) { /* Memory image copy for the int/bool/ptr members */
        // Implementation doing a quick copy, allocating instances of subobjects.
        return *this;
    }
    // Rest of the normal code for this struct.
}

One problem situation:

bool Magic::isTarget(EventInfo &_e, Thing *t) {
    EventInfo e = _e;
    // Rest of this function.
}

When isTarget exits, then _e is corrupted. This is because EventInfo only provides an assignment operator overload. However an assignment in a variable declaration uses the copy constructor, and in the absence of one, does a bitwise copy. Pointers to sub-objects then become shared, and the first version of EventInfo to be destroyed will destroy those sub-objects assuming itself to be the owner. In this case, it will be e which as a stack variable will be freed when the function returns.

Incursion is littered with perhaps a dozen cases where the bitwise copy constructor would have been employed. Each one a potential crash, if not source of corruption.

Good times!

planet-rldev

If you read this, and have a blog where you make posts about your work developing a roguelike, then consider submitting your blog for inclusion on Planet-RLDev.

Mysterious Incursion bug

In changes to Incursion back in August, I fixed compiler warnings related to casting. In theory, the changes should have been side-effect free. Testing of the specific lines of code, indicates this is the case. But people were reporting crashes related to the "room weights algorithm". In this case RM_Weights is an array of unsigned int, and c and tot are signed short.

    tot=0;
    for(i=0;RM_Weights[i*2+1];i++)
      tot += max(0,RM_Weights[i*2+1]);
    c = random(tot); 
    for(i=0;RM_Weights[i*2+1];i++)
      if (c < RM_Weights[i*2+1])
        goto RM_Chosen;
      else
        c -= RM_Weights[i*2+1];
    Fatal("Strange Error in room weights algorithm.");
RM_Chosen:
    RType = RM_Weights[i*2];
    RM_Weights[i*2+1] = -1;

I was unable to reproduce the crashes, although others reported doing so up to 15% of the time.

Were the crashes always there and were they merely hidden by all the other crashes, which have previously been fixed? Or are they caused by some unreproducible nuance of the casting? I'm guessing the former.

There's an obvious bug in the above logic. Points to whomever spots it without looking at my fixes on bitbucket.

Brogue v1.7.4

There's no public repository for Brogue, which means I maintain my own where I merge in each source release, which comes as part of each binary Brogue release.

Today I merged in v1.7.4.  It was a pretty straightforward merge, so should be an easy BrogueX release.

The only problem is that my BrogueX repositories are broken because of bad merging, where things have been merged in the wrong direction and I have no idea how to fix it besides throwing all my local repositories away and starting again.  It's strange how I keep doing this.

IncursionScript & the Accent compiler compiler

When I started working with the Incursion source code, which Julian released, one of the problems was that not all the source code was available.  The bulk of the game data, both for d20 elements and dungeon generation, is specified in scripts.  These "IncursionScript" files are compiled into a module, which Incursion can have more than one of.

The problem was that they are compiled using the Accent compiler compiler.  And Julian had a version of this, which had been custom modified to produce C++ compatible code, but no longer had the source code.  I downloaded the original Accent source code and proceeded to try and get it working.

The Accent tool takes a ".acc" file, and transforms it into ".c" and ".h" files which you can compile against.  But it is also generated source code, created using some tool called Gentile.  The correct way to do this, which it appears Julian also avoided, would be to modify the Gentile grammar for Accent, and to generate a new version.  Instead, the approach we both took was to modify the generated Accent source code.

Accent is old school C code.  Seldom having return types in it's own source code, and rarely producing return types in the code it generates.  Occasionally using uninitialised stack variables, and expecting the value to be NULL.  And it generated argument typing for function declarations the other way, where rather than including the type with the argument name in the parenthesised list following the function name, the variable is redeclared fully (in the same way as stack variables) following that list and preceding the function body.

function(argname1, argname2, argname3)
    int argname1;
    char *argname2;
    void *argname3;
{

It is really the fixing of these three things that makes Accent C++ compatible, rather than making it output C++ specific elements.  In any case, a modified version of the Accent source code is now checked into the Incursion repository.  This is built as a dependency of the main Incursion project, ensuring that if there are any grammar changes, then they are rebuilt as needed.

World of Darkness MMO

I worked on the World of Darkness MMO for a year and a half, then decided to return to New Zealand.  It had almost been 10 years since I left New Zealand, and there was some sort of thing where if you hadn't paid taxes in that period of time, you lost rights to something or other.

Living in the USA was great, and I would have loved to continue living there.  My apartment complex had real character.  Double shootings just before I moved in.  Armed police with weapons drawn at my door, as the previous tenant had a warrant out for their arrest.  A friend who was attacked on the footpath between work and the complex, by a short mexican with a small knife.  Walking past a car being hot-wired by some black dude, in the car park outside the movie theatre. Waffle house wednesdays.

It's sad to see it has been cancelled.  We did some really interesting things, and I'd be curious what the years since then resulted in.

Imaginary Realities, volume 6, issue 1 released

Get Imaginary Realities volume 6, issue 1, at the usual place.

I should really paste the table of contents here, but publishing this is so involved I have used up today's quota of willpower.

Incursion stabilisation post 2

Suck-cess!  There's some problem with foreground and background colour not taking, but that's a minor detail.  Incursion is now basically playable with a libtcod backend.

Incursion stabilisation post 1

I've been working on replacing the use of Allegro in Incursion, as it only works in the Debug build.

Unfortunately, most of last night and today was spent trying to work out why at first calloc() was failing, returning NULL with an errno of 12 (NOMEM).  Luckily, after an eventual reboot that switched to the call to TCOD_console_set_custom_font() crashing on exit.

Finally, I noticed that I was passing 8 and 8 respectively, as my font's nb_char_horiz and nb_char_vertic values.  After correcting it, my code is now stable.  I debugged that function umpteen times, and am not sure how this makes that much of a difference.

Roguelike MUD progress #7 - Web-based client

Previous post: Roguelike MUD progress #6

I set a mini-goal for myself, to display a curses-based program on a web page.

The first step was to find a no frills, easy to adopt and extend Python websocket solution. One I've stumbled on  few times, is the simple websockets client/server gist. I used a slightly fixed version of it as a base. The next step was to find decent web-based terminal emulation. There are frameworks available which ditch the terminal window, but they come with larger problems.  The best candidate is term.js.

So taking the simple websockets simple_websocket_client.html and adding term.js, then modifying simple_websocket_server.py, it was easy to get a simple echo working with embedded ANSI control sequences.

First, I tried to proxy the input and output from the nano editor. Unfortunately, doing this with the subprocess module resulted in nano outputting a message about not supporting redirection.  There's probably a way to do this, but too much bother and it is not really my goal anyway.

Next, I went for something simpler.  I did a simple proxying of input and output to a telnet connection. Specifically my Roguelike MUD codebase.  There were some teething problems.  Text incoming from the browser-based terminal through the websocket, is UTF-8 encoded.  And similarly, outgoing text has to be as well.  But responses from the MUD contain both ANSI escape sequences and telnet negotiation sequences.  In order to work around this, I stripped the telnet negotiation out of outgoing text, and modified the relatively basic websocket code to also send binary frames.

A working connection:

In-game display:

As the picture above shows, the ANSI sequences are working perfectly.  But the character set does not seem to contain the line drawing characters.  My game interface already has debugging tools which display accessible character sets.

The main character sets:

As can be seen above, the only character set with even a hint of line drawing characters, is the one exposed through the ESC(0 ANSI sequence.  Most of these sequences are faked by term.js, where known character sets are mocked up from the underlying unicode-supporting font.

One solution is to do what I do with Putty, which is to identify the connected client, and if it's one which supports unicode, then switch unicode on using terminal control sequences.  Modifying term.js to respond to the ENQ character (0x05), and send it's terminal name (xterm) was easy enough.

This is what I should be seeing now:

This is what I am actually seeing:

The correct unicode characters are being sent, but not being displayed correctly by term.js.  I don't expect this will be that difficult to correct when I get some more time to work on this.

OpenCyc experimentation

Last December, OpenCyc 4.0 was released. I've been meaning to get more familiar with OpenCyc for a long time, and luckily this release adds a lot of interface improvements.

• The search bar now has a drop down set of auto-complete matches.
• The display for a selected term is cleaner and easier to use.
• Terms have a popup menu that allows easy editing or deletion.

Experiment

I was hoping to translate the D&D SRD ability modifier formula into a CycL function, so that I could at a later point calculate the modifier for the given attribute of an entity. The OpenCyc documentation was never extensive enough to describe how to do this sort of thing, and it has not been updated since the original 1.0 release. Add into that dead links, and working out how to use OpenCyc is pretty hard going.

A huge amount of browsing terms in the OpenCyc ontology browser led me to the simple formula:

(#$TruncateFn (#$QuotientFn (#$DifferenceFn ?SCORE 10) 2))

And that's ignoring that I had trouble finding DifferenceFn and QuotientFn, originally using PlusFn and TimesFn in their places.

In order to test an expression like this, it needs to be wrapped in evaluate, which binds the result to a variable allowing it to be seen in the query page.

(#$evaluate ?RESULT (#$TruncateFn (#$QuotientFn (#$DifferenceFn ?SCORE 10) 2)))

Like a SELECT statement in SQL, this effectively displays one row with one column named RESULT showing the value of 3.

Defining the standard terms for a CycL function is pretty simple.

The first step is to create a term (a generic step) with the name of the function, in this case #$AbilityScoreModifierFn. In the top frame, there is a tools link on the right hand side. Click on this, and then select Create Term.

Next various properties are asserted for the term. In the top frame, there is a Assert link. Click on this, and then simply enter the relevant expressions and assert each in turn.

(#$isa #$AbilityScoreModifierFn #$UnaryFunction)
(#$arity #$AbilityScoreModifierFn 1)
(#$arg1Isa #$AbilityScoreModifierFn #$Integer)
(#$resultIsa #$AbilityScoreModifierFn #$Integer)

And finally the remaining task, is to associate the formula with the AbilityScoreModifierFn function. I've come to the conclusion that this actually isn't possible to do from within CycL.

There are two possible ways of associating logic with a term (that I've been able to find).

1. rewriteOf
2. evaluationDefn

With rewriteOf, you might assert something like:

(#$rewriteOf #$AbilityScoreModifierFn
  (#$Lambda (?SCORE) (#$TruncateFn (#$QuotientFn (#$DifferenceFn ?SCORE 10) 2))))

Unfortunately, rewriteOf expects a reifiable function as it's second argument. What this means, is that what this does is assert (#$AbilityScoreModifierFn 18) as a fact in the ontology. This is obviously not what I want, which is simply calculate and output a value, with no side-effects.

CycL expressions cannot be associated with evaluationDefn. This is intended rather to simply specify the name of a function in the lower level lisp language, called SubL. These are apparently easy enough to define, but it has been hard enough getting to this point, let along adding further complication outside of the ontology.

Experiment conclusion

At this point, I get the feeling it isn't intended that you can directly create formulas as expressions within CycL. Instead, I assume that it is expected that these are defined in SubL.

Ontology thoughts

I'm also not entirely sure that the effort of using OpenCyc is worth it. While there is a wealth of knowledge in the ontology, it doesn't seem deep enough in the right places to be used to back a game experience.

There are definitions for Crossbow and Longbow for instance, but they don't have the depth which there is for Gun. Gun has logic to define information about its projectiles, and defines the parts that make up both guns and their projectiles. But there is no corresponding breakdown of the parts of a bow, or the projectile which a bow fires.

The humanoid body has parts, but there is no definition of how the parts join together. Actually, that's not entirely true. I believe there are a few definitions of which rib comes before the next, but little more. Torso doesn't seem to be joined to arms, neck and legs or whatever it should be joined to. Of course, cutting up corpses is not a crucial MUD feature, but I believe this is illustrative of a general lack of depth where it counts.

OpenCyc thoughts

Do you know how much memory OpenCyc requires to run out of the box? A minimum of 5 gigabytes. Who wants to run a MUD and to have to run a second process which they connect to via SOAP, which uses this much memory? And who wants to write their own SOAP encoding of their queries and other commands directed at the OpenCyc process, because there are only Java bindings provided?

At this point I am wondering if there is any reason to bother experimenting further.

pysrd

One of my long-term projects is to programmatically generate game logic from the D&D 3.5 SRD.  The idea is that ideally if the required legwork was done, any time I wanted to prototype something around a game experience, it should be possible to plug in the processed data and be 98% of the way to having stock D&D gameplay.  There's a lot of hand-waving there around the phrase "required legwork", but that's not really important for the purpose of this post.

I've extracted the low level scripts I use to both extend the database and introspect it's contents, and published them on github under the project name pysrd.

The SRD is available from Wizards of the Coast as a set of RTF documents.  This of course, is not ideal, but fortunately it is possible to get the data from andargor.com in different database formats, including SQLite.  Unfortunately however, not all SRD data is included in these databases.  Fortunately, the OpenSRD project includes generated HTML versions of the RTF documents, which can more easily be processed.

Android SDL 2 gesture tester app

I've written and uploaded a simple free app to the play store, which allows someone to create a selection of gestures, and then to draw and see how well they get matched (or indeed, if the right ones even get matched).

In an ideal world, I'd be able to use this to author things like the Google maps pinch to scale in and out, or swipes to go from one page to the next.  Unfortunately, while simple letter shapes like N, Z, C, W and more match perfectly fine, the functional gestures like pinch to scale and swipe to switch get confused and don't seem to reliably distinguish between the direction of the actual gesture.

Hopefully I'll get feedback from the mailing list, and it'll be something I am doing wrong.  Otherwise there's a load more work in my future to use the Android Java-level gestures.

EDIT (19/06/2013): Published source code of latest released version.

Android, libtcod & gesture support

I've the beginnings of a gesture experimentation prototype running on Android within the libtcod sample program.  Currently it just allows the authoring of a gesture, but it's fairly straightforward from there to have the user author several gestures, then draw something and see which gesture SDL detects that it should be.

The SDL 2.0 gesture support works wonderfully.  But unfortunately a little too wonderfully, even unknown gestures are matched and the aspect that would distinguish a bad match, seems to be broken.  Currently every matched gesture has an error of -2.0.  Something I apparently have to debug myself, using printf-based debugging as proper debugging does not work at the C level.

More to come..