Javascript and canvas in the game "Life" by John Conway
Let us write this algorithmic game [1] so as to extract from it the maximum educational benefit in the field of algorithms, the Javascript language, good program style, the ability to optimize the code. The central place for discussion will not be the game, but the code, methods of implementation, optimization.It has been repeatedly stated in literature and articles that every programmer knows this game and that almost everyone has tried to program it. For example, various authors wrote that through it they learn new programming languages.
A recent survey [3] on Habré showed the real picture - 20% of programmers wrote its working implementation ever, and about 10% did not hear about it. Well, the more interesting the remaining 80% will be to find out what can be learned from the implementation of the game.
')
What kind of game is it?
A full answer will give the tag "game of life" on Habré [1] or an article from Wikipedia [2] . Another translation of the name of the game into Russian is “Evolution” (met in the journal “Science and Life” of the 70s). Another translation of the author's surname into Russian is Conway (John Conway, game "Life"). Here's what Conway himself says about the game (youtube, 4 min.) [4] , ibid - a vivid story about the rules of the game (English).Perhaps the reason for the non-headlong popularity in narrow circles is that, as Danov wrote in the commentary, "... warcraft and other simulators have nullified the excitement of moving squares." (But real mathematicians shouldn't be interested in this?)
If you search for results on youtube.com according to the words “life conway”, then we will find a lot of examples of demonstration of playing fields like “Life” [5] and games using similar rules, then according to connections - demo evolutionary algorithms, searching for the shortest way around and other interesting visual demos. So, over them somewhere there is a persistent "fruitful" work.But what are the fruits? After saturating the brain with visual effects, you will have to admit that this is a rather useless task if you do not explore other problems with it. For example, the speed of visualization in a particular language by different methods, the management of libraries of source data.
A lot of implementations in Javascript can be found by searching on google - “game life javascript”. But, due to the innate natural laziness of educated people, we will not go into their details. Later, after implementation, we will try sometime to compare the effectiveness of one or another solution. (I tried to do it, but I didn’t want to look beyond the 2nd decision on the quality of the result.)Idea implementation
Let's make it on the torus (more precisely, spirals), organized in the form of a linear array, so as not to care about the boundary effects. The parameters of height and width are variable, therefore the maximum rate of change of generations can be regulated by the size of the working field. The starting point of the array is shifted with each generation to record the results in the same array. The speed will be affected by the rendering method: text, table with background colors, canvas, pictures.Why exactly? The index of a one-dimensional array is calculated most quickly, therefore, if the task is reducible to a one-dimensional array, it is useful to use this. I remember that I did it on GW-Basic on an 80 by 50 text field to speed up, and satisfied the curiosity of observing the evolution of the most long-playing 5-point shape, resembling a square root sign. True, in the torus 80 by 50 she did not fit.
JS makes it convenient to do it because the speed and capabilities of modern browsers make it possible to portray everything you need on one page, therefore, debugging will be fast and convenient, and the working environment is not needed - everything is in browsers. A universal text editor with syntax highlighting will be useful (Notepad ++, E Editor, UltraEdit, ...).
OOP week on Habré
Further, we recall that we, writing educational articles, are responsible for all those who are accustomed to write poorly in JS, in the traditions of 2000–2005, when no one thought about global variables. Until yesterday, I also did not think about it and wrote how it would have to, but then it suddenly dawned ... Let's even arrange such a simple task in the best traditions of the PLO, encapsulating implementation details into an object. Not for nothing that the PLO week passed on Habré:
habrahabr.ru/blogs/cpp/111120 - “10 years of practice. Part 1: building a program.
habrahabr.ru/blogs/development/111125 - "Thoughts about the PLO."
habrahabr.ru/blogs/development/111162 - "Why OOP."
McConnell - "Perfect Code".
habrahabr.ru/blogs/javascript/111393 - "Wrappers for creating classes: evil or good?".
True, we will not need classes and inheritance, only the encapsulation of the implementation in the constructor.
Below is a script with the very overloaded methods that, if used in inheritance, would have given the effect of reproduction of functions and memory waste that was not recommended in the last article. But writing the word “prototype” unnecessarily on each function also did not want to duplicate the Mootools solutions in the native code too.
In general, a good overview on how to organize OOP in JS is known where [6] , so the next step for self-writing good code should be to study this article. But so far I do not see the urgent need to move to different coding styles.
All simple projects suffer from this: until there is a need to write “well” in the sense of a large, lively and expandable project, hands write “bad”. I think everyone went through the “bad letter” stage, until something made you write well. It will be interesting to hear the opinion of experienced comrades, as, for example, in this project to find the motivation for writing good code.
Script
In order not to litter the article with long codes with backlight (there are no spoilers on the Habré), we will publish them on another resource .
How and where to use the script
It is enough to take the above code through copy-paste into the HTML page to see its work. Or view the spmbt.imtqy.com/spmbt/lifeConway.htm page, [take] .
If the field size is too large for the monitor screen (I need at least 1400 by 1050), reduce the numbers in the “Width,” Height ”fields, then click on one of the“ Init ... ”buttons. The simplest interface on the buttons allows you to observe the actions described in the article with the script and the execution time from pressing the button to stopping execution.
Visualization
To begin with, the most unsophisticated version of the display is chosen - the text, believing that with the text display all browsers should have an excellent update rate. Then, after working with the text, you can try the graphics in different representations to compare the speeds.
Indeed, the measurements of the speeds of the first version on Opera 10.51 showed that the calculation time of the new generation was 30%, and the drawing time was 70%. A good ratio for visualization. And in 10 seconds, 1000 fields were drawn with the size of 180x150. If everything is started in the working cycle with viewing of each generation, it will be slower (reflow) - in 75 seconds (it depends a lot on the processor, browser and video card).
Comparison of script speeds in browsers
The results of checking for random filling field 180x150, 100 generations. (E2180, 2.0 GHz, Radeon X1650 video, WindowsXP)
(For correctness, the entire field should be on the screen, the window should be in focus, no other actions should be performed on the computer.)
| IE8 | 34c. |
|---|---|
| Opera 10.51 | 7.5c. |
| FF 3.6.10 | 125c. |
| Chrome 8 | 4.3c. |
| Safari 5.02 | 25c. |
Optimize for Firefox
The analysis shows that 80% of the time for calculating the 180x150 array eats away moving the calculated values ​​(w + 1 pieces, a little) to the beginning. And the interesting fact is that the first generation calculation is 100 ms faster than the next ones (a.splice (0, w1 + w1) is “responsible” for this). Hence, the source of inhibition is not so much the array itself, as part of working with it.
Of course, when the code was written for the first time, it was created consciously briefly, to the detriment of optimizations, but in favor of expressiveness. We rewrite the movement of values ​​in another way. Both the first cycle and the subsequent ones did not last for 120–200 ms, but for 90–100. (We will know that .splice () is not implemented in FF.) New code:
var b=[]; b = a.slice(iStart +w1+1, iStart +w1+w1+1).concat(a.slice(w1+w1, iStart+w1+1)); a=b; Testing of all browsers on the new code.| IE8 | 14.5s. |
|---|---|
| Opera 10.51 | 7.0c. |
| FF 3.6.10 | 12.5c. |
| Chrome 8 | 4.1c. |
| Safari 5.02 | 5.5c. |
What is useful from the abstract game? Future directions
The choice of language has greatly facilitated the development, because there are the necessary means of both calculations and visualization. There were data on the comparison of different visualization methods in different browsers, estimated the development time of the visualization task, similar to the real one. Perhaps someone will find a similar benefit from optimization techniques and test organization.
For future development, a suitable base has been prepared by selecting a thoughtful design of the program code. Depending on the direction in which further specialization will be relevant, we can choose ways to further improve the program.
1) mouse interface: by clicking and dragging the mouse, insert points, clear areas, add and rotate library elements, expand or cut the working field, shift the whole playing field;
2) store biblitechnye elements;
3) to work out the profiling of the program parts;
4) visually display the statistics of the generations in the game: changing the color of the dots depending on age, show the density and activity of changes;
5) optimization of the calculation speed due to the detection and elimination of empty fields (keep statistics of the empty environment on the basis of the same okr, so that on the next move you know whether to calculate the new value here);
6) to drop everything and do business: in real programs, you can also work out perfect techniques for yourself - they still pay for it.
Other forms of "life"
Among the rules of behavior of cellular automata, variations with interesting results are possible. A clone of rules with a hexagonal grid was mentioned. You can imagine and try to visualize three-dimensional lattices, observe the lifetime of cells, change the rules on a simple lattice. For example, for a long time, mathematicians suggested a clone of games with regard to the age of the cells - the younger ones are more enduring than the older ones. tangro said that he wrote a multiplayer game: "two players build figures on their half of the field in order to destroy the opponent's pieces." There are variants of cellular automata algorithms on graphs.
An example of a rule change
Let's try to expand the rules within the traditional cells (method .step ()). If we reduce the rules not to logic, but to a table, then we obtain a simple and universal table - the dependence of the next cell value on the sum of the values ​​of the surrounding cells.
| The number of environmental points | The next field value, if it was 0 | The next field value, if it was 1 |
|---|---|---|
| 0 | 0 | 0 |
| one | 0 | 0 |
| 2 | 0 | one |
| 3 | one | one |
| four | 0 | 0 |
| five | 0 | 0 |
| 6 | 0 | 0 |
| 7 | 0 | 0 |
| eight | 0 | 0 |
// () var prav = [0,0,0,1,0,0,0,0,0,0, 0,0,1,1,0,0,0,0,0,0]; // (180*150, 1000 4.5 .( )) for(i = iStart + w1; i >= w1; i--){ okr = a[i-w1] + a[iw] + a[i-w1m] + a[i-1] + a[i+1] + a[i+w1m] + a[i+w] + a[i+w1]; a[i+w1] = prav[10*a[i] + okr]; } It is easy to see that small changes in the rules lead either to empty fields, or to chaos (or maybe this is not chaos, but real life? :)), and the most entertaining behavior occurs precisely according to the Konevsky rules.
Modification of I.Sidorov (1975)
Let's follow the path of modifying the rules (the old article in “Science and Life” 1975, [10] ), which take into account the age of the points. Younger more resilient, but also more aggressive to the old. The author of the modification is the author of the article, the engineer-physicist I. Sidorov.
Here is a description in words from livejournal: "... the other rules are cells of two types, young and old. After birth, cell 1 is young, then it becomes old. Young cells do not die. Old cells without young neighbors survive the Conway rules. Old cells with young neighbors must have 2 neighbors (either young or young and old), otherwise she dies. Cells are born according to the same rules as Conway’s. "
To describe the rules of survival of old cells and fit into the same crucial matrix, you need to call the young cell number 5, and the old one - number 4. We get such a crucial matrix.
| The sum of the values ​​of environmental points | The next field value, if it was 0 | The next field value, if a [i] was = 5 (“young” point) | The next field value, if a [i] was = 4 (“old” point) |
|---|---|---|---|
| from 0 to 7 | 0 | four | 0 |
| from 8 to 11 | 0 | four | four |
| 12 | five | four | four |
| from 13 to 15 | five | four | 0 |
| more than 16 | 0 | four | 0 |
if(rule ==11){ // var prav = [0,0,0,0,0, 0,0,0,0,0, 0,0,5,5,5, 5,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0,0 ,0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0,0 ,0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0,0 ,0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0,0 ,0,0,0,0,0, 0,0,0,4,4, 4,4,4,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0,0 ,4,4,4,4,4, 4,4,4,4,4, 4,4,4,4,4, 4,4,4,4,4, 4,4,4,4,4, 4,4,4,4,4, 4,4,4,4,4, 4,4,4,4,4,4]; for(i = iStart + w1 + w1; i >=0; i--){if(a[i] ==1) a[i] =4;} for(i = iStart + w1; i >= w1; i--){ // okr = a[i-w1] + a[iw] + a[i-w1m] + a[i-1] + a[i+1] + a[i+w1m] + a[i+w] + a[i+w1]; a[i+w1] = prav[41*a[i] + okr]; } } And we will supplement the this.show () method with a line for the numbers “4” and “5”: var s = a.join('').replace(/0/g,'\xb7').replace(/[14]/g,'o').replace(/5/g,'s'); Let's see how the field with random filling works with these rules. Go to viewing the game according to these rules in the finished program, you can select the radio button "Sidorov's".The rules are checked and rechecked, even read again on the scan of the magazine. There are no errors in the implementation, static Konevsky constructions, indeed, live, “quanta” fly (checked, slightly changing initLib (), substituting “quant for clone”). But, unfortunately, accidentally filled turns into chaos. From which we can conclude that the rules are imperfect. Perhaps that is why there was no further mention of them. Large chaotic structures easily live indefinitely long without coming to cyclical variants. Obviously, the reason is the excessive stability of young cells. They need to define some rules of dying when surrounded by more than N neighbors, then maybe something will work out.
Thus, we have created a tool for modifying and researching other rules of the game. It would be nice to figure out how to make a symmetric (with respect to 0 and 1) variation of the game [7] , but you will have to do it not now, because it is nearing January 11th.
In the world there are many programs that support the game and its modifications. There are even data storage formats for the game. For dating, just look at one of the collections of references on the topic [9] . Therefore, in fact, the process of integration of the program just described with a huge array of developments has not even started yet, and the hours already spent by other researchers on surveys are measured in thousands.
UPD (01/12/2011): Day & Night variation of the rules [7]
A variation of the " Day & Night " rules has been added to the program, described in Wikipedia and interesting because if the field values ​​change from 0 to 1 and vice versa, nothing will change, the world will simply become "inverse", but living according to the same laws. With the prepared functionality, it was very easy to make an add-on (which was what we were aiming for).
if(rule==2){ var prav = [0,0,0,1,0, 0,1,1,1,1, 0,0,0,1,1, 0,1,1,1,1]; // (DayNight) for(i = iStart + w1; i >= w1; i--){ // okr = a[i-w1] + a[iw] + a[i-w1m] + a[i-1] + a[i+1] + a[i+w1m] + a[i+w] + a[i+w1]; a[i+w1] = prav[10*a[i] + okr]; } } This world has its own oscillators. The field tends to move to static and oscillating objects, there is no easy occurrence of moving objects, but they exist. All the rules and a small introduction can be read in English in the archive attached there, but they are also visible in the code above. The finished program can be run in the same place as the others, on one of the demonstration pages: [*] , double ; There is no add-on to codepaste.ru (for some reason I can not log in to change the version of the code). You need to select the “DayNight” radio button , and then - as usual.For observations, the initial conditions on the buttons are slightly changed: the random field is filled with a density of not 1/6, but 1/2. Over time, it tends to break up into small “white” and “black” areas in which static and oscillators live. The initial matrix of 2x2 blocks with 1 extra point didn’t “explode”, so I added one more point to initiate the process. After that, the "explosion" also turns out beautiful and original.
A long-lived figure in the usual “Life” (the “Init 'r'” button) turns out to be an oscillator with a period of 16 in this world. To conveniently set any shapes, a cycle of laying out a fragment of a field was added ( taken from the description "[Figure 15. Two p32 ships collide to form a rocket]" - a collision of 2 ships). Then the resulting rocket is aimed at an oscillator. By the 400th move, we see a “swirling cloud” after a rocket collides with an oscillator, which soon disappears.
As it turned out, this is a rather interesting modification of the game, with its own peculiar behavior.
Visualization on canvas
Thinking about better visualization is caused by 3 reasons:
1) the influence of the text display styles in browsers on the text strings that make up the playing field (there are irresistible browser settings "minimum font size");
2) the display time is longer than the step calculation time;
3) large fields in browsers can work, but with a cell size of 1 character, they do not fit in the window.
We will not experience clutter of pictures, cells of tables, blocks, absolute positions of tens of thousands of elements - there are doubts about their simplicity of organization, therefore - about the speed of work. We will draw on canvas canvas.
We use a quick, but not the most efficient method to start with: drawing each point during each move to evaluate the power. It is clear that then it can be optimized by drawing sprites (putImageData ()). But even in the first approximation, the canvas gives it the expected: the speed of work increases, and the scale can be reduced by 2-3 times.
To enable the canvas mode (“canvas”), turn on the checkbox “on canvas”, change the point size (“size”), draw options (checkboxes “rect”, “grid”), then choose one of “init ...”, then - "Step".
Let's arrange drawing of 4 options: circles, rectangles , with a grid and without it. Of course, the rectangles should be drawn faster, which is confirmed by experiments. With small cells, the shape of a point no longer matters, so we have savings without losing quality.
The grid is clearly a disadvantage - to draw each point. If it were necessary to optimize, it is better to make the canvas a little transparent, and to position the grid under it. Better yet, announce the background image on the canvas itself. In our program, we can estimate how grid drawing is unprofitable. If there are a few points (100 to 200), then we can agree with their drawing.
Note that now the more points on the screen, the slower the script, because it needs to draw every non-empty point. It is also noticeable that drawing a circle edging (stroke ()) is very poorly digested by the script. Therefore, I did not display it in the checkbox, but simply commented out - who is interested, he will check.
At the end we will lay out the most beautiful achievements: “explosion” of a regular matrix of blocks for 200 moves on a 408 by 402 field in the fastest canvas (Opera) browser; table of processing speeds of different modes in different browsers; picture of the result of the “explosion” of the block matrix "- from 1 point the action was completed in 38 seconds, 5.3 steps per second.
Life of a randomly filled starting field, 100 steps (e2180, 2.0 GHz, ...)
| Browser, 180x150, execution time (s) | text, 12px | canvas, circle, 6px, grid | canvas, circle, 6px | canvas, square, 6px | canvas, square, 4px |
|---|---|---|---|---|---|
| (cell type) |  |  |  |  |  |
| IE8 | 14.5 | - | rest | in | peace |
| Opera 10.51 | 7.7 | 18 | 6.8 | 4.5 | 4.2 |
| FF 3.6.10 | 15 | 41 | 14.5 | 12 | 14 |
| Chrome 8 | 4.2 | 46 | 7.6 | 5.0 | 4.0 |
| Safari 5.02 | 5.5 | 61 | 10.8 | 5.3 | 4.8 |
The destruction of a stable matrix of 2x2 blocks, caused by one extra cell.
Recall that this is not the fastest canvas achievable in the algorithm, the use of sprites should improve performance. In general, we see that Javascript naturally, with the improvement of browsers, shows its strength and provides a convenient environment for experiments in solving applied problems.
Conclusion
Run game programming option. Some lines of code are written without regard to the principles of high-quality code — for example, there are repetitions of statements. Probably, the quality of the code needs to develop a glimpse, and perhaps this is a normal practice - to write the code “as necessary”, which is not used in the future, and then rewrite the parts of interest.
Links
*. Working implementation for the article. (01/11/2011) , double .
1. Selection by tag "game life"
2. Wikipedia - Life (play)
3. Poll for programmers: did you write the implementation of the game “Life” of Conway?
4. John Conway Talks About the Game of Life Part 4 (4:10)
www.conwaysgameoflife.net - Conway's Game of Life
5. youtube.com, "game life conway" . The most interesting videos:
5.1. Amazing Game of Life Demo (4:47) many very complex organized designs.
5.2. Cellular Automata: Conway's Game of Life (3:56)
5.3. Conway's Life - Cyclic Universe (0:40)
6. OOP in Javascript: inheritance. I. Kantor
7. Day & Night , symmetric implementation of the rules regarding the values ​​of the fields "0" and "1" in a game similar to "Life".
8. Mathematical game “Life” . Other programs and game description.
9. Links to the game "Life . "
10. Description of the modified rules taking into account the age of the cells from the article in “Science and Life”, 1975, # 3, “Evolution of the game“ Evolution ””, I.Sidorov ( archive - DjVu). Scans of this and similar articles.*) Idea for abnormal programming: the game Life on Excel without macros.
**) At the time of writing, no working hour was hurt.
Source: https://habr.com/ru/post/111686/
All Articles