Sunday, 10 May 2009

Here be dragons

I've advocated the use of arrays elsewhere, but I appear to have tripped over a big array related issue in Unangband.

For a little history, I've included the following comments from the start of cmd6.c describing a known issue relating to the fact the inventory is an array of items:

* There may be a BIG problem with any "effect" that can cause "changes"
* to the inventory. For example, a "scroll of recharging" can cause
* a wand/staff to "disappear", moving the inventory up. Luckily, the
* scrolls all appear BEFORE the staffs/wands, so this is not a problem.
* But, for example, a "staff of recharging" could cause MAJOR problems.
* In such a case, it will be best to either (1) "postpone" the effect
* until the end of the function, or (2) "change" the effect, say, into
* giving a staff "negative" charges, or "turning a staff into a stick".
* It seems as though a "rod of recharging" might in fact cause problems.
* The basic problem is that the act of recharging (and destroying) an
* item causes the inducer of that action to "move", causing "o_ptr" to
* no longer point at the correct item, with horrifying results.
As it turns out, Unangband doesn't have a "staff of recharging". But it does have items which can cause reordering to items earlier in the inventory as an "effect". The example the bug was logged for was a scroll of fire proofing, which can be applied to a single magic book. Magic books occur earlier in the inventory than scrolls, so the unstacking process which automatically occurs to get a single magic book from a collection of such books causes the inventory to reorder. The only reference to the scroll is an array index, which is no longer valid, and causes some other object to be used up instead.

I initially thought that just eliminating any item from the game which could potentially effect items earlier in the inventory would be sufficient. But because I've made it possible for the player to hit themselves with spells, anything which could destroy items in the inventory qualifies. And that means a whole lot of items.

The correct solution is reimplementing the inventory as either a linked list, or an array of pointers to items. But that's a lot of work.

So I'm going to mark the item which needs to be consumed with a flag before applying the "effect" and then relocate the flagged item in the inventory afterwards. It's a hack, but I hope a forgiveable one.


Nick said...

Seems like a reasonable solution. Incidentally, I get around the specific fireproofing problem in FA by making the item tester only return items which are already single - at least, I did that because it was easier, and never even thought of the unstacking problem :)

Jonathan S. Fox said...

In Liberal Crime Squad, an STL Vector object is used to store an array of pointers to all the characters you've recruited to your cause. Some way is needed to find a recruit in this vector on demand, for many reasons.

Since LCS does use a vector of pointers, and not a vector of objects, storing the memory address itself will work for individual function calls, but even with this solution, LCS requires permanent references to other objects stored into objects. For example, every character must remember who he or she was recruited into the organization by. Storing a pointer into another object won't work here though, because it jams up saving.

It might be tempting, then, to address recruits by index into this vector, which will be stable across save and load. But in that case, the vector has to always be stable, from new game to end game; this would create memory wastage as recruits die off or lose contact and get deleted from the game, and it would start to slow down the many parts in the game that loop over every recruited character.

In order to support reorganizing the list of characters at will, every character in the game is labeled with a unique ID number. A single helper function then allows looking up a character by ID number, instead of index. This function just loops through the vector, comparing ID numbers, and then returns a pointer or reference to the character requested.

This is an easy solution to the problem you're describing (and also much larger problems arising from arrays getting reordered) that requires minimal code overhead, just a couple of support functions of no more than five lines or so. It requires several bytes more per object you're tracking with ID numbers, but that's it. And because the ID numbers are completely memory independent, they've extremely save-friendly.

That being said, the problem you're running into is a very small issue, and it doesn't need a "big guns" solution like assigning unique ID numbers to every item in the game. You just need the array to be stable for a very short period of time. You mentioned converting the inventory into an array of pointers would work. But with the minimal requirements you need, your solution, to simply not reorganize the array during that brief period of time that you have to address something in inventory, seems perfectly reasonable to me. Are you ever really going to need something more robust?