MAP02 in ObHack-696 branch is non-deterministic

[samboy]

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.

[samboy]

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.

[samboy]

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.

[samboy]

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.

[samboy]

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).

[samboy]

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

[samboy]

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).

[samboy]

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.

[samboy]

Locking conversation to prevent spam.

[samboy]

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)

[samboy]

Related discussion: https://news.ycombinator.com/item?id=22269453

[samboy]

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.