2

What I am asking here is an algorithm question. I'm not asking for specifics of how to do it in the programming language I'm working in or with the framework and libraries I'm currently using. I want to know how to do this in principle.

As a hobby, I am working on an open source virtual reality remake of the 1992 first-person shooter game Wolfenstein 3D. My program will support classic mods and map packs for WOLF3D made in the original format from the 90s. This means that my program will not know in advance what the maps are going to be. They are loaded in at runtime from user provided files.

A Wolfenstein 3D map is a 2D square grid of normally 64x64 tiles. let's assume I have a 2D array of bools which return true if a particular tile can be traversed by the player and false if the tile will never be traversable no matter what happens in the game.

I want to generate rectangular collision objects for a modern game engine which will prevent collisions into non traversable tiles on the map. Right now, I have a small collision object on each surface of each wall tile with a traversible tile next to it and that is very inefficient because it makes way more collision objects than necessary. What I should have instead is a smaller number of large rectangles which fill all of the squares on the grid where that 2D array I mentioned has a false value to indicate non-traversible.

When I search for any algorithms or research that might have been done for problems similar to this, I find lots of information about rectangle packing for the purposes of making texture atlases for games, which packs rectangles into a square, but I haven't found anything that tries to pack the smallest number of rectangles into an arbitrary set of selected / marked square tiles.

The naive approach which occurs to me is to first make 64 rectangles representing 64 rows and then chop out whatever squares are traversible. but I suspect that there's got to be an algorithm which can do better, meaning that it can fill the same spaces with a smaller number of rectangles. Maybe something that starts with my naive approach and then checks each rectangle for adjacent rectangles which it could merge with? But I'm not sure how far to take that approach or if it will even truly reduce the number of rectangles.

The result doesn't have to be perfect. I am just fishing here to see if anyone has any magic tricks that could take me even a little bit beyond the naive approach.

Has anyone done this before? What is it called? Just knowing what some of the vocabulary words I would need to even talk about this are would help. Thanks!

(later edit)

Here is some sample input as comma-separated values. The 1s represent the area that must be filled with the rectangles while the 0s represent the area that should not be filled with the rectangles.

I expect that the result would be a list of sets of 4 integers where each set represents a rectangle like this:

  1. First integer would be the x coordinate of the left/western edge of the rectangle.
  2. Second integer would be the y coordinate of the top/northern edge of the rectangle.
  3. Third integer would be the width of the rectangle.
  4. Fourth integer would be the depth of the rectangle.

My program is in C# but I'm sure I can translate anything in a normal mainstream general purpose programming language or psuedocode.

Improve this question
7
  • 1
    cool problem. Can you give an example input/output? Commented Jan 11, 2022 at 23:06
  • I will try to get some sample input posted soon. It'll just be 1s and 0s based on the Wolfenstein 3D shareware levels. Commented Jan 12, 2022 at 1:26
  • @Marat Here is the sample input: gist.github.com/BenMcLean/3455b91854fe01162256cef07467d337 Commented Jan 12, 2022 at 3:19
  • I have edited the question to explain an output format. Commented Jan 12, 2022 at 3:27
  • If the rectangles can overlap, then for each single row rectangle (x0,r)-(x1,r), you can scan up and down and merge it with any row rectangle (x0,q)-(x1,q) with the same x0-x1, provided that all rows between r and q are filled with 1 in the range x0-x1, the process is O(n^2) in the number of tiles, so for a such small number will be fast enough. Commented Jan 12, 2022 at 14:01

1 Answer 1

Reset to default
2 
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

However simplistic it looks, it will likely generate minimal number of rectangles - simply because we need at least one rectangle per pair of top corners.

For faster downward expansion, it makes sense to precompute a table holding sum of all element top and left from the tile (aka integral image).

For non-overlapping rectangles, worst case complexity for an n x n "image" should not exceed O(n^3). If rectangles can overlap (would result in smaller number of them), integral image optimization is not applicable and the worst case will be O(n^4).

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

How to detect a "top left corner"? I assume that means it needs to check each tile to see if (it is a 1 AND that the tile above it is either 0 or off the map) and (that the tile to the left is either 0 or off the map). If that comes out true then the tile is a top left corner. Is that right?
@BenMcLean basically, yes. But in addition to 0 and off-boundaries, it could be a visited 1
I suppose I should add a step to mark all of the "0" tiles as visited at the start

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.