Author Topic: Outpost 2 mapper auto-tiling ruleset & new tiles  (Read 6633 times)

Offline Vagabond

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 1013
Outpost 2 mapper auto-tiling ruleset & new tiles
« on: April 14, 2018, 11:28:28 AM »
Hey everyone,

As a lot of you know probably know, we do not have a auto-tiler that can can automatically places transition tiles on an Outpost 2 map. I've played with the mapper a fair amount and verified with others on mirc that the wells (tilesets) in Outpost 2 do not actually contain a full set of transition tilesets to play with. See the picture below for what I'm talking about.



Basically, we need transition tiles to line up in the same place between each tile. Outpost 2 sometimes has multiple transition tiles for the same transition, with each one lining up at a different spot on the map from each other. Sometimes the transition tile just doesn't exist.

In light of someday getting a more friendly mapper created, it would be nice to have a solid auto-tiler-placer that handled putting down transition tiles automatically.

I would like to document the current state of transition tiles in the game with the goal of determining exactly which transition tiles are missing. Before I put any time into it though, I wanted to ask around and see if anyone already has the data sitting around. If so, it would be great to post it here to reduce duplicating work. I know some people have looked into the problem before, I just don't know if they have anything useful written down.

Outpost 2 is capable of accepting more tilesets and individual tiles. I think we have plenty of space for more tilesets. If I remember correctly, there isn't room for very many new tiles though. Does someone happen to know how many more tiles we can add to the game, assuming all current tilesets are loaded into a map?

If we can create a new tileset containing the missing transition tiles and distribute it with the game without exceeding the allowed tile count, this would be ideal. I do have an idea on how to get around the limit but perhaps someone smarter than me on memory hacking could modify the limit to be higher through HxD/OllyDbg? Anyways, I figure we should count and see how many more tiles are needed before worrying about getting around/increasing the limit.

Once the tiles are identified, it would be nice to have an artist step forward to design the missing tiles.

Outpost 2 tilesets are 8bpp BMPs with indexed color palettes. The stock Outpost 2 BMPs are all named well00XX.bmp and stored in art.vol (currently maps.vol until version 1.3.7 comes out). Each tileset is exactly 1 tile wide (32 pixels) and a varying number of tiles tall.  The key here is you only get 256 colors to work with on each tileset, although you can index the color palette and choose those 256 colors individually. Ideally all the new transition tiles would go on one sheet, but if more than 256 colors are needed, it wouldn't be a problem to add a couple of tilesets. I've used Gimp, a free open source image editor, and it allows messing with indexed color palettes, although I'm sure there are a lot of other tools available.

The idea here would be to provide the new tiles and a table of data that could be used when someone was ready to program an actual auto-tile-mapper. I'm willing to put time into documenting the ruleset and missing tiles, but I'm probably not who you want actually drawing the new tiles.

Thoughts?

Thanks,
Brett
« Last Edit: April 14, 2018, 11:30:36 AM by Vagabond »

Offline leeor_net

  • Administrator
  • Hero Member
  • *****
  • Posts: 2350
  • OPHD Lead Developer
    • LairWorks Entertainment
Re: Outpost 2 mapper auto-tiling ruleset & new tiles
« Reply #1 on: April 16, 2018, 05:21:02 PM »
What you're describing is the basics of an auto-tiling system but according to _A_ and BlackBox, the tiles aren't designed in such a way as to be auto tiled like that. I thought I'd try my hand at it because there are groups defined in the maps so there absolutely has to be some sort of pattern that can be eeked out of it even if it's not perfect.

In the editor that I started putting together, I have a Tilegroups palette that shows the tilegroup definitions. This is what you can find for the transition fringes:



They all more or less look like this. You also have the terrain 'base' sets which I discovered is how you basically do a sort of 'flood fill':



From what I'm seeing this is all very very doable, it's a matter of defining a rule set for applying terrain transition fringes and then applying it into the editor's tool set.

The code for the editor you see in the screenshots is up on git-hub: https://github.com/OutpostUniverse/op2-landlord

I use a modified version of the OP2Editor code -- basically I stripped out the COM and rewrote the input/output using byte streams in-memory. This was before the work you and Hooman did on the OP2Editor backend so it might be better to dump what I did and replace it with yours.

Offline Arklon

  • Administrator
  • Hero Member
  • *****
  • Posts: 1267
Re: Outpost 2 mapper auto-tiling ruleset & new tiles
« Reply #2 on: April 16, 2018, 08:46:50 PM »
Given that some dumb unused maps like the DIE! BUT HAVE A NICE DAY one still have decent tile transitions, I think Dynamix's map editor had an automated way to do it. But yeah, the tiles don't line up nicely for that, as least the way you'd typically think. Perhaps you need to think of the transitions at the 2x2, 3x3, or whatever-size block granularity, instead of the individual tile granularity?

Making new tileset graphics is probably never going to happen, unless you want them to look like the tacked-on MS Paint water and bridges in Mcshay's Greenworld maps (base Greenworld was just ripped from Total Annihilation).

Offline Vagabond

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 1013
Re: Outpost 2 mapper auto-tiling ruleset & new tiles
« Reply #3 on: April 17, 2018, 03:03:27 AM »
Quote
I use a modified version of the OP2Editor code -- basically I stripped out the COM and rewrote the input/output using byte streams in-memory. This was before the work you and Hooman did on the OP2Editor backend so it might be better to dump what I did and replace it with yours.

I would like to see your editor's backend work massaged into OP2Utility so we can unify the backend code between the mapper, OP2MapImager, and OP2Archive in one reusable place. Dumping is probably the wrong word as you may have functions that do not yet exist in OP2Utility that would need to be transferred over. I would be willing to help on this endeavor though it is out of scope for this thread.

Quote
Given that some dumb unused maps like the DIE! BUT HAVE A NICE DAY one still have decent tile transitions, I think Dynamix's map editor had an automated way to do it. But yeah, the tiles don't line up nicely for that, as least the way you'd typically think. Perhaps you need to think of the transitions at the 2x2, 3x3, or whatever-size block granularity, instead of the individual tile granularity?

I hadn't thought about working in multiple tiles for the transition. This concept would be more difficult to implement automated, but I think maybe you are right on how Outpost 2 did it originally. This is how the cliffs are done, where you line up chunks of 2x2, 3x2, etc tiles instead of automapping at the individual tile level.

After carefully reviewing the tile sets in OP2 Mapper, I put the images below together trying to unify individual transition tiles. It looks like we are missing 3 needed tiles on each transition to make it work. Also, tile 'L' on the dirt-rock transition does work, but maybe could be replaced by a better tile. If multiple tiles could satisfy a particular transition, they are displayed next to the tile they could replace. IE tile 'B' in the dirt-rock transition set had 2 tiles that seemed to transition in the same location.




This approach of looking at individual tiles would also discard a large number of the more interesting transition tiles unless they were touched in manually. However, if they were grouped into tile chunks as suggested by Arklon, they would be easier to add after the auto-tiler laid down a generic transition, even if the auto-tiler didn't take into account the tile chunks.

I'd still have to look at the rock-sand and the rock-lavaRock transitions as well. Assuming they are missing about 3-4 each, that would be a total of about 12-15 tiles that would be needed to make it work on a single tile transition solution.

Thanks,
-Brett
« Last Edit: April 17, 2018, 03:06:21 AM by Vagabond »

Offline Hooman

  • Administrator
  • Hero Member
  • *****
  • Posts: 4954
Re: Outpost 2 mapper auto-tiling ruleset & new tiles
« Reply #4 on: April 17, 2018, 03:25:00 AM »
We really need this. This would be a wonderful project if we got this sorted out.

The TileGroups do contain transition sets, as Leeor has pointed out, though the pattern is not clear. It's tantalizing though, as there does seem to be a pattern when comparing different transition sets, though there was some irregularity with one of them.

I think Arklon is right, in that Dynamix probably had an automated way to do the transitions. I'm just not certain what pattern they used, or if it's even really a pattern. Maybe there was some additional metadata about the tiles that aided transitions.

I see this more as a creating/recreating metadata problem, rather than a tileset extension problem. I think there are sufficient tiles there for decent results, it just might not present itself in an obvious way.

There is room for extending the tileset, though that feels like opening a whole new can of worms. I would rather not rely on tileset extensions to get smooth auto transitions. I wouldn't mind if we had a metadata approach that could accommodate new transition tiles, I just don't want to require that.

As an aside, maps can use a portion of the tiles from a tileset. If you wanted to work around the tile limit, you could do so by selectively using tiles from tilesets.


Related projects are the AutoMapMaker, TileSetOrganizer, and VirMask.

The AutoMapMaker scanned the existing maps to see which tiles have appeared next to each other, and used that data to create the fitness lists. The problem is, existing maps contain many errors and graphical glitches. As such, the fitness lists contained lots of errors.

The TileSetOrganizer was meant to classify the various TileGroups, though didn't include a breakdown of transitions within the transition groups.

The VirMask simulates the light/darkness and blight overlay. It uses a 2x2 grid to produce the correct overlay tiles. You may want to take note of the pattern. This relates to Arklon's comment about the 2x2, 3x3, or whatever-size block granularity comment.

Curiously though, the transition groups are 6x8 tiles = 48 tiles. This is not a power of 2. Most transition algorithms seem to work with on/off adjacent tile switches, and produce a power of 2 list of tiles for the transitions. They clearly did something else here.

One thing I had noticed, was some tiles appear to be a diagonal transition along the same edge, or like there was some variation in tiles for an otherwise identical adjacency. I never delved too deeply into this. Though it seems you've just pointed this out yourself.

Another point worth considering, is the pattern used for walls and tubes. That is another regular binary on/off adjacency algorithm. It's different from VirMask, as it's a different set of adjacent tiles that matter.


Cliffs are an even messier looking problem.

Offline lordpalandus

  • Banned
  • Hero Member
  • *****
  • Posts: 825
Re: Outpost 2 mapper auto-tiling ruleset & new tiles
« Reply #5 on: April 17, 2018, 01:39:18 PM »
Looks like an interesting jigsaw puzzle to me. Hope you guys figure it out!
Currently working on Cataclysm of Chaos, Remade.
Link to OPU page = http://forum.outpost2.net/index.php/topic,6073.0.html

Offline leeor_net

  • Administrator
  • Hero Member
  • *****
  • Posts: 2350
  • OPHD Lead Developer
    • LairWorks Entertainment
Re: Outpost 2 mapper auto-tiling ruleset & new tiles
« Reply #6 on: April 17, 2018, 07:57:14 PM »
I assumed that there was a lower granularity as Arklon mentioned. I don't think looking at it as individual tiles will work. That's the general feel that I've gotten.

Your mention of the seam issues confirms what I thought I'd noticed in a variety of maps. It tells me that the Dynamix developers went with a "this is good enough" approach. Perhaps we can do the same? It ultimately doesn't need to be perfect, just usable.

I'm also thinking that the way the tiles are set up, an algorithm won't be terribly effective. I imagined a lookup table of sorts... which meshes well with your suggestion of meta data. This is where the ruleset comes into play and we may need to actually manually set up the first set by actually looking at the individual tile indicies and then matching them up based on surrounding tiles. It'll be a bit of a chore but may be the only way to do it effectively.

Quote
Quote
I use a modified version of the OP2Editor code -- basically I stripped out the COM and rewrote the input/output using byte streams in-memory. This was before the work you and Hooman did on the OP2Editor backend so it might be better to dump what I did and replace it with yours.

I would like to see your editor's backend work massaged into OP2Utility so we can unify the backend code between the mapper, OP2MapImager, and OP2Archive in one reusable place. Dumping is probably the wrong word as you may have functions that do not yet exist in OP2Utility that would need to be transferred over. I would be willing to help on this endeavor though it is out of scope for this thread.

Can browse the code in GitHub here: https://github.com/OutpostUniverse/op2-landlord

Relevant files include the MapFile (header, source), TileGroup (header, source), TileSetManager (header, source) and the StreamReader/Writer classes (source directory). Note that StreamWriter is currently just an interface with no actual implementation (I got lazy, don't judge me).

The most interesting (I think) code is in the MapFile class: MapFile::load

NOTE: slight modifications to get the code syntax highlighter working without barfing

Code: [Select]
void MapFile::load(const std::string& filename)
{
    int temp = 0;

    try
    {
        File _f = Utility<Filesystem>::get().open(filename);
        File::RawByteStream stream = _f.raw_bytes();
        StreamReader stream_reader(stream);

        stream_reader.read(&mMapHeadInfo, sizeof(mMapHeadInfo));

        /**  Update map header fields */
        mMapHeadInfo.tileHeight = RoundUpPowerOf2(mMapHeadInfo.tileHeight);

        mTileWidth = 1 << mMapHeadInfo.lgTileWidth; /** Calculate map width */
        mTileHeight = mMapHeadInfo.tileHeight;

        int cellCount = mTileWidth * mTileHeight;
        mTileData = new int[cellCount];

        /**  Read in the tile data */
        stream_reader.read(mTileData, cellCount * MAP_CHUNK_SIZE);
        stream_reader.read(&mClipRect, sizeof(mClipRect));

        mTilesetManager = new TileSetManager(mMapHeadInfo.numTileSets, &stream_reader);

        readTag(&stream_reader, mMapHeadInfo.tag);
        /**  Something about units between reads of the tag. */
        readTag(&stream_reader, mMapHeadInfo.tag);

        /**  Load tile groups from file */
        int group_count = 0;
        stream_reader.read(&group_count, MAP_CHUNK_SIZE);
        stream_reader.read(&temp, MAP_CHUNK_SIZE);

        for (int i = 0; i < group_count; i++)
        {
            int width = 0, height = 0;
            stream_reader.read(&width, MAP_CHUNK_SIZE);
            stream_reader.read(&height, MAP_CHUNK_SIZE);

            /** TileGroupInfo _tgi; */
            TileGroup* _tg = new TileGroup(width, height, mTilesetManager);

            /**  Read in the tile data */
            for (int y = 0; y < height; y++)
            {
                for (int x = 0; x < width; x++)
                {
                    stream_reader.read(&temp, MAP_CHUNK_SIZE);
                    _tg->index(x, y, temp);
                }
            }

            _readTileGroupName(stream_reader, *_tg);
        }
    }
    catch (const std::string& errorMsg)
    {
        std::cout << errorMsg << std::endl;
    }
    catch (...)
    {}
}

Code: [Select]
readTag()
can be found in Common.cpp -- it's just a simple helper function.

Much of this is unchanged from the original implementation but with changes regarding the use of the StreamReader class which was modified to remove COM and use a 'raw byte stream' (basically just an unsigned char* buffer implemented as a std::string for memory management).

So basically, to sum up an overly verbose post, I removed the non-portable Windows stuff from the code and reimplemented some functions through a virtual fileystem (via NAS2D) and changed the drawing code to also take advantage of NAS2D. The filesystem stuff can be replaced with calls to C++11/C++17 filesystem calls instead (which is probably much more portable). The raw byte stream is basically just an unsigned char* buffer.
« Last Edit: April 17, 2018, 08:21:20 PM by leeor_net »

Offline Vagabond

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 1013
Re: Outpost 2 mapper auto-tiling ruleset & new tiles
« Reply #7 on: April 18, 2018, 01:39:59 AM »
Below is a link to BlackBox attempting to solve the autotiling of transitions back in 2006. The problem has remained unsolved for 12 years. I am still wanting to explore just adding ~15 tiles to the game and solving it that way with an easier and more standardized algorithm. Anyways, the post is probably worth reading.

https://forum.outpost2.net/index.php/topic,3153.0.html

That post mentions a map may contain up to a maximum of 512 tile sets and 2048 tiles. When I pull up a current map with all WELLs loaded, it contains 2011 tiles. So we should have 37 tiles to work with.

I added a new WELL with 15 new tiles to a map. There was an artifact at the bottom of each tile in the Mapper. Then when I loaded the map in Outpost 2, the tiles loaded as mostly whitespace with a little vertical strip of color. I was exporting the WELL from Gimp, so I'm guessing I need to fiddle with the settings some more on export to an 8bpp palettized index bmp.

Leeor,

OP2Utility contains a family of StreamReaders that is integrated with a class called MapData and the Archive code. MapData is basically your MapFile but does not contain any draw code. We would have to implement TileGroup and TileSetManager in OP2Utility and then I guess you would be off to the races. Is this something you want to try in the near future?

-Brett

Offline leeor_net

  • Administrator
  • Hero Member
  • *****
  • Posts: 2350
  • OPHD Lead Developer
    • LairWorks Entertainment
Re: Outpost 2 mapper auto-tiling ruleset & new tiles
« Reply #8 on: April 18, 2018, 11:49:56 AM »
I added a new WELL with 15 new tiles to a map. There was an artifact at the bottom of each tile in the Mapper. Then when I loaded the map in Outpost 2, the tiles loaded as mostly whitespace with a little vertical strip of color. I was exporting the WELL from Gimp, so I'm guessing I need to fiddle with the settings some more on export to an 8bpp palettized index bmp.

Think you already nailed it. Probably a format issue.


Leeor,

OP2Utility contains a family of StreamReaders that is integrated with a class called MapData and the Archive code. MapData is basically your MapFile but does not contain any draw code. We would have to implement TileGroup and TileSetManager in OP2Utility and then I guess you would be off to the races. Is this something you want to try in the near future?

In fact it is something I'd like to try. The editor I started working on is better fleshed out as an interface with a lot of potential features in the code base already -- the part I had some trouble with was loading and saving. I'd love to integrate the new code you and Hooman came up with, get something more standardized across all of these projects as they're all sort of inter-related.



Anyway, back to the topic at hand. If you think adding just the 15 tiles will make this doable, I say do it. We can then come up with the auto-terrain function and get OP2-Landlord as our new replacement editor (or another one if everybody would prefer that).

Offline Hooman

  • Administrator
  • Hero Member
  • *****
  • Posts: 4954
Re: Outpost 2 mapper auto-tiling ruleset & new tiles
« Reply #9 on: April 26, 2018, 02:35:26 PM »
That was good review reading through BlackBox's thread. All the horrors are coming back to me now.  :P

I've sort of thought about a ternary/trinary system for a while now, where a transition tile can expect either of 2 tilesets along an edge, or a don't-care third value. That could handle cases where 3 tilesets meet, which does happen in some of the original maps. Though I suspect that might only happen for corner tiles, so not very relevant if you're only considering edge adjacency.