Possible indeterminism in Digger._findWall

[airstruck]

Found this bug in a Lua port of rot.js (bug report here) and noticed it probably also affects rot.js.

In Digger's _findWall, for..in is used to build up an array, and then a random element is selected from that array. The problem is that iteration order of for..in isn't predictable (according to ES5 section 12.6.4, the "mechanics and order of enumerating the properties is not specified").

Not sure how much this actually affects rot.js. In the Lua port, it caused Digger to produce different maps given the same seed over a single run of the program. It was easy to spot in Lua.

In most implementations, the JS for..in construct seems more predictable than its Lua counterpart, so I suspect it will be more subtle in JS. Wouldn't expect it to generate the same map on two different UAs, even if it seems determinate on one UA, for example.

Anyway, just a heads-up.

[ondras]

Hi @airstruck,

good catch! The enumeration order in JS/ES is indeed undefined, yet it often causes heated discussions (see https://bugs.chromium.org/p/v8/issues/detail?id=164 for example).

JS implementations are somewhat aligned so that web pages behave the same in multiple browsers. Still, AFAIK, the V8 (Chrome) enumerates numeric keys sorted before other keys, while other JS impls use the enumeration order that matches creation order.

Sorting the array in _findWall might be the proper way to go here, what do you think?

[airstruck]

Sorting would probably be the most straightforward solution. We've removed most of the string concatenation in the Lua version since it was impacting performance, and just store the room's doors as an array of points and iterate the whole thing when looking for a door at a position (actually ends up being more efficient).

[ondras]

Sorting would probably be the most straightforward solution.

So the offending line, var id = arr.random(), could be modified:

var id = arr.sort().random();

And that's it, right?

As far as string concatenation goes, this would result in a more complex refactoring and I am not sure I want to undergo it right now (also, it is not related to this particular issue). ES2015 has a proper Map type that can be indexed by arrays, but re-writing rot.js to ES2015 is a too complex task for me right now.

[airstruck]

I think that should do it.

The x+','+y thing was an unfortunate double whammy in Lua, since the function that iterates those hash keys doesn't JIT compile either. Hopefully nothing to worry about on the JS side.

[airstruck]

I believe Object.keys is guaranteed to return keys in the order they were added, so that could be another option if you don't need to support ES3. Should be more efficient than sorting, although I doubt sorting handfuls of doors would ever be a bottleneck.

[ondras]

I believe Object.keys is guaranteed to return keys in the order they were added, so that could be another option if you don't need to support ES3.

According to MDN (emphasis mine):

The Object.keys() method returns an array of a given object's own enumerable properties, in the same order as that provided by a for...in loop

I will go on with the sort() approach.

[ondras]

Fixed in https://github.com/ondras/rot.js/commit/6d9d163c1638d43483b50743700e35f7e9e627ae.

[airstruck]

You're right, my mistake! I had a vague recollection that Object.keys was guaranteed to do something, but apparently nothing particularly useful. Should have checked spec first.