Civilization III BIX/BIQ file format

[AlanH]

But the underlying terrain is the same in all Dianthus' situations. This is what I saw. There seems to be a random element coming into the selection of the overlay icon.

[edit] Or are you saying that the plains icons in a pure plains underlay are actually different icons?

[Legend]

Yes. There are 16 distinct "all grassland" icons/tiles, and I think there are quite a few "all Plains" ones (maybe even using tiles from different files). Marking them with numbers, and with different colours for different files really makes it easy to tell!

I did a few tests:

Any hill not connected to another hill is always icon "0".

Two hills north-west/south-east are MOSTLY 2 and 8 (IIRC, verify later), and two North-East / South-West are MOSTLY (can't remember). However, there are certain situations where the two hills are both "0" (not 'joined'). This happens on certain combinations of underlying tiles. You get similar behaviour for three joined tiles.

[Dave_Shack]

For the "which icon to use" questions, I wonder if the x/y coordinates of the square come into it? As a programmer, if I wanted the appearance of a random distribution but wanted it repeatabile so the same map always looks the same, I'd hash the x/y somehow to come up with an icon index.

[AlanH]

The TECH data structure shows a length of 104. The byte count for the listed structure adds up to 108. 104 is the correct length for vanilla, and probably for PtW, but a C3C version 1.22 file I'm checking has a length value of 112. There appear to be two extra LONGs on the end, not just the one for flavours that's listed.

Anyone else seen this? Or is it just me?

[Legend]

Yes - I see two. I don't know what one of them is (I mark it as "unknown", but the other is "Flavour".

[Quintillus]

I debated whether to bump this thread or post at CFC, but all the context and background information for this post is here, so I decided to post here. In particular, this post relates to questions starting with AlanH's post #42 on page 2. The large versions of the attachments are only visible on the old server, and you can jump to page 2 of this thread there with this link.

I've been looking into the layout of mountains/hills, and after alot of going like this: , I encountered a pattern. But first, I'll detail the failed attempts.

I initially tried to go on the idea that the icon purely depended on whether hilly/mountainous terrain was to the SE/SW/NW/NE, using the same formula for determining the icon that Dianthus posted here. While it was close enough to verify that it did work sometimes, it didn't hold up even on a small scale (I was using Iceland in Paasky's WWII Europe scenario as a testing ground). I noticed that some of the snow-capped mountains would work if they only considered which mountains (not hills) were around them, but unfortunately this didn't work for all the snow-capped mountains. It also couldn't explain why one of the hills in Paasky's Iceland was affected by a nearby mountain, but the other wasn't. No matter what sort of special relations between mountains/snow mountains/hills I tried, two particular snow mountains (26, 8) and (27, 9) wouldn't fit in right. So, while a relatively straightforward approach, it didn't work.

Legend's idea that the overlay terrain depended on the icon of the underlying terrain was appealing, even if it were to depend both on the underlying terrain and file. I created a blank map with a large plains, and some two-snow-mountain chains running NE-SW (see attached BIQ in a ZIP, Annoying Mountains.zip Annoying Mountains.zip). For all the sub-chains in the NE chain of 5 sub-chains, I put the NE mountain first; for the lower (SW) chain, I put the SW mountain first. There didn't seem to be any rhyme or reason to which ones formed chains and which one didn't. Like Legend said, most of them formed chains, but some didn't.

I then printed out some diagnostics of the mountain tiles. I copied diagnostics about three of the sub-chains into WordPad documents. The results are visible in the attached JPG. WordPadComparison.jpg Take note especially of the right two chains (four documents). The middle chain is a Civ3 range; the right is standalone Civ3 mountains. But they have the same image and file data! The sum of their indices in the TILE array (401+450, 704+753) are also both odd. Thus no pattern can be derived from either the icons of the underlying terrain, or the indices of the TILES.

However, just as I was thinking the formula may be so convuluted that it wouldn't be decodable, I hit upon a pattern. I created a new map in the editor, put in a big plains, and put a two-mountain NE-SW chain with the NE mountain at (5, 5), just like in Annoying Mountains.biq. They were standalone mountains. I created a new map, did the same thing, and they were standalone again. And again, and again. I tried with tundra instead of plains, and they were standalone again. Other mountain chains, such as the one whose NE mountain is at (6, 12), also retained their standalone/range properties. I tried different map sizes, as well - even on a 16x16 Ubertiny map, the chains occupying the same tiles retained the same properties.

So I think Dave_Shack is headed down the right road. I haven't figured out what the formula is yet, but that idea is the only one that's giving consistent, repeatable results, across a wide variety of conditions. I'll be working it some more, but if anyone else notices anything (or has in the past five and a half years), that'd be great.

[Quintillus]

I've continued to look into this, and Dave_Shack indeed did have the right idea. I have figured out how to determine if any two mountains will connect on a NW/SE basis, and once I convert it into a nice explicit formula, I'll post it here. (Currently it's a recursive formula that requires you to go back to tile (0, 0) to figure out if you connect mountains or not !).

NE/SW is more difficult. The good news is, I have found at least one repeating pattern. The bad news is, I've only found it in one place. I think I'll need to get quite a bit more data to figure out the overarching pattern. If I can't figure it out, I'll post some organized notes (right now my notes for NE/SW are not organized at all and probably quite confusing to anyone other than me), and maybe someone else will be able to spot the key pattern.

In another bit of good news, the NW/SE connection rule appears to apply even if the mountains involved also have connections to the NE or SW. They also appear to apply regardless of whether it is snow-capped mountains, regular mountains, or hills involved. I won't say 100% until I can verify tiles all over the map with the help of an explicit formula, but it certainly appears to be the case.

[Quintillus]

With more and more data, the recurrent patterns are too obvious to miss in NE-SW chains. However, they abruptly and sometimes inconsistently end, sometimes morphing into a different recurrent pattern, sometimes seemingly becoming random. I've screenshotted my spreadsheet below:



Highlighting or border-coloring indicates a recurrent pattern (I had to use both due to occasional overlap). A lighter highlight or border-coloring of the same basic color indicates the pattern occuring in reverse. While the blue pattern may in fact be random, the others are long enough that I highly suspect they are not random/coincidental. Unfortunately, I haven't been able to figure out why, for instance, the orange pattern is sometimes preceded by 2, 3, but not other times. There has to be some algorithm as to when these recurrent patterns occur (so the editor can handle whatever map sizes it is given), though, unless Firaxis manually input numbers for 65,000 possible tiles (to cover 362x362 and everything smaller) and just used copy-paste occasionally. We can rule that out as maps larger than 362 tiles in any one direction do work properly in Civ3 Conquests itself, implying there must be some algorithm at work.

What, you may ask, do these numbers mean? First, the maps. I have two maps for this spreadsheet, Mountain Patterns 3.biq and Mountain Patterns 6.biq. In each one I make long ranges of NE-SW snow-capped mountain chains going from the very top Y row (Y=0) to the very bottom Y row (Y=99). The two files are so that there are no NW-SE contacts in these long chains (I could still do that with those, but it's easier to spot the graphics I need this way, as there are fewer of them). MP3.biq includes the chains starting at (0, 0), (4, 0), (8, 0), etc. MP6.biq includes the chains starting at (94, 0), (98, 0), (2, 0), etc.

The StartX is then the X coordinate of the northernmost mountain in one of these chains - that mountain is at (x, 0). I get the number in the Partial column by going SW from the (x, 0) upper bound of the chain I am interested in until I hit the graphic representing a snow-capped mountain that has a neighbor only on the northeast (or, the graphic representing a standalone mountain). The count of how many mountains occur until I hit that graphic is the number in the Partial column for that chain. I then repeat the process until I reach the southernmost mountain in
the chain, at (newX, 99). The last count, ending at (newX, 99), goes in the Final column. If an entry lacks a Partial and/or Final entry, I didn't include that data, and the numbers entered are guaranteed not to bound on the nothern/southern edge of the world. Missing entries before a Final column are not a problem, as chains with more 5- and 4-length chains before the NE-only border graphic will have fewer columns in the spreadsheet.

The "real" and "fake" labels should be taken with a grain of salt. They relate to the possible concept of the chains wrapping. At one point I thought perhaps the chains wrapped around from south to north. However, I now rather doubt this. This also explains the 3(2+1) for the Partial in StartX 98 - the actual partial is 2, with a possible 1 carryover from wrapping. This conveniently fit the pattern in light green.

Below are two attachments. One is the BIQs I used. I could auto-generate the mountain chains, but thus far have not. The other is the spreadsheet as well as my plain-text notes. From the plain-text notes can be derived any Partial or Final values missing in the spreadsheet. The [ends at (x, y)] notes can also be used to trace where exactly these patterns occur in the BIQ files, and verify that the data in the spreadsheet is correct. Being a notepad, the notes also includes in-search thoughts, some of which were fruitful and some weren't.

Mountain Patterns.zipMountain Range Notes.zip

While this approach has established that there are patterns in NE-SW chains, I'm uncertain whether it will result in the algorithm we are seeking. More data may be enough to unravel it. However, a few other possibilities exist:

• The X=0 column is really important and I'm making a big mistake by making Y=0 my point of reference. While I'm afraid of this, I should also note that simply starting at Y=0 and working NE does not solve the problem of the # of tiles before a "SW only border" graphic appearing follows no obvious pattern. So I don't see any compelling reason to believe that would make the solution more obvious.
• What might be more helpful is noting all the tiles at which "NE only" graphics occur. The NW-SE chains were easy to derive from the X,Y coordinates, with an easily recognizable pattern when NW/SE was observed with no NE/SW influence. However, no such pattern exists for NE/SW. Perhaps looking at all the "NE only" graphic locations (or all the "SW only" locations) would make a mathematical pattern become evident.

Either way this is probably a labor-intensive process (unless someone spots the key pattern with just a bit more labor input). This possibility exists to set C3CEdit to 25% zoom and screencap a whole bloomin' Tiny World, and then use image recognition to try to automate it, but I feel like writing the code for that might take longer than just doing it manually.

Questions on the notes/spreadsheet are expected, as they're basically scratchwork. I also do still plan to formalize the NW/SE pattern, but kind of want to figure out this puzzle first.

[Quintillus]

I have completed a slightly less-recursive version of the formula for determining if mountains connect to the southeast or northwest. It's still a bit long, so I've decided to simply post my code segment. It is in the Java language (version 1.5 or later, although earlier may work, with Log4J [otherwise take out all the logging statements]):

                //Fragment from another method
                //Base terrain 5 is hills, 6 is mountains
                //Does the tile connect to the southeast?
                boolean southeastConnection = southeastConnection(xpos, ypos);
                //If the tile directly SE isn't a mountain, there is no SE connection regardless
                if (getTile(xpos + 1, ypos + 1) == null)
                    ;
                else if(getTile(xpos + 1, ypos + 1).getBaseTerrain() != 6 && getTile(xpos + 1, ypos + 1).getBaseTerrain() != 5)
                    southeastConnection = false;
                //Does the tile connect to the northwest?  Assume yes, then figure out if it doesn't.
                boolean northwestConnection = true;
                if (getTile(xpos - 1, ypos - 1) == null)
                    ;
                else if(getTile(xpos - 1, ypos - 1).getBaseTerrain() != 6 && getTile(xpos - 1, ypos - 1).getBaseTerrain() != 5)
                    northwestConnection = false;     //Northwest
                //If the tile NW doesn't connect, this one won't either.
                if (!(southeastConnection(xpos-1, ypos - 1)))
                    northwestConnection = false;

    /**
     * Returns true if and only if, in an infinitely extending NW-SE chain of
     * mountains/hills, the mountain at (xpos, ypos) will visually
     * connect to the mountain directly to its southeast.
     *
     * This is determined by figuring out if the mountain at (xpos, ypos)
     * will *NOT* connect to the mountain directly to the southeast, as this
     * is the rarer condition, and then returning the opposite of what that
     * calculation determines.
     *
     * @param xpos - The x position of the mountain/hill in question.
     * @param ypos - The y position of the mountain/hill in question.
     * @return - Whether, in a chain of mountains, that mountain/hill will
     * connect to the mountain/hill to its southeast.
     */
    private boolean southeastConnection(int xpos, int ypos)
    {
        //check for top of map.
        if (ypos < 0 || ypos >= wmap.height - 1)
            return false;
        //NW/SE
        int numberOfFives = ypos/5; //(to nearest integer)
        int baseX = xpos;
        int baseY = ypos;
        //But we need baseX to be >= baseY if this is going to work.  So if it's less, add the width to it.
        if (baseX < baseY)
            baseX = baseX + this.wmap.width;
        baseX = baseX - 5*numberOfFives;
        baseY = baseY - 5*numberOfFives;
        //(BaseX, BaseY) will be in the first 5 rows and will be 5z tiles NW of the one in question, z an integer
        //Now, there are 5 key tiles - (0, 0), (4, 2), (8, 4), (7, 1), and (11, 3).  These are the first tiles where
        //a "No SE" block occurs
        boolean noSE = false;
        if (logger.isTraceEnabled())
            logger.trace("baseX, baseY: " + baseX + ", " + baseY);
        while (baseX >= 0)
        {
            if (baseX == 0 && baseY == 0)
                noSE = true;
            if (baseX == 4 && baseY == 2)
                noSE = true;
            if (baseX == 8 && baseY == 4)
                noSE = true;
            if (baseX == 7 && baseY == 1)
                noSE = true;
            if (baseX == 11 && baseY == 3)
                noSE = true;
            baseX-=5;
        }
        if (logger.isTraceEnabled())
            logger.trace("X: " + xpos + ", Y: " + ypos + " connects SE? " + !noSE);
        return !noSE;
    }

    /**
     * Returns the TILE specified by its x and y positions.  This involves
     * converting the 2D location into a 1D location in the TILE array.
     * @param xPos
     * @param yPos
     * @return
     */
    public TILE getTile(int xPos, int yPos)
    {
        int index = 0;
        //always add in a width-worth * yPos/2 (truncated)
        index+=((yPos/2)*(wmap.width));
        if (yPos % 2 == 1)  //add in half a width worth of tiles
            index+=((wmap.width)/2);
        index+=xPos/2;
        try{
            return tile.get(index);
        }
        catch(java.lang.IndexOutOfBoundsException e){
            return null;
        }
    }

wmap refers to the World Map section of the BIQ; I think otherwise the variable names are either intuitive or explained in the code. I can clarify them if need be.

My more recursive explanation, which I first came up with, follows:

If we start at (0, 0), the first "Most SE" graphic in a chain starting there is at the 1st position - (0, 0) = (0, 0) + (0, 0)
For each jump directly E (first to (2,0)), we add 2 to the index of the 1st "Most SE" graphic - it is the third graphic for the next NW-Se chain at (2, 0)
It is the fifth graphic for the chain starting at (4, 0)
And then the second graphic for the one starting at (6, 0), because we take a modulus five
The fourth for the chain starting at (8, 0)
And the first again for the chain starting at (10, 0)

And we can figure out whether a graphic further south is the "Most SE" one by figuring out if it is an offset of (5x, 5y) from a "Most SE" graphic in the top 5 rows.  Thus, the chain starting at (4, 0) has "Most SE" graphics at (8, 4), (13, 9), etc.

That definition isn't as formulaic and thorough, but may be more understandable. Both may well be improveable, to either simplify them or speed them up, but most importantly, the Java method does work correctly.

For determining the graphic to use, you then follow the formula in Dianthus's post #43, using northwestConnection and southeastConnection to determine whether to add 1 and 8 for NW/SE respectively.

I unfortunately have not been able to figure out what the formula for NE-SW chains is. I'm simply always adding 2/4 for NE/SW, respectively, which doesn't always match up with Civ but does more than half the time. At this point I've decided to throw in the towel on figuring that out and go forward with other things in life. But I'm uploading my most recent spreadsheets and notes so that if someone else cares to look, they can have a base of information to start from.

Mountain Chain Search NE SW.zip