Conways game of life avisynth implementation

[MBit]

Hi,
I'm new to this forum and would like to share some thoughts and code about the implementation of Conway's Game Of Life (http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life) in avisynth. Don't ask for the practical use of this :D

This is a simple implementation which takes a picture file and creates subsequent frames according to the game's rules:

# Eventually useful to avoid memory problems
SetMemoryMax(128)

# our source picture, the clip lasts only 1 frame
imagesource("F-Pentomino.png", end=0)

# ensure we have an alpha channel:
converttorgb32()

# make sure our source picture is black&white (monochrome) pixels only:
gen0=greyscale.Levels(127, 1, 128, 0, 255, false)

# make a fully white clip with the same properties as our source picture:
global white=blankclip(gen0, color=$ffffff).killaudio


# The Game of Life iteration function, produces a clip with gen+1 frames,
# each frame being the life successor generation of it's predecessor:
function recurselife(clip clip, int gen) {
return gen==0 ? clip.life : clip.life+recurselife(clip.life, gen-1)
}

# returns the next step from the 1-frame long input clip.
# A convolution mask is applied to give each pixel a value
# depending on it's own brightness and it's neighbour's brightness.
# Then we clear out colors that represent black pixels with 3 white neighbors
# and white pixels with 2 or 3 white neighbors.
# Then the mask is overlayed on the white clip, and it's white pixels shine through
# where we have cleared out pixels in the mask. Finally all other shades of
# gray (they are all in the range of 0 to 17) are clipped to black:
function life(clip clip) {
mask=clip.GeneralConvolution(0, "1 1 1 1 9 1 1 1 1", 254, false). \
ColorKeyMask($030303, 0). \
ColorKeyMask($0B0B0B, 0). \
ColorKeyMask($0C0C0C, 0)
return Layer(white, mask). \
Levels(254, 1, 255, 0, 255). \
ResetMask
}


# This finally produces our clip, consisting of the source frame and its successors:
gen0+recurselife(gen0, 1200)
assumefps(25)

# some scaling for visibility
pointresize(Width*3, Height*3)
Use this script with attached image or your own images

Now to some of the problems:
First, when increasing the image size or frame count to compute, avisynth crashes. This must be some consequence of the iterative-recursive nature of the script. Avisynth somehow traverses through all frames in the script during startup (but does it completely precompute and store them in memory?). Any suggestions on how to make this more robust are very welcome.
Second, I had to use ResetMask after Layering the mask over the white background, otherwise the function produces totally incorrect results. Took some while to figure this out, but WHY does Layer produce a clip with non-opaque alpha values ??

Greetings,
MBit

http://img18.mediafire.com/169173149e7aefd310e5837ba78a664cb036389b95d95b15b626bb71c40ab9fb6g.jpg

[Gavino]

One immediate observation - you can cut the number of filter instances by roughly 50% (hence saving memory) by only calling 'life' once rather than twice in the recursive function.
function recurselife(clip clip, int gen) {
c = clip.life
return gen==0 ? c : c+recurselife(c, gen-1)
}

[IanB]

GeneralConvolution() malloc's 4*width*height bytes per instance.

You could possible use Blur(0.3) which only mallocs rowsize bytes per instance.

You may need to tweak the 0.3 which gives a 1:8.65 kernel instead of the ideal 1:9 kernel

The blur kernel is calculated thus :-
A = 2 ** -BlurValue
Centre = 2 * A
Sides = 1 - A

[Gavino]

The blur kernel is calculated thus :-
A = 2 ** -BlurValue
Centre = 2 * A
Sides = 1 - A
That's right in relative terms. The actual values (summing to 1) are
Centre = A
Sides = (1 - A)/2

But I don't think Blur will work for this, as you need a 2-D kernel in which all the off-centre values are equal.
If you have a 1-D Blur kernel of [B A B], the 2-D kernel is
B^2 A*B B^2
A*B A^2 A*B
B^2 A*B B^2
So the corner values (B^2) are not the same as the 'centre-side' values (A*B).

Perhaps one of the MaskTools functions could be used in place of GeneralConvolution. This would require working in YV12 instead of RGB32 - I expect the ColorKeyMask etc bits can also be done using MaskTools.

[-Vit-]

Yes, masktools can do it, mt_edge can do a general convolution. In YV12 now:

SetMemoryMax(128)
ImageSource("F-Pentomino.png", end=0)
ConvertToYV12()
mt_binarize()
RecurseLife(last, 1200)
PointResize(Width()*3, Height()*3)

function RecurseLife(clip clip, int gen) {
return gen==0 ? clip : clip + RecurseLife(clip.Life, gen-1)
}

function Life(clip clip) {
clip.mt_edge( "1 1 1 1 9 1 1 1 1 255", thY1=0,thY2=255, U=1,V=1 ). \
mt_lut( "x 3 = x 11 = x 12 = | | 255 0 ?", U=-128,V=-128 )
}


Uses a lot less memory than the original, still very gradually creeps up due to its recursive nature.