… sandbox building game based on a simple grid system …
… is there a more efficient or better way to store part CFrame or position/orientation values in a datastore?
My first question is: do you need to store the CFrame?
If all placed objects are grid-aligned:
- Do you allow placement along the Y axis? If not, you can throw that out and just store the X/Z grid indices
- If user are able to rotate objects …
- Are they able to rotate them in true 3D space, or are they only able to rotate a specific axis e.g.
yaw? - If it’s the latter: only save that axis, and only do so if that value is greater than 0
- Are they able to rotate them in true 3D space, or are they only able to rotate a specific axis e.g.
etc etc
If you do need to store the CFrame:
Alongside using some lossless compression algorithm like those found here, you could also compress the CFrame itself by considering the matrix as a Vector3 and a Quaternion, e.g.:
Example
Note: Roblox doesn’t yet support binary data to be saved to the DataStore, as discussed here, so you would have to encode the buffer as Base64 before saving it e.g. this repo
local LP_EPSILON = 1e-6
local I16_PRECISION = 32767
-- i.e flags for CFrame datatype, learn more:
-- - https://www.alanzucconi.com/2015/07/26/enum-flags-and-bitwise-operators/
-- - https://turnerj.com/blog/fun-with-flags-enums-and-bit-shifting
local sigFlags = {
-- ---------------------
-- | BINARY | Decimal |
-- ---------------------
None = 0, -- | 0000000 | 0 |
Coordinate = 1, -- | 0000001 | 1 |
Positional = bit32.lshift(1, 1), -- | 0000010 | 2 |
Rotational = bit32.lshift(1, 2), -- | 0000100 | 4 |
X = bit32.lshift(1, 3), -- | 0001000 | 8 |
Y = bit32.lshift(1, 4), -- | 0010000 | 16 |
Z = bit32.lshift(1, 5), -- | 0100000 | 32 |
Component = bit32.lshift(1, 6), -- | 1000000 | 64 |
-- ---------------------
}
-- i.e. maps a sigFlag to a quaternion index, i.e. 1 = x; 2 = y, 3 = z
local quatIndex = {
[sigFlags.X] = 1,
[sigFlags.Y] = 2,
[sigFlags.Z] = 3,
}
-- i.e. maps a quaternion index (1 = x) to a sigflag
local quatRelative = {
[1] = sigFlags.X,
[2] = sigFlags.Y,
[3] = sigFlags.Z,
}
-- e.g. some custom datatype you could define
local customDatatypes = {
-- e.g. some custom datatype(s)
GridAlignedData = 'table', -- blahblah
}
--[=[
Computes a normalised quaternion given a CFrame
@param cf CFrame -- a CFrame value
@return varargs<...> -- normalised components of a quaternion
]=]
local function computeNormalisedQuaternion(cf)
local axis, angle = cf:ToAxisAngle()
local x = axis.X
local y = axis.Y
local z = axis.Z
local d = x*x + y*y + z*z
if d > LP_EPSILON then
d = 1 / math.sqrt(d)
x *= d
y *= d
z *= d
else
x = 1
y = 0
z = 0
end
local ha = angle*0.5
local sha = math.sin(ha)
local w = math.cos(ha)
x = sha * x
y = sha * y
z = sha * z
d = x*x + y*y + z*z + w*w
if d > 0 then
d = 1 / math.sqrt(d)
return x*d, y*d, z*d, w*d
end
return 0, 0, 0, 1
end
--[=[
Compress a quaternion into { 1x u8, ... 3x i16 }
@param qx number -- x component of a quaternion
@param qy number -- y component of a quaternion
@param qz number -- z component of a quaternion
@param qw number -- w component of a quaternion
@param qw boolean -- (optional) boolean to det. whether we will
attempt to compress the quaternion such that
its qi component represents a quaternion's index
if its value is approx. 1
@return varargs<...> -- the compressed quaternion components
]=]
local function compressQuaternion(qx, qy, qz, qw, useMinimal)
local index = -1
local value = -math.huge
local element, v0, v1, v2
for i = 1, 4, 1 do
local val = select(i, qx, qy, qz, qw)
local abs = math.abs(val)
if abs > value then
index = i
value = abs
element = val
end
end
-- i.e. if 1x component is approx. 1 then we can reduce to single u8; since rotation (w, x, y, z) = -1*(w, x, y, z)
if useMinimal and math.abs(1 - value) < LP_EPSILON then
return index + 4
end
local sign = element >= 0 and 1 or -1
if index == 1 then
v0 = math.floor(qy * sign * I16_PRECISION + 0.5)
v1 = math.floor(qz * sign * I16_PRECISION + 0.5)
v2 = math.floor(qw * sign * I16_PRECISION + 0.5)
elseif index == 2 then
v0 = math.floor(qx * sign * I16_PRECISION + 0.5)
v1 = math.floor(qz * sign * I16_PRECISION + 0.5)
v2 = math.floor(qw * sign * I16_PRECISION + 0.5)
elseif index == 3 then
v0 = math.floor(qx * sign * I16_PRECISION + 0.5)
v1 = math.floor(qy * sign * I16_PRECISION + 0.5)
v2 = math.floor(qw * sign * I16_PRECISION + 0.5)
elseif index == 4 then
v0 = math.floor(qx * sign * I16_PRECISION + 0.5)
v1 = math.floor(qy * sign * I16_PRECISION + 0.5)
v2 = math.floor(qz * sign * I16_PRECISION + 0.5)
end
return index, v0, v1, v2
end
--[=[
Compress a quaternion into { 1x u8, ... 3x i16 }
@param cf CFrame -- a CFrame value
@param qw boolean -- (optional) boolean to det. whether we will
attempt to compress the quaternion such that
its qi component represents a quaternion's index
if its value is approx. 1
@return varargs<...> -- the compressed quaternion components
]=]
local function compressQuaternionFromCFrame(cframe, useMinimal)
local qx, qy, qz, qw = computeNormalisedQuaternion(cframe)
return compressQuaternion(qx, qy, qz, qw, useMinimal)
end
--[=[
Attempts to derive a valid quaternion from a compressed quaternion
as given by the `::compressQuaternion` and `::compressQuaternionFromCFrame` method
@param ... varargs<...> -- compress components
@return varargs<...> -- the x, y, z and w components of the inflated quaternion
]=]
local function decompressQuaternion(qi, q0, q1, q2)
-- decompress minimal where index describes one q component that's 1
if qi > 4 then
if qi == 5 then
return 1, 0, 0, 0
elseif qi == 6 then
return 0, 1, 0, 0
elseif qi == 7 then
return 0, 0, 1, 0
elseif qi == 8 then
return 0, 0, 0, 1
end
end
-- decompress components
q0 /= I16_PRECISION
q1 /= I16_PRECISION
q2 /= I16_PRECISION
local d = math.sqrt(1 - (q0*q0 + q1*q1 + q2*q2))
if qi == 1 then
return d, q0, q1, q2
elseif qi == 2 then
return q0, d, q1, q2
elseif qi == 3 then
return q0, q1, d, q2
end
return q0, q1, q2, d
end
----------------------------------------------
-- --
-- EXAMPLE --
-- --
----------------------------------------------
--[[
[!] Note:
The 'writeExampleBuffer' could do with some work here:
1. you should be iterating through the values and determining the len of your
buffer first before creating it
OR;
2. You should be dynamically resizing your buffer
The same can be said for the read example which could be expanded to
read a u8 that would describe the datatype; the reader would read that flag
before decoding the value
]]
------
--[=[
Attempts to write the given value to the buffer according to its datatype
@param datatype string -- the desired datatype
@param value any -- the value to write
@return (1) boolean -- reflects success state
(2) buffer | string -- either (a) the resulting buffer or (b) an error message
]=]
local function writeExampleBuffer(datatype, value)
local t = typeof(datatype)
if t ~= 'string' then
return false, string.format('Expected string for DataType but got %q', t)
end
local trueDataType = customDatatypes[datatype] or datatype
t = typeof(value)
if datatype ~= t then
return false, string.format(
'TypeMismatch: expected value as type %q but got %q',
datatype, t
)
end
local buf
if datatype == 'CFrame' then
local vector = value.Position
local qi, q0, q1, q2 = compressQuaternionFromCFrame(value, true)
local hasPositionalData = vector.Magnitude >= LP_EPSILON
local hasRotationalData = qi <= 4
local sg, sz
if hasPositionalData and hasRotationalData then
sg = sigFlags.Coordinate
sz = 19
elseif hasPositionalData then
sg = sigFlags.Positional
sz = 13
elseif hasRotationalData then
sg = sigFlags.Rotational
sz = 7
else
sg = sigFlags.None
sz = 1
end
local index
if qi > 4 then
index = quatRelative[qi - 4]
if index then
index = bit32.bor(index, sigFlags.Component)
end
else
index = quatRelative[qi]
end
if index then
sg = bit32.bor(sg, index)
end
local offset = 1
buf = buffer.create(sz)
buffer.writeu8(buf, 0, sg)
if hasPositionalData then
buffer.writef32(buf, offset + 0, value.X)
buffer.writef32(buf, offset + 4, value.Y)
buffer.writef32(buf, offset + 8, value.Z)
offset += 12
end
if hasRotationalData then
buffer.writei16(buf, offset + 0, q0)
buffer.writei16(buf, offset + 2, q1)
buffer.writei16(buf, offset + 4, q2)
offset += 6
end
else
-- e.g. some other datatype
end
if buf then
return true, buf
end
return false, string.format('NotImplementedError: unknown datatype %q', datatype)
end
--[=[
Attempts to read the given datatype from the given buffer at the given offset
@param buf buffer -- the buffer to read from
@param datatype string -- the desired datatype to read
@param offset number -- (optional) buffer offset index
@return (1) boolean -- reflects success state
(2) buffer | string -- either (a) the resulting value or (b) an error message
(3) number -- the offset after reading the value
]=]
local function readExampleBuffer(buf, datatype, offset)
local t = typeof(buf)
if t ~= 'buffer' then
return false, string.format('Expected BufferObject for buffer but got %q', t), offset
end
t = typeof(datatype)
if t ~= 'string' then
return false, string.format('Expected string for DataType but got %q', t), offset
end
t = typeof(offset)
if t == 'nil' then
offset = 0
elseif t ~= 'number' then
return false, string.format('Expected number|nil for offset but got %q', t), offset
end
if datatype == 'CFrame' then
local sig = buffer.readu8(buf, offset + 0)
offset += 1
local coordinate
local x, y, z
local qi, q0, q1, q2
local qx, qy, qz, qw
local isComponent = bit32.band(sig, sigFlags.Component) == sigFlags.Component
if isComponent then
sig = bit32.band(sig, bit32.bnot(sigFlags.Component))
end
if bit32.band(sig, sigFlags.Coordinate) == sigFlags.Coordinate then
-- some coordinate frame incl. position + rotation
sig = bit32.band(sig, bit32.bnot(sigFlags.Coordinate))
qi = sig > 0 and quatIndex[sig] or 4
qi = isComponent and qi + 4 or qi
x = buffer.readf32(buf, offset + 0)
y = buffer.readf32(buf, offset + 4)
z = buffer.readf32(buf, offset + 8)
q0 = buffer.readi16(buf, offset + 12)
q1 = buffer.readi16(buf, offset + 14)
q2 = buffer.readi16(buf, offset + 16)
qx, qy, qz, qw = decompressQuaternion(qi, q0, q1, q2)
coordinate = CFrame.new(x, y, z, qx, qy, qz, qw)
offset += 18
elseif bit32.band(sig, sigFlags.Positional) == sigFlags.Positional then
-- some positional coordinate +/- rotation
sig = bit32.band(sig, bit32.bnot(sigFlags.Positional))
qi = sig > 0 and quatIndex[sig] + 4 or 8
x = buffer.readf32(buf, offset + 0)
y = buffer.readf32(buf, offset + 4)
z = buffer.readf32(buf, offset + 8)
qx, qy, qz, qw = decompressQuaternion(qi)
coordinate = CFrame.new(x, y, z, qx, qy, qz, qw)
offset += 12
elseif bit32.band(sig, sig) ~= sigFlags.None then
-- some rotational coordinate
if bit32.band(sig, sigFlags.Rotational) == sigFlags.Rotational then
sig = bit32.band(sig, bit32.bnot(sigFlags.Rotational))
qi = sig > 0 and quatIndex[sig] or 4
qi = isComponent and qi + 4 or qi
else
qi = sig > 0 and quatIndex[sig] or 0
qi = isComponent and qi + 4 or qi
end
if qi <= 4 then
q0 = buffer.readi16(buf, offset + 0)
q1 = buffer.readi16(buf, offset + 2)
q2 = buffer.readi16(buf, offset + 4)
offset += 6
end
qx, qy, qz, qw = decompressQuaternion(qi, q0, q1, q2)
coordinate = CFrame.new(0, 0, 0, qx, qy, qz, qw)
else
-- identity
coordinate = CFrame.identity
end
return true, coordinate, offset
else
-- e.g. some other datatype
end
return false, string.format('NotImplementedError: unknown datatype %q', datatype), offset
end
----------------------------------------------
-- --
-- DEMO --
-- --
----------------------------------------------
-- e.g. some wrapper function around your read/write methods ...
local function someWrapperFunction(target)
local success, result = writeExampleBuffer('CFrame', target)
if success then
success, result = readExampleBuffer(result, 'CFrame', 0)
if success then
return true, { Target = target, Result = result }
end
end
return false, result or 'Unknown error occurred'
end
-- [?] Note:
-- The following is wrapped in a function because I tested it using a storybook,
-- just rip out the contents and use it in some script to test it
--
return function ()
local exampleCFrame = CFrame.new(0, 5, 0) * CFrame.Angles(math.pi*0.25, 0, -math.pi*0.25)
local success, result = someWrapperFunction(exampleCFrame)
if not success then
warn(result)
return
end
local part = Instance.new('Part')
part.Size = Vector3.one + Vector3.zAxis
part.Shape = Enum.PartType.Block
part.CanCollide = false
part.CanQuery = false
part.CanTouch = false
part.Anchored = true
local parts = { }
for name, cframe in next, result do
local p = part:Clone()
p.Name = name
p.CFrame = cframe
p.BrickColor = BrickColor.Random()
p.Parent = workspace
table.insert(parts, p)
end
return function ()
for i, v in next, parts do
pcall(v.Destroy, v)
end
end
end
Some things to note in this example:
-
Storing a
CFramenaively in a buffer would cost 48 bytes if you wrote the components asfloat32; -
We can reduce that a little more by storing its position as a
Vector3via 3xfloat32and either (a) 3xfloat32for the euler angles, or (b) its axis angle representation which would be 4xfloat32- this gets you to 24 - 28 bytes respectively -
The following example is dynamically sized:
- In the best case, e.g. when storing an identity quaternion, it would be represented as 1 byte
- In the case of a
CFramecontaining only rotational data, it would be presented as 7 bytes - In the case of a
CFramecontaining only positional data, it would be represented as 13 bytes - In the worst case, where a
CFramecontains both positional and rotational data, it would be represented as 19 bytes
-
This means that - compared to the naive method - in the best case we’re achieving space saving of ~97.92% and in the worst case, we’re at ~60.42%; i.e. compression ratio of 2.08% - 39.58%
P.S. You can do a similar thing with the grid-aligned data if you’re only considering (x, z, yaw):
-
Encoding yaw:
- Map the yaw to -180 to 180
- Write it as an
int8
-
Encoding X / Z:
- Since it’s grid-aligned, we can store it as an
integer - Assuming the players can’t place items at any position:
- You could compute the grid-aligned position relative to the placement origin, e.g. they can only place in a 100x100 square, mapped to the grid indices - this can be further reduced by storing it as one integer where the
indexwould now be:index = x + width*y - Stored as an integer of an appropriate size, e.g.
uint8would give you a range of 0 - 255 or auint16of 0 - 65,535
- You could compute the grid-aligned position relative to the placement origin, e.g. they can only place in a 100x100 square, mapped to the grid indices - this can be further reduced by storing it as one integer where the
- Since it’s grid-aligned, we can store it as an