• notice
  • Congratulations on the launch of the Sought Tech site

Algorithm to fill arbitrary marked/selected tiles on a square grid with the fewest rectangles?

I'm asking an algorithmic question here.I'm not asking about the specifics of how to do this with the programming language I'm using or the frameworks and libraries I'm currently using.I would like to know how to do this in principle.

As a hobby, I'm working on an open source virtual reality remake of the 1992 first-person shooter Wolfenstein 3D.My program will support WOLF3D's classic mods and map packs in their original 90s format.This means my program doesn't know ahead of time what the map will be.They are loaded at runtime from a user-provided archive.

A Wolfenstein 3D map is a 2D square grid of usually 64x64 tiles.Suppose I have a 2D boolean array that returns true if the player can traverse a particular tile; if whatever happens in the game, that tile will Never traversable, return false.

I want to generate rectangular collision objects for modern game engines to prevent collisions with impenetrables on the map ceramic tile.Right now, I have a small collision object on each surface of each wall tile with a movable tile next to it, which is very low Effective because it generates more collision objects than needed.Instead I should have a smaller number of large rectangles that fill all the squares on the grid, where the 2D array I mentioned has the wrong value to indicate Not traversable.

When I searched for any algorithm or research that might be done for a similar problem, I found a lot about Info on rectangle packing, used to make texture atlases for games, packing rectangles into squares, but I haven't found anything that tries to pack a minimal number of rectangles into any set of selected/marked square tiles.

The naive approach I thought of would be to first make 64 rectangles representing 64 rows, then cut out any possible Traversed square. but I suspect there must be an algorithm that does a better job, meaning it fills the same space with a smaller number of rectangles. Maybe start with my naive approach and check each rectangle for adjacent rectangles that can be merged? but I'm not sure how far I can go with this approach, or if it actually reduces the number of rectangles.

The result is not necessarily perfect.I'm just fishing here to see if anyone has any magic that can take me beyond the naive approach.

Has anyone done this? What is this called? Just knowing some words I even need to talk about is helpful.Thanks!

(edit later)

Here are some example inputs with comma-separated values.1 indicates areas that must be filled with rectangles, while 0 indicates areas that should not be filled with rectangles.

I expect the result will be a list of sets containing 4 integers, where each set represents a rectangle, as follows:

  1. The first integer is the x-coordinate of the left/west edge of the rectangle.
  2. The second integer will be the y-coordinate of the top/north edge of the rectangle.
  3. The third integer is the width of the rectangle.
  4. The fourth integer is the depth of the rectangle.

My programs are written in C#, but I'm sure I can use normal mainstream general-purpose programming languages or pseudocode to translate anything.

uj5u.com enthusiastic netizens replied:

Mark all tiles as not visited
For each tile:
    skip if the tile is not a top-left corner or was visited before
    # now, the tile is a top-left corner
    expand right until top-right corner is found
    expand down
    save the rectangle
    mark all tiles in the rectangle as visited

No matter how simple it may seem, it will probably generate the least amount of rectangles-simply because We need at least one rectangle per pair of top corners.

For faster downward scaling, precompute a table that contains all elements top and left The sum of (also known as integral image ).

For non-overlapping rectangles, nxn"image"worst Case complexityshould not exceed O(n^3).If rectangles can overlap (will cause their number to decrease) , the integral image optimization is not applicable, the worst case is O(n^4).


Technical otaku

Sought technology together

Related Topic


Leave a Reply