Kiedyś szczytem techniki była pralka zastępująca popularną "Franię". Dumnie zwana była automatem, bo potrafiła sama uprać i odwirować majtasy całej rodziny. W Polsce pojawiła się w latach 70-tych. Ale z automatem, i to nie piorącym, mieliśmy do czynienia kilkadziesiąt lat wcześniej.
Pustynna teoria.
Automat komórkowy to model matematyczny reprezentowany przez grupę (zazwyczaj siatkę) komórek, których stany podlegają zasadom przejść. Przejścia następują synchronicznie dla wszystkich komórek i dla pojedynczej komórki mogą być zależne od jej sąsiadów. Liczba stanów komórki jest liczbą skończoną, przy czym stan początkowy każdej komórki może być inny. Siatka komórek jest w całości wypełniona, choć przy reprezentacji wizualnej niektóre miejsca mogą być puste. Nie oznacza, że brak tam komórki - po prostu może być w stanie martwym.
Brzmi to jak definicja, więc może prościej.
Siatkę automatu można porównać do planszy szachownicy, której polami są komórki. W danym momencie życia automatu (np. co sekundę) sprawdzamy stan komórki i jej sąsiadów i w zależności od zasad wyłączamy, włączamy lub przemieszczamy komórkę. Każda sekunda w tym przypadku będzie cyklem ewolucji automatu - cyklicznie coś będzie się działo na planszy.
Komórka (podobnie jak piksel na ekranie) może mieć 8 siąsiadów na siatce 3x3 - jest to sąsiedztwo Moore'a, 4 na siatce 3x3 (jak róża wiatrów - tylko N, S, E oraz W), wtedy jest to sąsiedztwo van Neumanna. Można też rozpatrywać sąsiedztwo na siatce 4 elementów (2x2) - sąsiedztwo Margolusa. I właśnie tym sąsiedztwem się zajmiemy, a dokładnie automatem komórkowym symulującym piasek.
Twórcą automatów komórkowych jest wspomniany pan John van Neumann. Właściwie teorii, bo na czasy kiedy ją opracował (lata 40'-50') było zbyt trudno przenieść teorię na rzeczywistość. Jeśli pamiętasz/znasz "grę w życie", którą opracował John Corton Conway, to właśnie ona również opiera się na teorii automatów komórkowych.
Ale wróćmy do działania. Poniżej możesz przyjrzeć się zasadą przejść dla sąsiedztwa Margolusa:
| > | |||||||
| > | |||||||
| > | |||||||
| > | |||||||
| > | lub | ||||||
Zasada 1 oraz 2 mówi o spadającym ziarnku piasku, kiedy obok niego nie ma innego ziarnka.
Zasada 3 oraz 4 nawiązuje do sytuacji kiedy jedno ziarnko jest na drugim, wtedy górne ziarnko spada na dół zajmując pustą komórkę.
Zasada 5 dotyczy dwóch ziarenek obok siebie. Tu dla zapewnienia większego realizmu losujemy jedną z dwóch sytuacji (prawdopodobnieństwo=0.5). Jeśli ziarenka ze względu na lepkość zaklinują się w otoczeniu, to zostają na swojej pozycji. Jeśli nie, to sklejone spadną w dół.
Wewnątrz każdej iteracji operujemy na blokach 2x2, a dodatkowo w parzystej iteracji przesuwamy blok o 1 komórkę w prawo i 1 w dół.
Babki z piasku.
Już pewnie wyczułeś, że będziemy bawić piaskiem. Tak, to prawda, bo zasada Margolusa idealnie nadaje się do symulacji piasku czy też cząsteczek gazu. A skoro tak, to należałoby się zająć implementacją algorytmu. Wykorzystamy nieśmiertelny, póki co, CANVAS. Opis jak zwykle w kodzie, aby na bieżąco analizować każdą linijkę.
/* rozmiar <canvas>
*/
const width = 100;
const height = 100;
const canvas = document.querySelector('canvas');
canvas.width = width;
canvas.height = height;
const ctx = canvas.getContext('2d');
/* tryb kreślenia
*/
let drawing = false;
/* tryb animacji
*/
let falling = false;
/* kolory piasku, bloków betonowych
oraz pustego
*/
const sand = 'rgba(255,0,0,1)';
const empty = 'rgba(0,0,0,1)';
/* czyścimy <canvas>
*/
ctx.fillStyle = empty;
ctx.fillRect(0, 0, width, height);
/* spacją włączamy animację
(można podczas niej rysować)
*/
document.addEventListener('keydown', function(e) {
if (e.keyCode == 32) {
falling = !falling;
}
});
canvas.addEventListener('mousedown', function(e) {
/* jeśli któryś z przycisków
myszy wciśnięty, to znaczy,
że włączamy tryb kreślenia
*/
drawing = true;
ctx.fillStyle = sand;
ctx.fillRect((e.clientX - canvas.offsetLeft) >> 1, (e.clientY - canvas.offsetTop) >> 1, 1, 1);
});
/* jesli puścimy klawisz myszy
to nie kreślimy podczas poruszania
*/
canvas.addEventListener('mouseup', function(e) {
drawing = false;
});
/* jeśli klawisz wciśnięty i mysz
się porusza, oraz jesteśmy w trybie
kreślenia, to rysujemy
(można rysować w czasie animacji)
*/
canvas.addEventListener('mousemove', function(e) {
if (drawing) {
ctx.fillStyle = sand;
ctx.fillRect((e.clientX - canvas.offsetLeft) >> 1, (e.clientY - canvas.offsetTop) >> 1, 1, 1);
}
});
let step = 0;
/* nasza funkcją animująca
*/
function cycle() {
/* pobieramy dane o RGBA pikseli
*/
const pixelData = ctx.getImageData(0, 0, width, height);
/* obliczamy szerokość danych
(cztery składowe więc jeden wiersz * 4)
*/
const pixelDataWidth = pixelData.width << 2;
/* w cyklu parzystym operujemy
na bloku startującego
od (x+0,y+0), a w nieparzystym
od (x+1,y+1)
*/
for (let y = 0 + (step % 2); y < height; y += 2) {
for (let x = 0 + (step % 2); x < width; x += 2) {
/* pobieramy czterech sąsiadów piksela,
dla ułatwienia tylko składową R,
bo taki kolor ma piasek
*/
/* ziarnko lewy góra
*/
let s1 = pixelData.data[(y * pixelDataWidth) + (x << 2)];
/* ziarnko prawy góra
*/
let s2 = pixelData.data[(y * pixelDataWidth) + ((x + 1) << 2)];
/* ziarnko lewy dół
*/
let s3 = pixelData.data[((y + 1) * pixelDataWidth) + (x << 2)];
/* ziarnko prawy dół
*/
let s4 = pixelData.data[((y + 1) * pixelDataWidth) + ((x + 1) << 2)];
/* jeśli na dole brak ziarenek
*/
if (s3 === 0 && s4 === 0) {
/* jeśli na górze są obydwa ziarenka,
to z prawdopodobieństwem 50% obydwa
zostają w miejscu lub obydwa spadają
(zasada 5)
*/
if (s1 === 255 && s2 === 255) {
if (Math.random() < 0.5) {
ctx.fillStyle = empty;
ctx.fillRect(x, y, 1, 1);
ctx.fillRect(x + 1, y, 1, 1);
ctx.fillStyle = sand;
ctx.fillRect(x, y + 1, 1, 1);
ctx.fillRect(x + 1, y + 1, 1, 1);
}
/* jeśli jest tylko lewe górne ziarenko,
to przesuwamy je w dół
(zasada 1)
*/
} else if (s1 === 255) {
ctx.fillStyle = empty;
ctx.fillRect(x, y, 1, 1);
ctx.fillStyle = sand;
ctx.fillRect(x, y + 1, 1, 1);
/* jeśli jest tylko prawe górne ziarenko,
to przesuwamy je w dół
(zasada 2)
*/
} else if (s2 === 255) {
ctx.fillStyle = empty;
ctx.fillRect(x + 1, y, 1, 1);
ctx.fillStyle = sand;
ctx.fillRect(x + 1, y + 1, 1, 1);
}
}
/* jeśli są ziarenka na dole
*/
else {
/* jeśli lewego dolnego brak,
czyli jest prawe dolne
*/
if (s3 === 0) {
/* jeśli jest górne lewe,
to przesuwamy je na dół
(bo jest prawe dolne, więc
to spada w dół)
(zasada 1)
*/
if (s1 === 255) {
ctx.fillStyle = empty;
ctx.fillRect(x, y, 1, 1);
ctx.fillStyle = sand;
ctx.fillRect(x, y + 1, 1, 1);
/* zapisujemy informację,
że ziarenko lewe dolne
jest zajęte
*/
s3 = 255;
}
/* jeśli jest górne prawe,
a dolne lewe wciąż puste,
to przesuwamy je na dół
w lewo, ziarenko obsuwa
się po dolnym prawym
(zasada 4)
*/
if (s2 === 255 && s3 === 0) {
ctx.fillStyle = empty;
ctx.fillRect(x + 1, y, 1, 1);
ctx.fillStyle = sand;
ctx.fillRect(x, y + 1, 1, 1);
}
}
/* jeśli prawego dolnego brak,
czyli jest lewe dolne
*/
if (s4 === 0) {
/* jeśli jest górne prawe,
to przesuwamy je na dół
(zasada 2)
*/
if (s2 === 255) {
ctx.fillStyle = empty;
ctx.fillRect(x + 1, y, 1, 1);
ctx.fillStyle = sand;
ctx.fillRect(x + 1, y + 1, 1, 1);
/* zapisujemy informację,
że ziarenko prawe dolne
jest zajęte
*/
s4 = 255;
}
/* jeśli jest górne lewe,
a dolne prawe wciąż puste,
to przesuwamy je na dół
w prawo, ziarenko obsuwa
się po dolnym lewym
(zasada 3)
*/
if (s1 === 255 && s4 === 0) {
ctx.fillStyle = empty;
ctx.fillRect(x, y, 1, 1);
ctx.fillStyle = sand;
ctx.fillRect(x + 1, y + 1, 1, 1);
}
}
}
}
}
step++;
}
/* co 100 ms kreślimy
kolejny cykl, jeśli
jesteśmy w trybie
animacji
*/
setInterval(function() {
if (falling) cycle();
}, 100);
HTML + CSS:
<canvas></canvas>
canvas{
transform-origin:0 0;
transform:scale(2);
image-rendering: pixelated;
}
Aby nie męczyć oczy CANVAS jest powiększony dwukrotnie, jednak pozycja myszy wciąż jest odczytywana standardowa - jeśli kursor myszy jest w połowie takiego powiększonego elementu, to otrzymamy współrzędne jak byśmy byli w jego prawym dolnym rogu. Dlatego też w kodzie są one dzielone przez dwa (>>1), aby móc rysować w normalny sposób.
No i nasz automat komórkowy symulujący piasek w działaniu (rysujesz myszą). Jeśli nie czujesz, aby Twój mózg został wyprany po dzisiejszym wpisie, to zapraszam Cię na kolejny. Do przeczytania!
Przydatne linki:
Automat komórkowy w Wikipedii.