0
\$\begingroup\$

I am making a game similar to Volfied using Unity:

Screenshot of Volfied

The player outlines an area using straight lines, either horizontal or vertical.

I am stuck at the algorithm to decompose the area into rectangles so that I can :

  • count for the percentage of area claimed by multiplying the width and height of the rectangles then summing the result.
  • Add "Sprite mask" component to the generated rectangles for masking effect.
  • I am currently not dividing my game into grids/cells so probably flood filling algorithm may not be the best option.

I am not sure if this is the easiest way to do it or not but what algorithm I could apply to this situation?

Thank you.

\$\endgroup\$
7
  • \$\begingroup\$ Do you have a way of differing whether the tile is taken or not? \$\endgroup\$
    – koogel
    Jun 16, 2023 at 21:08
  • \$\begingroup\$ Do you absolutely need rectangles or would calculating the area covered (without decomposing it into rectangles) be sufficient? \$\endgroup\$
    – Pikalek
    Jun 16, 2023 at 23:02
  • \$\begingroup\$ @koogel I am not using grid based system so I am just using lines to check whether the area is taken or not. \$\endgroup\$
    – nicklowkc
    Jun 17, 2023 at 0:04
  • \$\begingroup\$ @Pikalek not sure about that but that's what came to my mind. Or probably use polygon instead? \$\endgroup\$
    – nicklowkc
    Jun 17, 2023 at 0:06
  • 1
    \$\begingroup\$ Does this answer your question? How to calculate area to fill in this Snake/Qix game variant? \$\endgroup\$
    – Pikalek
    Jun 18, 2023 at 18:19

2 Answers 2

1
\$\begingroup\$

As long as your polygon has no holes, and you have a list of the corners of the shape in order as you walk clockwise around the perimeter, you can calculate the area directly using the shoelace formula, like so:

float area = 0;

// Start with the edge joining the last corner back to the first corner.
Vector2 start = corners[corners.Count - 1];

// Visit the edge ending at each corner in the list.
foreach (Vector2 end in corners) {
    // Accumulate the area attributable to this edge.
    area += start.x * end.y - start.y * end.x;

    // Advance our edge start point for the next edge.
    start = end;
}

// The above calculates double the area, so we halve it to get the true area.
area /= 2;

How this works is that for each edge of the polygon, you're computing the signed area of the triangle formed by that edge and a point at the origin - positive for triangles wound clockwise, negative for triangles wound counter-clockwise. (Technically you're getting the signed area of the parallelogram formed from two copies of that triangle, but we divide by two at the end to get rid of that).

The counter-clockwise triangles subtract out the excess area covered by the positive triangles, leaving you with the complete area of the polygon.

This keeps the workload proportional to the number of edges in the polygon, not its area, and does not require discretizing the problem to a grid.

This also works if your edges are diagonal, and even if the polygon is self-intersecting (though you will count the overlapped area twice).

If you find you're getting negative areas, you've wound your corners list counter-clockwise, and you can multiply by -1 or take the absolute value to get back to a positive area.

\$\endgroup\$
6
  • \$\begingroup\$ hi, thank you for your help. The reason I am trying to split the shape into rectangles is because I want to use sprite mask to mask the hidden image and I am not familiar with shaders. Thus splitting it into rectangles make it seems easier for me to bot only masking but also counting the areas. The shoelace formula seems approachable too in my case but only for counting areas, I think. \$\endgroup\$
    – nicklowkc
    Jun 19, 2023 at 23:10
  • 1
    \$\begingroup\$ That sprite masking requirement should have been stated in your question, then - make sure you edit it in now so there are no more surprise requirements to throw off other users trying to answer. Myself, though, I'd do this with a single polygon mesh rather than a collection of rectangular masks. If you're not familiar with shaders, just ask, rather than making the job harder for yourself by trying to work without them. \$\endgroup\$
    – DMGregory
    Jun 20, 2023 at 0:35
  • \$\begingroup\$ hi DMGregory, sorry for my not thorough description of my question. I have edited my question again, hopefully it makes sense now. Before that, I have found one topic related and one of the commentator recommended polygon method. But since I don't have that much experience to generate a mesh in unity so i just thought of using rectangles. gamedev.stackexchange.com/questions/125471/… \$\endgroup\$
    – nicklowkc
    Jun 20, 2023 at 2:22
  • \$\begingroup\$ The code I linked above literally generates meshes in Unity, given an ordered loop of vertices, so you don't really need experience of your own - you can build on what's been published. \$\endgroup\$
    – DMGregory
    Jun 20, 2023 at 2:54
  • \$\begingroup\$ Hi dmgregory, sorry for late reply. Okay, let's say if I am using polygon mesh instead, how could I delete the points inside the polygon when I claimed an area? I tried to use polygon collider in unity and provide points of the lines. But the points on the lines are being included hence it deleted my lines. \$\endgroup\$
    – nicklowkc
    Jun 23, 2023 at 10:58
0
\$\begingroup\$

Since all you need is the area and this is a calculation that runs infrequently (i.e. it's not running every frame), here's how I would approach the problem:

First I would create a bitmap representing the play area. This could be a bitmap in the image sense (i.e. data structure that backs a .BMP or other image type) it doesn't need to be. A 2D array of Boolean would also work. The idea here is that you want a rasterized representation for the area of interest.

When lines are made in the play area also make them on the bitmap. Ideally, your bitmap should be the same dimensions as your play area. If the bitmap is not a one-to-one representation of the player area, scale and round the coordinates accordingly. For example, let's say your bitmap is 1000x900 but your actual game area is 800x700. Then some point x,y in the game area would be represented by location (1000x/800),(900y/700). Obviously scaling & rounding can introduce a degree of error. For that reason I would initially start with a one-to-one representation & only consider alternatives if there are performance problems that can be traced back to that decision via profiling.

Whenever a section is completed, use a flood fill algorithm on the bitmap to flag that area as complete.

Finally, calculate the area that has been flagged. If you're making a custom flood fill, this step could be part of the previous step (by keeping a running tally of the pixels/cells changed by the flood fill). If not, you can also brute force it by iterating over the entire bitmap and compare the flag count to the previously recorded count. While not the most efficient, it's easy to code, less prone to error and unlikely to noticeably affect performance.

The key aspect of this solution is that you're abstracting your problem (how to keep track of area) from your player facing game aspects (whether or not the player sees a grid, where things are on the physical screen, etc).

Note: while a logical bitmap is probably a more memory efficient way to solve the problem as stated, there are a couple of reasons why an image based data structure might be better:

  • If there's already a flood fill available in your image API, that's one less thing to write & debug.
  • You might also have an in-game use for the image; for example it could be used as a mini-map if your play area spans more than one screen's worth of space.

If you prefer to calculate the area directly as a series of rectangles, it's an example of a dissection problem (see also). Most of the solutions I've seen are interested in various constraints (for example solutions with the minimum number of rectangles for an area), though there may be simpler solutions that aren't concerned with those complications. There appears to be a good explanation on Stack Overflow along with links to related problems.

\$\endgroup\$
2
  • \$\begingroup\$ Hi @Pikalek, thanks again for your through answer. I am sorry that I didn't mention in my original post that I am not dividing my game into grids/cells so probably flood-fill algorithm may not be the best option. I have updated my post again. Though, I am pretty interested in the dissection problem that you introduced! Thank you! \$\endgroup\$
    – nicklowkc
    Jun 20, 2023 at 2:26
  • \$\begingroup\$ @nicklowkc The solution I've proposed works for finding the area based on the coordinates of the lines. It doesn't require you to have a grid or cells in the game, it uses a matrix internally to represent the problem & performs calculations based on its own internal representation to solve the problem. \$\endgroup\$
    – Pikalek
    Jun 20, 2023 at 4:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .