Search Unity

  1. Unity 2018.3 is now released.
    Dismiss Notice
  2. The Unity Pro & Visual Studio Professional Bundle gives you the tools you need to develop faster & collaborate more efficiently. Learn more.
    Dismiss Notice
  3. Want more efficiency in your development work? Sign up to receive weekly tech and creative know-how from Unity experts.
    Dismiss Notice
  4. Build games and experiences that can load instantly and without install. Explore the Project Tiny Preview today!
    Dismiss Notice
  5. Nominations have been announced for this years Unity Awards. Celebrate the wonderful projects made by your peers this year and get voting! Vote here!
    Dismiss Notice
  6. Want to provide direct feedback to the Unity team? Join the Unity Advisory Panel.
    Dismiss Notice
  7. Improve your Unity skills with a certified instructor in a private, interactive classroom. Watch the overview now.
    Dismiss Notice

Looking for an algorithm to divide a grid into sub-rectangles.

Discussion in 'Scripting' started by Kev00, Oct 14, 2018.

  1. Kev00

    Kev00

    Joined:
    Dec 6, 2016
    Posts:
    154
    Given an MxN grid that contains a number of predefined sub-rectangles (blocked areas). How would you divide the grid into a min-set of sub-rectangles that don't overlap each other. The new rectangles will represent open areas.

    Thanks
     
  2. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    5,996
    What do you mean by 'open-areas'?

    Are you asking how to scan a region, such as a walkable region for a pathing grid, where open areas are those spaces that are walkable. Implying closed regions are unwalkable?

    Do you have a algorithm/method to test "openness" of a sub-region?

    Like something like this:
    GridSubRects.png
    Where the red blocks are 'unwalkable/closed', and white are 'open/walkable'?

    And we joined nodes to be larger rectangular areas (as shown by some shade of blue/purple)?

    Note... you're going to have to define things like "min-set" and "open" and what not.

    Example, in this image above we could easily rotate the rect in the lower left, making a 2x3 rect, removing the dark blue small rect above it, and making a new 2x2 square to the right of it. And still have the same number of over-all rects.

    So... what would "min" mean? Min scanning from a left-right direction? Min from a maximum size rect first preference? Min from a small size rect first preference? From some other undefined meaning of 'min' that I could not guess at?

    ...

    Personally, instead of trying to run down some graph-theory rabbit hole.

    How I usually deal with these sorts of problems is that I draw on paper what it is I'm trying to reduce.

    Then I attempt to do it in a more human method... just filling in the regions in a manner that I think works (like I did here in the pic I posted).

    I keep doing this looking for a pattern that I keep using to attempt to fill the job. And iterate on that pattern until I have a specific rule set that I keep using... rather than a gut feeling. Like maybe I scan from upper-left to lower right just filling block by block until I hit a wall and I then walk that rect.

    Once I have this human algorithm... I just translate it to computer.

    Then once in computer form I can sometimes see optimizations in loops or what not which allow me to iterate further on the algorithm.

    I don't do this for long... just as a proof of concept. If it works, then YAY, no need to study for hours. If not I then research based on my experience gathered (such as how I noticed by simply rotating a rect I can create a unique grid with the same number of rects... thus creating a proof that 'min' is nebulous).
     
    Last edited: Oct 14, 2018
    eses likes this.
  3. Kev00

    Kev00

    Joined:
    Dec 6, 2016
    Posts:
    154
    I already know what areas are walk-able. that's the easy part. I didn't ask for a scanning algorithm.

    As for " min-set of sub-rectangles". I'm looking for the smallest number of rectangles that will fill the open areas without overlap. This means that correct solution contains rectangles that are as large as possible and fewest in number.

    With that said, there are obviously many solutions that will result in 7 rectangles ( as per your grid). I only need one of them. Your second graph is what I'm looking for.

    I've tried to develop an algorithm a few times on graph paper, but I haven't really figured it out. I was just wondering if anyone has seen something like this or has any ideas.


    Thanks.
     
  4. Kev00

    Kev00

    Joined:
    Dec 6, 2016
    Posts:
    154
    The solution I have so far is to start with a large rectangle and check for overlaps. If it doesn't overlap, flag all the squares it fills, and continue searching. When the grid search is complete, loop over the grid again with a smaller rectangle.

    The problem is how to reduce the size of the rectangle on each iteration. I suppose I could do it many different ways and then pick the solution with the smallest number of rectangles.

    I'll probably have to scan the grid many different ways on each iteration.
    Scan method 1 Reduce width only
    Scan method 2. Reduce height only.
    Scan method 3. Reduce height and width
     
    Last edited: Oct 14, 2018