Cell bitfield (proposal)

[airstruck]

Currently the contents of a cell is indicated by a number value: 0 for floors and 1 for walls.

Doors are sometimes represented by a 2, but aren't usually included with those 1s and 0s (passed to dungeon callbacks), presumably because they're neither walls nor floors and they'll screw up dungeon generation if they're put into self._map. So after you call create to get the 1s and 0s, you have to call getDoors to get the 2s.

I propose adding the doors to that self._map data by treating the value as a bitfield.

• 0 = floor
• 1 = wall
• 2 = open door (door + floor)
• 3 = closed door (door + wall)

In map generators, instead of checking floors with n==0 and walls with n==1, check with n%2==0 and n%2==1.

The bitfield can also be extended for Digger's buildable and priority walls, and for other implementation-specific cell details.

I have an experimental branch using this approach and it seems to work well. Here's the helper module I'm using (comments should help explain the idea):

-- Defines bit flags for map cells used by map generators.
local Cell = {}

--[[

64 32 16  8  4  2  1  (0 = floor)
 |  |  |  |  |  |  |
 |  |  |  |  |  |  wall
 |  |  |  |  |  door
 |  |  |  |  mark
 |  |  |  priority
 |  |  red
 |  green
 blue

The "wall" bit indicates a wall or a floor, or a closed or open door when
combined with the "door" bit.

The "mark" bit is used to mark walls for expansion.

The "priority" bit indicates expansion should happen immediately when combined
with "mark" bit, or failed priority expansion (dead-end) without "mark" bit.

Dungeons may use RGB bits separately or together for implementation-specific
cell details, for example hidden doors, cellular water/lava, materials, etc.

High bit is reserved for future use.

--------  =  0 = floor 
-------1  =  1 = wall
------1-  =  2 = open door
------11  =  3 = closed door (door + wall)

-----1--  =  4 = marked floor
-----1-1  =  5 = marked wall (marked for optional construction)
-----11-  =  6 = marked open door
-----111  =  7 = marked closed door

----1---  =  8 = unmarked priority floor
----1--1  =  9 = unmarked priority wall (appears next to dead-ends)
----1-1-  = 10 = unmarked priority open door
----1-11  = 11 = unmarked priority closed door

----11--  = 12 = priority floor
----11-1  = 13 = priority wall (marked for immediate construction)
----111-  = 14 = priority open door
----1111  = 15 = priority closed door

]]

Cell.WALL = 1
Cell.DOOR = 2
Cell.MARK = 4
Cell.PRIORITY = 8
Cell.RED = 16
Cell.GREEN = 32
Cell.BLUE = 64
Cell.RESERVED = 128

function Cell.has(n, flag)
    return math.floor(n / flag) % 2 == 1
end

function Cell.set(n, flag, on)
    return Cell.has(n, flag) == on and n
        or n + (on and flag or -flag)
end

function Cell.hasWall(n) return Cell.has(n, Cell.WALL) end
function Cell.hasDoor(n) return Cell.has(n, Cell.DOOR) end
function Cell.hasMark(n) return Cell.has(n, Cell.MARK) end
function Cell.hasPriority(n) return Cell.has(n, Cell.PRIORITY) end
function Cell.hasRed(n) return Cell.has(n, Cell.RED) end
function Cell.hasGreen(n) return Cell.has(n, Cell.GREEN) end
function Cell.hasBlue(n) return Cell.has(n, Cell.BLUE) end

function Cell.setWall(n, on) return Cell.set(n, Cell.WALL, on) end
function Cell.setDoor(n, on) return Cell.set(n, Cell.DOOR, on) end
function Cell.setMark(n, on) return Cell.set(n, Cell.MARK, on) end
function Cell.setPriority(n, on) return Cell.set(n, Cell.PRIORITY, on) end
function Cell.setRed(n, on) return Cell.set(n, Cell.RED, on) end
function Cell.setGreen(n, on) return Cell.set(n, Cell.GREEN, on) end
function Cell.setBlue(n, on) return Cell.set(n, Cell.BLUE, on) end

return Cell

This is a departure from rot.js way of doing things, but backwards compatibility could be provided with a generator option to control whether callbacks only get passed the low bit of each bitfield.

What do you guys think of this? I've found it to be really useful for getting more interesting behavior out of a modified Digger, and visually figuring out what happened during map generation. I'll put a PR together if this is something you guys want.

[timothymtorres]

Alright so here are my thoughts on this feature. I've used bitflags for quite a few of my projects. Love2D uses LuaJIT, which by default, has a built in bit library. Basically, you won't need to write your own bit operation functions and that should simplify things quite a bit.

Be careful that the bitfield does not grow to be larger than 32 bits else it will overflow. I had this happen to me previously.

Now on to the cell bitfield itself. Is it really necessary to track the Cell.PRIORITY and Cell.MARK alongside the other bitfields? Sure, when the dungeon is first being constructed it would be needed, but once it's completed it would be redundant, no? Perhaps that could be isolated, or even trimmed from the bitfield once the dungeon is complete. I'm not too familiar with the dungeon generation algorithms.

As for the rest of the idea, it is pretty sound, and something I'm sure other roguelikes have used for their map data. Using bitflags like this would make saving/loading maps faster, not to mention sending the map via packets through a network travel at lightspeed.

I refactored your code to make it much simpler.

local bit = require('bit')
local bnot = bit.bnot
local band, bor, bxor = bit.band, bit.bor, bit.bxor

-- Defines bit flags for map cells used by map generators.
local Cell = {}

--[[

64 32 16  8  4  2  1  (0 = floor)
 |  |  |  |  |  |  |
 |  |  |  |  |  |  wall
 |  |  |  |  |  door
 |  |  |  |  invisible  (toggle this on to make a hidden door/structure)
 |  |  |  oil
 |  |  lava
 |  water
 altar

]]

-- If you are going to have lots of flags, I'd highly recommend you use 2^n 
Cell.WALL =         2^0
Cell.DOOR =         2^1
Cell.MARK =         2^2
Cell.PRIORITY =     2^3
Cell.RED =          2^4
Cell.GREEN =        2^5
Cell.BLUE =         2^6
Cell.RESERVED =     2^7

function Cell.has(flag, n) return band(n, Cell[flag]) == Cell[flag] end

function Cell.set(flag, n) return bor(n, Cell[flag]) end

function Cell.unset(flag, n) return band(n, bnot(Cell[flag])) end

--[[  To use just...

If Cell.has('WALL', map[y][x]) then
  -- do this thing...

map[y][x] = Cell.set('DOOR', map[y][x])
map[y][x] = Cell.unset('WALL', map[y][x])
--etc.

-- might be a good idea to also remove all caps from the flags?
--]]

return Cell

Also a little off topic but I was looking at porting the dice module to rotJS, but it appears JS does not support operator overloading. This limits the modules usefulness as that was a core feature that made the dice easy to use. Thoughts on this?

@paulofmandown You may want to look into something like zenhub to use with rotLove. It would make new features and issues much easier to manage and assign. I'd love to help out too!

I'm also considering adding a skill module for rotLove. Almost all roguelikes have a skill system and I've coded in a few files for games using a good setup. It uses bitflags on a player/mob/NPC for a skill to add, remove, or check them quite easily. It would be about the same usefulness as the event scheduler. If you guys think this would be useful I can work on it.

[airstruck]

Thanks @timothymtorres, some good points there.

Regarding LuaJIT, I agree we should use their bit library when available, I just wanted to make sure it would also work without LuaJIT (since Love can run on PUC Lua as well, and since rotLove is largely independent of Love and can run on PUC Lua with a custom display module).

Technically we have 53 bits available with the current code, but using LuaJIT's bit ops would limit it to 32. My intent was to limit it to 8 bits and introduce a high-performance "_map" implementation with FFI byte arrays when FFI is available and JIT is on, with a fallback to current tables of numbers approach.

About "mark" and "priority," you're correct that these are only useful while generating the dungeon. Actually that's the main point of this proposal; this is really a format for use during map generation, not necessarily exposed to the client. In other words the default behavior could be for create callbacks to only receive the low bit and behave exactly as they do now, but you could also set an option to receive the entire bitfield. In that case, those bits can be useful when populating the map, for example you can easily find the occasional dead-ends and stick something interesting at the end.

---

Regarding JS operator overloading, you're out of luck there. Honestly, some of those overloads smell a bit funny to me. Why does / modify number of faces on the die? I'd rather call a method (why isn't there one?) or set a field so it's clear what's happening. I'd expect Dice('1d6') + Dice('1d6') to be equivalent to Dice('2d6'), but it only works for Dice('1d6') + 1 -> Dice('1d6+1'). Not obvious why * represents number of dice and % represents number of "sets," etc. This is just my opinion and I don't mean any disrespect by it, but I don't think these operator overloads lead to clear or intuitive code.

On the other hand (and even further off-topic), I'd really like to use operator overloads for colors, where there's a direct line between operators and some functions that are currently available (adding and multiplying colors). But we need to be rid of that weird 30log deep-copy behavior first. Might open a ticket on 30log's issue tracker about this if we want to keep it, although I think we've already recreated all the features we need in class.lua.

About skill system, I've been thinking some kind of framework on top of (but separate from) rotLove would be a good place for that kind of thing. Would also like somewhere to put UI-related code, like text entry fields, health bars, scrolling logs, and so on (appearing in the regular display, of course). We could open a new project for discussion on that if you're interested.

[airstruck]

Closing for now after discussion here: https://github.com/ondras/rot.js/issues/123

Might still be useful for a new map type (some kind of "super digger").