0
\$\begingroup\$

I already have a working algorithm for this but it's home-made and there is some redundancy in the things it checks, so I'm looking for a fast algorithm (or the name of it) that would detect undrawn portions of a 2d map (a picture or a grid), returning those portions as a list of Rectangles which borders are parallel to the axis (x, y, width, height). The map is not very big, like 200x200.

Edit: Rectangles to detect have to be parallel to the axis x and y

For instance ran on this map and looking for space character " " and for 2x3 rectangles :

*C***DDD****
*01F  *E*  *
***   ***  *
**    *    *
*A****  ****
************

It would detect the portions marked with "X":

*C***DDD****
*01FXX*E*XX*
*** XX***XX*
**  XX*  XX*
*A****  ****
************

Has anyone heard of one algorithm like this, but fast? Right now what I'm doing is that I'm scanning through each cell and checking if the w*h Rect at current position is filled with the search value. However you can see there is a lot of redundancy there.

I wonder if some bitmap compression algorithm like PNG don't use that kind of detection, so as to compress repetitions of tiles/uniform areas. If that's the case that should be very fast algorithm they use because speed is an issue for them.

The detection doesn't have to be exact (it's ok if some areas are not detected, but most need to be). So mostly it needs to be very fast.

\$\endgroup\$
9
  • \$\begingroup\$ By "undrawn" you mean any parts outside view frustum, right? \$\endgroup\$
    – wondra
    Commented Sep 16, 2014 at 10:19
  • \$\begingroup\$ If you want something really fast, I came across these slides for frustum culling in battlefield 3. (there is also a thread on gamedev.net where it is mentioned) \$\endgroup\$
    – wondra
    Commented Sep 16, 2014 at 10:34
  • \$\begingroup\$ wondra: The grid is a collection of Int, by undrawn squares I mean a square having any arbitrary value, for instance 0. \$\endgroup\$
    – the_yellow_logo
    Commented Sep 16, 2014 at 13:29
  • \$\begingroup\$ GameAlchemist: that is true, however if you draw corridors in there it becomes significantly more expansive to structurally manage the undrawn portions (otherwise I could just use bounding boxes). \$\endgroup\$
    – the_yellow_logo
    Commented Sep 16, 2014 at 13:31
  • \$\begingroup\$ @Avt'W - could you please outline the intended usage of this set and your current method of storing your map. As it stands your question seems to be asking about culling processes in general which would make this too broad (covering, among other topics, backface culling, frustum culling and Spatial partitioning trees/mechanisms) \$\endgroup\$
    – OriginalDaemon
    Commented Sep 16, 2014 at 16:23

2 Answers 2

Reset to default
1
\$\begingroup\$

This algorithm will identify the lower right corner of every a by b block of non-blocked tiles.

We iterate over the rows of the grid from top to bottom, keeping an array as wide as the grid of integers as state. Initially this array is all zeros. Within a row, we proceed from left to right. Initially, a counter is zero at the beginning of every row. We look at the cells of the grid in order. If a cell is blocked, then we reset the count to zero. If it is unblocked, we increment the count. Thus after we have done this test the counter tells us how many open spaces (including the current one) it is until the next blocked cell.

After we have reset or incremented the counter, we compare it to the width a. If it is greater or equal, then we increment the counter for that cell in the array. Otherwise, we set that counter to zero. Essentially, if there is enough space in the current row at a given column to hold one row of our a by b rectangle to the column's left, then the array counter for that column is incremented. Thus, if the array counter at a particular place is at least b (the height of the sought rectangle), then there are b-many a by 1 rectangles above and including the current row, with their right edges in the current column. Therefore, after incrementing/resetting the array counter, if it is at least b then we have found the lower right corner of an a by b rectangle.

This algorithm has complexity O(m*n), where m and n are the width and height of the grid. This is as efficient as possible, because any algorithm solving this problem must read every cell of input in the general case. In addition, this algorithm has a fast inner loop, and very cache friendly.

\$\endgroup\$
0
\$\begingroup\$

EDIT: Ok apparently this is totally different question now so here's my factored answer (v3) ...

Marching Squares

http://www.emanueleferonato.com/2013/03/01/using-marching-squares-algorithm-to-trace-the-contour-of-an-image/

Taking this approach will allow you to crawl your map and determine areas on the outside of / inside of something.

This assumes you can easily represent your map as an image and then "march" the pixels.

\$\endgroup\$
7
  • \$\begingroup\$ That would be ideal for a continuous (3d, or cell-less) space, however in that case it's simply a 2d grid (and a small one, of say 200x200). In that case I expect some faster results could be obtained through cleverly iterating the grid. I suspect some non-degrading image compression algorithms use similar methods to the one I'm looking for, unfortunately I'm not well-versed in the nomenclature so I don't really know where to start. \$\endgroup\$
    – the_yellow_logo
    Commented Sep 16, 2014 at 13:39
  • \$\begingroup\$ I apply this to specified "limited" volumes all the time. Don't get why it can't solve your problem here too ... weather you use chunking or not you have the same problem "what do I process / draw" ... in my case this was determined by distance from the camera in your case the criteria may be different but the theory should still be relevant. \$\endgroup\$
    – War
    Commented Sep 16, 2014 at 14:20
  • \$\begingroup\$ Suppose you want to generate a level, finding undrawn rectangles in the map. Then your camera variable would have to be moved through each square. It would work yes, but my current implementation also works. I'm looking for an optimized algorithm, without all the arithmetics involved in the distance (even after getting rid of the root square in distance by squaring it, there still is a number of operations). So ideally we're looking for an optimized algorithm for grids, without too much redundancy. (this is a level generator located on a server, so performance dictates how well it scales). \$\endgroup\$
    – the_yellow_logo
    Commented Sep 17, 2014 at 9:34
  • \$\begingroup\$ Running on server? then your logic could be flawed ... the drawn tiles depends on the players camera, is the server tracking all client cameras? there's an issue ... the server should not be worried about where cameras are ... chunking still solves this problem IMO ... even if you apply a bool property to each chunk to save on the per frame math the same logic would still apply its just that rather than asking a map for chunks in a specific location you ask for chunks with a flag set or not set ... i'll add this to my answer. \$\endgroup\$
    – War
    Commented Sep 17, 2014 at 9:57
  • \$\begingroup\$ Camera are of no concern at this point, it's just about creating walls, corridors and features. There are no players, no camera, the matter is just having a fast rectangle detection algorithm because all the rest rely on it, so it will probably become the bottleneck. (Chunks is an approach I was considering btw, but I think for a grid the granularity it induces it would miss a lot of rectangles, and fixing that would require having several layers of chunks or dubious things like that. In a vast, continuous 3d space with float coords I would definitely take your approach). \$\endgroup\$
    – the_yellow_logo
    Commented Sep 17, 2014 at 11:59

You must log in to answer this question.

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