Proposal: Recursive RLE
Posted: September 13th, 2009, 11:07 am
I have been experimenting (in Python) with an extension to RLE which allows the definition and reuse of subpatterns, including the transformation and evolution of subpatterns, and nested subpatterns.
For the formalists, here is the BNF:
(The above is for Life patterns; the idea can be extended to other rules, including rules with more than two states, by extending state in the usual way.)
A subpattern is delimited by @ on the left and a transformation on the right.
The transformations are the four rotations (including the identity rotation) and the four reflections, as follows:
The visual scheme here is that . should be thought of as a v, and <, ^ and > are rotations of it, and each of the four reflections is indicated by its line of symmetry.
Subpatterns are defined in a "local raster", ie such that a $ in a subpattern aligns with the top-left corner of the subpattern. Transformations are performed "in place", ie roughly relative to the "centre" of the subpattern. (I'll write this up in more detail if anyone shows interest.)
An evolution, if present, is performed after the transformation for the purposes of transforming "in place".
Both subpattern definitions and subpattern references are included at the current place in the enclosing pattern, with the given evolution and transformation. A subpattern definition or reference does not increment the raster pointer in the enclosing pattern.
A subpattern name may be any mixture of letters, digits and _, including a simple integer (although 01 and 1 would be different names).
It seems to me that the main advantages of extending RLE in this way, rather than extending file formats to included additional "command" lines, are that (1) the parser for the above is relatively trivial, (2) the format is in the spirit of RLE: not very human-readable, but very compact, and (3) very large patterns like the Caterpillar could be jammed into relatively small files.
What isn't trivial is a general-purpose pattern-to-RLE converter. It is expected that patterns generated with software assistance, like the MRM or the Caterpillar, could generate fairly efficient RLE strings.
I'll try to include some examples in a future post.
Cheers, Paul (Chapman)
For the formalists, here is the BNF:
Code: Select all
rle = pattern '!'
pattern = [ unit ]...
unit = run | subpattern
run = [ integer ] ( state | '$' )
state = 'b' | 'o'
subpattern = '@' ( definition | name ) [ evolution ] transformation
definition = name '=' pattern
evolution = '+' integer
transformation = '.' | '<' | '^' | '>' | '-' | '\' | '|' | '/'
integer = ( digit )...
id = ( letter | digit )...
letter = 'A' | ... | 'Z' | 'a' | ... | 'z' | '_'
digit = '0' | ... | '9'
A subpattern is delimited by @ on the left and a transformation on the right.
The transformations are the four rotations (including the identity rotation) and the four reflections, as follows:
Code: Select all
. - Identity
< - Rotate 90 degrees clockwise
^ - Rotate 180 degrees
> - Rotate 90 degrees anticlockwise
- - Reflect in a horizontal line
\ - Relfect in a leading-diagonal line
| - Relfect in a vertical line
/ - Reflect in a skew-diagonal line
Subpatterns are defined in a "local raster", ie such that a $ in a subpattern aligns with the top-left corner of the subpattern. Transformations are performed "in place", ie roughly relative to the "centre" of the subpattern. (I'll write this up in more detail if anyone shows interest.)
An evolution, if present, is performed after the transformation for the purposes of transforming "in place".
Both subpattern definitions and subpattern references are included at the current place in the enclosing pattern, with the given evolution and transformation. A subpattern definition or reference does not increment the raster pointer in the enclosing pattern.
A subpattern name may be any mixture of letters, digits and _, including a simple integer (although 01 and 1 would be different names).
It seems to me that the main advantages of extending RLE in this way, rather than extending file formats to included additional "command" lines, are that (1) the parser for the above is relatively trivial, (2) the format is in the spirit of RLE: not very human-readable, but very compact, and (3) very large patterns like the Caterpillar could be jammed into relatively small files.
What isn't trivial is a general-purpose pattern-to-RLE converter. It is expected that patterns generated with software assistance, like the MRM or the Caterpillar, could generate fairly efficient RLE strings.
I'll try to include some examples in a future post.
Cheers, Paul (Chapman)