diff options
Diffstat (limited to 'allocation.lua')
| -rw-r--r-- | allocation.lua | 474 |
1 files changed, 474 insertions, 0 deletions
diff --git a/allocation.lua b/allocation.lua new file mode 100644 index 0000000..6f34059 --- /dev/null +++ b/allocation.lua @@ -0,0 +1,474 @@ +-- allocation.lua - Maintains the grid node allocation table +--[[ +In contrast to classical mapgens, cellworld does not rely on perlin noise and "reproducable randomness". +Because structures can have varying size, and it is not specified which direction is explored first, +we cannot safely reconstruct the existing structures easily only from noise. + +Gridmine instead stores an "allocation map" along with the map, which stores which structures have been placed where. +Generated structures are selected during generation on a "what fits" basis. + +Binary file format: + +1byte version +2byte number of structureID entries +[ +2byte structure id +string structure name +\n +] +[ +6byte cellPosition +4byte indirection entry or structure entry +] +EOF + +Position: +<gnx 2byte><gny 2byte><gnz 2byte> + +Indirection entry: +I<xoff 1byte><yoff 1byte><zoff 1byte> +This node is part of a structure whose origin is at x-xoff .. z-zoff + +Structure entry: +S<rotation char><structureId 2bytes> + +All entries have a length of 4 bytes. + +]]-- + +local function int_to_bytes(i, clip) + local x = i + if clip then + x=i+32768--clip to positive integers + end + local cH = math.floor(x / 256) % 256; + local cL = math.floor(x ) % 256; + return(string.char(cH, cL)); +end +local function bytes_to_int(bytes, clip) + local t={string.byte(bytes,1,-1)} + local n = + t[1] * 256 + + t[2] + if clip then + return n-32768 + else + return n + end +end + +-- quick unit test +assert(bytes_to_int(int_to_bytes(42))==42) +assert(bytes_to_int(int_to_bytes(-42))~=-42)-- this must not work! +assert(bytes_to_int(int_to_bytes(42,true),true)==42) +assert(bytes_to_int(int_to_bytes(-42,true),true)==-42) + +--local variables for performance +local gma_structids={} +local gma_entries={} + +local function gmaget(x,y,z) + local ny=gma_entries[y] + if ny then + local nx=ny[x] + if nx then + return nx[z] + end + end + return nil +end +cellworld.alloc_get_cid = gmaget + +local function gmaset(x,y,z,v) + if not gma_entries[y] then + gma_entries[y]={} + end + if not gma_entries[y][x] then + gma_entries[y][x]={} + end + gma_entries[y][x][z]=v +end + +local function format_cid(x,y,z,cid) + if not cid then + return "<nil>" + end + + local indirection = string.sub(cid, 1, 1) + if indirection == "I" then + local ox,oy,oz = string.byte(cid, 2, 4) + + local icid = gmaget(x-ox, y-oy, z-oz) + return "I "..ox.." "..oy.." "..oz.." -> "..x-ox.." "..y-oy.." "..z-oz.." "..format_cid(x-ox, y-oy, z-oz, icid) + elseif indirection == "S" then + local rotation = string.sub(cid, 2, 2) + local stid_char = string.sub(cid, 3, 4) + local stid = bytes_to_int(stid_char) + local stna = gma_structids[stid] + return "S str="..stid.." ("..(stna or "?")..")" + else + return "???" + end +end + +local path=minetest.get_worldpath()..DIR_DELIM.."cellworld_allocation_map" +--load +function cellworld.load_allocation() + cellworld.log("loading structure allocation map") + local file, err = io.open(path, "rb") + if not file then + cellworld.log("Couldn't load the allocation database: ", err or "Unknown Error") + else + -- read version + local vers_byte = file:read(1) + local version = string.byte(vers_byte) + if version~=1 then + error("Doesn't support allocation file of version "..version) + end + + -- read structure ids + local nstr_byte = file:read(2) + local nstr = bytes_to_int(nstr_byte) + for i = 1,nstr do + local stid_byte = file:read(2) + local stid = bytes_to_int(stid_byte) + local stna = file:read("*l") + cellworld.log("structure id:", stid, "->", stna) + gma_structids[stid] = stna + end + cellworld.log("read", nstr, "structure ids.") + + -- read nodes. code suspiciously resembles advtrains ndb, not that I copied it :) ... + local cnt=0 + local hst_x=file:read(2) + local hst_y=file:read(2) + local hst_z=file:read(2) + local cid=file:read(4) + while hst_z and hst_y and hst_x and cid and #hst_z==2 and #hst_y==2 and #hst_x==2 and #cid==4 do + gmaset(bytes_to_int(hst_x,true), bytes_to_int(hst_y,true), bytes_to_int(hst_z,true), cid) + cnt=cnt+1 + hst_x=file:read(2) + hst_y=file:read(2) + hst_z=file:read(2) + cid=file:read(4) + end + cellworld.log("read", cnt, "structure allocations.") + file:close() + end +end + +--save +function cellworld.save_allocation() + local tmppath = path + local file, err = io.open(tmppath, "wb") + if not file then + cellworld.log("Couldn't save the allocation database: ", err or "Unknown Error") + else + cellworld.log("Saving allocation database...") + -- write version + file:write(string.char(1)) + + -- how many structid entries + local cnt = 0 + for _,_ in pairs(gma_structids) do + cnt = cnt + 1 + end + -- write structids + local nstr = 0 + file:write(int_to_bytes(cnt)) + for stid,stna in pairs(gma_structids) do + file:write(int_to_bytes(stid)) + file:write(stna) + file:write("\n") + nstr = nstr+1 + end + cellworld.log("wrote", nstr, "structure ids.") + + -- write entries + local cnt = 0 + for y, ny in pairs(gma_entries) do + for x, nx in pairs(ny) do + for z, cid in pairs(nx) do + file:write(int_to_bytes(x,true)) + file:write(int_to_bytes(y,true)) + file:write(int_to_bytes(z,true)) + file:write(cid) + cnt=cnt+1 + end + end + end + cellworld.log("wrote", cnt, "structure allocations.") + file:close() + end +end + +function cellworld.dump_allocation() + for y, ny in pairs(gma_entries) do + for x, nx in pairs(ny) do + for z, cid in pairs(nx) do + cellworld.log(x,y,z,format_cid(x,y,z,cid)) + end + end + end +end + +function cellworld.alloc_dump_area(lx,ly,lz,ux,uy,uz) + cellworld.log("-- allocation dumping area",lx,ly,lz,"<>",ux,uy,uz) + for dx,dy,dz,dcid in cellworld.alloc_get_area_iterator_raw(lx,ly,lz,ux,uy,uz) do + cellworld.log(dx,dy,dz,format_cid(dx,dy,dz,dcid)) + end + cellworld.log("-- end of dump") +end + +local function resolve_structure(cid, ox, oy, oz) + local rotation = string.sub(cid, 2, 2) + local stid_char = string.sub(cid, 3, 4) + local stid = bytes_to_int(stid_char) + local stna = gma_structids[stid] + --cellworld.debug(" structure rot=",rotation,"stid=",stid,"stna=",stna) + if stna then + return stna, vector.new(ox,oy,oz), string.byte(rotation) + end + cellworld.log("[allocation] Warn: unknown structure name for id",stid,". Ignored") + return nil +end + +--cellworld.alloc_get_cid(x,y,z) +cellworld.alloc_get_cid = gmaget + +-- returns: +-- structure_name, relative_pos, rotation +-- Note: structure rotation not calculated here yet +function cellworld.alloc_get_structure_at(cell_pos) + local cid = gmaget(cell_pos.x, cell_pos.y, cell_pos.z) + if not cid then return nil end + return cellworld.alloc_resolve_cid(cell_pos.x, cell_pos.y, cell_pos.z, cid) +end + +-- returns: +-- structure_name, relative_pos, rotation +function cellworld.alloc_resolve_cid(x, y, z, cid) + --cellworld.debug("alloc_resolve_cid(", x, y, z,")") + local indirection = string.sub(cid, 1, 1) + if indirection == "I" then + local ox,oy,oz = string.byte(cid, 2, 4) + --cellworld.debug("alloc_resolve_cid(", x, y, z,")") + local icid = gmaget(x-ox, y-oy, z-oz) + --cellworld.debug(" indirection +",ox,oy,oz,format_cid(x-ox, y-oy, z-oz,icid)) + if not icid then + cellworld.log("[allocation] Warn: Indirection at",vector.new(x,y,z),"has nil target. Ignored") + cellworld.alloc_dump_area(x-3,y-3,z-3,x+3,y+3,z+3) + return nil + end + indirection = string.sub(icid, 1, 1) + if indirection ~= "S" then + cellworld.log("[allocation] Warn: Indirection at",vector.new(x,y,z),"points to something other than S. Ignored") + cellworld.alloc_dump_area(x-3,y-3,z-3,x+3,y+3,z+3) + return nil + end + return resolve_structure(icid, ox, oy, oz) + elseif indirection == "S" then + return resolve_structure(cid, 0,0,0) + else + cellworld.log("[allocation] Warn: Unknown node type",indirection,"at gridpos",vector.new(x,y,z),". Ignored") + return nil + end +end + +function cellworld.alloc_set_structure(cell_pos, structure_name, rotation, structure_extent, no_clobber) + --cellworld.debug("alloc_set_structure(",cell_pos, structure_name, rotation, structure_extent, no_clobber,")") + for x=0,structure_extent.x-1 do + for y=0,structure_extent.y-1 do + for z=0,structure_extent.z-1 do + -- write indirection + if x==0 and y==0 and z==0 then + --continue + elseif no_clobber and gmaget(cell_pos.x + x, cell_pos.y + y, cell_pos.z + z) then + local ocid = gmaget(cell_pos.x + x, cell_pos.y + y, cell_pos.z + z) + cellworld.log("[allocation] While trying to place",structure_name,"at grid position",cell_pos,"extent",structure_extent) + cellworld.log("[allocation] Not clobbering ",vector.new(cell_pos.x + x, cell_pos.y + y, cell_pos.z + z),"which has entry",format_cid(cell_pos.x + x, cell_pos.y + y, cell_pos.z + z, ocid)) + error("Failed to place structure; see log...") + --continue + else + local indir = "I"..string.char(x)..string.char(y)..string.char(z) + --cellworld.debug(" indirection ",cell_pos,"+",x,y,z) + gmaset(cell_pos.x + x, cell_pos.y + y, cell_pos.z + z, indir) + end + end + end + end + if no_clobber and gmaget(cell_pos.x, cell_pos.y, cell_pos.z) then + return + end + -- write structure + local stid + for istid, istna in ipairs(gma_structids) do + if istna==structure_name then + stid = istid + break + end + end + if not stid then + stid = #gma_structids + 1 + cellworld.debug(" allocating new structure id ",stid,"for",structure_name) + gma_structids[stid] = structure_name + end + local struct = "S"..string.char(rotation)..int_to_bytes(stid) + --cellworld.debug(" structure ",cell_pos,"rot=",rotation,"stid=",stid) + gmaset(cell_pos.x, cell_pos.y, cell_pos.z, struct) +end + +function cellworld.alloc_has_space(cell_pos, structure_extent) + for _ in cellworld.alloc_get_area_iterator(cell_pos, vector.add(cell_pos, structure_extent)) do + --if any result, no space + return false + end + return true +end + +-- Returns an iterator function that iterates over all allocation entries in the given area, in raw format. +-- Iterator returns: x, y, z, cid +-- where cid can be decrypted by calling cellworld.alloc_resolve_cid(x,y,z,cid) +function cellworld.alloc_get_area_iterator(gp_min, gp_max) + return cellworld.alloc_get_area_iterator_raw(gp_min.x, gp_min.y, gp_min.z, gp_max.x, gp_max.y, gp_max.z) +end +function cellworld.alloc_get_area_iterator_raw(lx, ly, lz, ox, oy, oz) + local x, y, z = lx - 1, ly - 1, lz - 1 + local it_y, it_x + return function() + while y<=oy do + if it_y then + while x<=ox do + if it_x then + while z<oz do + -- locating next z + z=z+1 + if it_x[z] then + --[[local realcid = gmaget(x,y,z) + if realcid ~= it_x[z] then + cellworld.log(x,y,z,"CIDs dont match real=", + format_cid(x,y,z,realcid),"found=", + format_cid(x,y,z,it_x[z])) + cellworld.dump_allocation() + error("CIDs dont match in iterator") + end]]-- + return x, y, z, it_x[z] + end + end + -- through with iterating it_x + z=lz-1 + end + -- locating next x + x = x + 1 + it_x = it_y[x] + end + -- through with iterating it_y + x=lx-1 + it_x = nil + end + -- locating next y + y = y + 1 + it_y = gma_entries[y] + end + -- through with iterating everything + return nil + end +end + + +--[[ +local TEST_table = { + [1] = { + [1] = { + [1]="A", + [4]="B", + [5]="C", + }, + [3] = { + [2]="D", + }, + [5] = { + }, + }, + [2] = { + [3] = { + [2]="E", + }, + }, + [4] = { + [1] = { + [1]="F", + [4]="G", + }, + } +} +function cellworld.alloc_get_area_iterator_TEST(lx, ly, lz, ox, oy, oz) + local x, y, z = lx - 1, ly - 1, lz - 1 + local it_y, it_x + return function() + while y<=oy do + if it_y then + while x<=ox do + if it_x then + while z<oz do + -- locating next z + z=z+1 + cellworld.log("next z",z) + if it_x[z] then + return x, y, z, it_x[z] + end + end + -- through with iterating it_x + z=lz-1 + end + -- locating next x + x = x + 1 + it_x = it_y[x] + cellworld.log("next x",x,it_x~=nil) + end + -- through with iterating it_y + x=lx-1 + end + -- locating next y + y = y + 1 + it_y = TEST_table[y] + + cellworld.log("next y",y,it_y~=nil) + end + -- through with iterating everything + return nil + end +end + +for x,y,z,letter in cellworld.alloc_get_area_iterator_TEST(1,1,1,5,5,5) do + cellworld.log(x,y,z,letter) +end +]]-- + +-- Checks efficiently whether no, some or all cells in the given area are allocated +-- returns: +-- 0 - no cells allocated +-- 1 - some cells, but not all, allocated +-- 2 - all cells allocated +function cellworld.alloc_check_some_cells_allocated(gp_min, gp_max) + local have_skipped = false + local have_any_cell = false + for y=gp_min.y, gp_max.y do + local ly = gma_entries[y] + if ly then + for x=gp_min.x, gp_max.x do + local lx = ly[x] + if lx then + for z=gp_min.z, gp_max.z do + if lx[z] then + have_any_cell = true + else have_skipped=true end + end + else have_skipped=true end + end + else have_skipped=true end + end + if not have_any_cell then return 0 end + if have_skipped then return 1 end + return 2 +end |