MAP02 in ObHack-696 branch is non-deterministic
samboy opened this issue · 11 comments
There is a bug where 2FreeDoom1 MAP02 has different designs for the individual cells every time I run ObHack. Sometimes, the shotty and blue key cells have cages in them; sometimes they do not. Sometimes, there are bookshelves in the secret Chainsaw room, sometimes there is not. Sometimes, the exit switch is on the left side of the exit room (as one enters the room), sometimes it is on the right side.
As far as I can tell, this probably comes because the Lua primitive pairs()
is unordered and probably runs in a different order. I know the doors in MAP02 are being placed in a different order when the cell designs vary.
Note that the maps are mostly the same (same look, same cell placement, same quests); it’s only the stair, cage, and monster placement which varies.
This is a needle in a haystack to find. So far, it’s builder.lua
that is acting differently. In particular, on different runs, the code around line 1732 of builder.lua
has non-deterministic behavior:
if MID.kind == "empty" and not c.hallway and
(c == PLAN.quests[1].first or c == c.quest.last or
dual_odds(links_in_cell(c) >= 3, 70, 25))
then
MID.kind = "room"
end
For some reason, this condition only sometimes passes.
In particular the call dual_odds gets a different number from the random number generator, which means that, in some code called just before this, we call the random number generator a non-deterministic number of times. So, the next thing is to log all RNG calls and see what kind of call is being done the “wrong” number sometimes.
After a very very deep dive in to a rabbit hole, this code in util.lua
looks very suspect:
function merge_table(dest, src)
for k,v in pairs(src) do
dest[k] = v
end
return dest
end
Note the pairs
which is non-deterministic in Lua (ugh).
Here’s a deterministic version of the above function:
function sorted_table_keys(t)
local a = {}
local b = 1
for k,_ in pairs(t) do
a[b] = k
b = b + 1
end
table.sort(a, function(y,z) return tostring(y) < tostring(z) end)
return a
end
function merge_table(dest, src)
local i = 0
local k
for i,k in ipairs(sorted_table_keys(src)) do
dest[k] = src[k]
end
return dest
end
Some other functions in ObHack need the same treatment. In util.lua:
function merge_missing(dest, src)
for _,k in ipairs(sorted_table_keys(src)) do
if not dest[k] then dest[k] = src[k] end
end
return dest
end
function expand_copies(LIST)
local function expand_it(name, sub)
if not sub.copy then return end
if sub._expanding then
error("Cyclic copy refs: " .. name)
end
sub._expanding = true
local orig = LIST[sub.copy]
if not orig then
error("Unknown copy ref: " .. name .. " -> " .. tostring(sub.copy))
end
-- recursively expand the original
expand_it(sub.copy, orig)
merge_missing(sub, orig)
sub._expanding = nil
sub.copy = nil
end
-- expand_copies --
for _,name in ipairs(sorted_table_keys(LIST)) do
expand_it(name, LIST[name])
end
end
function rand_table_pair(tab)
local count = 0
for k,v in pairs(tab) do count = count+1 end
if count == 0 then return nil, nil end
local index = rand_irange(1,count)
for _,k in ipairs(sorted_table_keys(tab)) do
if index==1 then return k,tab[k] end
index = index-1
end
error("rand_table_kv: miscounted!")
end
function rand_key_by_probs(tab)
local key_list = {}
local prob_list = {}
for _,key in ipairs(sorted_table_keys(tab)) do
table.insert(key_list, key)
table.insert(prob_list, tab[key])
end
local idx = rand_index_by_probs(prob_list)
return key_list[idx]
end
Doing these changes fixes the issue; the levels are deterministic; however, as a side effect, it causes ObHack to generate completely different levels.
I think I can keep the levels consistent with older versions of ObHack by only using sorted_table_keys()
with some, but not all, of the above functions (I’ll keep the old not-quite-deterministic pairs()
behavior for the functions starting in rand_
, which appears to keep the level plans the same as older ObHack).
It took me about eight hours to find this. Debugging this old 2009 version of LUA can be a pain (I think never versions of LUA are better here).
After further testing: There is no way to keep the old levels and make ObHack deterministic.
The entire design of the old ObHack levels depended on Lua’s pair()
function returning table entries in a certain order, which, as per the Lua specification, it doesn’t. So, for me to fix this, I need to change the levels ObHack will make.
Locking conversation to prevent spam.
I figured out how to keep some of the look of the old 2009 maps while updating them to be consistent in the ObHack-696 branch: I only use the non-deterministic legacy version of the code when determining the themes to use, and once the theme and layout is made, I reseed the random number generator and build the level. This way, the maps are consistent and different, while having the same layout and overall feel as the ObHack-1.0.0 maps (which are inconsistent, because of pairs()
being used everywhere in the old code)
Related discussion: https://news.ycombinator.com/item?id=22269453
Related: #8
Right now, we’re mostly deterministic. With the 2FreeDoom1
seed and default settings, all of the maps are the same and the wad has the same SHA256 sum on multiple invocations. With the 1FreeDoom1
seed, three maps (notably, MAP06
) vary. Before fixing the use of pairs()
, every single last map varied in some way.