CODEWITHSUNDEEP
pythonalgorithmpython-2.7recursiontiling
L.B
L.B

Reputation: 139

Tiling, how to use recursion in this case?

I am trying to make an algorithm that's able to solve a big tileset in the tiling problem. Right now it's able to find the correct Tiles to place based on their width and height, but there are some problems with making it properly recursive.

As you can see the idea is that after each tile that's placed the field will be separated in a Field Right and a Field Below. The algorithm will first try to fill the Field Right and as soon as that's done it has to start trying to fill Field Below.

The problem I have is that once Field Right is solved it has to be "send back" in a way (I think using recursion, though this is quite complex) to get it to go back a Tile and go to the Field Below that belongs to that Tile. I put the idea in some pseudocode to make it a bit easier to follow.

As you can see when FieldRightWidth is solved and the FieldBelowHeight is also solved I want to make it return to the previous tile to check if FieldBelow is solved. I think that's where I need to put some code to make this work, but after hours of Googling I still have no clue.

Pseudocode:

def Methods:
   create global tileset
   create local tileset (without duplicates)

   If globaltiles is empty: 
      solved    
      end
   else:
           if fieldRightWidth == solved:                  
               if fieldBelowHeight == solved:
                   return True???
               #FIELD BELOW
               else:
                    Search for Tile
                    Place Tile
                    Return Methods

           #FIELD RIGHT       
           else:
                Search for Tile
                Place Tile
                Return Methods

And a picture of what I want the algorithm to do: enter image description here

And all of the code: http://pastebin.com/8t4PeiZP

http://www.filedropper.com/tilingnew

I'm still a newbie in coding, so any advice or help is very appreciated!

Upvotes: 4

Views: 1414

Answers (1)

Bear
Bear

Reputation: 572

alright, let's think the area you want to calculate are either square or rectangular,(not rotated), it start from minimum [x,y] and end maximum [x,y] right, like so:

SMaxX = 5
SMinX = 0
SMaxY = 5
SMinY = 0

or if you are familiar with 2D vector you can optimize it like so:

S = [5,5]

you might know about 2D vector, just in case i explain what is vector in 2D cartesian coordinate:
enter image description here S = [5,5] means, if S start from [0,0], it will end at [5,5], (simpler right?)
so boxes also will be like so:

#space each box taking
box1 = [3,3]
box2 = [2,2]
box3 = [1,1]

and since there is priority for each box, let's say:

#priority of each box
box1 = 6
box2 = 4
box3 = 2

we can merge both space and priority into dictionary like so:

#Items
dic = {'box1':{'space':[3,3] , 'priority ':6},
       'box2':{'space':[2,2] , 'priority ':4},
       'box3':{'space':[1,1] , 'priority ':2}}

having priority and spaces of each boxes, looks like Knapsack problem algorithm.
if you are familiar about Knapsack problem algorithm, in a table we are trying to find the highest priority that fill the space perfectly, or in other word best possible way of fitting boxes. check this link1 and link2.

however Knapsack problem algorithm's chart is 1D solution, which if you do it, you will get 10, so Box1 and Box2. but since it's 2D and you have different height and width, so the standard 1D formula wont work, maybe you need to look into it see if you can come up with 2D formula or ask around see if someone done that before.

enter image description here enter image description here

other than Knapsack problem algorithm you can try Flood fill algorithm which is a bit slower if you have huge area, but it work just like how Tetris game is.

you need to set standard size like 1x1, and then define the whole area with 1x1 data, and store it in a variable and set each True (Boolean), then with higher priority of boxes fill the area and set those 1x1 date to False, then really easy you can check if how many of the them are True and what area are they taking.

anyway, i'm trying to figure out the same thing in irregular shape, so that was all i found out, hope that help you.
(check this link as well, i got some useful answers.)

Edit: okay, if you use Tetris idea with defining the area and Knapsack problem algorithm in one axis and then base on standard Tetris area, use Knapsack problem algorithm again in other axis should work perfectly.

Upvotes: 2

Related Questions