Trying to fix my first bug: thoughts on capacity.

[Ranieri]

Dear Developers,

First of all, thanks for making UFOAI. You managed to really capture the xcom spirit. You are definitely on to something here, I enjoyed playing the game immensely. Of course, the thing being open source and all, it was only a matter of time before I got tempted to get the development files and have a look at the codebase.
Of course, just browsing code doesn't do much. I was silly enough to ask the guys on IRC if there was something small that needed doing, and they obliged.

After fixing a trivial display bug (that took me on a scenic route of .po files and .ufo scripts before I managed to track down the proper line, very educational) someone suggested I tried my hand at this one:
http://sourceforge.net/tracker/index.php?func=detail&aid=1801131&group_id=157793&atid=805242

I was not able to reproduce the bug by building a single small hangar and stuffing more than 2 stilletto's in. However, I did notice that you could destroy a full hangar without losing the planes stored therein. While it's technically a different bug, the effect is the same: more planes than you have space for.
Spurned by this I investigated the capacity subsystem and came to the following conclusions. Correct me if I'm wrong though, this is just what i gleaned from a preliminary look at the code.

* Planes are a special form of a general problem. With the exceptions of Aliens (who are destroyed when their containment is torn down) this problem exists with living quarters, storage, labs etc. It is worth putting some effort into a general solution.
* Capacity for different resources is handled at the building level. You have one building with cap 5 and one with cap 3, buy an item worth two units and it could be taken off either off the two leaving you with 3/3 or 5/1. I think it's taken off the oldest first if it has space.
* As far as I can tell however, the items are however not liked to the building, so if you are handed a building for demolition, you cannot tell what currently resides in it. You can tell whether it's empty or not, but the player has no provisions for moving items out.
* Moving capacity out is not guaranteed to work unless you can move it all to a new place in one block. The 5 could be made out of 5 items 1 big (so you can split them no prob) or one item 5 big. Then you can't.

Questions:

* Is there a way to trace contents back to a building that I missed?
* Are there utility functions to rearrange the contents of a set of buildings to empty one? This could be called before the tear-down. If this call is succesful, the tear-down could continue.
* If not, is it worth doing? Is there a better way?

Thanks for your time!

[Punkiee]

Is there something that can be stored in 2 different type of buildings? If not then there is no problem as every type of items/buildings can be linked to their storage/items. If yes, which?

[BTAxis]

Craft can be in different hangars. It's possible for large hangars to house small craft. I don't know if that's relevant, though. It probably doesn't use the item code at all.

[Ranieri]

As far as I can tell, the aircraft are specialcased almost everywhere. The algorithm for it is rather straightforward: Try are store small crafts in small hangars. If that's not possible, try storing them in large hangars. They do share most of the capacity code.
I'm not sure what you mean exactly with "item code".

If not then there is no problem as every type of items/buildings can be linked to their storage/items.

I follow your logic, but I do not agree that there is no problem. If my understanding of the code is correct (and it may very well not be, checking this reading was the main reason for this post) items are indivisible. That means that you can't just pool capacity between different buildings. Allow me to elucidate with an example:

Suppose add an item (which can be a craft, an actual item, an alien, whatever) with a size of 4. Suppose I have a building with remaining capacity 3, and another with remaining capacity 2. Although there should be enough capacity left in the base to accommodate the item (with one to spare even), neither of the buildings has enough space to house it in its entirety.
Now you could re-shuffle items to make enough room in one of the two stores for the new item, but that would require knowing the sizes of the items in the buildings to make sure you are not splitting any indivisible items. Note that even if you do know the item sizes this degenerates into the knapsack problem which is known to be NP complete.

So, let's take a step back and answer these questions first:

• Are items supposed to be indivisible?
• Are items currently indivisible?

Indivisible items are cool, but they require tons more bookkeeping than simple base-level capacity pooling.

[Zenerka]

* Is there a way to trace contents back to a building that I missed?

For aircrafts - yes (int hangar in aircraft_s struct). For any other case - no.

* Are there utility functions to rearrange the contents of a set of buildings to empty one? This could be called before the tear-down. If this call is succesful, the tear-down could continue.

There is not and I am afraid it is not possible to do that (or at least not with a lot of code). With the current code, if you have two storages with tons of stuff (both storages are full), and you will destroy one, the stuff stored in first one is not removed so basicaly we just overflow the capacity so you cannot buy/produce anything (like in the real life, if you have to empty your one room, you move all the stuff in there to another room creating a real mess in it). This of course should not be the case when your storage is destroyed in UFO attack, but such way is not implemented yet.

* If not, is it worth doing? Is there a better way?

I don't know. For some cases like destroying building by UFO, the whole content of such building should be destroyed too, but I do not have a clue how to easily implement it now. (For example every item should track the building index in base when being added, to be removed when building is destroyed -> PITA).

[Ranieri]

Okie-dokie. It sounds like the behaviour is, at least until we decide to change it, by design.

I won't bother you guys with it again unless we come up with some alternative spec first.

[Crab]

This of course should not be the case when your storage is destroyed in UFO attack, but such way is not implemented yet.I don't know. For some cases like destroying building by UFO, the whole content of such building should be destroyed too, but I do not have a clue how to easily implement it now. (For example every item should track the building index in base when being added, to be removed when building is destroyed -> PITA).

There is an easier way:
1. find out how many 'storage space' of items were stored in the building. (for example - if there is 4 storages, then 25% of items are in one of them)
2. just destroy items at random, counting how many 'storage space' they used to take, until needed number of 'storage space' is destroyed.