A MarkovJunior-like demo using DFAs for pattern-matching

[kaya3]

I mentioned in my other thread that I was working on a proof of concept for an algorithm that can efficiently keep track of all matches of a set of patterns in a 2D grid, using DFAs; I finished it and made a neat demo that works like some of the simpler examples from this project, which people here might be interested in.

Here's an example, and a link to the demo:

The rules for the demo: it's all a single "Markov node".

    const rules = [
        // make a few lakes by random growth
        rule('B', 'I', LAKE_SEEDS),
        rule('IB', '*I', LAKE_SIZE - LAKE_SEEDS),
        
        // make some land by a self-avoiding random walk with backtracking
        rule('B', 'R', LAND_SEEDS),
        rule('RBB', 'WWR'),
        rule('RWW', 'EER'),
        rule('R', 'E'),
        
        // erode narrow sections of land
        rule('BBWBB', '**B**'),
        
        // replace the solid lakes with isolated pixels
        rule('II', 'BB', LAKE_SIZE / 2),
        
        // fill unused space with a water texture
        rule('BB*/BBB/*B*', '***/*I*/***'),
        rule('*I*/IBI/*I*', '***/*I*/***'),
        
        // delete water pixels at random, for an animated effect
        rule('I', 'B'),
    ];

To be clear, this doesn't use the MarkovJunior project itself, and I didn't translate any of the C# code, but the basic idea is the same.

Updating the data structure when one pattern is rewritten takes O(ab + m) time where a,b are the maximum dimensions of a pattern in the set, and m is the number of matches which were made or broken by the rewrite; regardless of the number of patterns. Or, if you are applying a lot of rewrites, you can update the data structure for the whole grid in O(wh + m) time. The data structure then allows matches to be counted or sampled randomly in O(1) time. The TypeScript source code is here (MIT license); if you would like to adapt it for MarkovJunior then I'm happy to answer any questions you have about how it works (though hopefully the comments preempt most of them). It should be fairly easy to generalise it to 3D as well, but I didn't do that.

[aseaday]

You give a good idea for me for how to give another system of markov junior language in JavaScript.