ไม่สามารถเล่นวิดีโอนี้
ขออภัยในความไม่สะดวก
How To Code a Falling Sand Simulation (like Noita) with Cellular Automata
ฝัง
- เผยแพร่เมื่อ 12 ส.ค. 2024
- Download and play with this simulation here: tinyurl.com/43dzu9r5
Java Repository: tinyurl.com/88ndcdez
Links:
All the old Java Applets: androdome.com/Sand/
Exploring the Tech of Noita: • Exploring the Tech and...
Conways Game of Life: playgameoflife.com/
Noita: noitagame.com/
Matrix Wrapper class: tinyurl.com/894ztzt8
Movable Solid class: tinyurl.com/4hcwdku7
TraverseMatrix Algorithm Gist: tinyurl.com/32senju4
Explosion Code: tinyurl.com/6xnjz4xt
----
Music by artdsigns on Pixabay: tinyurl.com/ube8kvjw
Intro: (0:00)
Cellular Automata: (0:25)
First Element Examples: (1:15)
Code Structure: (2:12)
Step Function Pseudo Code: (3:51)
Improving Water: (4:24)
Traversing The Matrix: (5:42)
Enhancing Solids: (7:46)
Particles: (10:39)
Explosions: (11:40)
Creating New Elements: (13:27)
Optimizations: (15;48)
MultiThreading: (16:21)
Chunks: (17:07)
Final Notes: (19:23)
Conclusion: (20:34)
This was the video that first introduced me to noita. 2 years and hundreds of hours of play later - thanks!
I was trying to stop procrastinating, but youtube showed me this piece of art. Fair enough.
I'll do what I must do later.
you're literally still procrastinating
@@lOmaine777, it has been 3 weeks. How did I know that I'm still procrastinating?
Very nice. I really like the inertial resistance concept, seems quite unique. But I would not use class hierarchy for elements ever again. From like 2014 to 2017 I was developing similar game in Java and when elements and their interactions were getting more complicated it end up with explosion of classes. It was hard to change element's single feature (movability, flammability...) while maintaining others, facing the diamond problems etc. Years later I was learning JavaScript while developing another falling sand game. I encoded elements directly into ArrayBuffer, together with colors, values and feature flags. Now, I can say that this is much better. Great performance (even in JavaScript!), trivial serialization.
Mentioned game are Sand Game 2 and Sand Game JS If you are curious.
Thanks for sharing your experience! I checked out your Sand Games and really liked the plant growing mechanics.
Up to this point in development I didn't encounter much issue with adding new classes but I could definitely see the effort exponentiate as you add more unique features that each new element must account for.
There are also way too many megamorphic virtual calls everywhere
This is incredibly in depth and well explained. Thank you for sharing this!
One thing to note - Gas isn't just reversed solids. Gas has the fundamental property of liking to spread out a lot.
this has been a great help for me, ive had some struggles with my own falling sand engine, couldnt find any good guides, but you explain these things really well, and also had great solutions i would have never thought about doing, i might just try to continue/finish my own! thanks again, great video
I started working on a Falling Sand Simulation a few month back since it just looks so interesting but I soon realized that there were many challenges that I broke my head about for days so I stopped working on it after a while. Today I decided to try to start working on it again but I would do some research before although last time I couldn't find what I needed so my hopes where not high until I saw that someone's released a new video about this topic.
This video was just great I think I've got some Ideas on how to fix some of my big problems so thank you really much. Also your voice is really nice and your Sand Simulation turned out great 😂👍🏻
Hey! I'm so glad you found the information useful and hope you're able to solve those problems you were stuck on before. Thanks for letting me know the video helped you.
I would of never of thought there was so much math and physics involved in those falling sand games. kudos to whoever first come up with the code for this.
simulation without physics is not a simulation, ad physic without math is not physic. but the bigest problem is not the physic but the code optimisation.
@@skymanclaw441well… that’s not exactly true. I simulate math problems with random variables occasionally and that doesn’t have any physics involved. For example: what is the average length of two random points selected within a 1x1 square assuming equal distribution? You can solve this problem by integrating the distance formula over a 1x1 square, or you can just simulate 10k pairs of random points selected in a 1x1 square, take the distance for each pair then take the average.
@@blablabla7796 They said physics without math it's not physics, they didn't said maths without physics is not math
@@secrom36 no, they said simulation without physics is not a simulation. That’s literally the first line in their message.
Nice video, looks like you've implemented most of the things in the noita dev talk video, nice work.
I usually split my particles up into: Liquid, Solids, Gases, and Statics. A static is a custom element that isn't affected by gravity.
ive watched this video for several years.
its really fun to watch and very informational. Not only do i like wathcing it, but i also have used this knowledge for my own falling sand sims.
tysm for the video! its really good!
wow. this will be such a big help for my assignment. Thank you so much!
Instead of manually detecting what element each liquid element is on top of, you could use a density value and decide to either stay up or go down depending on the value compared to the one below. You can also use this value to do inertial calculations, and it can also be used for gasses (by providing a negative value instead of positive).
Note: that last part (gasses) would likely require a pressure gradient over the vertical axis to solve with.
Aside from the audio being incredibly low, what a wonderful video!
this is exactly what I needed (working on a similar project), thank you so much for making this video
i know this video is quite old but something i was thinking about is, when the inertial resistance was added, you could also give each particle a mass and the more mass a particle has placed on it the lower its inertial resistance is, like a buildup in pressure. for example, when you removed the floor from next to the sand, this would make it so a small pile would stay put but a large one would crumble immediately.
Yeah thats a great thought. I know other older sand simulations implemented some sort of pressure system but integrating it with the inertial resistance could provide some interesting results.
Thanks. Your explanations are pure gold. There is not too much information about those techniques available elsewhere.
i always come back to this video, it's so inspiring!
WOW, this is extremely impressive. Great work!
This tutorial really helped me with coding my own falling sand game. thanks!
This is great! Playing noita makes me want to make a game like no other game does.
I'd encourage you to explore using Composition rather than Inheritance. Not all that crucial, but a useful paradigm
Thank you for inspiring me on how to use my Conway's Game of Life experiment!
@6:35 there's an integer only version of that algorithm called the Bresenham Line Algorithm. The difference between integer and floating point math is significant when at the scale of really big particle simulations.
this video is suprisingly obscure, even though its really well done and shows the ideas!
This is exactly what i needed. Thank you so much! Im making something similar with c++ and sfml. Well explained tutorial
There are some design patterns I disagreed with watching this, but the 'Particle' logic you explained is really clever; I like it!
This has to be my favourite video about falling sand simulations, the amount of topics covered here is great.
It's so nice seeing a bunch of devs in the comments giving suggestions and being genuinely interested in the topic and I've been checking out their own projects too.
I've also been working on an engine (hopefully with multiplayer support eventually) and have since starting uploading some basic vids showcasing some features. I plan to open source it in the future if it gets to a point where I can start developing games with it (but right now the code isn't too pretty to say the least).
I'd personally love to see more games utilising falling sand be developed in the future so I'm grateful for awesome resources like this video to exist.
Agreed. Really cool seeing everyone else's approaches on this subject. Your simulation looks incredible so far. You already have the rigidbodies working really cleanly.
Do you know yet how you plan to network the sand simulation? I imagine that would be very challenging.
Thanks, I'm glad you like it.
The current plan for networking is to ensure the simulation is deterministic in such a way that it can also be multi threaded. Both the server and clients run the same simulation.
Each chunk is responsible for it's own RNG with the seed being set based on the chunk coordinates in the world. Each chunk also keeps a hash that loosely represents the state of itself as modifications occur within the chunk.
Every n ticks, the server and clients will add together each chunk state hash and compare. If there is a discrepancy, the simulation is paused and they will identify what chunks are different based on the chunk hash, the server will then send the chunk data to the client to be overwritten, resuming the simulation when completed.
As for synchronising rigidbodies, the current idea I have is to find all rigidbodies that overlap chunks that need to be overwritten (by querying the Box2D world) and also overwrite them.
The network data is compressed using LZ4 and send over a reliable UDP connection. No visual information about a pixel is sent (like colour) which helps with compression (with the exception of rigidbodies). Things things like darkened explosion marks won't be sent but the client knows what colour a pixel should be by default anyway.
Now you might run into a problem that a client simulation falls behind when there's a lot to process due to variability in processing power. And how do you queue up actions so that they occur on the same simulation tick across all clients? In these cases, I'm looking into how games like Factorio synchronises things (mainly a technique called deterministic lockstep) as there's some overlap between that solution and these problems. Part of the first problem requires the ability to step the simulation forward n amount of ticks so that all clients can catch up to each other, which is not really an issue when the simulation is deterministic.
If there are too many chunk discrepancies per second or a client is running on a literal potato and can never catch up, the connection can be terminated in that case.
There's still a lot to solve and I'm not sure what the optimal approaches are, however that's the plan so far and I've at least laid some of the foundation for this approach to work.
If you're still interested in pursuing falling sand simulations, I'd be more than happy to give you access to the repo and I'm always free to chat about it/explain my approach towards any and all features.
Discord: @exzilorate
Thanks for reading this long mess of an explanation lol
@@exzilorate Thanks for the detailed write up. Conceptually, that all make sense. And if you begin working on the simulation with the deterministic 'physics' behavior in mind that can help a lot.
I'll reach out on discord!
This video is very pleasant to watch and listen to
This is exactly the info I needed! Thank you so much
Nice video! I've been struggling with adding the horizontal + vertical movement (because further I'd like to have explosions) and mainly with optimizations (I'd like to split world into chunks aswell), hopefully I'll manage to accomplish it with these hints.
Would love to see a part2 about how you'll deal with the box2d stuff :)
L
You deserve a lot more views, my friend. Thanks a lot for this information.
That was so satisfying to watch. I love particles!
Real thanks for the video, it was of great help!
I'm pretty sure it'll blow up in 4 years when the youtube algorithm will do its thing, but until then, good luck on your projects!
Very concise and informative, thanks for the video!
Very good stuff, I dont plan on implementing one of those any time soon but I still enjoyed the video for the thought process. Seems like a really fun challenge.
I love it. Thank you a lot. I will definitely look into it more after your video :D
Great video. Keep up the awesome work!
Amazing !!! You are Just Awesome Genius man !!! how come you have only 1.4k subs ...
love this video, definitely earned a sub.
Wow, nice! I'm working on a similar project, this will definitely give me inspiration :)
This was very valuable, thanks
Excellent video!
Thanks man. Working on an Excalidraw clone and I happened to be looking for a good way to connect the line for the free-brush tool.
Stupid youtube keeps deleting most of my comments lately (everywhere), and I tried commenting here more than once and couldn't... :(
If this comment goes through I just want to say wow! I never expected anyone to ever share knowledge on falling sand games with this level of depth. Thanks for taking the time to put this all together. :)
This one made it through!
I'm glad that this information was useful.
Whoa! Lovely YT algorithm led me here. Awesome content. You made me want to throw away all stuff Im coding and start doing similar project. Thanks!
nice! i've done something like this before, but it was in GLSL
Awesome!!
Very well made.
This was beautiful
Cool project
Very good video!
Holy shit...
This video has 79 views???
This was a great watch.
Remember me when this gets thousands of views.
Looks good!
this is a beautiful video
very good video!
This is great! it's exactly what I came to ~steal~ i mean learn from.
Imma try to implement this in Unity.
exactly the same. although i'll just stick to making my own engine in C++, as always. Unity is an engine far too large for a sand simulation. and super inefficient for that too; with my computer, i can't sacrifice even the smallest bit of performance. Also, you get striketrough with minus signs in youtube comments, not tildes.
I liked the part with the sand.
Soooo coooooooll~! Simulation stuff is my favourite and Noita was amazing in that category, the simulation you do here is nearing that complexity from what I can tell. I have one question: do gasses and liquids (i.e. fluids) have any sort of pressure as to allow for fluid dynamics (ex: a U shape of liquid with solids around it, does the liquid balance on both sides or would one side that's higher stay so)? Super cool overall! As a game-dev who's going to be adding cellular elements to my game soon, this is a super cool demonstration and gives me ideas for what I should be implementing. A lot of what you've done was covered in the Noita GDC talk so it's neat seeing someone go through the implementation process. Oh, and with that line algorithm, does that mean that cells with velocity can move diagonally through other elements?
Thanks!
Gasses and fluids do not have pressure in my simulation. So in your example with the U bend, one side would stay higher than the other and would not balance out. This is the same in Noita, it would definitely be possible to add fluid pressure to the simulation but that would probably be pretty expensive. Just depends on what you are trying to accomplish.
With the line algorithm, if I am understanding your question correctly, yes a fluid could passes "between" two solid elements if they are diagonal from each other. You could adjust the algorithm to not allow that, but it just depends on what you want to do.
Thanks for giving such cool insights. In programming books, we are left with classes and objects. Where to study these things ?
Im not even into coding but this was amazing
and thank you too for making this video.
Very cool :D
great vid
This video is the best material about making sand games I could find. But would you mind explaining (simplified of course) how does fire work?
Hey thanks!
The way I implemented fire is that certain elements are flammable (as opposed to fire being its own element). If I want a material to not be flammable I override "receiveHeat()" with a blank definition. Each element has a flammability resistance. When an element receives heat from a neighboring element or explosion, the value passed to receiveHeat() reduces its 'flammability resistance'. Once the resistance reaches 0 the element becomes ignited. It performs all the same element logic it did before except now it also calls the receiveHeat() method on neighboring elements causing the fire to spread. Also the ignited element checks if it is completely surrounded by other elements, this suffocates the fire and if it is surrounded for long enough the element will no longer be ignited and its flammability resistance will be reset. I like this method because it gives more life to the simulation and also it seems more along the lines of what Noita does. If you choose to just convert an element to a "fire" element then you lose any state that was associated with the element and it can't be extinguished. However, this does requires a lot more processing power to apply heat to neighboring elements and also check if it is surrounded, thats a lot of "get" calls to the matrix just for one ignited element.
@SCREAMINGSNAKE Thanks for the explanation. It seems like a very good idea. I'm currently finishing a sand game which just updates numbers on the array ( eg. if(grid[x][y] == 3) { update_sand(x, y) } ) which takes only the very basic things into account (since I store all info about a cell in one uint8). The way I implemented fire is that, after it moves, it also check for the neighboring flammable elements and has a random chance to change them into fire. After I finish this up, I want to rewrite it into full OOP (every cell is an object) like you did in the video. Once again thanks for the explanation, and have a nice day.
great job! (:
Very cool, thanks for the detailed explanations!
Regarding multi-cell movement in any direction, you might be interested in Bresenham's line algorithm to compute all cells along a path. It's supposed to be pretty efficient, since it does not need multiplication and division operations.
How would you handle small velocities, such that particles do not move at least 1 cell per frame? I figured you could store the positions with more precision, as floats for example.
Bresenham's algorithm seems exactly along the line of what I'm looking for. Thanks for the suggestion.
I have each cell at whole number coordinates. If an element has a velocity on the x or y axis less than 1, then each frame it accumulates the velocity in another variable until it is greater than 1 at which point it will move one cell in that direction.
So if an element has an x velocity of 0.4 then it will move 1 cell over on the x axis 3 frames later.
Not sure why I did it that way, and I completely forgot I implemented that until looked it up just now but it seems like a different way of accomplishing the same thing.
@@marf1610 On the efficiency of Bresenham's algorithm, I have found your approach to be marginally better in my case. I'm guessing it's due to having a small bit of branching logic in Bresenham's, instead of a mostly mathematical approach from yours. I was working on a FSG several months ago and cant remember the exact details but I was fairly surprised at the outcome of my tests.
Mine is coded in C and compiled with gcc with optimizations on max during my tests so I'm not sure if that would have a different outcome in Java. Also I was calling the line drawing way too much as I was taking a different approach to velocity. I was attempting a data-oriented system and was hoping to have liquids, solids and gasses be emergent from how I was simulating. Long story short, the change in efficiency is likely trivial and your approach is surprisingly effective for this.
Hmmmm...interesting. Thanks for sharing your findings! I will consider this as I port the simulation over to C++. Maybe I'll try comparing the two approaches and see what I find.
3D would be sick lol
I’m trying to make something like this but I’m a bit confused about how the velocity works. Do particles move based on the cellular automata rules or their velocity? Because the rules for sand doesn’t make it move sideways but it did move sideways from its velocity.
Tracking velocity is a way to expand the rules of the simulation. So if a particle has an X velocity of positive 2 then it will attempt to move 2 cells to the right that frame (checking the contents of each cell along the way). This is different than the basic rules mentioned at the beginning.
This is actually my first time commenting here. I wondered wether you got a discord? Or if not let me just ask my question here:
As every Element has a step function, do you first check wether the cell SHOULD update and then set the corresponding chunk to "update_next_frame" to true?
Each chunk has shouldStepNextFrame set to false at start of the entire update cycle (before any elements have been updated). As elements update, if they perform any action that would require the chunk to be updated next frame (such as changing position or being on fire) then they set shouldStepNextFrame to true on the chunk.
At the start of the next frame shouldStepThisFrame inherits the value of shouldStepNextFrame and shouldStepNextFrame becomes false again.
So to directly answer your question, each element knows already if it should update this frame due to the value of shouldStepThisFrame on the chunk it belongs to. It does not know if it should step next frame and that is determined this frame.
Very good project, however I did not manage to build/run the code from your repo (created an Issue with my findings on Github). Can you actualise or at least give a guide how to make it work? Thank you!
Hello, I just wanted to ask about one thing - how do you handle update order?
In your simulation if I place a ball of sand it falls nicely and breaks after hitting the ground, in mine it breaks mid-air.
Why?
Because I update the matrix from up-left to down-right. The higher sand particles think their down neighbors won't fall down, so the higher ones stay in one place (or move in different non-down directions).
What I have done in this simulation is update from the bottom row to the top and the update order within each row is random.
Another adjustment I made after I implemented velocity was if a piece of sand is falling down and encounters another element that is also currently falling then it will stay above that element and match its velocity. That prevents clumps of falling elements from breaking apart mid-air.
@@marf1610 Thanks for the answer!
Now I’m wondering if there’s a way to do this entirely with shaders on the gpu and if that would be much faster
It is possible to run a falling sand sim on the GPU but it would be much more challenging to achieve the same level of functionality as I have in this simulation.
I heard at the end of the video you make your threads every time through the loop? Why not keep the threads around and just reassign work every loop? Thread creation has overhead in the cpu time
I did this project as a way to get more experience with Java since I was using it at work (web dev). This is why many of my approaches are not as well suited for game dev. Also, this was the first time I ever worked with multi-threading. So it was simply an oversight and lack of knowledge on my part. Good catch.
@@marf1610 no worries! i was just curious if there was a reason behind it is all. the project is really awesome, just when i heard it that was one thing that i was like "hold on every frame? that wouldnt be very fast" and i had come across a similar issue in the past working on a project. so was just throwing it out there. thank you for sharing your journey on it
This makes me want to learn C++.
Really hard to do this in C.
Lol, looking back I managed to learn C++ and love it
I know it's been two years, but have you perhaps revisited this problem by coding the logic in shaders? I tried this myself recently and it's promising in that the framerate becomes a non-issue due to the massive paralelism (a modern GPU has hundreds, if not thousands, of cores), but at the same time I've run into problems where the multiple "threads" step on each other's processing areas, resulting in problems like particles disappearing or appearing out of nowhere.
It is possible to code a falling sand sim via shaders but overall you have much less control over state and processing (like what you were mentioning). Most of the things described in this video could not be done on the GPU. Look into "Jelly In The Sky" for a game made on the GPU.
If tNice tutorials isnt the most true tNice tutorialng ive ever read
what are the specs of your computer? (in regards to the performance of the simulation)
that's CPU based no? I'm planning on doing a uni project on falling sandbox kinda like that, but utilizing webgl and storig cell states in 2D textures. Then updating the world using a checkboard pattern of some sort and swapping values inside the matrices. I'm pretty sure it's gonna be heavier on memory but something tells me I might be able to have a fast as fck sim in the end.
Yes mine is CPU based. I think to implement all the functionality I have in this simulation on a GPU would be more difficult. But a GPU would be much faster and able to handle more particles overall.
There is a game called "Jelly In The Sky" which is entirely run on the GPU which might be interesting to look into.
@@marf1610 yeah I don't think I'll go as deep as you, I'll try to get a few things working and submit it lol. I'll check that game, thanks a bunch
Mabye im missing something... How did you make the speed of the pixels falling/updating frame independent
I gave each element instance a velocity value which was updated each frame by gravity and can be affected by other things such as explosions. Each element also had two sets of coordinates. Integer coordinates which are its placement in the grid. And floating point coordinates which are updated by the velocity.
So if a single element is in free fall for a long uninterrupted time, its velocity will increase as the force of gravity accumulates each frame. If Y velocity is greater than 1 it will move one cell, if velocity it greater than 2 it will move 2 cells.
Then the floating point coordinates are rounded down and that's the new placement in the matrix for that element
@@marf1610Thanks, nice vid👍
hey, great video! I am having some trouble implementing the water physics correctly however, using velocity on the x dimension to speed up the spreading of water. I'm just running into lots of strange issues, I think relating to how it chooses a direction to go in. I am not sure how else to explain it, but I was wondering if you perhaps had any tips in implementing the water physics? I'm doing this in c++.
Thanks!
After implementing velocity in the simulation the elements no longer check both right and left for a place to go. If the x velocity is positive it only looks to the right and down-right. If it hits a Solid element then the x velocity is multiplied by -1. So next frame it would only look to the left and down-left. This isn't explicitly mentioned in the video.
The same logic is applied for solids and gasses. This reduces the amount of cell checking required each frame once liquid begins looking further than one cell away.
For liquids the velocity usually indicates just direction. And the maximum is taken between dispersionRate (usually around 5) and velocity for how many cells away to look for an open spot. This ensures it is always looking at least 5 cells away.
Also, if a liquid is falling downward for lets say 4 cells and hits a solid then it will launch another function to search right or left (based on velocity direction) another 5 cells. This helped liquid spread out further once it hits the ground when falling.
@@marf1610 Thanks for the very helpful answer. So do you just decide randomly when first creating water what x velocity it should have?
hmm I am not sure what I am missing. my attempt at implementing the spreading as you said has just resulted in water sometimes not falling to the left when it should, and long perfectly straight lines shooting out to the right...
so upon a lot of pain I'm beginning to think this is out of my current scope of possibilities 😅 I'm hitting road block after road block. Hopefully i can come back to this in the future when I'm a better programmer :p
Yes when liquid is created it randomly generates a positive or negative x velocity (Very small so it just indicates direction).
Lots of pain is exactly right haha. I spent many hours on this project trying to solve challenges that I was never able to figure out and had to choose a new direction. But all of that work (which sometimes feels wasted) contributes to becoming a better programmer. Good luck!
Hey, would implementing the quadtree for optimization instead of grid/chunks be a better decision ... ?
I would hesitate to say that it could be better due to its added complexity and increased processing requirement to calculate it on the ever changing simulation. The chunk method is very simple to understand and implement. I would be curious to see it implemented that way if you ever do it.
@@marf1610 ohh ... Yeah I got it ... I'm at very basic level and learning rn but I'll surely let you know if I ever could implement the same! Thank you for reply and keep uploading... I'm a huge fan! Keep the good work 🙌🏼
Those are fair optimizations but you'll get multiple magnitudes more performance out of shaders. Or even cuda, if you have them.
How and when exactly do you disable a chunk? I understand that you report to the chunk when you place an element or when an element updates and set it's step value to true. Do you just disable a chunk at the end of the frame?
Basically, yes. At the start of every frame each chunk has shouldStepThisFrame set to the value of shouldStepNextFrame. And then shouldStepNextFrame is set to false for all chunks. Throughout the current frame shouldStepNextFrame is set to true for chunks which have activity in them.
@@marf1610 Thanks for the quick reply. Fortunately I figured it out 15 minutes after posting my comment. Your video has been very helpful! Wish you well.
Is there a way to code this using Python ? Am an architect that starting to make my way through programming and currently aiming to learn Python and program something like this for to be implemented into erosion studies later on
I don't have much experience with Python but looks like you could try using Pygame as a starting point.
I ran into the same step stair problem at chunk edges. Do you just offset the bounds of the chunks each frame to resolve this?
The step stair problem arose from processing the elements in columns where the columns start and end positions did not change across frames. To fix this I added random offset to the columns start and end positions each frame.
The chunk bounds remain the same across all frames and the chunk bounds have no meaningful correlation to the processing threads' column start and end positions.
This is different from Noita where the chunks both keep track of if the elements contained need to be processed, and the bounds in which each thread processes elements. In Noita when there is a large body of liquid that begins moving all at once I have consistently seen the step stair effect as the elements fall. It seems unavoidable if your chunks are also the bounds of a processing thread.
Moving the bounds of chunks across frames would defeat the purpose of a chunk since it will not have knowledge of the new elements within its bounds after it moves.
@@marf1610 Thanks for the reply! My chunks don't keep track of the elements within, merely a bottomleft position for the chunk and a flag to update the chunk next frame (and a numChangesMade integer). I give a random x and y offset to all chunks apart from the ones at x=0 or y=0 at the start of each physics update. This has totally eliminated the step stair problem although it has broken the code that alerts neighboring chunks to update.
How are you determining the order of processing the elements? Just left to right, bottom to top? Any multithreading?
I also update update the elements within each row subsection in a column in a random order.
@@marf1610 I'm processing the chunks left to right, bottom to top in separate threads. For the cells, I create a MoveCell struct for each necessary movement and shuffle those instructions and execute them after all threads are finished.
How are you alerting neighboring chunks to wake up if the elements get processed in a random order? Are you passing chunk bounds information whenever you update a cell? I'm using bool onChunkEdgeX = (x%chunkWidth == 0 | (x+1)%chunkWidth == 0)
@@prodevus Ah yeah so if you are using chunk boundaries to define the regions where threads update then you will always have this stair step looking issue.
It makes the most sense to update cells that way. The Noita devs do the chunk checkerboard multithreaded update pattern which allows them to simulate such a large world (similar to what you're doing), but the downside is that you will have those visual artifacts since the bounds of the threads update range always start and end on the same indices across frames.
You could try creating a new "chunk" class that only defines the thread update boundaries and references your original chunk logic for if a cell should update or not. You can add offset to these new thread boundaries each frame which would eliminate that stair visual effect but this would require you to check every single coordinate in the simulation and then reference your original chunk logic if that coordinate needs to be updated.
To answer your other question, whenever a cell performs some action which would require itself and its chunk to be processed next frame it sends its coordinates the matrix class which determines the appropriate chunk to update and the logic there determines if it is on a chunk boundary.
fluid simulation please😊
So how do I actually start being able to make one of these games like if I was asking how do I paint I need to know what the paper is and how to get it and like what's the brush and how do I hold it like I don't know how to actually start making one of these falling Sand games and I think it'd be a good place to get started but I can't figure out what it is that I need like is unity a thing can I make sand falling Sand games in unity I don't know how to use unity
The issue with falling sand games is that you need pretty low level control over each element in your 2D matrix. And also you need to control the order in which the elements update. If you used Unity and represented each element as a GameObject this would be a huge waste of space and you wouldn't have control over the order of updates (among other limitations).
This is why most of the sand simulations you see are not made with a game engine. Because game engines abstract away a lot of the fine control to speed up your development. This is also why the Noita devs created their own custom game engine.
When creating the 2D matrix and all the logic for updating elements you are essentially creating a building block of making a game engine.
To get started on this I think a very good place would be to use JavaScript and the HTML5 canvas. There are lots of tutorials out there on setting the canvas up and interacting with it. It will not be as performant but it would be a much easier starting place.
Also, I think Sandspiel is made with JS and HTML5 canvas.
@@marf1610 thank you so much that was a very detailed answer I appreciate that
How would a character interact with the solids ?
This is something I started working on but didn't complete. My plan was to treat a player character like an element which takes up multiple spaces. Take into account velocity, calculate next position, and iterate to that position checking for blocking elements along the way. It would get tricky for things like how a moving/falling solid shouldn't block a players movement, etc.
if you're processing each row one element at a time, wouldn't that lead to a scenario where something like water can move right, and then get processed a second time in one frame?
Yes that is a side effect. Some cells could be processed multiple times and some could be skipped. Randomizing the order of processing within each row seems to mitigate most of the visual effects from that. And 60 fps also makes it difficult to tell that is happening. But as you've described that can happen. I didn't realize it was happening until after I made the video actually.
I believe in the case of Noita, each cell knows what tick it was updated. The simulation has a "tick" counter that increases by 1 each simulation step. When it's time to process a cell, you check if it has been updated this tick, if not, process the cell and set that cell's tick number to match the simulation tick counter.
I tried compiling your game, and I just get a lot of "unresolved external symbol" errors
I think you may have tried to compile the C++ falling sand github repo that I had started working on. You want to use the FallingSandJava repo linked in the description.
If you are using the Java version then you will need to run the installation process on the gradle file included in the repo to download and install the necessary dependencies.
@@marf1610 oh, so the c++ version is still unfinished? That is the one I wanted to check out
@@gez_4515 Correct. I didn't know any C++ when I started it so I got stuck and got sidetracked doing other C++ projects since then to learn. I am unsure if I will revisit it.
Is there any way to do this in Unity?
There is another comment thread on this video where I discuss this with someone else. You can look through that for more details. But the short answer is yes you could get something to work. And I think you can find some Falling Sand in Unity videos on TH-cam.
But if you wanted to implement all the things I talk about in this video, you would be fighting against the design of Unity to make it work, you wouldn't be able to make use of the many development tools Unity offers, and this is why the Noita devs built their own engine. Because you need to have specific control over the update loop which Unity takes care of for you normally but would cause issues with something like this.
What program are people using to code stuff like this? I'm trying IntelliJ but it recognises NOTHING i'm putting in.. It would be super helpful to actually know what software you are using.
Generally you would want to use some sort of framework or engine that allows you to create a window and use the provided hooks for update and draw in that window. For this particular project I used LIBGDX since it was lightweight and made for Java. It eventually became a pain to work with since it was so barebones, has a small community, and is primarily for mobile development.
There aren't many Java based game engines out there. So you could use LIBGDX. Or if you used C++ you could use SFML. Or for something lightweight and browser based you could use JavaScript with the HTML5 canvas
@@marf1610 hey buddy, nice one for the reply! Have you or are you planning on doing any tutorials for a JavaScript/HTML tutorial for a sand fall game, or any sort of clicking game? I'd be interested to see how you'd go about creating a "game window" and interaction in html/JavaScript.
@@AquaDragon6629 I have thought about doing a follow along tutorial for a very simple HTML/JavaScript falling sand game but I haven't really explored it yet.
@@marf1610 Well, i've subbed, so if you do, i'll be there. I'd love to see it!
@@AquaDragon6629Awesome, thanks for the feedback!
how did you do the texture please?
For this project I iterated through the matrix and drew squares (or rectangles if there were multiple sequential cells with the same color) with the debug tool. This was extremely inefficient and inflexible. I have tried on two other platforms to code a better way to generate a texture that is more flexible and quicker to generate. But I think it requires more lower level knowledge of graphics programming than I currently have. Most game engines aren't well suited for this type of project which makes it require a lot of custom solutions once you get past initial implementations.
@@marf1610 thank you so much. I ended up using shaders for this, passing in the grid size and sprite position.
I’m currently trying to implement multi threading but struggling. Can you give me any pointers? I’m using godot 4, and can call Thread.new(callable) and have an update_position that I was using to move the sprites in my grid. How might I go about doing this? I’m able to split the grid up into columns. Thanks for your reply!
You process elements in random order?
The matrix is still processed row by row bottom to top but the update order within each row is random.
@@marf1610 I decided to use random sampling in order to get rid of floodfill jitteriness, but it probably won't cope well with multithreading.
A modern computer should have no problem simulating and rendering 250 000 particles at 60fps. Allocating an object for every particle is terrible for performance, allocating a large chunk of memory and compactly storing all of the data would be much better. This also has the nice effect of cleaning up the logic in the code, having one piece of code decide what to do with all the elements is nicer to work with than the "actOn" approach as the order in which things happen becomes more predictable. That also should make the problem actually parallelizable so you don't have to hack the thread boundaries.
I did mention at the end of the video there are likely better ways to accomplish what I had created. I created this over the years while I was learning to code and not until recently did I start to learn about memory management and efficiency. So thanks for your ideas.
However, your suggestions depend on what it is you want to accomplish. Sure you could have each particle type represented by a single struct and use that to only define how particles should react to each other. But that gives less control over individual cells. How would you go about staining the color of a cell while it remains of the same element type? Or how would you set an element on fire and then extinguish it and have it retain its original properties? If you wanted a tech demo just for performance purposes you could go with your approach. But the title of the video states how to create a falling sand simulation like Noita, and the methods I describe is more along the lines of what the Noita devs did.
The actOnOther method is only for special effects of a specific element subtype. The movement and interaction logic is consistent and inherited from the Liquid, Gas, and Solid types. If I did not use the 'actOnOther' method then I would fill the movement logic at the Liquid class level with innumerable 'if else' statements specifying subtype interactions between Acid and every other element type. The 'actOnOther' method scales with any amount of element types.
Since I do not use a double buffer and the matrix is modified in place, then regardless the simulation would need to be split into separate chunks and processed independently to avoid concurrent modification.
Check the 'Exploring the Tech and Design of Noita' video linked in the description and they describe their reasons for their design choices.
gave up on the c++ one?
I realized that I didn't know enough about c++ to really make it work. So I worked on some other easier projects in c++ and ended up creating the pixel sorting app I talk about in another video.
I also realized that I do not like c++. So this is still on my mind but trying to find a good language + game engine/framework without having to completely build my own.
is it possible to do this with unity?
I think there are some videos of sand simulations people have made with Unity. I think you will run into technical limitations if you really try to expand on this down the road. And you wouldn't really be utilizing all of the strengths of unity since all of your logic would be need to be custom. It wouldn't make sense for each element to be a GameObject.
@@marf1610 yeah, gameobject is not a good way to have millions of objects on screen. I hope ECS be ready soon.
@@TeppuTeppu I see your other replies in my notifications but they aren't appearing here.
With Unity you would probably have one GameObject which has the 2D matrix and the element objects (which would not inherit from Monobehavior) and each frame you just update your one GameObject that handles updating all the elements in the matrix.
At that point though you're not really using any of the benefits of Unity.
And then you'll have to come up with some custom drawing logic, a way to generate a texture based on the matrix.
Also, I don't think Tilemap would work well for this.
@@marf1610 I realize tilemap wouldn't work well so I deleted my comment. SetTile is not very good for performance.
What I don't get is: We have high rez, ultra realistic 3d games with millions of vertices, triangles, particles, shaders and textures which run on high fps no problem, but here in a 2d program our hardware somehow starts to struggle?
Why?
You didn't explain collision.
;)