> The idea was to build something fun that never shows adverts to them or tricks them into sneaky purchases by “accident”.
This part really resonated with me. Google promotes the absolute worst spammy shit these days. I have to browse tech forums to find clean simple games.
Last week I was trying to find a simple memory cards game and the search results were complete dog shit so I started building my own memory cards game. In a couple hours I made https://memorycardsgame.com/. Then browsing a svelte forum I found https://toddler-games.com which is much further ahead of mine but I'd never be able to find stuff like this by searching for it. Of course none of the good games are filled with a bunch of SEO spam which is kind of the point.
Since Steve Jobs didn't let his kid use an iPad we've decided the game isn't needed now.
An unsuspected (to me!) place for good kid friendly games, free of ads and in-app purchases or other predatory patterns, is Apple Arcade on iPad.
My 5 y/o is having great fun with the Crayola app and Cooking Mama, and, honestly, between each round, I'm waiting for an ad to pop, a nag screen to pay for stuff or review, a countdown or some other crap we're accustomed to on mobile games and no. Nothing. Just the full game and nothing else. It's a refreshing experience.
Thanks - that toddler-games.com is really nice. It’s so simply done that even a two year old could enjoy it for hours. My kids are 5 and 7 now so want something a bit more advanced, but I wish I’d found that a few years ago
Its a great read. It bothered me a little that there was an ad at the bottom of the page when it started with a passage about avoiding ads. But i share the sentiment and am especially triggered when those ads are in front of my kids. I'm adult and got over that feeling quickly and it is a terrific post.
If you're referring to my blog, sorry yeah I use the free Wordpress plan and they stick those ads there for themselves :-(. The app has no ads though, which is important when it's for kids
Very nice! A bit of feedback: when you quickly click many cards, they are open at the same time, which makes it trivial to see pairs. So maybe you want to wait opening any cards until the last pair is closed.
Nice! Small bit of feedback: when you click “restart” after winning, the emojis are replaced with new ones right before the flip animation plays, which briefly reveals the solution. I’m assuming that’s a bug and not an intentional hint, as it doesn’t happen the first time.
I moved to Vivaldi browser on mobile which has a built in ads/trackers blocker (how is that not a built in feature in any browser? Oh wait) and said goodbye to ads forever (ublock on PC ofc).
A few weeks before I made the move I started getting goatse style shock sites in google ads, some kind of leg disease, horrible stuff.
I was looking for colouring app two days ago but couldn't find a decent one. https://toddler-games.com seems to be something my niece's would love. Thanks.
Author here: I'm loving all the suggestions of ways that this might be achievable in either a faster or simpler method! The code is open source at https://github.com/shaneosullivan/example-canvas-fill and I'd love to see you hackers improve on it and share it with everyone. Any and all improvements I'll happily use going forward in my app.
I guess you are doing the same thing and memoizing the graph ahead of time. Perhaps find an optimized implementation in wasm and save yourself some maintenance time.
The fill algorithm is far from being properly optimized:
1. Use pointIdx instead of a string for fill keys. That's going to be way faster and memory efficient
2. There's no need to have separate added and visited. Just keep added and continue checking it before adding to the queue, and don't delete added entries
3. Even better, don't even use added but instead just check the output image data
4. Compute pointIdx incrementally by adding or subtracting 1 or width, only do a multiplication for the first point
5. Don't keep y coordinates in the loop, instead store the minimum and maximum pointIdx and then divide at the end to find the y coordinates (you still need to keep x to compute the x minimum and maximum if you need it, unless you can make the image have a power of two stride, in which case you can just mask pointIdx to compute x)
6. Use a black border instead of doing boundary checks
7. The % 5000 check is horribly slow since division is horribly slow. Use a power-of-two size and a bitwise and to be safe
8. Doing an update every 5000 pixels seems absurdly low. CPUs do billions of operations per second and a pixel should not take more than 100 CPU cycles with proper optimization, so even at around 100 fps you should be able to do in the magnitude of 100K pixels per frame, which means you shouldn't even need to do it incrementally or pre-process. If you really need incrementality you should use both a pixel number check and a timer and adaptively double or halve the pixel number if the timer check gives a too low or high time elapsed.
9. Using "chunks of pixel" is probably faster than single pixels and using horizontal groups of chunks even better, although that requires significantly more code
10. WebAssembly, with SIMD if available, is going to be faster than JavaScript
In general, this code has clearly not been written by someone experienced in writing optimized code, so I assume the pre-processing can also be greatly optimized (if it's even necessary after optimizing the filling code).
Also, there is no need to limit to 256 areas since you can use multiple images and all channels to store larger integers.
I wonder, if assembling an array of paths for outlines may improve things. You can check for a point being in inside path, use paths as hit areas, and you can apply fills. Notably, there wouldn't be any need for keeping various mask images in memory anymore. (You wouldn't want any curves in this paths, just pixel outlines. It may become a bit tricky with complex paths and negative shapes, though, which may be addressed by composing a mask image on-the-fly.)
a potential drawback is that it seems like the paths could be several times larger than the original image (consider a checkerboard pattern, where each pixel is its own fill area, or the pathological spiral pattern i suggested in a comment below)
Assuming you currently recompute the whole thing on every edit, it might be fairly straightforward to speed it up by reusing the results of the previous run. Areas which do not overlap the edited area shouldn't need to be recalculated. Bounding boxes would be a quick way to test overlap.
Having checked the website https://kidzfun.art, it looks like you compute the masks once, and don't recalculate anything upon edits.
If you would like to dynamically adjust the masks, the following algorithm should be O(sqrt(N)) lines of JavaScript executed for realistic cases:
Split the image up into monochromatic regions of at most 1000-4000 pixels (you want to regions to be roundish rather than long and stringy, so use breadth first search to create them). Then keep track of a graph of these regions with edges between adjacent regions. For a 2000x2000 pixel image, the graph should contain ~4000 nodes, so finding a monochromatic component would not take an appreciable amount of time.
Updating the graph after a fill operation is straightforward - just relabel the color associated with each changed region. The only point I'm uncertain of is whether canvas operations are fast enough that each region can have its own mask and up to 4000 draws as described in the blog post don't take too long. The individual masks wouldn't be very big, and the total number of pixels to be colored isn't any different to the blog post, so it may be possible.
If something is drawn with the pen tool, then every region it touches would need to be recalculated. Assuming the pen tool is circular and not substantially larger than 1000 pixels itself, this should be a fast operation as it won't overlap too many large regions and there are few enough regions we can iterate through all of them every frame for a bounding box test.
There are cases where this goes wrong - for example if the regions end up being very stretched. If there are 1000 1-pixel wide vertical lines, and the drawing tool allows a 1000 pixel horizontal line to be drawn in 1 frame, the algorithm described looks at a million pixels (possibly 4 times each as it checks for adjacency), which might be too slow. However, since this is aimed at a touchscreen, I'd be impressed if your children can and want to draw accurately enough to cause a problem. Further optimisations could work around this problem (and other problems such as having lots of 1-pixel regions that would bloat the graph).
devit's suggestions are also worth incorporating.
Since this algorithm only becomes interesting with edits, it's not really something I could implement as a pull request to the GH repo.
You could do instant flood-fill on a slow PC in the early 90s. There is no need to precompute this. The possible issues are:
1. You're using a slow algorithm. This is almost certainly the case, looking at how slowly it run and at the order in which pixels get painted. The Wikipedia page on flood fill is enough to find a good algorithm.
2. Possibly, the overhead of individual canvas operations is high, so setting each pixel at once is slow. If this is the case, it would be partially ameliorated by using a span-based algorithm, but you could also run the algorithm on an offscreen byte array and then blit the result to canvas.
I would bet money that a 90s state-of-the-art algorithm running in JavaScript on an offscreen array will be perceived as instantaneous on a modern computer.
Note that you loose 1-2 orders of magnitude just by the screen resolution (in the early nineties we used 640x480, sometimes even 320x200 vs 4K nowadays). Another order of magnitude is lost by using a more high level programming language, which sure you could probably optimize down to factor 2-3. Plus sublinear scaling of stuff like memory latency since the 90s. All in all I agree we should be able to do better, but it is by no means trivial.
If you are right that would be amazing! The demo code is open source, please send a PR with such a flood fill implemented.
The requirement is that when the user clicks on a 2k x 2k image it takes 50ms or less, running on a cheap Android tablet. If a better algorithm, perhaps implemented in wasm, can achieve this, I’d love to discard all my complex code and just use it
I love that everybody commenting here here emphatically insists that you must be doing it wrong, but real-world solutions are nowhere to be found. I admire your commitment to keeping a positive tone, but you'd be justified in feeling some frustration.
I do hope a PR shows up in the next few days so the internet can stop having this debate and move on with a good library.
There are fast segment based fill algorithms from the seventies or very early eighties in the literature and reprinted in the first volume of Graphics Gems. They work very well and do not require the call stack or amount of computation of simpler methods.
Ha, painting tablet app feels like a rite of passage for programmer parents. Here's mine from that era https://paints.netlify.app/
Where it got really interesting later was when one of my kids asked how I made it, how it worked, how they could add new features. So it grew a bunch of adorable haphazard hacks that my oldest implemented.
Very cute! I started out with basically this, and my kids kept asking me for more and more features :-). Recently they asked to make animations, and that took a chunk of time to get right. I'm looking forward to whatever they ask for as they grow more advanced!
Ha, guilty (https://safari-sketch.com)! Was also annoyed by an iPad game my son played that tried to extract money out of him every play session. It served as a nice excuse to learn some technologies I wouldn't otherwise play with.
That’s really essential, even if only for the clumsy thumb left on the screen with a naive grip. Being able to finger paint with all ten fingers is a bonus.
> Ha, painting tablet app feels like a rite of passage for programmer parents.
Only the first parents should have had to make it. The fact that one of these good home grown ones is not at the top of any search engine is a failure of the internet.
When it comes to performance, I find you really need to experiment with HTML Canvas. Some of the interfaces can be hundreds to thousands of times slower for manipulating the canvas than others.
It's not just the Canvas API that surprises, it's also how browser JS engines choose to implement those APIs. What works well in Chrome can often cause grief in Firefox or Safari. Working with canvas elements today often feels like frontend development back in the 2000s
the summary is that they preprocess the image to partition it into a disjoint set of fillable regions, but i feel like this maybe has to be redone whenever you mutate the image
maybe other optimization approaches would yield a flood-fill algorithm that just runs fast enough in js; wasm can surely do it
like i feel like you can probably loop over the pixels in a scan line until you encounter an obstacle at several tens of megapixels per second
as the dumbest possible test of js perf, this code (admittedly not accessing an imagedata object) gets about 250 million iterations per second on my 2.6 gigahertz palmtop in firefox
function tri(n) { let x = 0, y = n; while(y--) x += y; return x }
s = new Date(); console.log(tri(10_000_000)); console.log(new Date() - s)
A proper flood fill needs to iterate over an enormous ImageData object (or at the very least a huge 2d array) and page in/out memory as appropriate. Your code appears to just increment a variable. This is not a valid comparison.
the comment you are replying to explains that already, right above the code
the question of memory access time is quite deep
in shane's example of flood-filling a 2048 × 2048 image in 16ms, the image is 16 mebibytes; if you have less ram than that, so that you have to page in and out (as your comment says you do), you are not going to be able to do the computation fast enough. but my hand-me-down cellphone has 256 times that much ram so i guess you're using a pentium pro 200 or something, in which case you aren't going to be able to run a browser that supports canvas
assuming you're using a computer from the current millennium, one which has enough ram to run a browser that supports canvas, you won't need to do any paging, but you do need to think about dram bandwidth. probably the required bandwidth to dram is 2 gigabytes per second (one read and one write), while typical current ddr4 systems provide on the order of 30 or 40 gigabytes per second. that assumes you can keep the memory access reasonably sequential (if your l2 cache is less than those 16 mebibytes). this is usually the case with a simple line-by-line flood-fill algorithm, like the one used by gw-basic 40 years ago, but there are pathological images where it is not
consider a 1-pixel-black/1-pixel-white square double spiral that fills the full 4 mebipixels. whether a fill in the white covers all the white or just half of it depends on every single black pixel, so algorithms that can do this with better locality and a reasonable amount of parallelism are inherently going to be relatively hairy
but images like that cause problems for shane's existing algorithm too because they will make shane's web worker spin for a long time
If a wasm algorithm can run in under 16ms for arbitrarily large images that would be amazing. Hard to beat pre-computing all possible fills however, as the user perceives it as instant.
If you’ve seen a really fast wasm solution I’d love to replace the fill portion with it though.
I think people in this thread are being much too optimistic about browser performance. Writing a loop isn't the issue; memory access patterns are. Canvas implementations are just not well suited for the flood fill problem space. (I spent some time with flood fills + canvas ten years ago when I was working on the now-dead library Literally Canvas, but I assume that experience is pretty far out of date now.)
Precomputing fill areas is a really good idea for the situation you're in!
You can probably make the process extremely fast by replacing the flood-fill approach with a something based on a Connected-Component Labeling algorithm ( https://en.wikipedia.org/wiki/Connected-component_labeling ). There's a good amount of literature on the subject and it's often included in computer vision libraries (e.g. OpenCV).
You'd first threshold the image by checking if a pixel is 'close enough' to the clicked pixel. This will create a B&W image. Then you call the CCL on this binary image to produce a labelled image: each pixel will contain the id of its component (i.e. which enclosed space it belongs to). Once you have this, it's just a matter of replacing colors on the canvas for pixels with the same id as the clicked pixels.
Obviously, that's just the 'theory' part. If you can find a good library that includes one then you'll have to integrate it. Otherwise, you'll have to re-implement that in Javascript, which is easier said than done and may also not reach the desired performance.
I've tried writing a fast flood fill in JS and it's a lot more challenging than you and GP make it out to be. If it's really so straightforward, you should produce code. Otherwise, these comments don't add much to the discussion.
I wasn’t calling per pixel :-) even when just visiting each pixel once it would still take 50 - 100ms to fill a large image which the user perceives as lag. I wanted it to be instant
Surprised "jump flooding" hasn't been mentioned yet, which is the common technique to accelerate this sort of thing (used for color fills, signed distance field construction, outlines, etc.).
Jump-flooding is inexact and can jump over significant edges. The runtimes claimed are also incorrect - as it sets every pixel, it is O(N^2) in the image dimensions, just like flood-filling. If you're working with an image and setting pixels, you cannot avoid being O(N^2) in the dimensions of the filled area.
Jump-flooding is an algorithm suited for GPUs where you run operations for all pixels "simultaneously" which is why the complexity is often given in number of iterations and not number of operations. Naive flood fill fits this model badly and a GPU implementation would have a complexity of O(N^3) as you expand your fill region border by only one pixel width each iteration so you will need O(N) iterations for sufficiently large regions but you need to look at ALL pixels every time. You could force a CPU-like computation where you keep a stack of visited pixels to expand out from but that would actually end up slower for all reasonable sizes on the GPU unless your regions are much smaller than the image.
You can also modify the algorithm to not jump over edges if that matters to you, sacrificing its advantage in edge cases where there are thin connections between regions.
Readit News
This part really resonated with me. Google promotes the absolute worst spammy shit these days. I have to browse tech forums to find clean simple games.
Last week I was trying to find a simple memory cards game and the search results were complete dog shit so I started building my own memory cards game. In a couple hours I made https://memorycardsgame.com/. Then browsing a svelte forum I found https://toddler-games.com which is much further ahead of mine but I'd never be able to find stuff like this by searching for it. Of course none of the good games are filled with a bunch of SEO spam which is kind of the point. Since Steve Jobs didn't let his kid use an iPad we've decided the game isn't needed now.
Nice app.
My 5 y/o is having great fun with the Crayola app and Cooking Mama, and, honestly, between each round, I'm waiting for an ad to pop, a nag screen to pay for stuff or review, a countdown or some other crap we're accustomed to on mobile games and no. Nothing. Just the full game and nothing else. It's a refreshing experience.
Nice! Small bit of feedback: when you click “restart” after winning, the emojis are replaced with new ones right before the flip animation plays, which briefly reveals the solution. I’m assuming that’s a bug and not an intentional hint, as it doesn’t happen the first time.
There's always DOSBox!
Here's an example https://en.m.wikipedia.org/wiki/Connected-component_labeling
https://scikit-image.org/docs/stable/api/skimage.measure.htm...
I guess you are doing the same thing and memoizing the graph ahead of time. Perhaps find an optimized implementation in wasm and save yourself some maintenance time.
1. Use pointIdx instead of a string for fill keys. That's going to be way faster and memory efficient
2. There's no need to have separate added and visited. Just keep added and continue checking it before adding to the queue, and don't delete added entries
3. Even better, don't even use added but instead just check the output image data
4. Compute pointIdx incrementally by adding or subtracting 1 or width, only do a multiplication for the first point
5. Don't keep y coordinates in the loop, instead store the minimum and maximum pointIdx and then divide at the end to find the y coordinates (you still need to keep x to compute the x minimum and maximum if you need it, unless you can make the image have a power of two stride, in which case you can just mask pointIdx to compute x)
6. Use a black border instead of doing boundary checks
7. The % 5000 check is horribly slow since division is horribly slow. Use a power-of-two size and a bitwise and to be safe
8. Doing an update every 5000 pixels seems absurdly low. CPUs do billions of operations per second and a pixel should not take more than 100 CPU cycles with proper optimization, so even at around 100 fps you should be able to do in the magnitude of 100K pixels per frame, which means you shouldn't even need to do it incrementally or pre-process. If you really need incrementality you should use both a pixel number check and a timer and adaptively double or halve the pixel number if the timer check gives a too low or high time elapsed.
9. Using "chunks of pixel" is probably faster than single pixels and using horizontal groups of chunks even better, although that requires significantly more code
10. WebAssembly, with SIMD if available, is going to be faster than JavaScript
In general, this code has clearly not been written by someone experienced in writing optimized code, so I assume the pre-processing can also be greatly optimized (if it's even necessary after optimizing the filling code).
Also, there is no need to limit to 256 areas since you can use multiple images and all channels to store larger integers.
a potential drawback is that it seems like the paths could be several times larger than the original image (consider a checkerboard pattern, where each pixel is its own fill area, or the pathological spiral pattern i suggested in a comment below)
If you would like to dynamically adjust the masks, the following algorithm should be O(sqrt(N)) lines of JavaScript executed for realistic cases:
Split the image up into monochromatic regions of at most 1000-4000 pixels (you want to regions to be roundish rather than long and stringy, so use breadth first search to create them). Then keep track of a graph of these regions with edges between adjacent regions. For a 2000x2000 pixel image, the graph should contain ~4000 nodes, so finding a monochromatic component would not take an appreciable amount of time.
Updating the graph after a fill operation is straightforward - just relabel the color associated with each changed region. The only point I'm uncertain of is whether canvas operations are fast enough that each region can have its own mask and up to 4000 draws as described in the blog post don't take too long. The individual masks wouldn't be very big, and the total number of pixels to be colored isn't any different to the blog post, so it may be possible.
If something is drawn with the pen tool, then every region it touches would need to be recalculated. Assuming the pen tool is circular and not substantially larger than 1000 pixels itself, this should be a fast operation as it won't overlap too many large regions and there are few enough regions we can iterate through all of them every frame for a bounding box test.
There are cases where this goes wrong - for example if the regions end up being very stretched. If there are 1000 1-pixel wide vertical lines, and the drawing tool allows a 1000 pixel horizontal line to be drawn in 1 frame, the algorithm described looks at a million pixels (possibly 4 times each as it checks for adjacency), which might be too slow. However, since this is aimed at a touchscreen, I'd be impressed if your children can and want to draw accurately enough to cause a problem. Further optimisations could work around this problem (and other problems such as having lots of 1-pixel regions that would bloat the graph).
devit's suggestions are also worth incorporating.
Since this algorithm only becomes interesting with edits, it's not really something I could implement as a pull request to the GH repo.
1. You're using a slow algorithm. This is almost certainly the case, looking at how slowly it run and at the order in which pixels get painted. The Wikipedia page on flood fill is enough to find a good algorithm.
2. Possibly, the overhead of individual canvas operations is high, so setting each pixel at once is slow. If this is the case, it would be partially ameliorated by using a span-based algorithm, but you could also run the algorithm on an offscreen byte array and then blit the result to canvas.
I would bet money that a 90s state-of-the-art algorithm running in JavaScript on an offscreen array will be perceived as instantaneous on a modern computer.
The requirement is that when the user clicks on a 2k x 2k image it takes 50ms or less, running on a cheap Android tablet. If a better algorithm, perhaps implemented in wasm, can achieve this, I’d love to discard all my complex code and just use it
I do hope a PR shows up in the next few days so the internet can stop having this debate and move on with a good library.
Where it got really interesting later was when one of my kids asked how I made it, how it worked, how they could add new features. So it grew a bunch of adorable haphazard hacks that my oldest implemented.
Only the first parents should have had to make it. The fact that one of these good home grown ones is not at the top of any search engine is a failure of the internet.
web directories must make a return.
See for example: https://benchmarks.slaylines.io/
maybe other optimization approaches would yield a flood-fill algorithm that just runs fast enough in js; wasm can surely do it
like i feel like you can probably loop over the pixels in a scan line until you encounter an obstacle at several tens of megapixels per second
as the dumbest possible test of js perf, this code (admittedly not accessing an imagedata object) gets about 250 million iterations per second on my 2.6 gigahertz palmtop in firefox
the question of memory access time is quite deep
in shane's example of flood-filling a 2048 × 2048 image in 16ms, the image is 16 mebibytes; if you have less ram than that, so that you have to page in and out (as your comment says you do), you are not going to be able to do the computation fast enough. but my hand-me-down cellphone has 256 times that much ram so i guess you're using a pentium pro 200 or something, in which case you aren't going to be able to run a browser that supports canvas
assuming you're using a computer from the current millennium, one which has enough ram to run a browser that supports canvas, you won't need to do any paging, but you do need to think about dram bandwidth. probably the required bandwidth to dram is 2 gigabytes per second (one read and one write), while typical current ddr4 systems provide on the order of 30 or 40 gigabytes per second. that assumes you can keep the memory access reasonably sequential (if your l2 cache is less than those 16 mebibytes). this is usually the case with a simple line-by-line flood-fill algorithm, like the one used by gw-basic 40 years ago, but there are pathological images where it is not
consider a 1-pixel-black/1-pixel-white square double spiral that fills the full 4 mebipixels. whether a fill in the white covers all the white or just half of it depends on every single black pixel, so algorithms that can do this with better locality and a reasonable amount of parallelism are inherently going to be relatively hairy
but images like that cause problems for shane's existing algorithm too because they will make shane's web worker spin for a long time
If you’ve seen a really fast wasm solution I’d love to replace the fill portion with it though.
Precomputing fill areas is a really good idea for the situation you're in!
Edit: actually it was 7 years https://github.com/irskep/literallycanvas-pro-tools/blob/mas...
You'd first threshold the image by checking if a pixel is 'close enough' to the clicked pixel. This will create a B&W image. Then you call the CCL on this binary image to produce a labelled image: each pixel will contain the id of its component (i.e. which enclosed space it belongs to). Once you have this, it's just a matter of replacing colors on the canvas for pixels with the same id as the clicked pixels.
Obviously, that's just the 'theory' part. If you can find a good library that includes one then you'll have to integrate it. Otherwise, you'll have to re-implement that in Javascript, which is easier said than done and may also not reach the desired performance.
Dead Comment
I don't know what OP's original code is but maybe OP was calling a Canvas API method for every pixel (super bad).
You can add event listeners to the SVG's paths/groups and apply fill when clicked.
You can also modify the algorithm to not jump over edges if that matters to you, sacrificing its advantage in edge cases where there are thin connections between regions.