Universe Life - досл≥дженн¤ кл≥тинних автомат≥в

 р≥м гри "∆итт¤" ≥снуЇ багато ≥нших кл≥тинних автомат≥в, ≥з своњми правилами, ¤к≥ можуть бути ¤к под≥бними до закон≥в "∆итт¤" так ≥ дуже в≥дм≥нними в≥д них. ƒл¤ того, щоб ¤кось класиф≥кувати вс≥ закони кл≥тинних автомат≥в, њх об'Їднують в с≥мейства. «акони одного с≥мейства, ¤к правило, под≥бн≥ м≥ж собою ≥ в≥др≥зн¤ютьс¤ один в≥д одного менше, н≥ж закони р≥зних с≥мейств.

≤снуЇ досить багато с≥мейств кл≥тинних автомат≥в (—ј с≥мейств). ѕрограма Universe Life п≥дтримуЇ компексне с≥мейство УWeighted LifeФ, ¤ке дозвол¤Ї запрограмувати де¤к≥ ≥нш≥ —ј с≥мейства - "Generation", "Life", "Vote".

Life

—аме перше —ј с≥мейство, ¤ке п≥дтримуЇ закон гри "∆итт¤" (в≥н ще називаЇтьс¤ закон Conway`s Life). Ќа ньому базуЇтьс¤ багато ≥нших с≥мейств кл≥тинних автомат≥в. «акони с≥мейства Life в≥др≥зн¤ютьс¤ один в≥д одного лише значенн¤ми "¬иживанн¤" ≥ "Ќародженн¤". “обто ¤кщо дл¤ ∆итт¤" стр≥чка "¬иживанн¤" маЇ значенн¤ 2 ≥ 3, а стр≥чка "Ќародженн¤ маЇ значенн¤ 3, то ≥нш≥ закони Life можуть мати стр≥чки ≥з ≥накшим набором значень.

«акони гри "∆итт¤"

√ра "∆итт¤" була створена ƒжоном  онвеЇм у 1970 роц≥ ≥ моделюЇ розвиток "математичних живих орган≥зм≥в" - кл≥тин на де¤к≥й площин≥, ¤ка под≥лена на кл≥тинки.  ожна кл≥тинка може бути в двох станах: "живому" чи "мертвому". Ќа розвиток кожноњ кл≥тини площини впливають 8 сус≥дн≥х кл≥тин за такими правилами (¤к≥ ще називаютьс¤ "генетичними правилами  онве¤"):

1. якщо в кл≥тини Ї б≥льше 3-х або менше 2-х "сус≥д≥в" (тобто "живих" кл≥тин), то кл≥тина "вмираЇ" (в≥д т≥сноти або в≥д самотност≥).
2. якщо к≥льк≥сть "сус≥д≥в" знаходитьс¤ в межах 2-3 включно, то кл≥тина продовжуЇ жити. («наченн¤ 2 ≥ 3 називаютьс¤ значенн¤ми "¬иживанн¤". ј сукупн≥сть цих значень називаЇтьс¤ стр≥чкою "¬иживанн¤")
3. якщо пуста кл≥тинка маЇ р≥вно 3 живих сус≥дн≥х кл≥тини то в н≥й "народжуЇтьс¤" нова кл≥тина. (ј значенн¤ 3 називаЇтьс¤ значенн¤м "Ќародженн¤")
4. ѕроцеси "народженн¤" та "смерт≥" в≥дбуваютьс¤ одночасно.

“аким чином сукупн≥сть кл≥тин на площин≥ "живе" ≥ "розвиваЇтьс¤", аж доки вс≥ кл≥тини не зникнуть з площини або колон≥¤ кл≥тин не стане стаб≥льною чи почне цикл≥чно повторюватись. «м≥ни, ¤к≥ переживаЇ колон≥¤ в своЇму розвитку, дуже часто Ї досить красивими ≥ захоплюючими.

—ус≥дн≥ми називаютьс¤ т≥ 8 кл≥тин, ¤к≥ дотикаютьс¤ сторонами та кутами до кл≥тини, дол¤ ¤коњ визначаЇтьс¤, так ¤к показано на малюнку:

ќбласть сус≥дн≥х кл≥тин

оди сус≥дн≥х кл≥тин

 ожна сус≥дн¤ кл≥тина маЇ св≥й код, центральна кл≥тина маЇ код ME, це саме та кл≥тина, дл¤ ¤коњ п≥драховуЇтьс¤ к≥льк≥сть живих сус≥д≥в.  оди сус≥дн≥х кл≥тин використовуютьс¤ при кодуванн≥ правил.

¬ажливо!
якщо на ¤комусь кроц≥ дл¤ ¤коњсь кл≥тини настали умови смерт≥, то в цьому кроц≥ кл≥тина ў≈ ∆»¬ј ≥ враховуЇтьс¤ при п≥драхунку живих сус≥д≥в дл¤ ≥нших кл≥тин. “ак само, ¤кщо дл¤ ¤коњсь кл≥тини настали умови народженн¤, то в цьому кроц≥ кл≥тини ў≈ Ќ≈ ≤—Ќ”™. ÷е означаЇ, що в межах кроку кл≥тини просто позначаютьс¤ ¤к т≥, що мають народитись, ≥ т≥ що мають вмерти, ≥ лише в наступному кроц≥ це в≥дбуваЇтьс¤.

• ѕерша кл≥тина маЇ лише одну живу сус≥дню кл≥тину.
• ƒруга кл≥тина (середн¤) маЇ дв≥ жив≥ сус≥дн≥ кл≥тини.
• “рет¤ кл≥тина ¤к ≥ перша - маЇ лише одну живу сус≥дню кл≥тину.

Generation

ƒосить ц≥каве с≥мейство правил, схоже по умовах "народженн¤" та "виживанн¤" на "Life". ¬≥дм≥нн≥сть в≥д "Life" пол¤гаЇ в тому, що ведетьс¤ так звана "≥стор≥¤" кл≥тин.  ожна кл≥тина маЇ "в≥к" в≥д 1 до 256. ѕри народженн≥ кл≥тина отримуЇ в≥к "1" ≥ збер≥гаЇ його до тих п≥р, поки дл¤ нењ не настануть умови "смерт≥". ѕ≥сл¤ цього кл≥тина "стар≥Ї" - кожного покол≥нн¤ њњ в≥к зб≥льшуЇтьс¤ на 1.  л≥тина зникаЇ з пол¤ лише тод≥, коли њњ в≥к дос¤гне визначеного законом значенн¤. ѕри п≥драхунку к≥лькост≥ живих кл≥тин враховуютьс¤ лише т≥ кл≥тини, ¤к≥ мають в≥к 1. ÷е все досить сильно зм≥нюЇ правила цього с≥мейства.

• Ќа першому кроц≥ жодна ≥з кл≥тин не помре, так ¤к дл¤ жодноњ ≥з кл≥тин не настають умови смерт≥. ѕроте народ¤тьс¤ дв≥ кл≥тини (м≥сце народженн¤ показано червоною крапкою).
• Ќа другому кроц≥ умови смерт≥ настануть дл¤ вс≥х кл≥тин, так ¤к кожна ≥з кл≥тин маЇ три ≥ б≥льше живих сус≥да.  р≥м того, народ¤тьс¤ 4 нових кл≥тини.
• Ќа третьому кроц≥ т≥ кл≥тини, дл¤ ¤ких настали умови смерт≥ на другому кроц≥ - "постар≥ють" на одиницю (показан≥ син≥м кольором). ј дл¤ кл≥тин, що народились на другому кроц≥, настануть умови смерт≥, тому що вони не мають жодного живого сус≥да ≥з в≥ком 1. ” м≥сц¤х, в≥дм≥чених зеленою крапкою, також не народ¤тьс¤ кл≥тини, тому що хоч в тих м≥сц¤х к≥льк≥сть живих сус≥дн≥х кл≥тин ≥ р≥вна трьом, але не вс≥ ≥з тих кл≥тин мають в≥к 1.
• Ќа четвертому кроц≥ т≥ кл≥тини, дл¤ ¤ких настали умови смерт≥ на другому кроц≥, знову "постар≥ють" на одиницю ≥ так ¤к тепер њх в≥к р≥вний трьом - зникнуть ≥з екрану. “≥ кл≥тини, що народились на другому кроц≥ постар≥ють на 1 (показан≥ син≥м кольором).
• Ќа п¤тому кроц≥ вс≥ кл≥тини зникнуть ≥з екрану.

ѕроте цей приклад не Ї характерним дл¤ правил с≥мейства "Generation". ’арактерною особлив≥стю б≥льшост≥ закон≥в цього с≥мейства Ї те, що в ньому дуже багато рухомих конф≥гурац≥й. ¬ де¤ких правилах достатньо двох поставлених в р¤д точок, щоб на пол≥ почавс¤ рух великоњ к≥лькост≥ р≥зноман≥тних конф≥гурац≥й. ÷¤ особлив≥сть по¤снюЇтьс¤ тим, що при п≥драхунку к≥лькост≥ живих кл≥тин враховуютьс¤ кл≥тини ≥з в≥ком р≥вним 1. ј отже кл≥тини, що мають б≥льший в≥к заважають розвитку. ≤ коли ц≥ кл≥тини знаход¤тьс¤ лише ≥з одного боку конф≥гурац≥њ, то нов≥ кл≥тини народжуватимутьс¤ т≥лкьи з ≥ншого боку. ÷е ≥ приводить до руху конф≥гурац≥њ.

ќсь, наприклад, найпрост≥ший косм≥чний корабель правила Brian's Brain: блок кл≥тин 2х2. јле з одного боку кл≥тини мають в≥к 2, а з другого 1. ÷е правило не маЇ значень "¬иживанн¤", а лише одне значенн¤ дл¤ "Ќародженн¤" - 2. ÷е означаЇ, що стан смерт≥ на пол≥ настаЇ дл¤ вс≥х кл≥тин. јле таке низьке значенн¤ дл¤ народженн¤ даЇ велику к≥льк≥сть новонароджених кл≥тин. ѕроанал≥зуЇмо цей косм≥чний корабель.

• Ќа першому кроц≥ дл¤ двох живих кл≥тин настануть умови смерт≥, ще двоЇ син≥х (≥з в≥ком 2) постар≥ють на одиницю, ≥ народ¤тьс¤ дв≥ кл≥тини (м≥сце народженн¤ показано червоною крапкою). јле народитись кл≥тини зможуть лише з одного боку - з того, де немаЇ син≥х кл≥тин.
• ƒругий крок аналог≥чний попередньому: дл¤ тих живих кл≥тин, що народились в першому кроц≥ настануть умови смерт≥, знову народ¤тьс¤ дв≥ кл≥тини з правого боку, дв≥ кл≥тини, дл¤ ¤ких настали умови смерт≥ в першому кроц≥ - постар≥ють на одиницю, а т≥ дв≥ кл≥тини, що в першому кроц≥ постар≥ли, взагал≥ зникнуть ≥з екрану, тому що њх в≥к стане р≥вним 3 (тривал≥сть "≥стор≥њ" дл¤ даного правила)
• ≥ все повторюЇтьс¤.  орабель рухаЇтьс¤.

„и може хоч ¤кийсь закон ≥з с≥мейства "Life" похвалитись таким простим косм≥чним кораблем? “≥льки закони ≥з "≥стор≥Їю" кл≥тини спроможний на таке.

Weighted Life

¬ цьому с≥мейств≥ основною в≥дзнакою Ї зм≥на способу п≥драхунку к≥лькост≥ живих кл≥тин. якщо в с≥мействах "Life" ≥ "Generation" дл¤ вир≥шенн¤ дол≥ кл≥тини використовувалась сума вс≥х живих сус≥дн≥х кл≥тин, то в цьому с≥мейств≥ використовуЇтьс¤ сума не кл≥тин, а њх вагових коЇф≥ц≥ент≥в, значенн¤ ¤ких може бути в≥д -255 до 255.
–озгл¤немо це на приклад≥ закона Navaho1. ѕри цьому закон≥ панель вагових коЇф≥ц≥ент≥в (див. дов≥дку до програми) вигл¤даЇ так, ¤к показано нижче:

Ќаведемо два приклада обчисленн¤ суми вагових коЇф≥ц≥Їнт≥в дл¤ кл≥тин, позначених синьою крапкою. (“обто ми не будем анал≥зувати все поле, а лише одну центральну кл≥тину)

1-й приклад

2-й приклад

• 1-й приклад. ¬ центральноњ кл≥тини Ї 3 живих сус≥да: NE, WW, SS. —ума њх коЇф≥ц≥ент≥в р≥вна 4 + 5 + 1 = 10.  р≥м того, потр≥бно враховувати ≥ саму центральну кл≥тину, тобто 10 + 7 = 17. —аме ц¤ сума ≥ буде використовуватись дл¤ вир≥шенн¤ дол≥ кл≥тини.
• 2-й приклад. “акож три живих сус≥да, проте немаЇ центральноњ кл≥тини. —ума вагових коЇф≥ц≥Їнт≥в р≥вна 1 + 4 + 1 = 6.

¬ с≥мейств≥ Weighted Life може також використовуватись "≥стор≥¤" кл≥тин. ÷е ≥ робить с≥мейство Weighted Life комплексним. якщо вимкнути "≥стор≥ю" та задати вагов≥ коЇф≥ц≥енти р≥вн≥ 1 дл¤ вс≥х кл≥тин кр≥м центральноњ - то це вийде те ж саме с≥мейство Life. якщо при цьому вв≥мкнути "≥стор≥ю", то вийде с≥мейство Generation.

УVoteФ

ƒещо видозм≥нена верс≥¤ с≥мейства "Life". в≥дм≥нн≥сть пол¤гаЇ в тому, що наб≥р значень "¬иживанн¤" повинен бути такий самий ¤к ≥ наб≥р значень "Ќародженн¤".  р≥м того, при п≥драхунку к≥лькост≥ живих сус≥дн≥х кл≥тин враховуЇтьс¤ також ≥ так кл≥тина, дол¤ ¤коњ вир≥шуЇтьс¤, тобто центральна кл≥тина.