Conway's Life for speed

[Donone]

Attached is an attempt to get speed for this 'old chestnut'. It can be improved visually of course, with 'bells & whistles', but I am interested in speed. I believe I have optimised the logic of the 'neighbour' process (challenge) but don't know if there is a better way to utilise the Game API or whether routines should be elsewhere in the scheme of things.

OR whether there is a better (faster) approach than my use of cloned sprites.

Give it a try and then let me know if it can be improved (not fancy options; which are fairly obvious). There is a text file detailing changing grids etc.

[zehlein]

Hehe, so old Conway alive again. :)

I#m not sure if the idea of using a sprite for every cell is a good idea. This will surely produce a large memory and processing "overhead". Imagine a 120x120 grid - there would be nearly 15000 sprites to mangage for the GameAPI .
In my approach from the January 2008 PPL Newsletter processing of a 120x120 grid takes as much time as your way with a 40x40 grid. I think the main reason for this is the graphics stuff. The line 54:
ShowSprite(cells$[x$,y$],neighbours(x$,y$));
eats up well over 40% of the processing time.
I guess accessing the screen (or at least a buffer-surface) directly is way faster.

[Donone]

I don't think the neighbours analysis can be reduced any further, but I want to know more about the display. Surely a sprite is all you use to 'see something'. You mention buffer but is that not just a copy of the screen to work on without it showing until finished?

Possibly changing individual pixels could be done, using a pixel as a sprite but then they would be minute in size would they not?
I would like to be able to see the individual patterns. This also requires a visible grid?? Plus it is required to 'key in' a start patter which I imagine to be difficult at pixel level. The idea of the game is to experiment with different patterns rather than just watch pre-set ones. In addition it must be a spherical surface not just flat.
That said...

I am eager to hear more if you have time to give. I did look at your program but to get the rules and to see what optimising was all about, but I did not take much notice of the actual program.

[zehlein]

I don't think the neighbours analysis can be reduced any further

Oh, I'm pretty sure it can be made faster ;-)

The starting point would be the observation that most of the grid contains switched-off cells while cycling through the generations. And off-cells don't generate on-cells. So the idea would be maintaining a list that contains cells that could *possibly* get switched on/off at the next cycle. Everytime a cell gets switched all neighboring cells and the cell itself would be added to the list. At the end you should only have to cycle through the list's elements to determine their status for the next generation, not through the whole grid.
This is will probably slow down the processing of little grids (say 30x30) but would be a huge time-saver for bigger grids!
And the interesting things with Conway's lif need *big* grids! :-)

[kornalius]

I am looking into greatly reducing memory consumption for sprites in version 2.0. It is on my to-do list. I realized a while ago that it is a design flaw but it is already embedded very deep in the GameAPI engine, so it will need some rewriting which I don't want to get into until version 3.0.

[Donone]

:) Before starting, please be aware that none of my comments were or are to be taken as a challenge or a slight or anything else that is not straightforward discussion; sometimes I am accused of using inflammatory words inadvertently :) :)

I don't know if I have mis-understood your statement, but off cells 'can' generate on cells by a birth. Not sure whether you meant only 'on' neighbours rather than cells.
I think (though without proof) that the process of pre-analysing will take considerable effort and code. The tables or whatever will have to be tested during running?

When I said that I didn't think neighbour analysis could be reduced, I actually meant simplicity of statements, shortness of code etc. (no ifs); rather than speed. Basically because analysis is fast compared to display and so is not so relevant to the overall speed, and so simplicity is perhaps more important, with less risk of bugs.

My reference to speed was really to do with display, which I do not know enough about. Perhaps kornalius' comment regarding V2 may help in the future.
I can think of no other way than sprites (if you take my other comments into account about the game in general, rather than a competition for speed).

I believe that the thing slowing down any analysis of neighbours is lots of IF or other testing statements. If you look at my example of analysis it only does addition (the neighbours are not scanned in a loop or even tested (only the main cells) and the same loop covers the redrawing as well), there are no (buffers?) for analysing off edge wrapping it is simply done by Mod-ing.
I am not suggesting one way is better than the other, each has their merits.

I simply feel that the fewer individual 'tests' in the process the better.

As I said before to really make the 'game' useful you need to be able to see more clearly the individual automatons, which is helped by a grid. That by itself forces automatons to be bigger. That then means they can only be single pixels (rather than sprites) when wishing to illustrate pure unadulterated speed rather than a usable tool.
Also it is hardly possible to individually 'set up' the board manually with pixels.

Back to your main point... It would be nice to see whether the overhead of cutting the number of cells tested by testing whether they should be tested, does save code (or time even) or whether it balances out (or even slows it). Difficult to know by pure thought.

If you have nothing to do... ;)

So, also, back to my original point, given that something bigger than single pixels need to be used, is there a better method than that which I have chosen (having sprites present and turning them on/off)?
Could your pixel method be used but for say a block of 4 pixels per automaton and thus be faster than sprites? (or does that make them sprites??)

It would be nice to have an inkling before venturing out, so any knowledge you can bring to bear on those questions would be very gratefully received.

My purpose in still pursuing this; it is a useful way for me to learn the different aspects of PPL and how various parts work (because I don't have a clue about Windows programming and it's probably (nay; is) too late to start learning that as well).

No one long involved programme being written, permits all the areas of PPL to be explored. I find that writing small items like this on different subjects opens different areas/skills.
Becoming an eventual expert on the display/gameapi aspect, will still leaves me a dummy in other areas.

I hope I haven't taken too much of your time (reading) this. But then you didn't have to.

[zehlein]

Hi Donone,
it's always a pleasure to be in conversation with you. It gets myself back to thinking... :)

If you want to drwaw not a single point but a rectangular shape to the screen/surface g_DrawRect is your friend.

To make it a bit more clear what I had in mind with my previous post:
I would cycle through the whole grid only *once* to get a list of possibly changing cells.
After this is done I would only have to go through that list to compute the next generation because the cells that are not in there can't change and there is no need to test them. While processing the list I would build up the list of possibly changing cells for the next generation that would be my basis for the next cycle.
As for the performance:
My 120x120 grid has 14400 cells. If I start with a simple line of 10 switched-on cells (the rest being switched off) the list of possibly changing cells contains only 36 cells! That's all I have to test. The next generation only has 50 cells that could possibly change...
I think the difference here is obvious - it should be much faster to test only the cells that could possibly change rather than cycling through 14400 cells for every generation.

[kornalius]

You might want to look at Particles as well. Just an idea.

[Donone]

@kornalius
I had always thought (having used them with TurboSprite with Delphi) that particles were simply random. I have always avoided them in PPL on that basis. From your suggestion, this must not be the case and I will certainly look into how they work. They sound more interesting now.

@zehlein (my friend who helps me out)
I realise now what you are saying. I didn't really pick up the significance of 'List', I thought you meant that each time, you would 'find out which' (list) items for change and I considered that it would take just as much effort to do this.
I can see what you are suggesting, by a real List, and I think it would be interesting to follow up, (which will of course refresh me on their use).
There may be a little danger perhaps when the overall population grows very large, but that is difficult to predict.

I presume from your rectangle comment that it would still take less to do that than use a sprite, though I don't know enough about the engine to judge either way.

I was going to drop this, but it will be a useful learning tool to try to follow up your's and kornalius' suggestions.
If you have any thoughts to get me started then please suggest. Then I will keep you informed.

[Donone]

If anyone is interested? Deeper thought on this reveals more processing...

Duplicates will cause extra checking, either to avoid them or to process them.
The only way I see to avoid that is a 'lookahead' and 'lookback' which would be extremely difficult and add to processing. My brain is not sharp enough, yours may be.

e.g. If a cell and all adjacents including empties (to allow for births) are listed, then when an adjacent happens to be full its adjacents are listed, and they can overlap with what has already been listed. A stack would be required to keep track of what has been entered involving 'the current cell' and the one that is about to be checked for entry to the list and possibly the previous, because the overlap is also backwards one column or even up one row. (corners double the overlap). [This may be the basis of a simpler test]

When a cell dies it must be removed from the list... 'unless it remains a possible birth' governed by its neighbours, some of which have already been accepted/rejected from the list.
Probably sometimes its neighbours should also be removed. Failure to do this could end up with a list that eventually includes all cells.

Witness the situation of a heavily populated board with also a single filled isolated cell. When it dies (as it will) all neighbours should be removed.
If that filled cell is instead near others, that is not the case and some of those neighbours will/'may' be neighbours to others or may be possible births and should therefore remain.
One way to avoid this would be to totally re-produce the list every generation, rather than modify. But then we are back to processing all cells (one way or another) every generation.

It should be remembered that we are processing an ever changing list against a board.

It is beginning to look extremely complicated to avoid checking all cells.
Difficulties arise as early as simply having the user manually set the initial pattern (which may be done at random and use already entered 'empties'. Unless the list is only produced 'after' the pattern is set, not during entry (unlike the list produced while running).

Perhaps a compromise is reached by checking all cells but not checking neighbours 'until' a filled cell is discovered... or something... or something.
My brain hurts. Perhaps somebody is interested enough to add to this discussion. :)

[zehlein]

Hi Don,

I'm afraid I did not explain the list approach exactly. In fact, you will have to use *two* lists. One list you go through while computing the actual generation. And by doing so you build up the second list, which you will use for the next generation's computing. The first list gets emtied and filled again using the seconfd one and so on. In the meantime you have to maintain a grid-array (better two again, I think) to keep track of the generations.
Of course the list should be checked for duplicates...

[Donone]

Hello again zehlein. using two lists and emptying one will get rid of my stack (i expect). I do like the principle of ignoring off cells that have no live neighbours. I will investigate further.

[zehlein]

Hi Donone (and whoever might follow this silently :)),
I took some time today and implemented my idea with the lists. Works great and faaaast!
Processing time per generation is now independent of the grid size (which allows larger grids of course). Even with the little grid I used for my tutorial the new version speeds up things by 30%.
There seems to be a flaw in the edge wrapping logic I think, I will take care of that later.
Try a 200x200 grid! Lightning fast! :D

Attached you find the latest version

[Donone]

Hello zehlein. I have not been able to study your code yet it will probably take me ages. (I actually find it 'very very' difficult and it takes ages, to follow someone else's code, I don't know why.)
I have noted something about padding cells for the edge that you mention, and 'assume' that it some method of copying the opposite edge or something. I can suggest the following to treat the edges as a continuous sphere as in...

//Account for wrapped edges

y$=(y$-1+maxcellsY) mod maxcellsY;
y$=(y$+1+ maxcellsY) mod maxcellsY ;
x$=(x$-1+ maxcellsX) mod maxcellsX;
x$=(x$+1+ maxcellsX) mod maxcellsX;

The above checks neighbours for any cell X$,Y$ and will work wherever the cells are, middle or edge, there is no difference. At the edge the neighbours wrap and are taken from the opposite edge, either 0 or max.

I started work but you beat me to it. Well done.:D

However I am including the ability (which I personally think is essential) to have the user select the start pattern by clicking the screen as in my original.
Unfortunately a problem arises when a cell is selected and it's neighbours added to the list and then the user realises they have mis-selected (very easy) and de-selects that cell which then requires the neighbours to be removed from the list. They cannot be removed easily because they may also be neighbours to a cell that remains. (i.e. they 'were' duplicates.) Further tests are then needed.
One could attempt to remove simply the last added (undo), but unfortunatley the user may not change the last one entered, but one entered several clicks ago.

I have only got that far because unless I can add remove cells, I cannot test.
My aim was not to start afresh because I have a displayable system, so I am modifying the old (including user startup). Then when it works with sprites I will change the display part to try to use pixels or particles. The two parts are actually separate, the display and the logic.
See you sometime.

[zehlein]

...
Unfortunately a problem arises when a cell is selected and it's neighbours added to the list and then the user realises they have mis-selected (very easy) and de-selects that cell which then requires the neighbours to be removed from the list. They cannot be removed easily because they may also be neighbours to a cell that remains. (i.e. they 'were' duplicates.) Further tests are then needed.
One could attempt to remove simply the last added (undo), but unfortunatley the user may not change the last one entered, but one entered several clicks ago.


You may solve this problem by simply building up your list after the user did build up his startup figure. Cycle through the grid and run a "AddCellsToList" procedure everytime you find an "on"cell.
On the other side there is no need to care too much about a few extra processings. They do no harm and for the following generation they have no influence at all.

[Donone]

You are correct of course zehlein, I have had a mindset, difficult to shake off, to add to the list as items are generated. I absolutely hate loops and ifs.
Problem solved thank you.

[Donone]

Well, zehlein's suggestion to only process cells that might change has made a good speed improvement on my PPC one generation per half second instead of one per second (guesswork by observation) Haven't tried a larger grid or smaller.
Have done this in two stages (display - sprite clones - not changed yet. Only change one thing at a time.

There are two places where a full scan of the grid is still used, one is to clear the next generation boolean array, I don't know of a quick way to set all entries to False/0.
The other is to scan for the list, caused because of the earlier post regarding only being able to produce the list 'after' not 'before' the user has set up the pattern by clicking.

Solving that would enable the list to be done as clicked and therefore save a scan. I have used the same routine 'MakeList' throughout. It could probably be solved :)

The biggest process user is the gameproc and obviously a new approach is needed.

[zehlein]

There are two places where a full scan of the grid is still used, one is to clear the next generation boolean array, I don't know of a quick way to set all entries to False/0.
The other is to scan for the list, caused because of the earlier post regarding only being able to produce the list 'after' not 'before' the user has set up the pattern by clicking.


Emptying your Array can be done using
empty(YourArrayName$);
this is fast as lightning.

The other full-grid scan surely has no impact on the performance of your program it is really only done once while all the other stuff you do for every generation might make a difference in speed.

[Donone]

Thank you for that magic function zehlein, I think I must be losing my vocabulary, I can never seem to think of a word that might achieve my desire.

Regarding the other...
Yes I can scan the whole grid once to enter the start pattern and so no impact, but I used the same routine to create the list in all generations which my internal comment says can be reduced.
At the time I could not think of a way other than clearing the list for the next generation.
I have now been to bed and have decided on removing from the old generation list, all but live cells then running the Getnbs routine as before to add surrounding possible changing cells. That will reduce the scan as it should be.

In the scheme of things, this part of the program is not the most important until I can get rid of sprites which have too much overhead baggage (as you pointed out they are slow for this kind of application). Even particles are sprites, so I think they are out.
I shall consider blocks of pixels, (or rectangles as you hinted) hoping they will be faster but more visible and manageable than singles.

I value your continued input.

[zehlein]

Hi Donone,
regarding your creation of the ToTest list in every generation: the speed gain of the list approach comes from *not* cycling through the whole grid for every new generation. You can achieve this easily by adding the cells and it's neighbours that change in the actual generation only to the new generation's ToTest list. The trick here is to understand that cells that are not in the neighbourhood of changing cells can't change their state in the next generation. So you only have to process the cell that changed and it's neighbours and therefore only these go to the new list.
Another thing I stumbled upon is your using of the ToTest list. It grows longer and longer and will eat up a lot of memory eventually. You could avoid this by using two lists:
* actToTest list: that contains the possibly changing cells for the actual generation
* newToTest list: you fill up that list while processing actToTest and fill it as mentioned above
* after you are ready processing the actual generation you empty(actToTest) [yes, that works here, too :)]
* you copy newToTest to actToTest with AddList()
* you empty (newToTest) and fill it up again while processing the next generation

At least that is the way I do it at the moment...
Hope that helps!

[Donone]

Thanks for your comments zehlein, which I will study carefully after this quick reply.
I am grateful for the time you give to this.
I have mental aversions, call it obsessive behaviour, habit, non-flexibility, regarding length of code (and an attempt at elegance where possible) rather than speed, though of course speed *is* the essence here. It costs me hours.

I realise that the speed gain is not processing unchangeable cells. My problem was that I started from a position of user entry. That meant (as explained) that I had to do a *complete scan* to find those cells entered. Providing the user the ability to *draw* the first generation, sucked me into a hole. *That was actually a major problem.*

So the full scan could not be avoided. I then had to create the cycle, the first item of which 'MakeList' was this scan. I couldn't get 'it' out of the loop to introduce a second procedure to deal only with the previous generation cells. I would then only use the full scan once. There was my error!

Hence my thinking was that by simply removing the *empty* cells from the processed list and re-neighbouring with the new changeable empties I could avoid a second list. (I know it costs little, to have two.).
Donone wrote:
... have decided on removing from the old generation list, all but live cells then running the Getnbs routine as before to add surrounding possible changing cells. That will reduce the scan as it should be.

The growing list would be solved by this approach also because at each generation all that is left in the list are the live cells.

I will review your comments because speed *is* in this case the essence.
How is this speed measured please? I do it by eye, which is not close to accurate.

[EDIT] Final version of generation logic, before investigating use of pixels instead of sprites.

[zehlein]

For measuring speed I use the Profiler (Run -> Profile). This gives you information about the time and percentage of of processing time used by every procedure/function and, if you right cklick in the profiler window and activate details even for every single line of your code.
Keep in mind that if you want to compare results you should always start with the same on-cells in your startup-generation (that's why I used this single line of on-cells in my program) that should not be set by hand but by software. Furthermore cycle always through the same number of generations (use a while-loop).
Another approach would be using the tick() function to count the elapsed time.

[Donone]

Thank you for that info zehlein, I have just tried it, wow! what a useful tool. I shall now play for hours, testing things.

I see that I forgot to post the last code version, so do it here, editing doesn't permit sending files.

I have used one grid to check for duplicates (Used$).
Single list for current and next generation (lToTest$).
Removed the Next Generation array (ng$)

I'm afraid my obsession took over and forced me to try a single list for cheapness (I am not Scottish).

Once a generation is produced in the list, all empty neighbours are removed from the list, leaving only the live cells which are then re-neighboured in the same list. It should not grow for ever. (I don't know how to check that, but cannot see how it can).
The same List is then used to scan for birth/death neighbours.

Having used this Profiler I have determined that using a single list for both generations, i.e. while looking for neighbours, has slowed it down. It also seems irregular but that might be due to using sprites as the main grid.

This has illustrated to me that trying to use resources meagrely, whilst maybe elegant in the use of code, is not practical/sensible if speed is the main factor.
The obvious answer is to use as many grids and lists as desired and code loosely, anything for speed. Wow again, that profiler is great. I also note a Memory checker, I can't find a help on it.
*I shall now try your suggestion of two lists*. Thank you.