Conway’s Game of Life for CPC—very fast+many features coming! New: QuadLife! p.3

[db6128]

Hmm, I guess considering the number of SET/RES instructions you might need to add to avoid copying the visible screen, the copy may well be the faster option after all!

Sorry, maybe being dense, but I'm not sure what you mean. Do you mean if I was using the screen to store the cells?

With respect to my games, if you are interested (mad? ) then Edge Grinder also has commented (after a fashion) source.

Oh, good to know; thanks! These games look great. I'm going to load them up soon and see whether I have any bare minimum of skill left from my days of playing Hellfire on the Mega Drive.

[db6128]

I heard you like MODE 1


The reason that it's not as much slower as you might expect, despite processing 21844 cells instead of 13860, is that, thanks to the horizontal resolution being 256, I can move north/south simply by INC/DECing H.

Although this is a nice proof-of-concept, I don't know whether I'll pursue it much further. The only way to get the additional vertical height that the grid is screaming out for will be to use the extended RAM, but flipping back and forth between the two buffers will then take 2 additional NOPs for every cell that changes. So, although I could stretch as far as a 254×174 grid and still have a passable amount of space for future increases in the size of the program, it would be massively slow by that point, due not only to the doubled vertical resolution but also to the slowdown required to page between base and extended RAM.

Do we really need a larger grid that much? (Regardless of the computational requirements, it's getting ever so slightly hard to see : P) The only contexts in which I've found large grids to be necessary during my previous travels are
(A) for Turing machines and other computer-within-computer–type things, whether based on Life or some other cellular automaton – but these require much more space than 256×256 and are obviously far beyond the processing power of the Z80
(B) more relevantly to my plans and to the reality of the CPC, for some of the rules of Generations – but most of those have cells with more than 3 ages, to which MODE 1 is not conducive, due to Generations really requiring different colours for different ages (a limitation that would affect any automaton with >3 states).

Still, any thoughts/opinions/etc.?

Anyhow, back to normality! Safer ground – phew! With a video I recorded of the latest version of the normal MODE 0–based edition. It would be nice if it might attract the attention of people who saw this thread but didn't try the program yet.

[TFM]

That's really a great application, the best implementation ever seen on CPC. Greets!!!

[Prodatron]

This is still so damn fast!

I heard you like MODE 1


The reason that it's not as much slower as you might expect, despite processing 21844 cells instead of 13860, is that, thanks to the horizontal resolution being 256, I can move north/south simply by INC/DECing H.

Although this is a nice proof-of-concept, I don't know whether I'll pursue it much further. The only way to get the additional vertical height that the grid is screaming out for will be to use the extended RAM, but flipping back and forth between the two buffers will then take 2 additional NOPs for every cell that changes.

If I see it correctly, you do the field generation and conversion to the screen in the same step. Is that the way you do it? So I wonder, if you could seperate it into two steps without loosing performance (maybe you could even gain speed, as you have more registers for each step - on the other hand you have to read the data twice...). If you do it in two steps, you can store and calculate the two fields completely in the 2nd 64K ram bank (out #7f00,#c2). Only for plotting it on the screen, you change to the 1st ram bank. You only need to do memory banking about 3 or 4 times for each generation.

In any case, IMHO the Mode1 version is VERY impressive for an 8bit system, as it shows, that the CPC can do this even at a very high resolution!

CU,
Prodatron

[db6128]

That's really a great application, the best implementation ever seen on CPC. Greets!!!

Wow, thank you very much!

This is still so damn fast!

Thanks to you, too, again! Yes, the main advantage of MODE 1, and a big one, is that it enables rows of 256 cells wide, which therefore are aligned on page boundaries, which makes things a lot faster when I need to navigate up and down. That's why it doesn't slow down as much as might be predicted from the increased resolution (i.e. like it would if I had to add and subtract numbers other than 256).

Another boost, which I didn't think to mention before for some reason, is that this version doesn't have to plot twice vertically as in MODE 0; that's not a huge consumer of NOPs compared to other things, but it definitely counts. Incidentally, I have an option in my MODE 0 source to make the pixels single-height, but it doesn't look particularly nice!

If I see it correctly, you do the field generation and conversion to the screen in the same step. Is that the way you do it?

Yeah, it's all done at once. But what you said next is very interesting and might also mean that I don't give up on the idea of a MODE 1 version quite yet... so excuse me while I think aloud in my next paragraphs

So I wonder, if you could seperate it into two steps without loosing performance (maybe you could even gain speed, as you have more registers for each step - on the other hand you have to read the data twice...).

I probably wouldn't have considered separating the steps for the MODE 0 version, but since you've mentioned it and the potential benefits due to reallocation of registers, maybe it just might be better to separate the two, even despite having to read the buffer twice... It's worth a try, anyway. I'm coding that version now and will report the timings when I can.

Anyway, in a – completely hypothetical! – MODE 1 version using the extended RAM, that would definitely be the best way to do it, because...

If you do it in two steps, you can store and calculate the two fields completely in the 2nd 64K ram bank (out #7f00,#c2). Only for plotting it on the screen, you change to the 1st ram bank. You only need to do memory banking about 3 or 4 times for each generation.

Almost a whole 64 kB... Depending on how much space I allow for the program, I'm calculating that I could have 190, 222, maybe even 238 lines of vertical resolution – wow! I would save a tonne of NOPs by not having to page back and forth for every changing cell – which I now feel would have been very silly – instead, only before and after drawing. Also, even besides the RAM-paging, having a full 64 kB to play with would let me go back to the faster method of flipping the buffers that I use in the MODE 0 version; the current MODE 1 has to use a slower method to fit in the lower 64 kB alongside the screen. Actually, with separate computing and drawing passes, being able to reallocate registers would enable an even faster way of doing it! What an array of possibilities :O

So, combining all of these intriguing possibilities, you've made a fantastic suggestion – thanks a lot! This does make me quite a bit more likely to try this out, even if it's only due to extreme curiosity...  Since the current slower method generates about 1.2 generations per second (at an optimistic estimate), I wonder if, using all these advantages, I could at least double the vertical resolution and not go below 1 generation per second – which I would say is good enough, especially when we consider the numbers of cells that would be involved.

Although it wouldn't matter for this thanks to your idea, just to confirm a silly question: If I did want to use the full 128 kB from one bit of code, which would want to access bytes from both of the 64 kB pages – i.e. flipping between configurations 0 and 2 – I have to duplicate it at the same addresses in both pages, right, so that it's still there when they are swapped? Silly question, I know...

In any case, IMHO the Mode1 version is VERY impressive for an 8bit system, as it shows, that the CPC can do this even at a very high resolution!

Again, thanks a lot for the great positive feedback! And someone with your experience on the CPC/Z80 doesn't technically need to have a Humble Opinion, so it's appreciated even more.

And I hope it's clear that I really appreciate these suggestions; I'll let you know if I get any of them going. But there I was just doing simple things like sketching out how I can implement the four-colour–inheriting system of QuadLife; thinking about Generations, too; and other things... instead, now I'll be distracted by thoughts about an entire other version! Haha.

[Axelay]

Sorry, maybe being dense, but I'm not sure what you mean. Do you mean if I was using the screen to store the cells?

Ah, sorry.  Wrote out some thoughts, came to the conclusion I was wrong and just wrote the conclusion.    So this time I'll just leave it!  As you were saying the 'current' screen was required and I was trying to think of ways to avoid the initial copy, instead just swapping between the two.   It would perhaps use SET & RES to swap BC between the 'previous' screen (actually the visible one) and the new current one.   Possibly DE could always point to the buffer...  But then I thought having to do 2 RES & SET per byte, as there were two cells to a byte, would be slower than the single LDI.  Except *that* was wrong too!  There's two bytes per two cells in the mode 0 version.  And from what you've said I guess you're only writing cells that change, so maybe it could still be faster not copying the screen, assuming the cells that change are in a minority.  If I understood the code I looked at correctly, the cells were being masked in or out individually as they changed, so I'm also wondering about whether handling the cells in pairs (or 4's for mode 1) might provide any advantage.  Say by only reading the original byte once and handling all the cells in it at once, and only then doing a single write back to the screen buffer if any of them change, rather than masking the individual changed cells in or out of the screen data.  But after my last post, I expect to realise that this too is wrong after I post it!  .... Ah no, realised it already...    Without copying the screen, there'd be a need to copy cells that havent changed in the last two generations rather than one, which makes a real mess of things.

Oh, good to know; thanks! These games look great. I'm going to load them up soon and see whether I have any bare minimum of skill left from my days of playing Hellfire on the Mega Drive.

Well I shouldnt imagine any of them will be that troubling! 

[db6128]

Axelay: I think I'm more confused than you now, and I wrote the thing! : P Copying the screen is only necessary for double-buffering – I do need two copies of the cells, but not of their visual representation, if that's what you thought? – and, if enabled, isn't a huge hassle, really, as it represents a reasonably small fraction of the time required for each generation (about 70 ms on top of the 440 ms for the cells alone). Combining it with my data wouldn't work for the current methods or any of the ones I have planned, but I can see the appeal theoretically. I appreciate you taking the time to think over things like that and the swapping method, in any case!

Prodatron: I tried your suggestion of doing the plotting separately, and it did enable me to write a clever and fast routine for translating the data to pixels. It was only a little bit slower. I don't think I'll use it in MODE 0, but, as I said, it will definitely be essential for MODE 1. Of course, in the latter, the same nice and clever method won't work, because I have to process four pixels at a time rather than just two. :|

Next up, since some people are never happy...

Rubbish gfx, no sound. And a mode 0 game with only two colours? Pffft. Control is also so slow it seems your input has no effect at all.

...Let's see if I can't do something about that  


(video updated to reflect the newer version I've uploaded since originally posting this and show more of its features) [Edit One Million: well, it's already out of date now...]

This is QuadLife! Every cell has one of four types, conveniently represented by colours. A newly born cell inherits the colour/type that is the majority amongst its parents – or, if all three were different, the new cell inherits the one type/colour that none of its parents had.

The video shows how groups of particular colour can migrate and perhaps even 'outcompete' others in interesting ways. Randomly assigning colours can also provide its own type of interesting experience in terms of watching how the subsequent dynamics play out. Of course, things like this would be most interesting in the context of 'competitions' between different custom-drawn patterns.

And on that note, since I'm starting to get to grips with programming the keyboard, thanks to a guide from Kevin's site (which I initially found as a sneaky copy-and-paste without attribution on some other site), an editor shouldn't be too far away. In any case, I've already added a few little options for interaction. So, as well as enjoying this photorealistic depiction of the struggle for existence, you can now press (updated)...

   
• C to clear and restart with a new randomly generated grid, also swapping between quadrant-based and random assignment of colours;
• S to simply add (sprinkle/snow) more randomly generated cells on top of the current grid using the current method of assigning colours (but I haven't put in any of the proper checks for colour assignment over an existing grid, so forgive any quirks edit: done and updated at the bottom. I was unsure how to deal with adding cells to an existing grid, but it's actually trivial);
• D to toggle between the different methods of colour assignment and then drop another random bunch of cells on top of the current grid; or even
• X to reset your CPC (but why would you want to do that?)

Graphics, controls... Gryzor probably will insist that I still have to add sound effects or something. Are tank noises OK, or do you want lasers?

This might remain separate from the 'basic', even-more-optimised variant, but I am very pleased with – and surprised by – how well it turned out, and also how quickly it came together. To get around the overhead introduced by the inheriting system, I had to make some significant changes and develop several new clever tricks, and surprisingly, they all worked with a rare minimum of fuss and frustration. 

Edit:

Aaaaaand apparently I just chopped about 80 ms off each generation of QuadLife.

But that's not to ignore good ol' Original MODE 0 Version, as it's just gotten another boost of almost 100 ms per generation, taking it to around 350 ms for each.

Is 3 generations per second possible? I guess we'll eventually find out one way or another!

I've bundled both, now including both double-buffered and non-double-buffered versions of each, in the (yet another) attached DSK. Please enjoy and let me know what you think

[Axelay]

I think I'm more confused than you now, and I wrote the thing! : P

Glad I could help! 

Copying the screen is only necessary for double-buffering – I do need two copies of the cells, but not of their visual representation, if that's what you thought?

By the way you were AND/OR-ing the pixels in (iirc, or not), I thought you were preserving the contents of the bytes other pixel(s), so I thought that was why you were copying the whole screen, so you would only need to modify the changed cells on the visible screen.

Combining it with my data wouldn't work for the current methods or any of the ones I have planned, but I can see the appeal theoretically.

I thought this might well be the case, unfortunately after studying your earlier code a bit to confirm to myself my answer to your original question was good, I just couldnt quite manage to stop thinking about some of the rest of it. 

[db6128]

Yep, the pixels are masked, and cells are only plotted if they are changing. However, the screen does not have to be copied. That's only necessary if a static duplicate is desired to enable flicker-free transition between generations via double-buffering. There have to be two distinct buffers of the cells themselves (so that accumulating writes to the future do not affect reads from the present and thus mess everything up), but there is no such limitation to their pixels on the screen; altering the display on-the-fly is no problem at all.

My latest optimisations since the last DSK have gained significant speed-ups in both the basic MODE 0 version and QuadLife. QuadLife has gained about 80 ms per generation and thus is now running as fast as the non-colourised version used to, whereas that has sped up by 100 ms per generation and – whereas it wasn't quite there when I edited my previous post – can now indeed hit the milestone of 333 ms per generation, and thus 3 generations per second, fairly often.

I need a little break from moving squares for a while, I think...! but I doubt it will be long before I start on an editor and also some kind of basic interface for customising some parameters.

One thing I must correct: my calculations about MODE 1 were wrong... by a factor of 2, embarrassingly. The most lines I could get and still have some space left for code would by 118 (by 254), and I don't know if that's really worth all the trouble: mainly having to do the plotting entirely separately, naively, and using 4 possible shifts; but also losing colours (=less possible states/types); and other things, too. I'm considering other ways to do it, but I don't know if I'll judge it to be feasible enough in the end, at least at the kind of speed I want. So, MODE 0 is what I'm really thinking about.

[Gryzor]

Wow, now something is starting to shape at least. No laser sounds, of course, but gulping or withering-away sounds would be nice (good luck deciding which cells would emit a sound. O the cacophony!)

Yes, quite some interesting things going on there with your options, nice complexity! Thanks, this is turning out really nice

[db6128]

No laser sounds, of course, but gulping or withering-away sounds would be nice (good luck deciding which cells would emit a sound. O the cacophony!)

I know! Sir Alan, why so few channels ;_;

Wow, now something is starting to shape at least. [...] Yes, quite some interesting things going on there with your options, nice complexity! Thanks, this is turning out really nice

Thanks very much; I'm glad you're enjoying it!

—


Latest updates: The monochrome version now breaks the 3 generations per second (333 ms per generation) barrier for most frames, meaning that it's over 1.5× faster than the very first one I posted here. Ah, younger days... And QuadLife has also been sped up a lot, now hitting about 380 ms per generation instead of the slothful 450 ms of its youth. I've also resized the screen so that there's no gap at the bottom with the unused rows 28–31, which will also allow me to use their &800 bytes (4 rows × 8 scanlines × 64 bytes) of memory for not boring and definitely awesome things.

Once again, both are available in max-speed and double-buffered forms in the attached DSK, so as usual, please enjoy!

[db6128]

Confirmed to work on real hardware! Just as good... Actually, it seems even better/faster
Looks flashier on an actual TV, too, I must say – even if this is only one of 3 TVs (2 CRT, 1 flat) on which this RGB SCART cable works (1) with colour and/or (2) without ghosting/shuddering sideways – something I'll have to ask the seller about if it carries over to any more sets (I can believe that the two that didn't work might be due to their own faults, not the cable).

The only gripe is that, unlike WinAPE, my 6128 only accepts the first key of input and is unresponsive after that. I was just setting up the &F6 PPI A read, &F4 set matrix, etc. once and then only doing LD B,&F4:IN A,(C):BIT n,A within the main loop – is that not right?
Another program I tried seemingly crashed until I disabled my keyboard-reading code altogether, although that might be because it was using IN A,(C):JP P,0 to reset if the key in bit 7 was pressed, which might be a bad way to do it and might have made it reset every time.
Basically, on real hardware, which steps of that lengthy keyboard-initialising process are needed only once, and which are needed every time I want to test a key/line? Thanks in advance.

Also, I have to load things onto my 6128 via tape right now; can anyone suggest a better workflow than WinAPE -> 2cdt -> tapir?

Anyhow, off to find that BASIC type-in that supposedly identifies which CRTCs I have in my CPCs. The suspense... bad news for the 6128, at least :|

[db6128]

No, despite the date of the previous post, this project did not experience its own private Mayan apocalypse!

But a combination of holidays, extreme laziness, trying to buy a million synthesisers, and selling-my-laptop-and-having-to-use-a-crappy-desktop meant that I haven't felt like working on this for a while. However, I should be receiving a new laptop tomorrow – basically, the same exterior but several times better inside! – meaning that I will be able to compute in comfort, rather than having a desktop sitting on my floor (no, I don't have any other space here; that's how bad it is! Short of moving it into the kitchen – which is freezing), and will have a computer that I actually like.

So, WinAPE will doubtlessly be one of the first new residents of that oh-so-fresh hard disk, and I dare say that my constant procrastination will eventually redirect itself from extremely pointless things to slightly less pointless things such as the Game of Life. As I am fairly confident that it's almost exactly as fast as is possible (I know I've said that a million times, but look at it now: over 3 generations per second in monochrome mode!), including some additional speed-ups since my last released DSK, I will move to focussing on actual functionality, starting with a basic pattern editor.

I did wonder whether this could be a candidate for the 16 kB competition, but then it's not really a game, despite its name... Does anyone have any opinions on its validity or the lack thereof? Although to be honest, I don't think I'll have enough time to produce anything worthwhile, and I don't know whether the code being in ROM (mapped to the same range as the screen, thus freeing up the lower 48 kB) would offer a sufficient number of advantages. But I guess you never know what might happen if I find enough time... and, crucially, inspiration! Some of my previous breakthroughs did happen very rapidly, after all.

[Gryzor]

Just an idea - if you do a ROM version with it, maybe you could do a (slowed-down) version that runs in a corner window while the user can use the computer?

[db6128]

If so – world's biggest if! – that's actually a brilliant idea. But... I haven't a clue of how the separate window would be implemented, though; I imagine it would be easiest in BASIC, but I have no idea how it could be made to run in any other environment, particularly if the user was likely to be doing anything graphical of their own.

I don't have enough money to keep that laptop (returning it unopened), so programming won't be fun, but I may still give it a go. Sadly, no promises, as I don't know if I'll manage even to keep up with all my normal work starting soon, let alone programming on top of that. But again, y'never know.

[Gryzor]

Oh yes, obviously in BASIC, I doubt it could be made to work under anything else or if a program was loaded. Still it'd be fun

Too bad about your laptop, wish you the best

[litwr]

I am late but full of curiosity.  I hope somebody may continue talk.

This summer I developed such an application on the Z80, too. It isn't optimized (and still bugy), and I only focused on the interface/options/figure library/rule settings/memory friendly etc.:

I can't understand 0 and 9 stay alive/new cell conditions.  IMHO 9 is impossible case, and 0 is very difficult to implement.

If so – world's biggest if! – that's actually a brilliant idea. But... I haven't a clue of how the separate window would be implemented, though; I imagine it would be easiest in BASIC, but I have no idea how it could be made to run in any other environment, particularly if the user was likely to be doing anything graphical of their own.

Are there any news?  BTW I think it is possible to spend only about 65 NOPs per cell calculation.

[Prodatron]

I can't understand 0 and 9 stay alive/new cell conditions.  IMHO 9 is impossible case, and 0 is very difficult to implement.

Haha, yes, 9 was from an old beta version, which is shown in the video. The actual version only has 0-8.
But why is 0 difficult to implement? It's just a simple value which represents the number of neighbours, and this could be also 0.
There are quite interesting worlds you can create if using the 0 as well!

[litwr]

Wow!  Thank you for this reply. 

But why is 0 difficult to implement? It's just a simple value which represents the number of neighbours, and this could be also 0.
There are quite interesting worlds you can create if using the 0 as well!

"stay 0" condition is not difficult, but "born 0"... See the picture of the cellular automaton "period 168 knightship" designed by David Eppstein which has "stay 01" and "born 013568" conditions - http://litwr2.atspace.eu/demo/demo.html - or try it with Golly or Xlife.  
BTW where to take the new version of GoL for SymbOS?  This OS looks like something impossible for 8-bit computer...  The only dark spot is the absence of free sources.  I know man who wants to use it with Commodore.

Great stuff!    Would a 6502 be able to perform the same??   

http://litwr2.atspace.eu/xlife/xlife4cbm.html   

[kelp7]

Wow, love this project. Have been enamoured with Conway's "Life" since I first saw it as a kid on a VIC-20. Think I might write a version for my Z80 machine. Will be checking this out in an emulator