You could give your topple command (x, y) parameters so it only checks the one middle pixel to see if it needs to be toppled, and if it does then recursively calls itself for the four pixels around it. It’ll run way quicker than having to check every pixel every time.
implemented this and it made my topple function much faster. thanks for the idea (it helps with rendering too since you only need to render *changed* cells)
You can make it faster by "for" looping only from a minimum x up to a maximum x, and a minimum y up to a maximum y, avoiding looping through the yellow zone (and only through the "sand" rectangle)
I made the sandpiles go up to a maximum of 7 and fall off in 8 directions. And I used (256 / 8) * sandpiles(x)(y) for the coloring. It looks like some sort of alien lizard scales.
Wrote a version of this in QB64. Uses 2 arrays, one for the basic data and one for the update (the update just has the -4 and +1's accumulated for each pass) these arrays are then added together if the update array is non zero, also if the update occurs that's the only time it prints a pixel to the screen. It does 1000 generations (on 320x320 arrays) in about 3 seconds at the start and at 180000 generations that's about 6 seconds. Really cool to watch.
To make this faster u could store a "previousPiles" 2D array and then just swap them in topple(), instead of making a new one every frame :p Another suggestion would be to have a variable like a sandpiles "mask" so u can change it easier, for example in the video its: [[0,1,0], [1,0,1], [0,1,0]] but others would be interesting as well!
ShadowPlayz I think so, but instead of just assigning the num, should add to it (+=) like he did in the video, or else when its 3 for example (by propagation from neighbors) and u only assign the num to it, the 3 "sands" are lost
You could probably do a topple in place with the current array in memory. I was thinking something like: -Iterate over each pixel - if num > 3 - pixels[num] - 4 - pixels[above, below, left, right num] += 1 - iterate again Obviously this is more pseudo code than real code and would likely be recursive, looking something like: Function Topple(){ - Iterate over each pixel - if num > 3 - pixels[num] - 4 - pixels[above, below, left, right num] += 1 If ([insert some sort of search for 4, maybe a binary search]) return 1 } Bool Loop = True While Loop: Loop = Topple() In topple return 0 if all pixels are less than 3, 1 if there are any pixels with a 4. Mind you I'm typing this out on mobile and thinking it through while typing it out so take it with some salt as I said recursive but then typed out a non recursive loop lol. Regardless, this would skip creating a new array in memory and do everything in place in the current array
@AmericanOtter U cant do it with only one 2D array unfortunately.. Imagine there are consecutives "3" near a "4", your algorithm would do something like this (assuming neighbors on top/below): 2,2,4,3,3,3,3 --> 2,3,1,1,1,1,0 It will propagate the 4 many times in one topple pass and only on the direction of looping, the correct should be: 2,3,0,4,3,3,3
A faster way to get to the end sooner is to not do only 4 at a time, instead topple each cell entirely in the topple function. So in a grid 000/080/000 it would go straight to 020/202/020 instead of doing 010/141/010 in between. So instead of just subtracting 4 each time you divide it by 4 rounded down and put that into each neighboring cell, then get the remainder and put that back in the cell for the next generation
Note: this is kind of an advanced topic, but if you want a challenge and to do something nobody's ever done before (because there's not *that* many people writing sandpile programs): implement the HashLife algorithm for sandpiles. It produces a ridiculous, literally exponential speedup for game of life, and I see no reason why it shouldn't work for sandpiles.
I did this before and found a few ways to make it faster: 1. Don't check pixels that the sandpile hasn't reached yet. 2. Don't subtract from a pixel that is divisible by 4.For example, if it has a value of 1024, zero it and add 256 to each surrounding pixel. (saves a looooot of steps) 3. A sandpile for a starting value of 4x is a sum of 4 sandpiles for a starting value of x. So if you want to see what a sandpile of 4096 looks like, calculate one for 1024, multiply every pixel by 4 and then continue with processing it. (not sure about that one, it was a long time ago) However, you cant use these steps if you want to see the sandpile grow, but only if you want to see the end result.
You should make a video about FFT and convolution. You could do a bluring algorithm, or even this one (maybe, I'm actually not sure now that I think about it), much faster and more efficiently and I think it's a really good trick to have in your back pocket.
On line 25, I think is should be nextpiles[x][y] += (-4);, not (num-4). Otherwise you may never reach an end. For example if you have 5 in one spot and 0s adjacent to it, with your current algorithm, there would then be 6 in that spot instead of 1, and then the amount of sand in that spot would just keep growing exponentially.
Is the grid swap truly necessary? To me, the line "sandpiles = nextpiles;" alone does the trick -- no need to set 'nextpiles' back to the original since it gets overwritten at the start of the topple() function. When I comment out "nextpiles = tmp;", I don't notice any difference in the result.
I'm sure it's something someone will code themselves (maybe I'll give it a crack tomorrow), but it'd be cool to add a mousepressed event which adds a bunch of sand to the mouse position. Be interesting to see how the two expanding circles interact with one another.
Ok so I decided to give it a go, and it is awesome! The different circles actually interact with one another. I am going to choose some better colours though because currently I have yellow, then less yellow etc etc!
couldn't the topple function have just one loop by just adding the values to the elements in the array? (and in case of toppling just using the code he already has in the second loop)
Is there a reason you don't use try/catch when dealing with edge cases? That's what I've been doing, so I'm just wondering if it's a good way of handling them.
I would not recommend using a try/catch to handle these edge cases. Because throwing an exception is an expressive process. Also once the loop goes near the edge if could be throwing hundreds or even thousands of exceptions. As a general coding practice never use exceptions to handle flow control when you know what the problem is going to be and can be fixed completely with a single if statement. Also its much easier for someone to read. For example you see an if statement checking that an index is inside the array, that's very clear to see the reason, but if you see a try/catch around a block of code than it could be anything and maybe the try/catch may be for a method inside the block, but the reason for the try/catch is not as clear. Not to mention that an if statement will pretty much always be faster than the many thrown exceptions. Hope this helped.
Thanks for all the info. When you said throwing exceptions is an "expressive" process, did you mean expensive? I do make sure to well document my code, so anyone looking at it would know what the try/catch it doing.
Pheonix1328 Yes, sorry I meant expensive, throwing an exception is very expensive in terms of speed and when using for edge cases when you know the problem and when it will not just be throwing one exception but possibly thousands. Also for the case in the video if you did use a try/catch (not recommending) but you would need a try catch around each of the neighbours checks when a simple if statement would do. As a final note you mentioned that you comment and document your code which is great, but it's better if the code documents itself. As I mentioned, seeing an if statement that checks an array for out of bounds is very clear and doesn't even need to be commented of documented, but a try/catch around a block of code is not as clear.
Congrats on 500k Daniel :D Does anyone know a good resource to find these sorts of ideas? i love to watch the videos here then try and make them myself in python
During the live stream I blurted something about doing this in one pass, in stead of two. Should be faster, right. So I did this but my implementation turns out to be slower (almost twice). I guess because I need more if statements do get the same behaviour. learned something :-)
Hello Dan. On your website: thecodingtrain.com/Tutorials/. I think some of your tutorials are missing like nr 13 or from 2 to 6 for example. :) Just would like to have overview :)
12:10 about as stupid as any other apple user I've seen so far in my life... WHY DO YOU NEED A SECOND ARRAY? THIS IS SO MEMORY&TIME INEFFICIENT! YOU JUST COULD DO ONE PASS ON AN INITIAL ARRAY! argh...
Cool video but I must say that this code is pretty awful. Copying the entire array every time it topples is absolute insanity. I guess that isn't the point of the video. Just worries me how many people will be using these videos as a learning resource eh.
