sheep/pack/
simple.rs

1use std::cmp::{min, Ordering};
2use {Packer, PackerResult, SpriteAnchor, SpriteData};
3
4pub struct SimplePacker;
5
6impl Packer for SimplePacker {
7    type Options = ();
8
9    fn pack(sprites: &[SpriteData], _options: ()) -> Vec<PackerResult> {
10        let mut sprites = sprites.iter().cloned().collect::<Vec<SpriteData>>();
11
12        let mut free = Vec::new();
13        let mut absolute = Vec::new();
14
15        sprites.sort_by(compare_area);
16        sprites.reverse();
17        free.push((0, 0));
18
19        for sprite in sprites.iter() {
20            // Push the sprite to the next free anchor
21            let next_free = *free.first().expect("No free anchor");
22            absolute.push(SpriteAnchor::new(sprite.id, next_free, sprite.dimensions));
23
24            // find new anchors
25            let mut new_right = (next_free.0 + sprite.dimensions.0, next_free.1);
26            let mut new_bottom = (next_free.0, next_free.1 + sprite.dimensions.1);
27
28            // still finding new anchors
29            for i in 1..(free.len() - 1) {
30                // If we removed an anchor after the first round,
31                // we might be out of bounds at this point
32                if i > 1 && i >= free.len() {
33                    break;
34                }
35
36                if free[i].0 >= free[0].0 && free[i].0 <= new_right.0 {
37                    new_right.1 = min(new_right.1, free[i].1);
38                    free.remove(i);
39                    continue;
40                }
41
42                if free[i].1 >= free[0].1 && free[i].1 <= new_bottom.1 {
43                    new_bottom.0 = min(new_bottom.0, free[i].0);
44                    free.remove(i);
45                    continue;
46                }
47            }
48
49            // remove first, push new anchors
50            free.remove(0);
51
52            if !free.contains(&new_right) {
53                free.push(new_right);
54            }
55
56            if !free.contains(&new_bottom) {
57                free.push(new_bottom);
58            }
59
60            free.sort_by(compare_pos);
61        }
62
63        let width = free
64            .iter()
65            .max_by(|a, b| a.0.cmp(&b.0))
66            .expect("Invalid: No free anchors")
67            .0;
68
69        let height = free
70            .iter()
71            .max_by(|a, b| a.1.cmp(&b.1))
72            .expect("Invalid: No free anchors")
73            .1;
74
75        // Finally sort the anchors so that they are in the same order as the
76        // input sprites
77        absolute.sort_by_key(|s| s.id);
78
79        let result = PackerResult {
80            dimensions: (width, height),
81            anchors: absolute,
82        };
83
84        vec![result]
85    }
86}
87
88fn compare_area(a: &SpriteData, b: &SpriteData) -> Ordering {
89    (a.dimensions.0 * a.dimensions.1).cmp(&(b.dimensions.0 * b.dimensions.1))
90}
91
92fn compare_pos(a: &(u32, u32), b: &(u32, u32)) -> Ordering {
93    // NOTE(happenslol): We might overflow here quickly if the output
94    // sprite becomes too big, so we use u64s. This is why this algorithm
95    // doesn't scale very well...
96    let a = (a.0 as u64, a.1 as u64);
97    let b = (b.0 as u64, b.1 as u64);
98
99    (a.0.pow(4) + a.1.pow(4)).cmp(&(b.0.pow(4) + b.1.pow(4)))
100}
101
102#[cfg(test)]
103mod tests {
104    use super::*;
105
106    #[test]
107    fn pack_square() {
108        let sprites = (0..16)
109            .map(|i| SpriteData::new(i, (20, 20)))
110            .collect::<Vec<SpriteData>>();
111
112        let result = SimplePacker::pack(&sprites, ());
113
114        assert_eq!(result[0].dimensions.0, 20 * 4);
115        assert_eq!(result[0].dimensions.1, 20 * 4);
116    }
117}
sheep/pack/simple.rs

sheep/pack/
simple.rs
