What are Cellular Automata?
Вставка
- Опубліковано 26 чер 2024
- Cellular Automata are a fantastic demonstration of how a simple set of rules can elicit a complex emergent behaviour. In this video I show John Conway's Game Of Life implemented in quick and simple C++ at the command line.
Github: github.com/OneLoneCoder/Javid...
Blog: www.onelonecoder.com
A quick mod to this code to wrap-around can be found here: onelonecoder.com/2017/07/14/ill-show-you-how-to-create-life/
There's no life because 404 error! =(
It's down :c
@javidx9. Can you help us? The link is down and there is no results for cellular automata or life from the search bar enquires.
Hmm, yeah - that website doesnt exist anymore - In principle its quite simple - every time you read from the array, perform a boundary check, and move to the other side. This could be done with % modulus of the array size, or if your array is a power of two, you can simply mask the bits, say its 128x128, always AND your address coordinate with 0x7F as you read from the array.
I kinda love how he says “Hello” at the beginning of any of his videos xD
Yeah, he is a real human bean.
Cellular automata is deep. I find cellular automata to be useful in nano-electronics and self-replicating machines. Nice video !
I was exposed to them in the first instance when studying massively parallel processing systems. I think the self replicating algorithms are fascinating, but unsure if they have any practical advantage.
Thank you very much for making all those tutorials. You are the greatest c++ teacher on youtube for me )) I feel bad, you deserve 100x more views and subscribers than you have. Please keep the work, I recommend your channel to all my friends and acquaintances (even if they are not programmers).
This highly intrigued me, when I was 17 and had a vic 20 to code it with basic. I still love it.
javidx9 thanks so so much for this crystal clear explanation of cellular automata algorithm with Conways rule!
Great video as always and a huge thank you for the pixel game engine. One of my first tests of the engine was a 20 year old game of life version that I wrote in school using C. The test worked great with 90 fps on a 500x500 matrix. After seeing this video I changed the two dimensional arrays to singels with a lambda function. New speed: 9 fps! very strange
I wish, I had a chance to sit under the heel of you and learn a bit of computer literature and useful algorithms, this piece of information will be of great use to me. Greetings!
Really great video! :)
" it takes about three " that's when you know it's something interesting
I got this one working on the LED display (albeit slowly for now). It needed a third buffer to keep sending to display while swapping the first two, to stop strobing. It needs some kind of life killing cannon to spice things up a bit. a life killing cannon that moves slowly across the screen moving through several epochs in different places.
Oddly, I've never really considered "gamifying" game of life, but it could be quite cool. I'm also interested in creating an event based game of life simulator, so you could have massive surfaces with minimal processing/RAM overhead.
javidx9 What I did was use setpixel and getpixel to write between a pair of graphic framebuffers that are easily printed, but it would be far less costly to use two big char arrays and only a single framebuffer to write bits into. BUT I’ll be able to scroll text or whatever other graphic made purely of life bits into it :D
Great video!
Hey thanks Aaron!
This is really cool, makes me want to watch a video on fractals.
I like Automata, there's something a bit freaky about them, I think between automata, fractals and magnetism lies all the universes secrets :D
Yeah, you could probably evolve your automata into an AI, be careful. lol
Never thought it is such a tiny bit of code! :O
Do you think you could do a tutorial on fluid sim using cellular automata? Ive tried to make some but had troubles in the past with it working well. Something like how water in terraria game works
Now imagine putting the output of the maze code project into this project as the seed.... ;)
I just ported and got this running on an embedded system (STM32 and OLED display) on the first try! :D
nice
Reminds me of "Life" on the ZX Spectrum!
Functionally it is exactly the same, just a bit quicker :D
My first game of life was on an hp48 calculator. My version was very poor, it was about one or two seconds per frame but it still felt like success!
awesome!
Could you make a video explaining lambda expresions? I've been reading the Microsoft c# resources about them, but ive been unable to figure out how does it work.
Do you mean lambda functions in the "funclet" sense, or in the computer science sense?
@@javidx9 the "=>" operator
Maybe its a silly question, as it may be tought at universty. (As im still finishing highschool)
@@Xeros08 it's not a silly question at all :)
i watched a video about lambda functions yesterday and completely knew what they were about but now i forgot...
You can do some cool stuff with them like give functions values that are technically out of scope (iirc that's what the [&] parameter is)
Can you make a tutorial about probabilistic cellular automata?
Recently made my own one-file HTML + JS with options to change board size from 3 to 100 cells, step by step or autoplay with regulated speed and enclosed or not borders.
hey Mate, how would you implement this using OpenGL for rendering?
Two ways, first, just treat each cell as a pixel, and alter the texture before you copy it to your primary surface. Second, and a bit more fun, treat each cell as a textured quad or point sprite, and alter its attributes before rendering. You could in principle do all this in shaders.
That would be awesome to have a mesh with an evolving texture :)
lmfao 3D openGL cellular automata renderings...
actually that's bound to get a lot of views lol
(is there a 3D version of cellular automato?)
automato
lol
@@javidx9 i'm actually working on a roguelike in C++ and i found this video quite informative as i will be using a few similar techniques (cells with data, instructions that do something depending on data) data will be things like ''direction of room exits'' and that will tell the next cell where it can connect to + some rng magic
I haven't even started with the rng room algorithms yet but conceptually it should be sound right?
As long as there's markers or some sort of flag that makes sure the rng doesn't go ''back'' on itself and try to trace over an existing tile,
but i wonder if this is would provide a somewhat ''linear'' experience? I guess building it and testing it out is the only way to find out lol.
Otherwise maybe an idea to look at combining some of the existing roguelike worldgen algorithms (draw cells, then cut hallways from each cell to another)
Javid if you got any ideas on this i'd love to hear
One time at work I was bored waiting for a build so I made "Conway's Game of Thrones".
It had the same exact rules as the standard Game of Life, except that at random intervals a 5x5 cluster (Daenerys Targaryen) would sweep through in a random direction and kill everything it touched.
That is hand's down the nerdiest comment I've ever received! Well done! 🤣
@@javidx9 I'm honored!
I say automata, you say automahta, let's call the whole thing off.
Edit: Thanks for reminding me of my first assembler program on my first computer, an Oric 1.
if you zoom out really far, the game of life becomes itself all over again, it has infinite resolution like a fractal
javidx9. Hi javidx9 it's your new stalker :P. How come you've no clean up code for your new pointers or am I missing something? Asking for a friend....that looks like me
:D that's a great question! It's me being a bit lazy. You should of course clean up your memory. But many of my demos have no means of exit other than closing the console window. To do it right I'd need to capture close events events or facilitate a clean exit procedure. Suddenly the demo becomes about that and not the... bah I'm making excuses, always clean up your memory!
So is this correct then? ~GameOfLife() {
if (m_Output) {
delete[] m_Output;
m_Output = nullptr;
}
if (m_State) {
delete[] m_State;
m_State = nullptr;
}
????
That looks like the typical way to do it yes, I believe the "delete" operator checks for null pointers anyway now, but the way you're doing it is safer. Just ensure somewhere in your code you actually default the pointers to nullptr before using "new", or else they will have some random value which could cause all sorts of issues. That said, I've rarely had "new" fail on me, and when it did it was my own silly fault.
Of course this method will only work if something calls the destructor.
Interesting. I was always under the impression that if a constructor was called then the destructor was automatically called. But I tested the code and I don't believe it is called. If not to long why is that javidx9? PS Cheers for the vids. Very interesting what yo can do in the console.
Your assumption is correct, but only for stack allocated objects. As the game engine is declared on the stack, when it goes out of scope, it and its stack allocated resources get cleaned up automatically. This may involve calling the destructor if the object has one, and the destructor may call the destructor of all the other stack allocated objects the parent object may contain. Closing the command window simply kills the process, never allowing the object to formally go out of scope, thus never getting destructed.
If you've used pointers to allocate new objects/memory then these persist and must be deleted manually. This can lead to a classic memory leak situation, where your stack allocated object internally creates heap allocated objects. If your destructor is good shape, it should deal with this appropriately when the parent object goes out of scope.
I can kind of get away with it in the demo, because I know the OS is smart enough to release the memory I've asked for as part of killing the executing process, i.e. my machine wont stop after many runs of the demo. But it's bad practice.
However, you can actually capture the command window closing, as the process will be sent a signal you can react to. It's a bit complicated to go into a youtube comment, but absolutely video worthy. Upon reception of this signal, I could free resources as required.
It goes without saying, if you're allocating memory within a function, then always clean it up yourself. I threw together a little snippet here: pastebin.com/wysv50vz which if you step through with the debugger, you can see what gets called or not, though I'm sure you get the idea anyway.
Nice!
Could you provide me please a simple code using Cellular Automata model in building evacuation scenario ?
John Horton Conway died of COVID-19 on 11 April 2020. R.I.P.
Hi javidx9! I have a problem. After watching this video I was excited to try out this stuff, but unfortunately I always have runtime error. I thought I made a mistake somewhere, but I also tested your own code that is on github, so it gives the same problem. In debug mode it says something like : "An exception was thrown: access violation for writing.
this-> m_bufScreen was 0x1110396." in Draw function in your header file. I use VS 2017
Thank you
Hi ehzii. This looks like the console you are trying to make is too large for your primary display screen. The constructconsole function is failing. I don't check for errors in the video code unfortunately.
Thank you so much! Now it works properly and I finally able to see magic
i think the better way to explain it is the basic construct that is used in lambda calculus can be used as key tool where the basic propositional calculus or predicate calculus where logic can be used as an computation where and and nand and xnor gate can be used to compute any thing from strings or numbers or anything but the basic construct which is not being any of the wolfram video please tell it in another video if iam wrong be kind and correct me where the schools teach computers as pure number system but functional programming and cellular automata tells that gates and every thing used in computation is a function but dont even try to open the mathematical portal from here because the inversion is not allowed as function in lambda calculus but in group theory it does switching a number and getting a answer is thought in many schools but composition of function which does the magic makes Turing complete from gta to arithmetic and even word-processing is done by considering everything and a function and construct are developed and a higher grammar is used in computation even 1 2 3 and even everything is an function from true and false are also function which are developed but how the cellular automata is related the rules are related to lambda calculus and physics the rules emanate from simple rules but not hard encoded or is inside the code and after the graphs develop emanate and develop the computational algorithm and theory is enumerated no video in you tube tells this basic information correctly i guess if i am wrong please correct me i never shy away to learn even i fail
Hey I keep getting an error, Unhandled exception thrown: write access violation.
this->**m_bufScreen** was 0x1110396. occurred.
Hi Greg, you are probably creating a console that is too big for your display. Try halving the fontw and fonth values in construct console function.
@@javidx9 I'm sorry but i don't quite understand, with your code as an example where would the "fontw and fonth values in construct console function" be? this is all new to me and quite daunting. thanks for your time.
No problem greg, they are in the int main() of the program, when the console game engine is constructed. The problem is on windows yoy can only create a commanding prompt that is smaller than your main display resolution. The error you identify is common to those that are working on lower resolution systems, so it fails to create the console. Each pixel is determined by fontw and fonth, so reducing those values reduces the screen space required by the console window, hopefully making it small enough to fit on your screen.
would this be possible to implement in apple motion, thank you
Let me ask you how you achieved such incredible speed of program execution? My AMD Ryzen 5 5600H is only capable of producing 3-5 FPS at a console size of 320 X 200. I've been thinking about this for several days and I haven't been able to come to a definite conclusion. I'm confused. If anyone finds a solution, please let me know, I will be very grateful.
This is most likely caused by the thread sleep added in between. Maybe try removing the sleep or reducing it to around 5ms.
I did mine on JS.
Ok so I think I'm missing something here. You say that all the cells must be updated in the same pocket of time, which leads me to believe that each cell chould be proccesed in parallel. Yet here you simply loop over the entire array on each function call, which is not exactly in the same pocket of time and is technically going sequentially, which you said is wrong. I'm confused
Hi Danilo, your assumption is correct. I emulate a pocket of time by updating the cells by using input from the previous pockets output. Ie as I update each cell, if its output changes, that's not seen by its neighbours until the next pocket of time.
@@javidx9 Ah, so you are simulating the pocket by feeding the output of the cell into the input of the other by "delaying" the iteration. Clever.
How would we do this proccesed in parallel?
Would we create a thread for each cell and sync?
Also, a friend once tried to explain this to my and told me that these kinds of calculations are better done by the GPU, could you elaborate further on that?
P.S. Thank you for the reply, love your content.
If you break up time as we discussed, partitioning for parallel computing is trivial. A thread per cell is probably gonna work against you as threads have overhead, so you might want fewer threads processing several cells. GPUs "can" help here, but they introduce their own problems as cells that lie on the boundaries of the areas that are being processed need to communicate with each other, and this has a significant cost overhead for the GPU.
i get has exited with code 0 (0x0) when i run the code.
do Brian's brain next
hmmm, maybe i will :D
[SOLVED]
i have a weird doubt, I tried doing this in python and it didn't really worked,it produced really long strings of alive cells and cluster with way more neighbors than intended,after debbugin for a while I discovered that it was behaving just as if it was reading and writing from the same list, I used, more or less, the exact same code, but the fix was really weird, for some reason, even though I'm completely sure I'm only writting to state and reading from output, like in your code, it only works if I set STATE to zero after setting output = state, that makes no sense, i did de exact same thing as you did, setting output = state, read cell from output, set cell in state, and repeat
here's the relevant code, state is output and output input, and the silly reduce is there just because I didn't want a long one line sum but python wouldn't let me compile if the sum wasn't in a single line, but it let me if a reduced an array with the states,lol
import pygame
import utils as u
while (1):
u.updateArray(inputarray,outputarray,*size)
u.drawScreen(outputarray,screen,*green)
inputarray = outputarray
#output = u.genZeros(*size)
pygame.display.flip()
in utils.py
def updateArray(inputarray,outputarray,screenx,screeny):
gridx = int(screenx/10)
gridy = int(screeny/10)
cell = lambda x,y : inputarray[y*gridx + x][2]
for m in range(0,gridy - 1):
for n in range(0,gridx - 1):
neighbors = functools.reduce((lambda x,y: x + y),[cell(n - 1,m - 1),
cell(n,m - 1),
cell(n + 1,m - 1),
cell(n - 1,m),
cell(n + 1,m),
cell(n - 1,m + 1),
cell(n,m + 1),
cell(n + 1,m + 1)])
if cell(n,m):
outputarray[m*gridx + n][2] = int(neighbors == 3 or neighbors == 2)
else:
outputarray[m*gridx + n][2] = int(neighbors == 3)
[solution]
apparently, when you set two list equal in python they point to the same memory for some dumb reason,
you can quickly test it with this code
testlist = [0,1,2,3]
testlist2 = [4,5,6,7]
teslist = testlist2
teslist2[0] = "yep it fucks things up"
print(testlist)
I don't understand why is this the case, and why setting the whole list to zeros doesn't fuck up the input list, python be python
Your line "testlist2 = testlist" means: "testlist2 is another name for testlist", so they refer to the same memory location. You can fix it by changing it to "testlist2 = list(testlist)", which will copy testlist and store the result in testlist2. Keep in mind that you will need to make deep copies when using nested lists to avoid similar behavior.
Christ! I wrote a version of this in Microsoft Small Basic, and even with me streamlining the code as much as a I could, it only runs at a fraction of the speed of your example. Just goes to show how slow Microsoft Small Basic is :(
@10:07 why do we see cells on the edges that have no neighbors surviving ?
The map is not impemented with wrap around so its essentially reading noise in those locations
@@javidx9 thanks for your reply. I really love your videos, you're a great teacher.
@@javidx9 reason for that noise is that there is a bug in the code when you randomize cells on OnUserCreate(). It randomly puts 1 on some of edge cells and so nNeighbours is calculated wrongly. If you replace PIXEL_SOLID character with neighbour count, you can see it easily. For example, all 4 corners should have 3 neighbours and all other edges can have 5 neighbours maximum, but it says 8.
screenshot here: imgur.com/a/uXVzN5O
this fixes the bug:
for (int x = 1; x < ScreenWidth() - 1; x++)
{
for (int y = 1; y < ScreenHeight() - 1; y++)
{
m_state[y * ScreenWidth() + x] = rand() % 2;
}
}
13:52 Imagine making a Turing Machine out of your own body cells lol
you have 2^(m x n = pixels) possible states in that, not considering how you get to those states
intermediate rendering buffer(s), like rendering triangles into a 2d or 3d grid then rendering the closest grid cells in "draw once" order into the z-buffer
triple buffering or double buffering, with z-buffer
any machine has finite states, depending on the number of the memory states
no matter how you got there, in a state
Technically anything just be implemented in one line of code, but it would just be _really_ hard to read.
Next step: go for hashlife algorithm ? 😁
"If it is, I'm going to draw a white character, and if it isn't, I'm going to draw a black character."
I'm imagining an artist saying this out of context.
I thumbed it up all though i hate persons begging for it
To optimize the code as most as possible, it's just BRUTAL 3:)
you need hash functions and all of that complicated stuff
What are you ??
My girlfriend says you look like a nenuco with beard talking
a baby doll?
9:28 😳...realised all the BLACK characters die?!? ( reports for hate crime....*) 😉