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.

New Incursion roguelike web site

A new web site has been put up for Incursion.  This one is very simple, and is intended to meet a middle ground of preserving older links, with featuring the newer open source releases.  And of course, giving some illustration of what potential players might expect from the game.

http://www.incursion-roguelike.net/

Hopefully players will provide some interesting screenshots, to replace my quick initial efforts.  And perhaps even some Youtube videos of gameplay, to replace the one I located.  I didn't bother going into too much detail about what a roguelike is, I don't figure it will be converting new players to the genre.

Here's a screenshot of how the web site currently looks for posterity:

It's quite interesting to get back into more detailed CSS.  In the past I've tried to remain compatible with older browsers, but there comes a time when you have to ameliorate the pain of trying to get the CSS to do all the things you wish it to do, without hobbling yourself.

Getting CSS to go the last mile, is much the same as any other programming these days.  I encounter a problem like the footer background colour ending mid-page, and the page background colour then resuming until the end of the page.  But the natural inclination is to want the footer colour to extend down to the end of the page.  So I go to StackOverflow and find a solution, which generally involves abusing some language behaviour, and the CSS then does what I want it to, but it is left a little bit messier.

I considered using JQuery UI, but honestly, it is pretty clunky looking.  The themes don't help that much, and it seemed like a case of choosing the least ugly.  Then it broke on the CSS changes I had had to make to get my footer working as described above.  Deleted.

Next was the UI framework that Bitbucket uses, which can be seen providing things like the tab strip on Incursion's downloads page.  This is called AlloyUI.  The first warning sign was an 18MB download, compared to 500KB or so at most for JQuery UI.  The next was a "readme" file which instructed me to install a custom programming language, node.js, and to run the package manager that comes with it.  Completely unreasonable feature creep for a UI framework.  Deleted.

The same web page HTML and CSS skeleton is going to be reused for the Imaginary Realities, and in fact, it was actually the draft of the new Imaginary Realities web site repurposed for Incursion.  I'm hoping I can make use of the print media type, to generate the PDF and ePub e-books.

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?

Incursion PDCurses progress

After implementing use of the Windows file API for the Curses GUI implementation for Incursion, and a few final polishing moves, it now compiles.

Incursion running under PDCurses

Implementing Curses colour support

Getting the colours working, is a series of steps.  The first of which is to call start_color() immediately after initialising the screen (via the initscr() call all Curses programs do).

    bWindow = initscr();
    start_color();

All the desired colours also need to be identified to Curses as an index of RGB triples.  Curses colour values are in the range 0-1000, where programmers will know that rational thinking people store theirs in the range 0-256.  But that's a simple adjustment to make, as long as you know to make it.

    init_color(i, (Colors[i][0] * 1000) / 256, (Colors[i][1] * 1000) / 256, (Colors[i][2] * 1000) / 256)

And now we face the worst eccentricity of Curses, the fact that every printed character embeds its foreground and background colour as a colour index. This means that writing a character to a window coordinate is done in the following way.

    int16 colourpair_index = colour_pair_to_index(fg_index, bg_index);
    c |= COLOR_PAIR(colourpair_index);
    mvwaddch(bScreen, y, x, c);

This means that every foreground and background colour combination employed, needs to be registered. In theory, we could register all 256 possible combinations to begin with, but it turns out registering them on demand works just as well.

int16 cursesTerm::colour_pair_to_index(int16 fg, int16 bg) {
 int16 index;
 // Find out if we have already allocated the colour pair.  If so return it's index.
 for (index = 0; index < colour_pair_index; index++)
  if (colour_pairs[index][0] == bg && colour_pairs[index][1] == fg)
   return index;

 // Oops, we're out of allocatible pairs.
 if (colour_pair_index >= 256) {
  index = 0;
 } else {
  // Otherwise, add the pair in, and return the new index.
  index = colour_pair_index;
  colour_pairs[index][0] = bg;
  colour_pairs[index][1] = fg;
  colour_pair_index += 1;

  init_pair(index, fg, bg);
 }
 return index;
}

There is one remaining piece of the Curses colour puzzle remaining. Some documentation claims that each colour needs to be enabled for every single window which uses it, so in theory as a colour is registered, all windows should get a call to wattron(). But in practice, this does not seem to be needed. If I were to do it, it would be done in colour_pair_to_index() above after the call to init_pair().

    WINDOW *windows[] = { bScreen, bScroll, bCurrent, bSave };
    for (int32 j = 0; j < 4; j++)
        wattron(windows[j], COLOR_PAIR(index));

It may turn out that in the long run, it will be necessary to do this, should someone try and get Incursion's implementation to compile against ncurses on Linux or MacOS.

Incursion Curses support status

At this point, the game generally works.

However, there is a slight problem. Incursion allocates a window for the scrolling buffer, and this is larger than the game window. The player can of course page up and down through scroll text, and as they do so, the displayed range is copied onto the area of the game window where the pageable text is displayed. However, Curses limits the size of windows that can be created via it's newwin() function to the same or smaller number of rows and columns. This means that no pageable text is displayed, which is somewhat problematic for the player. The next step will likely be just allocating an array of chtype elements, to replace the scrolling buffer window. It's not a big deal, and just needs to be done.

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!

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.

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.

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.