- Home /
Overlapping shape detection
I'm trying to create a (2D) game where you need to match the shape. So for example you have a background figure which is a grey rectangle and the player has 2 drag-able smaller rectangles and need to overlap the grey background figure exactly.
Let me show you an example, because a picture says more than a thousand words...
What I can't figure out is how to detect if the grey area is completely overlapped without the drag-able objects overlapping the background as well. Also, I'd also like to have the option to rule out overlapping objects.
Currently I have the game set up as such:
A fullscreen grid where each square is 4x4 pixels.
One or multiple grey background figures, snapped to the grid. These are 4x4 sprites with adjusted scale.
Multiple drag-able playerobjects, snapped to the grid. Also 4x4 sprites with adjusted scale.
Answer by Bunny83 · May 29, 2018 at 02:58 PM
Since your whole game is grid based the easiest solution is to check every grid position. What you should implement for each of your shape is to convert it's local grid positions into the "worldspace grid".
I would probably use a Dictionary and add all target shape grid positions into that dictionary. Depending on how large your game area is you may use a Dictionary<ulong, int>
where the ulong value is the combined grid coordinate which we use as key. The actual value in the dictionary would be set to "1" for each target shape grid position.
Now we would do this:
Clear the dictionary
Add all grid positions of all targetshapes into the dictionary and set the value of those to 1
Iterate through all dragable shapes. For each shape you will determine two flags: overlapTarget and overlapBackground.
for each shape you iterate through all gridpositions and check the position against the dictionary. If there's no value in the dictionary or the value is 0, set overlapBackground to true for this shape. If there is a value in the dictionary and it's 1 you will set overlapTarget to true and subtract 1 from the dictionary value so it becomes 0.
Once all shapes have been checked you can simply inspect the two flags of each shape. If any shape has both flags set it's an invalud / incomplete setup. If all shapes have either only overlapTarget or overlapBackground set the puzzle is solved.
To form the dictionary key from a grid position, just do this:
ulong key = (ulong)y<<32 | (ulong)x;
This will give you a unique key for a particular grid position. If your grid has a limited size you can of course use a flattend index as well. As long as the key generation does not produce duplicates for two different grid positions and reliable produce the same key for the same grid position everything is fine.
This solution assumes that the target shapes do not overlap each other. If you want to support overlap, instead of just setting the value in the dictionary to 1 you could simply increase it by 1. So if two or more shapes should overlap a grid position the value would be 2, 3, 4, ...
The goal is that every value in the dictionary drops to 0 when everything is correct
Wow, this is some decent advice, thank you very much! There are however two questions that come to $$anonymous$$d when reading your answer.
What does "<<32" do? I've never seen a notation like that before.
You start of with "since your whole game is grid based". Would there be a better way to approach it without a grid? I've used a grid because then it would at least snap to position, otherwise it could be a hell for the player to get an object exactly on top of a target object.
The <<
operator is the bitwise left-shift operator. So the number on the left will be left shifted by the number of bits specified on the right. So "3<<4" == 48 since 3 (0000 0011) left shift by 4 is 48 (0011 0000)
The idea is to use an "ulong" (which is a 64 bit integer) and use its upper 32 bits to store the y value and the lower 32 bit to store the x value. The |
operator is the "bitwise or" operator and should not be confused with the "logical or" operator ||
X = 00000000000000000000000001010010 // value of 72
Y = 00000000000000000000000000001011 // value of 11
Y<<32 | X:
0000000000000000000000000000101100000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000001010010
----------------------------------------------------------------
0000000000000000000000000000101100000000000000000000000001010010
== "47244640338" in decimal or "0xB00000052" in hexadecimal
About your second point: No, it's the other way round ^^. Using a grid actually simplifies the problem. If the shapes wouldn't be aligned to a grid you would need to actually split each shape into primitive areas (usually triangles) and work out the overlap mathematically. This could get quite cimplicated depending on how the user can actually place the shapes. If the shapes are not snapped to a grid you would need to check for an approximate match since it would be pretty impossible for the user to align the shapes perfectly.
You don't plan to rotate the shapes, do you? A rotation of 90° would be fairly easy, any other angles would get complicated
Thanks for the explanation! I was actually planning on rotation, but maybe I should limit it to 90 degrees then.
Planning on a simple application always turns out into a headache like this ;)
Your answer
Follow this Question
Related Questions
Multiple Cars not working 1 Answer
Checking if object intersects? 1 Answer
Load specific sprites from SpriteAtlas into array 1 Answer
sunlight detection for vampire 0 Answers
How can I detect if UI elements are overlapping without colliders? 1 Answer