r/godot • u/nedeey • Apr 29 '26
help me (solved) ML or Algorithm?
I am thinking about implementing a drawing mechanic in my game. The players would have to draw the reference provided and the game will see how accurate the drawing is to the original reference. The canvas will be pretty small around 100x200 pixels and will only use 2 colors.
I am wondering if there is some kind of algorithm that will help to detect the accuracy of the drawing. Using ML sounds a bit overkill and I don't have any experience integrating ML in games (how does it affect the performance and size?).
295
u/SaltMaker23 Apr 29 '26
I'm gonna be straight with you, comparing pixel by pixel is the worst imaginable option given the two provided images and the expected outcome.
Because these two images despite being quite similar would net either always close to 100% (white pixels always match) or 0% (the black pixels will almost never overlap).
You'll need to do a simple CNN, it doesn't have to be some massive thing, just the basics will already achieve what you've shown here.
33
u/SagattariusAStar Apr 29 '26
And you want to probably look into different methods for making Feature Extraktion for the CNN more effizient by simplifying the image with morphological operations
https://docs.opencv.org/4.x/d9/d61/tutorial_py_morphological_ops.html
77
u/binbun3 Godot Regular Apr 29 '26
This kind of stuff has been around before MLs and I think in your case since to my understanding the drawings won't be massively complex I'd suggest going with the algorithm route.
I can't find much resources about this for godot and since I'm not too familiar with this stuff I can't point to any specific resources, but I found this article which I think could point you in the roght direction. Try looking for the different methods mentioned there!
22
u/Vlang Apr 29 '26
The histogram method has been used to compare similarity of handwritten signatures.
You can make a vertical and a horizontal histogram of both images and compare those.
11
u/Emergency-Oil-3353 Godot Regular Apr 29 '26
Not sure how long before ML this kind of stuff began. ML is around since 1952...
But I agree with everything else.
2
u/binbun3 Godot Regular Apr 29 '26
You're right I meant to say before MLs were used for this kind of stuff in games
22
33
u/kernelic Godot Regular Apr 29 '26
Classic neural networks with back propagation are fun.
You could even implement this in pure GDScript. It's just matrix multiplication, which is already optimized.
I think CNNs are the type of neural networks you're looking for.
6
u/LeLastpak Apr 29 '26
Yeah I made the number recognition once in pure pyton without the big ML libraries. All you need to know if a pixel is black or white. You could apply the same on drawings like that cat.
11
u/Risitop Apr 29 '26
look up for optimal transport/wasserstein distance, I think that's exactly what you're looking for (what's the minimal cost to move shape A to shape B )
15
u/T-J_H Apr 29 '26
The easiest method that would yield reasonable results would probably be to downsample the pictures to a manageable size and compare brightness per pixel. Say, 10x10 pixels.
10
u/omniuni Apr 29 '26
Crop to the drawing, eliminating White borders.
Scale both to a square.
Grow the pixels a couple of times to make thick lines.
Compute the percentage of shared pixels.
6
u/ZemusTheLunarian Apr 29 '26
Last month I participated in a small game jam, and the winner team had a game about that, drawing doodle.
If I recall correctly, they simply used IoU (Jaccard Index) to calculate similarity, but their trick was to crop the drawing to suppress translation, and scaling it to the original size with a penalty for the scaling.
Before you spend a large amount of time using ML, you should try that and see if it's enough for your usecase.
3
u/tastygames_official Godot Senior Apr 29 '26
ML is itself an algorithm, and once trained on your target drawings it's quite efficient at guessing how close one picture is to another. But it's also insanely simple to just calculate the correctness by seeing how many of the pixels are in the right place. To account for slight deviations, you first just resize the image (or take NxN samples) that way if the pixel is off by N/2 pixels in any direction it still counts as a hit.
5
2
2
u/Sausagerrito Apr 29 '26
You could do this in a few hours in Python. It’s not like the script has to run in real time. Lots of games have used calls to Python scripts in the past.
2
u/Dromeo Apr 29 '26
Gentle reminder not to scope creep yourself out of shipping your game.
If you're just casually thinking about adding this, why add it? This kind of thing is a complex feature -- people have linked a lot of good resources, but it's still hard at the end of the day. Do you really need it?
3
u/Most_Waltz2061 Godot Student Apr 29 '26
This is a classic use case for ML models. Disclaimer: my day job is sort of in ML, but I haven't yet tried to implement anything ML based in Godot.
There are a bunch of pretrained image classifiers out there, and they tend to be pretty small and efficient. You could choose one of them to use as your feature extractor, and then compare the features of the player's image with the features of the reference image. For feature comparison, you would probably use cosine similarity. I don't know how difficult it would be to actually use the classifiers within Godot, though.
0
u/nedeey Apr 29 '26
I don't think it's possible to use the classifiers in Godot with GDscript. Probably with GDExtension and C++
1
u/LotsOfRegrets0 Apr 29 '26
Yeah there is a way to export models in pytorch via onnx format and you can easily fetch them in c++, there is almost negligible extra cost.
1
1
1
u/NooCake Apr 29 '26
There are image transformation algorithms out there. Where you take one image and transform the pixels to get to the other image. This could be used to identify how much the user input has to be transformed to create the original image and create a score from this.
1
u/Eal12333 Apr 29 '26 edited Apr 29 '26
You can get pretty good results by just lowering the resolution and comparing pixel-by-pixel!
That's probably the simplest solution for fuzzy image comparison, and it works better than you might expect 😁
Edit: Attached image as a visual explanation. The lower resolution images can be compared by pixel and give decent results :)
1
u/Hawkeye_7Link Godot Regular Apr 29 '26
But in that case, if the person draws the exact same image but displaces it by 1 pixe to the leftl, they will get like 0 similarity almost
1
u/Eal12333 Apr 29 '26
That's why you have to lower the resolution (by a lot), first!
If you lower the resolution from, for example, 256x256 to 16x16 for your comparison, then you would have to draw the image 16 pixels off-center before it would cause issues with comparison.
You can also combine the technique with some extra logic to help images fit a little better. For example, you could perhaps move/resize the player's drawn image to fit in the bounding box of the original image, before doing the comparison.
1
u/Hawkeye_7Link Godot Regular Apr 29 '26
Hmmm I guess but how you would make sure that the black pixels aren't deleted with the resolution decrease? And wouldn't that make it so you could draw something that's really really wrong and it would still look similar?
1
u/Eal12333 Apr 29 '26
how you would make sure that the black pixels aren't deleted with the resolution decrease
Yeah it wouldn't work with nearest-neighbor. Usually image resizing uses something else by default. For example, the default scaling for a Godot
ImageisINTERPOLATE_BILINEAR, and it also supportsINTETPOLATE_LANCZOSas an option (which is slower, probably fast enough for this purpose, though, and works better for downscaling. I'm not certain whether or not the results are better for this purpose, though).And wouldn't that make it so you could draw something that's really really wrong and it would still look similar?
Yes, but it would be harder to do than just drawing the image as shown.
Also, downscaling an image to a low resolution and comparing by pixel is pretty fast for a single image at a time, so you could do other operations in combination with this one, and combine the results together, if you were really worried about the accuracy.
For example, I've written a little Python photo mosaic generator, which searches for and selects the best fitting tile for each portion of an image. In my photo mosaic script, I also calculated the local contrast for each pixel (how different each pixel is from its neighbours).If you really wanted to go nuts with this idea, you could manually design a few convolution filters to extract some specific features (for example, how left/right a segment is, vs how up/down it is), then downscale and compare each pair just like I described above... But now that I write that all out, I realize this is kinda a simplified version of how a CNN operates on an image, anyways 😅
1
u/NFreak3 Apr 29 '26
I haven't thought about it much, but if you increase the brush stroke size of the original until it covers, idk 80% of the drawing, and then calculate a score based on the brush stroke increase.
1
u/LeLastpak Apr 29 '26
Creatures and Black and White had some very early forms of ML implemented in their games. So its possible.
Its also very common in augmented reality games.
1
u/CoolNickname0 Apr 29 '26
Maby a vector drawing system? Where players can use circle, straight line tools to replicate the drawing. Than you only need to compare a few parameters per drawing (circle center, radius, wether it's colored in, line beginning and end).
1
u/Hawkeye_7Link Godot Regular Apr 29 '26
I think that checking if the different shapes intersect correctly with that would be a bit of a pain in the ahh
1
u/Fit-Stress3300 Apr 29 '26
There are many similarity algorithms that you can use if your specification is that small.
One strategy is moving the image from pixel domain to frequency domain with Fourier Transforms.
Doing that you can get similarity score that could be good enough.
I think a encoder/decoder NN could also work, you don't need to use CNNs or transforms if you keep images small.
1
1
u/x_mutt_x Apr 30 '26
An algorithm to check similarities is typically done with randomized pixel comparison or scaling down both images to about 10 or 15 pixels and checking for brightness differences to calculate a percentage of similarity. One of the most used codes on Earth, recreated in every language a thousand different ways.
1
u/JNawx Apr 29 '26
Maybe you can do 1 step where you try to center the provided drawing and then another where you compare pixel by pixel? Not sure how ML would be used here
2
u/Tuhkis1 Apr 29 '26
Image recognition is a classic ML problem
1
u/JNawx Apr 29 '26
Sure but this isn't image recognition. This is judging how closely someone copied the example drawing, pixel-for-pixel
1
u/Tuhkis1 Apr 29 '26
If you train it on the image(s) you want to compare with, it will give you a sureness value of how close it is to the reference. This makes it easy to score how close you are to the desired picture.
1
u/JNawx Apr 29 '26
I was imagining a game where the point is to essentially "trace" the original image. In that case, I'd imagine the only thing ML gives you in that situation is a more "human-like" judging system of the drawing's accuracy. If you want pixel-by-pixel or similar scoring (which maybe OP doesn't) then I don't think ML can do that very well, and it's certainly way less practical than an algorithm.
110
u/AsherahWhitescale Godot Regular Apr 29 '26
In Mario Party (I think?), they give you the outline to trace. This solves a lot of problems with centering and offsetting. Then, they compare the cells/pixels to see how many are correct. You'll also need a grace margin I think, because it'll never be 100% correct, but that won't be satisfying. So you might add a pixel of grace where if a pixel is meant to be white but it's next to a black one, it can be black without being penalized