mods/boxes/valloc.lua

   1
   2 --[[
   3
   4   ITB (insidethebox) minetest game - Copyright (C) 2017-2018 sofar & nore
   5
   6   This library is free software; you can redistribute it and/or
   7   modify it under the terms of the GNU Lesser General Public License
   8   as published by the Free Software Foundation; either version 2.1
   9   of the License, or (at your option) any later version.
  10
  11   This library is distributed in the hope that it will be useful,
  12   but WITHOUT ANY WARRANTY; without even the implied warranty of
  13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  14   Lesser General Public License for more details.
  15
  16   You should have received a copy of the GNU Lesser General Public
  17   License along with this library; if not, write to the Free
  18   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston,
  19   MA 02111-1307 USA
  20
  21 ]]--
  22
  23 --[[
  24         Box allocation.
  25
  26         To keep things simple, we will always allocate boxes with same width and
  27         depth, and with a sizee that is a multiple of boxes_resolution. Height is
  28         assumed to be unlimited above box_alloc_miny.
  29         In order to do that, we keep a quadtree of allocatable positions; an allocated
  30         box will always be a leaf of that tree. We also keep for each subtree the max
  31         size that can be allocated in it.
  32
  33         Thus, this is https://en.wikipedia.org/wiki/Buddy_memory_allocation in 2D.
  34 ]]
  35
  36 local boxes_resolution = 256
  37 local box_alloc_miny = 50
  38 local boxes_tree = {
  39         minp = {x = 1024, z = 1024},
  40         edge_size = 8192,
  41         max_alloc_size = 8192,
  42 }
  43
  44 local function split_leaf(node)
  45         assert (node.edge_size >= 2 * boxes_resolution)
  46         assert (node.children == nil)
  47         local new_size = node.edge_size / 2
  48         local x = node.minp.x
  49         local z = node.minp.z
  50         node.children = {
  51                 {
  52                         minp = {x = x, z = z},
  53                         edge_size = new_size,
  54                         max_alloc_size = new_size,
  55                         parent = node
  56                 },
  57                 {
  58                         minp = {x = x + new_size, z = z},
  59                         edge_size = new_size,
  60                         max_alloc_size = new_size,
  61                         parent = node,
  62                 },
  63                 {
  64                         minp = {x = x, z = z + new_size},
  65                         edge_size = new_size,
  66                         max_alloc_size = new_size,
  67                         parent = node,
  68                 },
  69                 {
  70                         minp = {x = x + new_size, z = z + new_size},
  71                         edge_size = new_size,
  72                         max_alloc_size = new_size,
  73                         parent = node,
  74                 },
  75         }
  76 end
  77
  78 -- Update `max_alloc_size` for node and all its parents.
  79 -- Also, merge subtrees if possible.
  80 local function update_alloc_sizes(node)
  81         while node ~= nil do
  82                 local max_size = 0
  83                 local el = node.edge_size / 2
  84                 local can_merge = true
  85                 -- a crash here with the following error msg:
  86                 -- `bad argument #1 to 'ipairs' (table expected, got nil)`
  87                 -- means that there is an unknown node on the map
  88                 -- hence, this assert:
  89                 assert(node.children)
  90                 for _, child in ipairs(node.children) do
  91                         max_size = math.max(max_size, child.max_alloc_size)
  92                         if child.max_alloc_size < el then
  93                                 can_merge = false
  94                         end
  95                 end
  96                 if can_merge then
  97                         node.children = nil
  98                         node.max_alloc_size = node.edge_size
  99                 else
 100                         node.max_alloc_size = max_size
 101                 end
 102                 node = node.parent
 103         end
 104 end
 105
 106 -- Function to know how close to zero a node is.
 107 -- Used to keep allocations close to (0, box_alloc_miny, 0).
 108 local function zero_close(node)
 109         local x = node.minp.x
 110         local z = node.minp.z
 111         local size = node.edge_size
 112         if x < 0 then x = x + size end
 113         if z < 0 then z = z + size end
 114         return math.abs(x) + math.abs(z)
 115 end
 116
 117 -- Allocated a box of size `size` horizontally, and unbounded vertically
 118 -- Returns box minimum position. The minimum position must be given to
 119 -- boxes.vfree to free the corresponding area.
 120 function boxes.valloc(size)
 121         assert (size > 0)
 122         if boxes_tree.max_alloc_size < size then
 123                 return nil
 124         end
 125
 126         -- Find leaf with enough room, splitting it if big enough
 127         local node = boxes_tree
 128         while node.edge_size / 2 >= size and node.edge_size / 2 >= boxes_resolution do
 129                 if node.children == nil then
 130                         split_leaf(node)
 131                 end
 132
 133                 local best = nil
 134                 local best_distance = 1e10 -- infinity
 135                 for _, child in ipairs(node.children) do
 136                         if child.max_alloc_size >= size and zero_close(child) < best_distance then
 137                                 best_distance = zero_close(child)
 138                                 best = child
 139                         end
 140                 end
 141                 assert (best ~= nil)
 142                 node = best
 143         end
 144
 145         local result = {x = node.minp.x, y = box_alloc_miny, z = node.minp.z}
 146         node.max_alloc_size = 0
 147         update_alloc_sizes(node.parent)
 148         return result
 149 end
 150
 151 function boxes.vfree(minp)
 152         assert (minp.y == box_alloc_miny)
 153         assert (boxes_tree.minp.x <= minp.x)
 154         assert (minp.x < boxes_tree.minp.x + boxes_tree.edge_size)
 155         assert (boxes_tree.minp.z <= minp.z)
 156         assert (minp.z < boxes_tree.minp.z + boxes_tree.edge_size)
 157
 158         -- Find leaf containing minp
 159         local node = boxes_tree
 160         while node.children ~= nil do
 161                 local cld = nil
 162                 local el = node.edge_size / 2
 163                 for _, child in ipairs(node.children) do
 164                         if child.minp.x <= minp.x and minp.x < child.minp.x + el
 165                                         and child.minp.z <= minp.z and minp.z < child.minp.z + el then
 166                                 cld = child
 167                                 break
 168                         end
 169                 end
 170                 assert (cld ~= nil)
 171                 node = cld
 172         end
 173
 174         assert (node.max_alloc_size == 0)
 175         node.max_alloc_size = node.edge_size
 176         update_alloc_sizes(node.parent)
 177 end
 178