1
# Packing Algorithm based on https://github.com/jakesgordon/bin-packing/blob/master/js/packer.growing.js
2
# converted to python
3
# By (Jake Gordon)[https://github.com/jakesgordon]
4
class GrowingPacker:
5
    def __init__(self):
6
        self.root = None
7

8
    def fit(self, blocks):
9
        num_blocks = len(blocks)
10
        w = blocks[0].get("w", 0) if num_blocks > 0 else 0
11
        h = blocks[0].get("h", 0) if num_blocks > 0 else 0
12
        self.root = { "x":0, "y":0, "w":w, "h":h }
13
        for block in blocks:
14
            node = self.find_node(self.root, block.get("w", 0), block.get("h", 0))
15
            if node:
16
                block["fit"] = self.split_node(node, block.get("w", 0), block.get("h", 0))
17
            else:
18
                block["fit"] = self.grow_node(block.get("w", 0), block.get("h", 0))
19
    
20
    def find_node(self, root, w, h):
21
        if root.get("used"):
22
            return self.find_node(root.get("right"), w, h) or self.find_node(root.get("down"), w, h)
23
        elif w <= root.get("w", 0) and h <= root.get("h", 0):
24
            return root
25
        else:
26
            return None
27
    
28
    def split_node(self, node, w, h):
29
        node["used"] = True
30
        node['down'] = { "x": node.get("x"), "y": node.get("y") + h, "w": node.get("w"), "h":node.get("h") - h }
31
        node['right'] = { "x": node.get("x") + w, "y": node.get("y"), "w": node.get("w") - w, "h": h }
32
        return node
33
    
34
    def grow_node(self, w, h):
35
        canGrowDown = (w <= self.root.get("w"))
36
        canGrowRight = (h <= self.root.get("h"))
37

38
        shouldGrowRight = canGrowRight and (self.root.get("h") >= (self.root.get("w") + w))
39
        shouldGrowDown = canGrowDown and (self.root.get("w") >= (self.root.get("h") + h))
40

41
        if shouldGrowRight:
42
            return self.grow_right(w, h)
43
        elif shouldGrowDown:
44
            return self.grow_down(w, h)
45
        elif canGrowRight:
46
            return self.grow_right(w, h)
47
        elif canGrowDown:
48
            return self.grow_down(w, h)
49
        else:
50
            return None
51
    
52
    def grow_right(self, w, h):
53
        self.root = {
54
            "used": True, 
55
            "x":0, 
56
            "y":0, 
57
            "w":self.root.get("w")+w,
58
            "h":self.root.get("h"),
59
            "down":self.root,
60
            "right": { "x": self.root.get("w"), "y":0, "w":w, "h":self.root.get("h") }
61
        }
62
        node = self.find_node(self.root, w, h)
63
        if node:
64
            return self.split_node(node, w, h)
65
        else:
66
            return None
67

68
    def grow_down(self, w, h):
69
        self.root = {
70
            "used": True, 
71
            "x":0, 
72
            "y":0, 
73
            "w":self.root.get("w"),
74
            "h":self.root.get("h") + h,
75
            "down": { "x": 0, "y": self.root.get("h"), "w": self.root.get("w"), "h": h },
76
            "right": self.root
77
        }
78
        node = self.find_node(self.root, w, h)
79
        if node:
80
            return self.split_node(node, w, h)
81
        else:
82
            return None
83

84

85
# This algorithm does not change the order of the sprites (so no "scrambling" of sprites)
86
# but at the cost of being *slightly* less space-efficient (so you get a slightly bigger spritesheet)
87
class OrderedPacker:
88
    def __init__(self):
89
        self.blocks = None
90
        self.root = None # not actually a root but named so for consistency
91

92
    def fit(self, blocks):
93
        self.blocks = blocks
94
        
95
        blocks_per_row = int(self._get_blocks_per_row_estimate())
96
        blocks_matrix = []
97
        for i in range(len(self.blocks)//blocks_per_row + 1):
98
            blocks_matrix.append( self.blocks[i*blocks_per_row:(i+1)*blocks_per_row] )
99
        
100
        if blocks_matrix[-1] == []:
101
            blocks_matrix = blocks_matrix[:-1]
102
        
103
        final_w = self._get_final_width(blocks_matrix)
104
        final_h = self._get_final_height(blocks_matrix)
105

106
        self.root = {
107
            'w': final_w,
108
            'h': final_h
109
        }
110

111
        curr_x = 0
112
        curr_y = 0
113
        max_heights = [ max([b["h"] for b in row]) for row in blocks_matrix ]
114

115
        for i, row in enumerate(blocks_matrix):
116
            for bl in row:
117
                bl["fit"] = {
118
                    'x': curr_x,
119
                    'y': curr_y
120
                }
121
                curr_x += bl["w"]
122
            curr_y += max_heights[i]
123
            curr_x = 0
124

125

126
    def _get_blocks_per_row_estimate(self):
127
        tot_area = sum([ x["w"]*x["h"] for x in self.blocks ])
128
        estimated_sidelen = tot_area**0.5
129
        avg_width = self._get_total_width()/len(self.blocks)
130
        return estimated_sidelen // avg_width
131

132
    def _get_total_width(self):
133
        return sum([ x["w"] for x in self.blocks ])
134
    
135
    def _get_final_width(self, rows):
136
        # maximum value of total width among all the rows
137
        row_sums = [ sum([b["w"] for b in row]) for row in rows ]
138
        return max(row_sums)
139
    
140
    def _get_final_height(self, rows):
141
        # sum of the maximum heights of each row
142
        max_heights = [ max([b["h"] for b in row]) for row in rows ]
143
        return sum(max_heights)
144