[✓][SUG] Prioritise exits over other objects | [DISC] Lemmini bit handling

[WillLem]

I'm currently investigating overlapping trigger areas in the Lemmini codebase. It doesn't seem to work in the same way as NeoLemmix, where multiple triggers can both exist and be detected in the same pixel.

Instead, the evidence suggests that each pixel can only be occupied by a single trigger, determined (as it seems) by the object's index relative to the other object(s).

So, if we place a water object at index 0, then a trap at index 1, then an exit at index 2, and have all 3 triggers overlap, the exit trigger will overwrite the other two.

At least, that's what I think is happening based on my findings so far.

If that's the case, then prioritising one over the other seems to be basically impossible unless we start hacking away at the rendering, or re-shuffle the indexing of people's levels; neither of these are particularly appealing. There must be another way.

If anyone has any insight into how "bits" work (as opposed to pixels), please do contribute.

[Simon]

Bitwise operations treat a byte (e.g., -128 through 127) as an array of 8 bools.

Decimal 31 is binary 00011111.
Decimal 85 is binary 01010101.
Then 31 & 85 is 21 because decimal 21 is binary 00010101, this has a 1 only where both of the sources had a 1. And 31 | 85 is 95 because decimal 95 is 01011111, this has a 1 wherever one (or both) of the sources had a 1.

Search the internet for: bitwise operators, Java bitwise operations.

https://www.w3schools.in/java/operators/bitwise

Or do you want to investigate the Java source together? I have little time this week, but we can schedule Tuesday night or Wednesday night. Tuesday 19:00 UTC in Mumble?

-- Simon

[WillLem]

Or do you want to investigate the Java source together? I have little time this week, but we can schedule Tuesday night or Wednesday night. Tuesday 19:00 UTC in Mumble?

Sure, sounds good. I've put it in the calendar

The Lemmini codebase is trickier to work with than NL, but if we can get to the root of how/where bits are written/read into/from the rendering, that'll be a good start.

[Simon]

All right, Tue, 19:00 UTC in Mumble. See you!

-- Simon

[namida]

One approach to allow prioritising could be during writing objects to the trigger map, check if a trigger already exists where you're trying to write one and only allow it if there's no existing one or the existing one is "lower priority". Lemmini doesn't have any trigger areas that change between on and off except for the temporary disabling of triggered traps while they're killing a lemming, so as long as no one wants to stick a trap right in front of an exit to require crowd compression into it (and the same puzzle can pretty much be done other ways anyway). And anyone actually making new levels is not overly likely to use Lemmini these days; it's mostly going to be existing content that's a concern, assuming you aren't planning any major overhauls or upgrades that would bring it more in line with NL and Lix.

Rather than dealing with bitwise operations, you could also just use multiple trigger maps like NL does. This will likely result in tidier and possibly more performant code, at the cost of higher memory usage.

[WillLem]

One approach to allow prioritising could be during writing objects to the trigger map, check if a trigger already exists where you're trying to write one and only allow it if there's no existing one or the existing one is "lower priority".

Yeah, this is pretty much exactly what I'm trying to do. From what I can tell though, the codebase only seems to care about data coming in rather than what's already written there.

Rather than dealing with bitwise operations, you could also just use multiple trigger maps like NL does. This will likely result in tidier and possibly more performant code, at the cost of higher memory usage.

Yes, this would be ideal. It would require significant refactoring though, I'm not sure it's worth it for such a niche physics concern.

If I can find a way to analyze the current pixel and return the existing mask, that's likely where the answer is (with part of the goal being to move as little existing code around as possible).

[WillLem]

OK, so I managed to find a way to check what's already there, and not replace it if it's an exit (in fact, explicitly convert the incoming data to exit data and write it in again). However, doing this for the mask alone doesn't work, and I've no idea why; the mask is a monochrome map of bit data, it shouldn't need to know anything other than which mask is written into which pixel.

But, it seems we also need to take into account the Object ID. This is the exact object according to its placement index, and it's difficult to know exactly what to do here, but we can at least implement a similar check-and-swap for incoming data.

As a test, I tried changing the mask from "whatever" to "exit" if the existing mask is "exit", and the incoming ID from "2" to "1" if the existing ID is "1". This works as long as there is only 1 exit and 1 overlapping object present in the level. If more are introduced, it no longer works. This doesn't make sense really, because adding objects shouldn't change the placement index of existing ones (and doesn't appear to, according to the [x, y] debugging data), so it should still work at least for the purposes of this experiment.

Obviously, swapping things out in this particular manner isn't a long-term solution anyway (at least as far as the ID is concerned), I just wanted to see if it could be done. But, the code is stubborn.

[namida]

Going back to the discussion about bits, I feel it might be easier for you to understand if we look at this from the other angle: First, we start with what we do with it, and how it's able to work, then later explain the connection to bits and binary.

The point of using binary in this context (ie: this is far from the only use for it) is to be able to store multiple on-off values in a single number. We do this to take advantage of several other useful properties of a single number: they take up little memory, and can be accessed easily and quickly, it generally takes less code when copying it around and it's also very easy to save / load from a binary blob (you can basically just write the number - or, a large block of such numbers, like one number per pixel in the case of a trigger area map) into a file.

How do we do this? We simply turn each of these on/off values into a number themself, and then add them, or modifications of them, together, in such a way that we can reverse this and figure out the original numbers again.

Let's put aside the on/off flags and binary for a second, and focus on this general concept using normal decimal numbers for a second. We already see this concept in the numbers we use everyday - the number 53 for example, specifically represents 5 tens and 3 ones. Except by exceeding the maximum amount of ones you can actually have in a single digit, there is no other way to represent this number. So as long as each digit represents something you can't have more than 9 of, you can pack information into a decimal number this way. One real-world case where we see this is in AMD's processor model numbers, where each digit of, for example, "7840" in the Ryzen 7840U's name means something - the 7 indicates the year of release, the 8 indicates it's a higher-end model, the 4 indicates it uses cores based on the Zen 4 architecture, and the 0 indicates it isn't a mid-gen refresh of Zen 4.

Now, back to on/off flags. In this case, we could do it the same way, just using 1s and 0s in decimal and ignoring the other digits. If we want to write a sequence of "true, true, false", we could represent this as 110. (Or perhaps we want to use 1 for true and 2 for false, and represent it as 112. The question of how you choose to represent the data is arbitrary, although there are common conventions; all that matters for the purpose of getting it to function, is that you're consistent between how you write it and how you read it.) Using a 32-bit integer which can have a value of (assuming unsigned) up to 2147483647, we could store up to 10 on/off flags this way.

However, there's actually nothing magical about the digit positions here, except for the fact that the packed info in them is easily human-readable. Keyword "human". The magic doesn't come from the digits themselves, but from the underlying purpose of the digits. Back to the earlier example, in 53, the 5 represents "five lots of ten". The 3 represents "three lots of one". If you're already familiar with numbers in other bases (like binary or hexadecimal), you'll get this concept already. But, let's say that we instead represented a number in terms of lots of something other than ten (and powers thereof). Let's say for example, that we have "six lots of eight, and five lots of one". This would also add up to 53. You could change the amounts of each one - perhaps we want to represent the number 37 instead. Critically, for each possible resulting number, there is - assuming certain restrictions are followed in selecting how you turn the data into numbers and combine it - only one possible way each it can be made.

Using a decimal example, as long as no single component/digit is allowed to be greater than 9, there's only one way to make 53 - five tens, and three ones. You don't have a "nines" or "threes" etc digit, and you can't have a digit higher than 9, so there's no other way to make 53 besides this. So if you're packing two one-digit numbers into a single larger number, and the packed number is 53, it's easy to tell that the first packed number is 5 and the second is 3 - you don't have to consider any other possibility, because the rules of how the data is being packed are set up such that each number only can represent one possible combination of values.

Any actual base used in real-world scenarios - decimal, hexadecimal, binary, octal - already inherently fit these rules. In more complex scenarios, you will need to know how to construct digit positions / limits such that they'll fit. Now, as far as the simple case goes - packing on/off flags into a value via binary - we're almost ready to put all of this together at this point. The only thing left is a quick explainer on binary itself (in terms of what I've explained here so far), just in case you - or anyone else reading this at a later date - needs it.

Binary, just like decimal, stores numbers by using digits - the difference is just that the digits only go up to 1, instead of going up to 9 like they do in decimal (or 7 in octal, or F (15) in hexadecimal). This also means that the value of each place is different - you don't have a ones digit, a tens digit, a hundreds digit, etc. Instead you have a ones digit, a twos digit, a fours digit, an eights digit, a sixteens digit, etc. The binary number 1101 represents "one eight, one four, zero twos, and one one" - or in decimal, 13. And the ONLY way in binary to make the value 13, is that - 1101.

Now, if we're dealing with on/off flags? Then 13 - or 1101 - represents the first flag on, second flag on, third flag off, fourth flag on. Note that you're still ultimately dealing with the same kinds of numbers you're used to - it just happens that the algorithm you're using to pack multiple numbers into one big one, lines up with how binary inherently operates, so the comparisons are common - and indeed, using certain programming features designed for working with raw binary values can come in very handy when packing and unpacking these numbers.

How to implement this in code is a much easier matter, and one I won't cover in this post - I'm sure Simon will get you up to speed on that, or I can go into it another time. It's also somewhat language-specific - the general concepts stay the same, but the exact syntax and operators differ.

Up to here is probably all you need to know for your immediate goal.

But let's take the concept a bit further. The examples we've seen deal with simple cases; using individual digits of a decimal number to represent small quantities (which mathematically is no different to any other case, but is far more human-understandable), or using individual binary digits to represent a series of on/off flags. In particular, these line up exactly with a commonly-used base.

There's no reason it has to though. The golden rule, in order to be able to reverse it, is simply "for each result number, there must be only one combination of inputs that can lead to it". Ideally also, there should be no gaps, every possible number (at least between zero and some maximum) should correspond to a valid combination of inputs; however, as long as you aren't expecting to deal with user input (or have means in place for detecting and handling invalid input), this rule is not critical to making it work. In order to achieve this, you should think of each piece of data you're putting in as a digit, then construct the value of digit positions from the range each piece of data can take. Notice the general rule of digits and digit positions in the various bases - the highest possible digit, is one less than the value of each position. In decimal, each digit position is ten times the one to its right (ones, tens, hundreds, thousands, etc - each is 10x the last), and the highest allowed digit is 9. In binary, each digit position is two times the one to its right (ones, twos, fours, eights, etc - each is 2x the last) and the highest allowed digit is 1. You don't have to use 10 or 2 here - if the highest value of any single digit (data point) you're encoding is 6, you could make each position increase in value by 7x (ones, sevens, forty-nines, etc). Perhaps you're encoding how many red, blue and green gems the player has obtained (when there's six of each in the game). The ones position represents red, the sevens position represents blue, the forty-nines position represents green. If the player has 3 red gems, 4 blue gems, and 2 green gems, then you go (3 x 1) + (4 x 7) + (2 x 49) = 129. The number 129 cannot possibly represent any other combination of 1's, 7's and 49's, as long as the input values for each position (number of gems) were indeed in the range of 0 to 6. To reverse this (note: more efficient ways exist when working with binary or other power-of-two bases specifically, but this is generally the best way in any non-power-of-two base AFAIK, including decimal), to check any particular position, you want to run the following operation, where b is the base (ie: one higher than the highest allowed digit; in this example, 7), p is the value of the position you're checking for (in this example, it'd be 1 for red, 7 for blue, or 49 for green), and n is the packed value you're trying to obtain the data from:

result = (n / p) mod b
(Note that / here represents integer divison, ie: immediately discard the remainder.)

Let's take an arbitrary number - 217 - and try and figure out, using the above encoding, how many blue gems the player has. I don't know either at this point - I didn't encode anything to make this number, I just picked an arbitrary number out of thin air. 217 itself is n; b is 7 as that's unchanged here; and we're looking for blue, represented by the 7s digit, so p is also 7. We throw that into the formula and get [(217 / 7) mod 7], which equals three. We can do the same calculations for the other colors too - I'll leave that as an exercise for the reader to figure out the steps, but if you've done it correctly, you should get...

Spoiler

No red, 3 blue, 4 green.

Want to take this a step even further? Okay so - in binary or decimal etc, each digit position is always some constant factor times the last. But for the whole number-packing thing in general, it doesn't HAVE to be. The rules to ensure that each value can be uniquely unpacked, with no gaps, are:

1. The smallest position is ones.
2. Each position's value is equal to the previous (to the right, digit-wise) value's position, multiplied by one higher than the highest value that position can hold.

So, let's say we want to encode talismans this time - bronzes, silvers and golds. But in our game, there are a total of 10 bronze talismans, 5 silver talismans, 3 gold talismans... and just for good measure, one platinum talisman.

One way we could approach this is by simply making each position able to hold up to 11 values (as there's 10 bronze talismans which is the highest of any of these values - the 11th value being zero). So we have a ones position, an elevens, a [121]s, etc. This would work, but there'd also be invalid values - for example, 74 would represent 8 bronze talismans and 6 silver talismans. There'd also be a total of 14,641 possible values - that's not really too bad, but if you were storing larger numbers (or more of them), you could end up going beyond the limits of an int or even long quite quickly (and floating-point values should never, ever be used for this purpose if possible, due to their imprecision - and certianly, once you get beyond the limits of ints / longs, floating point imprecision is going to rear its head; it won't be a problem while you're still well within int/long range, but then why not just use an int/long?).

We can instead approach this by using digit positions with a different value scale. The smallest one is the ones digit, which we'll use for bronzes (this is arbitrary - you could go the other way and have the ones digit represent platinums instead, or even do silvers or golds first, it doesn't matter as long as you're packing and unpacking them the same way around). There are 11 possible values for bronzes (the highest possible value being 10), so the next "digit" - for silvers - needs to be elevens. There's only six possible values for silvers (highest being 5 - again, don't forget about zero as a possible value), so the next digit will be [11 (silver digit position's value) x 6 (highest possible silver position digit value + 1)], or in other words, [66]'s, and that represents the golds. Finally, we need one more position for the platinum. The highest possible number of golds is 3, and the golds digit itself is worth 66, so to calculate the next position's value, [66 x 4], which is 264.

Using this scheme, our highest possible value is 527. That's far less possibility - and there's no gaps; every value from 0 to 527 represents some valid combination of talismans. Also, if you're doing the formula in full even when accessing the highest digit position in it, this will future-proof it - you can tack yet another piece of data onto it later, and (as long as you still stick to the rules about how you determine the value of digit positions) the only "breakage" would be that older versions will disregard the new data because they don't know how to interpret it - but they won't misinterpret it as, say, more than one platinum.

How does the formula for deconstructing it change though? The actual formula itself doesn't - it's still [result = (n / p) mod b]. N and P remain as they were before - the input value, and the value of the digit position we're trying to extract. The only thing that changes is b. Earlier, for the case of a constant base (ie: every digit position increases by the same factor, like being 2x the last or 10x the last etc), I defined it as:

where b is the base (ie: one higher than the highest allowed digit; ...)

For this more-advanced case, we should focus on the "one more than the highest allowed digit". Specifically, the highest allowed digit of the value we're extracting.

So let's once again pick an arbitrary number and try and extract info using this formula. Our number this time shall be... 358. Let's find out how many gold talismans this represents. Plugging it into our formula, n is 358, p is 66 - those two are easy. And as per the note above, b is 4 - because the highest allowed value for golds is 3, and we want one higher than that. So - [result = (358 / 66) mod 4] - 358 represents the player having just one gold talisman. And again, I'll leave it to the reader to try and work out the other ones; the answers you should get are:

Spoiler

1 platinum, 1 gold, 2 silver and 6 bronze

I'm sure there's some parts here that weren't perfectly clear, but I do think focusing on the results (and in particular, understanding that the relevance of binary / bits is mostly limited to "if the way you've encoded things lines up with binary, this allows some really efficient ways to handle it in code") will be helpful here.

[WillLem]

Thanks for the explanation namida, I skim read it for now but I'll have a proper look later and see if I can solve the included gem puzzle!

I've very briefly worked with this sort of thing when I fixed (what I consider to be) a bug in the Nintendont GameCube Emulator code base: the button press to restart the emulator is [L + R + Z + B + Down], which might seem like a combo that would never get pressed in a game, but only to people who've never played SSX Tricky!

The Nintendont code applies button combos using a numeric system to represent the buttons. I can't remember off the top of my head exactly what it was, but it was something like "02884" would represent a certain combination of buttons, where that particular string of digits would only be possible if those buttons were pressed. Getting the right number to reconfigure the buttons, then, was quite tricky, but I managed to figure it out and ultimately update the restart combination to [L + R + Start] by finding the right string of numbers that represented those exact buttons.

Thankfully, the Lemmini code doesn't do this sort of thing without giving things a proper name that can be used in a standard method, so there's no need to necessarily do any of that sort of thing in this particular context. It's more a case of finding out where exactly the trigger area stencil is built, and how to inject priority-based read/write for it. The fact that it uses bits is significant, though, and worth understanding even if it can all be done via standard operators.

[WillLem]

result = (n / p) mod b
...
(questions)

My answer for the first question

0 red, 3 blue, 4 green.

I'm not sure about the second question (regarding talismans), I'm not sure I understand exactly what the value of p and b should be for each talisman.


@Simon

Are you free again any time this week to help me finish off the refactoring for stencil prioritisation? I've pushed some commented-out code to the repo (commit c02a201), could do with a bit of guidance with the next few steps if you wouldn't mind helping me out with it.

The end result should be: the Stencil get/setMask methods decide whether or not to overwrite the existing mask, based on a priority list that we decide. We also need to take into account object ID (this part is a total pain, kinda makes me wish each object just has its own separate stencil like with NL (and Lix?), but that would require much further-reaching refactoring throughout the rendering code so let's just work with what we have).

[namida]

I'm not sure about the second question (regarding talismans), I'm not sure I understand exactly what the value of p and b should be for each talisman.

In earlier examples, the place value (as a multiple of the next one) was constant for each place, but the same concept applies here.

We have four digit positions - platinum, gold, silver, bronze. We'll assume we're going with the order of platinums being in the highest value digit, and bronzes in the lowest value (ie: ones) digit.

So we have the lowest position, bronzes, and the lowest one is always ones. There are 11 possible values for this position - as we can have up to 10 bronzes, and zero is also a possible value. The next position, for silvers, is thus 11's (11 possible values x position value of 1). There's six possible values for silvers (0 to 5), so the next position, for golds, is 66 (6 possible values x position value of 11). Etc.

We still determine P the same way as in the simpler case. It's the value of the digit position we're looking for. So for example - if we were looking at bronzes, it'd be 1. Silvers, 11. Golds, 66. It might be slightly trickier to work out those position values in the first place, but once we know what they are, using them works exactly the same way.

As for B, it's the number of possible values for the position you're currently looking at - the same number you'd multiply by this position's value, in order to get the next position's value.

The underlying concept is still the same as in the simpler case. We're just using digit positions that have different maximum values from each other. And in fact, we can see a real-life case of this too - with times, when divided into hours/minutes/seconds. We have some positions that go up to 9 (XX:XX:XX) and others that only go up to 5 (XX:XX:XX). If you've ever written your own code to convert between hours/minutes/seconds and just total seconds (or some metric subdivision thereof), you've already worked with this concept!

(I should also just note - do not assume I have used the correct terms for things here. Simon can probably chime in with the actual terms. Focus only on the general concepts.)

[Simon]

I can offer Friday, 21st, 19:00 UTC.

Consider splitting the physics map into two parts. There will be a dumb part for terrain/steel/..., no gadgets. In the dumb part, every pixel can any subset of those types, and the logic will be outside the physics map. This is useful because the program wants dumb pixel data for existing logic elsewhere than during level initialization.

The second part will be gadgets, where every pixel stores at most one gadget and has the prioritisation logic and retrieval logic. If you want at most one gadget per pixel, then design your class to hold at most one. Design your problems out of existence.

Split the long level initialization into smaller methods. You'll find parts that can move into different classes.

Bloaters: Long methods, ...
Youtube: Venkat on Core Principles

-- Simon

[WillLem]

I can offer Friday, 21st, 19:00 UTC.

Sounds good, let's do it

Consider splitting the physics map into two parts.

This can absolutely be a long-term goal, but for now I'm thinking that both of our time on this is limited and I'd rather have your help to apply the proposed fix that we brainstormed in our previous session.

If you want at most one gadget per pixel, then design your class to hold at most one. Design your problems out of existence.

This, we might be able to do with what's already there. I'll need your help with the "how", but I can certainly point to where things are. This is a worthwhile goal for Friday, if we have time.

Split the long level initialization into smaller methods.

This we can definitely do with what's already there. I can make a start breaking the long method into smaller ones tomorrow in time for our session on Friday.

[Simon]

All right, Friday, 21st, 19:00 UTC.

-- Simon

[WillLem]

Many thanks to Simon for helping me figure out how to prioritise object triggers.

New behaviour: wherever trigger areas overlap, we always "prefer" whichever is highest in the hierarchy, with exits being top of the list.

Steel, OWWs and terrain are always written into physics as-is; they are unaffected by this update.

More investigation and refactoring of the codebase is needed for the cleanest possible implementation and future maintainability, but for now it's good enough for release. The behaviour has proven stable following tests on different levels and with different object setups, and the minimalist approach taken should ensure that it's easy enough to debug in the months following the release of 2.0.