TASVideos

Tool-assisted game movies
When human skills are just not enough

Bisqwit / Source / Image Tile Mapper

Image tilemapper

The tilemapper is a feature I have created for compressing the numerous images shown on this site into "blobs" that contain a number of screenshots in a single file. It also removes redundancy from the files by detecting identical tiles and storing them only once.

There is discussion about this feature on the forums.

Back to:
<< Bisqwit / Source
<< Bisqwit

tableoptimizer.cc

Table optimizer is a stand-alone C++ program for optimizing HTML tables. You feed it a list of table cells, and it tells you which cells can be merged together using colspan & rowspan settings. It uses a greedy algorithm which tries to maximize the number of cells that are made redundant by colspan&rowspan.

Each cell contains the following properties:

  • The background image (filename)
  • X and Y coordinates inside the image from where the background image for this cell can be found
  • The background color (optional). A non-empty background color implies that the background image will be ignored.

The table contains the following properties:

  • tilexsize and tileysize: The pixel dimensions of each cell (i.e. tile)
  • xsize and ysize: The number of tiles horizontally and vertically in the table.
  • The cells.

The output of this program lists the following properties for all the cells:

  • removed: Zero if this cell should be rendered, nonzero if it should be ignored when rendering.
  • colspan, rowspan: The colspan & rowspan attributes for this cell.

#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>

/*

This program reads a description of a table,
and outputs a plan of which cells can be merged using
a combination of colspan&rowspan, still such that no
two cell-spans overlap.

Copyright (C) 1992,2008 Joel Yliluoma - http://iki.fi/bisqwit/
*/

#include "tableoptimizer.hh"

struct Cell: public TableOptimizer::CellBase
{
    std::string blobfile, bgcolor;
    unsigned xpos, ypos;
    
public:
    Cell(const std::string& bf,
         const std::string& bg,
         unsigned xp, unsigned yp)
     : CellBase(),
       blobfile(bf),
       bgcolor(bg),
       xpos(xp), ypos(yp)
    {
    }

    bool CanExtend(const Cell& b,
        unsigned x,unsigned y,
        unsigned tx,unsigned ty) const
    {
        if(blobfile != b.blobfile) return false;
        if(bgcolor  != b.bgcolor)  return false;
        if(ty && bgcolor.empty())
        {
            if(xpos != b.xpos + x*tx) return false;
            if(ypos != b.ypos + y*ty) return false;
        }
        return true;
    }
};

static const Cell ReadCell(const char* arg)
{
    const char* cp = std::strchr(arg, ':');
    std::string blobfile(arg, cp);
    arg = cp+1;
    int xp=0, yp=0, chars_ate = 0;
    std::sscanf(arg, "%d:%d:%n", &xp, &yp, &chars_ate);
    arg += chars_ate;
    
    /*std::fprintf(stderr, "Created cell[%d,%d]: (%d,%d)\n",
        (unsigned)cells.size()%width,
        (unsigned)cells.size()/width,
        xp,yp);*/
    
    return Cell(blobfile, arg, xp, yp);
}

int main(int argc, const char* const* argv)
{
    if(argc < 5)
    {
        std::fprintf(stderr,
            "Usage: tableoptimizer <xsize> <ysize> <tilexsize> <tileysize> {<cell>}\n"
            "\n"
            "       Where <cell> is <blobfile>:<xpos>:<ypos>:<bgcolor>\n"
            "\n"
            "       Output consists of lines of <masked>:<colspan>:<rowspan>\n"
            "       Where <masked> is 0 if the cell should be rendered, 1 if skipped\n"
            "\n"
            "Copyright (C) 1992,2008 Joel Yliluoma - http://iki.fi/bisqwit/\n"
            "\n");
        return -1;
    }
    
    unsigned width = std::atoi(argv[1]);
    unsigned height = std::atoi(argv[2]);
    
    TableOptimizer::Table<Cell> table(
        width,
        height,
        std::atoi(argv[3]),
        std::atoi(argv[4])
    );
    
    for(unsigned p=0; p<width*height; ++p)
    {
        table.AddCell(ReadCell(argv[5+p]));
    }
    
    table.Optimize();
    
    table.Dump();
}

tableoptimizer.hh

#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>

namespace TableOptimizer
{

    /* The core of tableoptimizer.cc ...
     * Here because also binpack2d.cc uses it
     */
     
    struct CellBase
    {
        unsigned colspan, rowspan;
        bool     masked;
        bool     tried_1x1;
        bool     decided;
        
        CellBase()
          : colspan(1), rowspan(1),
            masked(false),
            tried_1x1(false),
            decided(false)
        {
        }
        
        bool CanExtend(const CellBase& /*b*/,
            unsigned /*x*/,unsigned /*y*/,
            unsigned /*tx*/,unsigned /*ty*/) const { return false; }
    };

    template<typename CellType>
    struct Table
    {
        unsigned width, height;
        unsigned tilewidth, tileheight;
        std::vector<CellType> cells;
        
    public:
        Table(unsigned w,unsigned h, unsigned tw,unsigned th)
            : width(w), height(h),
              tilewidth(tw), tileheight(th),
              cells()
        {
            cells.reserve(w*h);
        }
        
        void AddCell(const CellType& cell)
        {
            cells.push_back(cell);
        }
        
        void Optimize()
        {
            unsigned bestw = 0, besth = 0, bestx = 0, besty = 0;
            
            for(unsigned x=0; x<width; ++x)
                for(unsigned y=0; y<height; ++y)
                {
                    // Find out what kind of rowspan/colspan would be possible at this slot
                    CellType& cell = cells[cp(x,y)];
                    if(cell.masked) continue;    // part of another span-cell
                    if(cell.tried_1x1) continue; // already found to be simply 1x1
                    if(cell.decided) continue;   // already decided to be a span-cell
                    
                    unsigned maxcol = width, maxw = 1, maxh = 1;
                    for(unsigned y2=y; y2<height; ++y2)
                    {
                        unsigned w=0, h=y2-y;
                        for(unsigned x2=x; x2<maxcol; ++x2)
                        {
                            const CellType& cell2 = cells[cp(x2,y2)];
                            if(cell2.masked || cell2.decided) break;
                            
                            if(!cell2.CanExtend(cell, w,h, tilewidth,tileheight)) break;
                            ++w;
                        }
                        if(w < 1) break;
                        ++h;
                        unsigned size = h*w;
                        if(size >= maxw*maxh) { maxw=w; maxh=h; }
                        w += x;
                        if(w < maxcol) maxcol = w;
                    }
                    //fprintf(stderr, "Suggest(%d,%d): %d,%d\n", x,y, maxw,maxh);
                    if(maxw*maxh > bestw*besth)
                    {
                        bestw = maxw;
                        besth = maxh;
                        bestx = x;
                        besty = y;
                    }
                    if(maxw == 1 && maxh == 1)
                    {
                        cell.tried_1x1 = true;
                    }
                }
            
            if(bestw > 1 || besth > 1)
            {
                //fprintf(stderr, "yay, %dx%d at %d,%d\n", bestw,besty, bestx,besty);
                MarkRectangle(bestx,besty, bestw,besth);
                Optimize(); // tail call, find more spans
            }
        }
        
        void MarkRectangle(unsigned xpos,unsigned ypos, unsigned width,unsigned height)
        {
            for(unsigned y=ypos; y<ypos+height; ++y)
                for(unsigned x=xpos; x<xpos+width; ++x)
                {
                    CellType& cell = cells[cp(x,y)];
                    if(x == xpos && y == ypos)
                    {
                        cell.colspan = width;
                        cell.rowspan = height;
                        cell.decided = true;
                        cell.masked = false;
                    }
                    else
                        cell.masked = true;
                }
        }
        
        void Dump()
        {
            unsigned ncells = width*height;
            for(unsigned cellno=0; cellno<ncells; ++cellno)
            {
                std::printf("%d:%d:%d\n",
                    cells[cellno].masked,
                    cells[cellno].colspan,
                    cells[cellno].rowspan);
            }
        }
        
        unsigned cp(unsigned x,unsigned y) const { return x + y*width; }
    };
}

image_tilemapper_fun.php

This module contains the function TilemapImage(), which, when given an image collection image and a list of sections describing the locations of individual images inside that collection image, generates a compressed image and the description how to decode each of the individual source images from it.

<?php

function TilemapImage($im, &$sections)
{
  $alltiles = Array(); // crc32 => (xs,ys, xpos,ypos, doneflag)
  
  foreach($sections as $sectname => &$sectcoords) // xs,ys, xpos,ypos, sizex,sizey,tilelist
  {
    $width  = $sectcoords[0];
    $height = $sectcoords[1];
    $xpos = $sectcoords[2];
    $ypos = $sectcoords[3];
    $sizex = $sectcoords[4];
    $sizey = $sectcoords[5];
    
    if(!$sizex || !$sizey)
    {
      CalculateOptimalTilesize($width,$height, $sizex,$sizey);
    }
    
    #print "Chose $sizex,$sizey for $width,$height\n";
    
    $tilelist = Array();
    
    for($y=0; $y<$height; $y+=$sizey)
      for($x=0; $x<$width; $x+=$sizex)
      {
        $sx = min($sizex,$width-$x);
        $sy = min($sizey,$height-$y);
        $crc32 = Crc32Image($im, $xpos+$x,$ypos+$y, $sx,$sy);
        if(!isset($alltiles[$crc32]))
          $alltiles[$crc32] = Array($sx,$sy, $xpos+$x,$ypos+$y, false);
        $tilelist[] = Array($x,$y, $crc32);
      }
    
    $sectcoords[4] = $sizex;
    $sectcoords[5] = $sizey;
    $sectcoords[6] = $tilelist;
  }
  
  $puzzle = Array();
  
  foreach($sections as $sectname => &$sectcoords)
  {
    $width  = $sectcoords[0]; $sizex = $sectcoords[4]; $xpos = $sectcoords[2];
    $height = $sectcoords[1]; $sizey = $sectcoords[5]; $ypos = $sectcoords[3];
    $tilelist = &$sectcoords[6]; // crc32, doneflag. doneflags: 0=not, 1=new, 2=irrelevant
    
    $localset = Array();
    $piece = Array();
    $wid = ceil($width/$sizex);
    $hei = ceil($height/$sizey);
    
    $p=0;
    for($y=0; $y<$hei; ++$y)
      for($x=0; $x<$wid; ++$x)
      {
        $crc32 = $tilelist[$p++][2];
        $piece[$y][$x] = (!(isset($localset[$crc32]) || $alltiles[$crc32][4]));
        //     ? $crc32
        //     : false;
        $localset[$crc32] = true;
      }
    unset($localset);
    
    PutMask($piece,        /* false/true map of which tiles need placing */
            $puzzle,       /* Currently organized blocks */
            $wid,$hei,     /* Geometry of this block */
            $sizex,$sizey  /* Geometry of the tiles */
           );

    $p=0;
    for($y=0; $y<$hei; ++$y)
      for($x=0; $x<$wid; ++$x)
      {
        $dx = $piece[$y][$x][0];
        $dy = $piece[$y][$x][1];

        $sx = min($sizex,$width -$x*$sizex);
        $sy = min($sizey,$height-$y*$sizey);
        
        $crc32 = $tilelist[$p][2];
        if(!$alltiles[$crc32][4])
        {
          $alltiles[$crc32][0] = $dx;
          $alltiles[$crc32][1] = $dy;
          $alltiles[$crc32][4] = true;
          $puzzle[$dy][$dx] = Array($sx,$sy,$crc32, "$sectname $x,$y");
        }
        else
        {
          $dx = $alltiles[$crc32][0];
          $dy = $alltiles[$crc32][1];
        }
        
        $tilelist[$p][0] = $dx;
        $tilelist[$p][1] = $dy;
        ++$p;
      }
    #print_r($puzzle);
    #print "$sectname:\n";
    #dump($tilelist);
  }
  unset($tilelist);
  
  #print "plan:\n";
  #print_r($puzzle);
  //dump($puzzle);

  /* Figure out the extents of the puzzle */
  $minx=0; $maxx=0;
  $miny=0; $maxy=0;
  foreach($puzzle as $y=>$row)
    foreach($row as $x=>$cell)
    {
      $maxx = max($maxx, $x+$cell[0]);
      $maxy = max($maxy, $y+$cell[1]);
      
      #print "{$cell[0]},{$cell[1]} at $x,$y\n";
    }
  
  //print_r($alltiles);
  
  $result = ImageCreateTrueColor($maxx,$maxy);
  ImageAlphaBlending($result, false);
  $tp = ImageColorAllocateAlpha($result, 0,0,0,127);
  ImageFilledRectangle($result, 0,0, $maxx,$maxy, $tp);
  ImageSaveAlpha($result, true);
  ImageAlphaBlending($result, true);
  foreach($puzzle as $y=>$row)
    foreach($row as $x=>$cell)
    {
      $crc32 = $cell[2];
      ImageCopy($result,$im,
        // target position
        $x,$y,
        // source position
        $alltiles[$crc32][2],
        $alltiles[$crc32][3],
        // width, height
        $cell[0],
        $cell[1]);
    }
  
  return $result;
}

function CalculateOptimalTilesize($width,$height, &$sizex,&$sizey)
{
  $sizex = CalculateOptimalDivisor($width);
  $sizey = CalculateOptimalDivisor($height);
}
function CalculateOptimalDivisor($value)
{
  //if($value % 2 == 0)  return 2;
  //if($value % 10 == 0)  return 10;
  //if($value % 4 == 0)  return 4;
  if($value >= 480)
  {
    if($value % 128 == 0)  return 128;
    if($value % 64 == 0)  return 64;
  }

  if($value >= 160)
  {
    if($value % 32 == 0)  return 32;
    if($value % 16 == 0)  return 16;
  }

  //if($value % 2 == 0) return $value / 2;

  //if($value % 8 == 0)  return 8;
  //if($value % 5 == 0)  return 5;
  //return 8;
  
  return $value;
}

function Crc32Image($tile, $xpos,$ypos, $sx,$sy)
{
  $result = '';
  for($y=0; $y<$sy; ++$y)
    for($x=0; $x<$sx; ++$x)
      $result .= pack('V', ImageColorAt($tile, $xpos+$x,$ypos+$y));
  return crc32($result);
}

/* piece: the image to put into the collection
 * (divided into tiles, tiles may be holes, holes indicated by false)
 * puzzle: the collection
 * wid,hei: the dimensions of the piece, in tiles
 * sizex,sizex: the dimensions of a tile, in pixels
 */
function PutMask(&$piece, $puzzle, $wid,$hei, $sizex,$sizey)
{
  $pack_cmd = "util/binpack2d -ci -sr -x$wid -y$hei -X$sizex -Y$sizey ";
  for($y=0; $y<$hei; ++$y)
    for($x=0; $x<$wid; ++$x)
      $pack_cmd .= ($piece[$y][$x] !== false) ? '1' : '0';

  foreach($puzzle as $y=>$row)
    foreach($row as $x=>$cell)
      $pack_cmd .= " $x,$y,{$cell[0]},{$cell[1]}";

  file_put_contents('php://stderr', "$pack_cmd\n");
  
  exec($pack_cmd, $pack_result);

  $i=0;
  for($y=0; $y<$hei; ++$y)
    for($x=0; $x<$wid; ++$x)
    {
      $line = $pack_result[$i++];
      sscanf($line, '%d %d', $xp,$yp);
      #print "Gets($xp)($yp)\n";
      $piece[$y][$x] = Array($xp,$yp);
    }
}

binpack2d.cc

This program does the actual tough algorithm for the tilemapper. Shortly described, given a puzzle and a puzzle piece, it figures out where to place the puzzle piece. Except that given the right options, it can pulverize the puzzle piece and scatter the pulver uniformly around to populate the puzzle ;)

#include <vector>
#include <map>
#include <algorithm>
#include <cmath>

#include <getopt.h>

#include "tableoptimizer.hh"

enum PieceCompressionMethod
{
    PIECE_COMPRESSION_INTACT,
    PIECE_COMPRESSION_DELETE_EMPTY_COLUMNS_AND_ROWS,
    PIECE_COMPRESSION_MAKE_SQUARE,
    PIECE_COMPRESSION_MAKE_SQUARE_FROM_LARGE_RECTANGLES
};
enum PieceSplitMethod
{
    PIECE_SPLIT_INTACT,
    PIECE_SPLIT_EACH_TILE,
    PIECE_SPLIT_LARGE_RECTANGLES
};

struct XY
{
    unsigned x, y;

    bool operator< (const XY& b) const { if(y!=b.y) return y<b.y; return x<b.x; }
    bool operator==(const XY& b) const { return x==b.x && y==b.y; }

    XY(unsigned xx,unsigned yy) : x(xx), y(yy) { }
    XY() : x(),y() { }


    unsigned size() const { return std::max(x,y); }
};

struct Piece
{
    XY size;
    std::vector<bool> exists;
    std::vector<XY>   solution;
    
    Piece() : size(), exists(), solution() { }
    

    Piece(unsigned x,unsigned y, bool existsinit=false)
        : size(x,y), exists(x*y, existsinit), solution(x*y)
    {
    }
};

typedef std::map<XY/*where*/, XY/*tilesize*/> Puzzle; /* What areas are reserved? */

struct PieceCell: public TableOptimizer::CellBase
{
    bool exists;
    PieceCell(bool m) : exists(m) { }

    bool CanExtend(const PieceCell& b,
      unsigned,unsigned,unsigned,unsigned) const { return exists && b.exists; }
};

typedef std::vector<unsigned char> BitMaskType;

static int FitBitMask
    (const BitMaskType& puzzle_map, const XY& puzsize,
     const BitMaskType& piece_map, const XY& piesize,
     const XY& puzpos,
     const XY& piepos, const XY& slicesize)
{
    int result = 0;

    for(unsigned y=0; y<slicesize.y; ++y)
        for(unsigned x=0; x<slicesize.x; ++x)
        {
            XY piebitpos(x+piepos.x, y+piepos.y);
            unsigned piebit =
                (piebitpos.x < piesize.x && piebitpos.y < piesize.y)
                    ? piece_map[piebitpos.y * piesize.x + piebitpos.x]
                    : 2; // not-exist

            XY puzbitpos(x+puzpos.x, y+puzpos.y);
            unsigned puzbit =
                (puzbitpos.x < puzsize.x && puzbitpos.y < puzsize.y)
                    ? puzzle_map[puzbitpos.y * puzsize.x + puzbitpos.x]
                    : 0; // not-exist

            /*      &      piebit
             *   puzbit    1=exists 2=empty
             *   0=free       0       0
             *   1=resv       1       0
             *
             *      ^      piebit
             *   puzbit    1=exists 2=empty
             *   0=free       1       2
             *   1=resv       0       3
             */

            if( (piebit & puzbit) != 0)
                return -1; // collision

            result += (piebit ^ puzbit);
            // Score:
            //    Empty  -> free:  2
            //    Empty  -> resv:  3
            //    Exists -> free:  1
        }
    return result;
}

void PutPieceInPuzzle(
    Piece& piece,
    const Puzzle& puzzle,
    const XY& tilesize,
    PieceCompressionMethod compression = PIECE_COMPRESSION_INTACT,
    PieceSplitMethod split = PIECE_SPLIT_INTACT)
{
    /* Assign coordinates for each tile of the piece, relative
     * to the origin of the tile. These coordinates are stored
     * into piece.solution[]. It is not the final solution, but
     * just numbers that help the actual algorithm to know where
     * each tile is located.
     */

    // Check out which columns/rows of the piece are unused
    std::vector<bool> x_used(piece.size.x), y_used(piece.size.y);
    unsigned n_used=0;
    for(unsigned y=0; y<piece.size.y; ++y)
        for(unsigned x=0; x<piece.size.x; ++x)
            if(piece.exists[y*piece.size.x+x])
            {
                x_used[x]=true;
                y_used[y]=true;
                ++n_used;
            }

    switch(compression)
    {
        case PIECE_COMPRESSION_INTACT:
            for(unsigned y=0; y<piece.size.y; ++y)
                for(unsigned x=0; x<piece.size.x; ++x)
                {
                    piece.solution[y*piece.size.x+x].x = x*tilesize.x;
                    piece.solution[y*piece.size.x+x].y = y*tilesize.y;
                }
            break;
        case PIECE_COMPRESSION_DELETE_EMPTY_COLUMNS_AND_ROWS:
            for(unsigned yp=0, y=0; y<piece.size.y; ++y)
            {
                for(unsigned xp=0, x=0; x<piece.size.x; ++x)
                {
                    piece.solution[y*piece.size.x+x].x = xp;
                    piece.solution[y*piece.size.x+x].y = yp;
                    if(x_used[x]) xp += tilesize.x;
                }
                if(y_used[y]) yp += tilesize.y;
            }
            break;
        case PIECE_COMPRESSION_MAKE_SQUARE:
        {
            unsigned scramblewidth = (unsigned)(0.5+std::ceil(std::sqrt(n_used)));
            for(unsigned p=0, xp=0, yp=0, y=0; y<piece.size.y; ++y)
                for(unsigned x=0; x<piece.size.x; ++x)
                    if(piece.exists[y*piece.size.x+x])
                    {
                        piece.solution[y*piece.size.x+x].x = xp*tilesize.x;
                        piece.solution[y*piece.size.x+x].y = yp*tilesize.y;
                        ++p;
                        if(++xp >= scramblewidth) { ++yp; xp=0; }
                    }
            break;
        }
        case PIECE_COMPRESSION_MAKE_SQUARE_FROM_LARGE_RECTANGLES:
        {
            // Place each rectangle of this piece into a private puzzle,
            // and use that data for the placement of the tiles in the piece.

            PutPieceInPuzzle(piece, Puzzle(), tilesize,
                             PIECE_COMPRESSION_INTACT,
                             PIECE_SPLIT_LARGE_RECTANGLES);
            break;
        }
    }

    TableOptimizer::Table<PieceCell> table(piece.size.x, piece.size.y, 0,0);
    for(unsigned y=0; y<piece.size.y; ++y)
        for(unsigned x=0; x<piece.size.x; ++x)
        {
            PieceCell cell(piece.exists[y*piece.size.x+x]);
            if(!cell.exists) cell.masked = true;
            table.AddCell(cell);
        }

    switch(split)
    {
        case PIECE_SPLIT_INTACT:
        {
            /* The whole piece is a single cell */
            table.MarkRectangle(0,0, piece.size.x, piece.size.y);
            break;
        }
        case PIECE_SPLIT_EACH_TILE:
        {
            /* Every tile of the piece marks a separate cell */
            // Nothing to do, the cells in the table are configured like that by default.
            break;
        }
        case PIECE_SPLIT_LARGE_RECTANGLES:
        {
            /* Mark maximally large rectangles */
            table.Optimize();
            break;
        }
    }
    if(split != PIECE_SPLIT_INTACT)
    {
        /* The piece was split into multiple parts.
         * Our current algorithm cannot find the location
         * for multiple parts simultaneously, so we must
         * use recursion.
         */
        /* Get a read-write copy of the puzzle. We need it
         * because we will be calling ourselves multiple
         * times in a row, and we must have a way of marking
         * which locations have already been assigned.
         */
        Puzzle tmppuzzle = puzzle;

        for(unsigned y=0; y<piece.size.y; ++y)
            for(unsigned x=0; x<piece.size.x; ++x)
                if(piece.exists[y*piece.size.x+x])
                {
                    const PieceCell& cell = table.cells[y*piece.size.x+x];
                    if(cell.masked) continue;

                    unsigned w = cell.colspan, h = cell.rowspan;

                    // Create a solid rectangle and place it in tmppuzzle.
                    Piece tmppiece(w,h, true);

                    PutPieceInPuzzle(
                        tmppiece, tmppuzzle, tilesize,
                        PIECE_COMPRESSION_INTACT,
                        PIECE_SPLIT_INTACT);

                    // Update the actual piece's solution coordinates
                    // for this rectangle's area.
                    for(unsigned y2=0; y2<h; ++y2)
                        for(unsigned x2=0; x2<w; ++x2)
                        {
                            XY d = tmppiece.solution[y2*w+x2];
                            tmppuzzle[d] = tilesize;
                            piece.solution[(y+y2)*piece.size.x + (x+x2)] = d;
                        }
                }
        return;
    }
    else
    {
        /* We can discard "table" at this point,
         * because we won't be using it.
         */
    }

    /* Figure out the extents of the puzzle */
    XY puzmax(0,0);
    for(Puzzle::const_iterator i=puzzle.begin(); i!=puzzle.end(); ++i)
    {
        puzmax.x = std::max(puzmax.x, i->first.x + i->second.x);
        puzmax.y = std::max(puzmax.y, i->first.y + i->second.y);
    }

    /* Convert the puzzle into a bitmap */
    BitMaskType puzzle_map(puzmax.x * puzmax.y); // initialized to 0
    for(Puzzle::const_iterator i=puzzle.begin(); i!=puzzle.end(); ++i)
        for(unsigned y=0; y<i->second.y; ++y)
            for(unsigned x=0; x<i->second.x; ++x)
                puzzle_map[(x+i->first.x) + puzmax.x*(i->first.y+y)] = 1;

    /* Figure out the extents of the piece */
    XY piemax(piece.size.x * tilesize.x, piece.size.y * tilesize.y);

    /* Convert the piece into a bitmap */
    BitMaskType piece_map(piemax.x * piemax.y);
    int hole_sum = 0;
    for(unsigned y=0; y<piece.size.y; ++y)
        for(unsigned x=0; x<piece.size.x; ++x)
        {
            unsigned xp = piece.solution[y*piece.size.x+x].x;
            unsigned yp = piece.solution[y*piece.size.x+x].y;
            unsigned bit = piece.exists[y*piece.size.x+x] ? 1 : 2;
            for(unsigned py=0; py<tilesize.y; ++py)
                for(unsigned px=0; px<tilesize.x; ++px)
                    piece_map[(yp+py) * piemax.x + (xp+px)] = bit;
            if(bit != 1) ++hole_sum;
        }

    /* Decide the granularity for spots to test */
    XY step = tilesize;
    // XY step(1,1);

    /* Find the best spot. */
    int best=-1;
    XY bestpos;
    XY bestsize(puzmax.x + piece.size.x*tilesize.x, puzmax.y + piece.size.y*tilesize.y);
    XY origsize(puzmax.x, puzmax.y);

    // max{x,y} = puzmax rounded up to step increments
    unsigned maxx = ((puzmax.x + step.x-1) / step.x) * step.x;
    unsigned maxy = ((puzmax.y + step.y-1) / step.y) * step.y;
    for(unsigned y=0; y<=maxy; y+=step.y)
        for(unsigned x=0; x<=maxx; x+=step.x)
        {
            int good = FitBitMask(puzzle_map, puzmax,
                                  piece_map, piemax,
                                  XY(x,y),
                                  XY(0,0), piemax);
            if(good < 0) continue;

            XY newsize(std::max(puzmax.x, x + piece.size.x*tilesize.x),
                       std::max(puzmax.y, y + piece.size.y*tilesize.y));

            bool yay = best == -1;

            // Prefer a positioning that does not enlarge the picture very much.
            if(newsize.size() < bestsize.size())
                yay = true;

            if(newsize.size() == bestsize.size())
                yay = good > best;

            if(yay)
            {
                best = good;
                bestpos  = XY(x,y);
                bestsize = newsize;
                
                // Have we found a dream position?
                // A dream position is one where each hole of the piece
                // overlaps with material from the puzzle and the image
                // size is not incremented.
                if(bestsize == origsize && best == hole_sum) goto FoundBestSpot;
            }
        }
FoundBestSpot:;
    // Save the position.
    for(unsigned y=0; y<piece.size.y; ++y)
        for(unsigned x=0; x<piece.size.x; ++x)
        {
            piece.solution[y*piece.size.x+x].x += bestpos.x;
            piece.solution[y*piece.size.x+x].y += bestpos.y;
        }
}



int main(int argc, char** argv)
{
    /* Define the variables and the default options */
    Piece piece;
    Puzzle puzzle;
    XY tilesize(1,1);
    PieceCompressionMethod compression = PIECE_COMPRESSION_MAKE_SQUARE_FROM_LARGE_RECTANGLES;
    PieceSplitMethod       split       = PIECE_SPLIT_INTACT;
    
    unsigned piecesizex = 1;
    unsigned piecesizey = 1;

    for(;;)
    {
        int c = getopt(argc, argv, "c:s:x:y:X:Y:h");
        if(c == -1) break;
        switch(c)
        {
            case 'c':
                /***/if(strcmp(optarg, "i") == 0) compression = PIECE_COMPRESSION_INTACT;
                else if(strcmp(optarg, "i") == 0) compression = PIECE_COMPRESSION_DELETE_EMPTY_COLUMNS_AND_ROWS;
                else if(strcmp(optarg, "s") == 0) compression = PIECE_COMPRESSION_MAKE_SQUARE;
                else if(strcmp(optarg, "r") == 0) compression = PIECE_COMPRESSION_MAKE_SQUARE_FROM_LARGE_RECTANGLES;
                else goto ArgErr;
                break;
            case 's':
                /***/if(strcmp(optarg, "i") == 0) split = PIECE_SPLIT_INTACT;
                else if(strcmp(optarg, "e") == 0) split = PIECE_SPLIT_EACH_TILE;
                else if(strcmp(optarg, "r") == 0) split = PIECE_SPLIT_LARGE_RECTANGLES;
                else goto ArgErr;
                break;
            case 'x': piecesizex = std::atoi(optarg); break;
            case 'y': piecesizey = std::atoi(optarg); break;
            case 'X': tilesize.x = std::atoi(optarg); break;
            case 'Y': tilesize.y = std::atoi(optarg); break;
            case 'h'://thru
            default: goto ArgErr;
        }
    }
    
    piece = Piece(piecesizex,piecesizey);
    
    if(optind == argc)
    {
    ArgErr:
        std::fprintf(stderr,
            "Usage: binpack2d -x<piecesizex> -y<piecesizey>\n"
            "                 -X<tilesizex> -Y<tilesizey>\n"
            "                 [-c<compressionmethod>]\n"
            "                 [-s<splitmethod>]\n"
            "                 <piecedesc> [<puzzledesc> [...]]\n"
            "\n"
            "       Where piecedesc is a string of 0 or 1\n"
            "             Length of the string must be piecesizex*piecesizey\n"
            "             0=hole, 1=exists\n"
            "       And puzzledesc is xpos,ypos,xsize,ysize (all units are pixels)\n"
            "             Each entry describes a reserved section\n"
            "       Unit of piecesize is tiles\n"
            "       Unit of tilesize is pixels\n"
            "\n"
            "       Compressionmethods:\n"
            "           i = keep the shape of the piece intact\n"
            "           d = delete empty columns and rows\n"
            "           s = reshape the piece into a square\n"
            "           r = reshape the piece into a square of optimal rectangles (default)\n"
            "       Splitmethods:\n"
            "           i = intact, arrange the piece as whole (default)\n"
            "           e = each tile of the piece is arranged separately\n"
            "           r = each optimal rectangle of the piece is arranged separately\n"
            "\n"
            "       Output is lines of: <xpos> <ypos>\n"
            "       Units of position are pixels\n"
            "       Each line tells the positioning for one part of the piece\n"
            "\n");
        return -1;
    }
    
    for(unsigned a=0; a<piecesizex*piecesizey; ++a)
        piece.exists[a] = argv[optind][a] != '0';
    
    for(int a=optind+1; a<argc; ++a)
    {
        int xpos=0,ypos=0, xsize=0,ysize=0;
        std::sscanf(argv[a], "%d,%d,%d,%d", &xpos,&ypos,&xsize,&ysize);
        if(xsize && ysize)
            puzzle[XY(xpos,ypos)] = XY(xsize,ysize);
    }
    
    /* Do the bulk of the work */
    PutPieceInPuzzle(piece, puzzle, tilesize, compression, split);
    
    /* Output the solution */
    for(unsigned y=0; y<piece.size.y; ++y)
        for(unsigned x=0; x<piece.size.x; ++x)
            printf("%u %u\n",
                piece.solution[y*piece.size.x+x].x,
                piece.solution[y*piece.size.x+x].y);
}

Example use of image_tilemapper_fun.php

This is an example program that utilizes the image_tilemapper. It reads in an image and creates another image and some HTML code that demonstrates that it still works. It is used in a certain easter egg on the site.

Note: This code is provided only for illustration; you may need to alter it for your needs.

<?php

require 'image_tilemapper_fun.php';

error_reporting(E_ERROR);

$im = ImageCreateFromPng('../css/ratingbg.png');
ImageAlphaBlending($im, false);

$sections = Array(
  'tasvideos'    => Array(76,15, 50,36),
  'stuff'        => Array(52,10, 51,51),
  'background'   => Array(300,20, 0,0,    5,5),
  'xkeeper'      => Array(54,8, 50,60),
  'megaman'      => Array(25,13, 103,51, 5,13),
  'cursor_c'     => Array(20,20, 0,40, 5,5),
  'cursor_i'     => Array(5,20, 38,40, 5,5),
  'indicator_c'  => Array(20,20, 0,20, 5,5),
  'indicator_i'  => Array(5,20, 38,20, 5,5),
  'petA0' => Array(16,24,128+16*0,20,   8,8),
  'petA1' => Array(16,24,128+16*1,20,   8,8),
  'petA2' => Array(16,24,128+16*2,20,   8,8),
  'petA3' => Array(16,24,128+16*3,20,   8,8),
  'petA4' => Array(16,24,128+16*4,20,   8,8),
  'petA5' => Array(16,24,128+16*5,20,   8,8),
  'petA6' => Array(16,24,128+16*6,20,   8,8),
  'petA7' => Array(16,24,128+16*7,20,   8,8),
  'petB0' => Array(16,24,128+16*0,44,   8,8),
  'petB1' => Array(16,24,128+16*1,44,   8,8),
  'petB2' => Array(16,24,128+16*2,44,   8,8),
  'petB3' => Array(16,24,128+16*3,44,   8,8),
  'petB4' => Array(16,24,128+16*4,44,   8,8),
  'petB5' => Array(16,24,128+16*5,44,   8,8),
  'petB6' => Array(16,24,128+16*6,44,   8,8),
  'petB7' => Array(16,24,128+16*7,44,   8,8),
  'fb0g' => Array(8,8, 56+8*0,20),
  'fb1g' => Array(8,8, 56+8*1,20),
  'fb2g' => Array(8,8, 56+8*2,20),
  'fb3g' => Array(8,8, 56+8*3,20),
  'fb4g' => Array(8,8, 56+8*4,20),
  'fb5g' => Array(8,8, 56+8*5,20),
  'fb6g' => Array(8,8, 56+8*6,20),
  'fb7g' => Array(8,8, 56+8*7,20),
  'fb8g' => Array(8,8, 56+8*8,20),
  'fb0r' => Array(8,8, 56+8*0,28),
  'fb1r' => Array(8,8, 56+8*1,28),
  'fb2r' => Array(8,8, 56+8*2,28),
  'fb3r' => Array(8,8, 56+8*3,28),
  'fb4r' => Array(8,8, 56+8*4,28),
  'fb5r' => Array(8,8, 56+8*5,28),
  'fb6r' => Array(8,8, 56+8*6,28),
  'fb7r' => Array(8,8, 56+8*7,28),
  'fb8r' => Array(8,8, 56+8*8,28)
);

$result = TilemapImage($im, $sections);

ImagePng($result, '/WWW/imagemergetest.png');

echo '<img src="/imagemergetest.png">';

$gdata = Array();
foreach($sections as $sectname => &$sectcoords)
{
  $width  = $sectcoords[0]; $sizex = $sectcoords[4]; $xpos = $sectcoords[2];
  $height = $sectcoords[1]; $sizey = $sectcoords[5]; $ypos = $sectcoords[3];
  $tilelist = $sectcoords[6]; // crc32, doneflag. doneflags: 0=not, 1=new, 2=irrelevant
  $wid = $width /$sizex;
  $hei = $height/$sizey;
  
  $data = '';
  for($y=$p=0; $y<$hei; ++$y)
    for($x=0; $x<$wid; ++$x)
      $data .= chr(65+$tilelist[$p++][0] / $sizex);
  for($y=$p=0; $y<$hei; ++$y)
    for($x=0; $x<$wid; ++$x)
      $data .= chr(65+$tilelist[$p++][1] / $sizey);
  $data = Array('x'=>$sizex,'y'=>$sizey, $data);
  $gdata[$sectname] = $data;
  
  echo "<h3>$sectname</h3>";
  echo '<table cellspacing=0 cellpadding=0>';
  $p=0;
  for($y=0; $y<$hei; ++$y)
  {
    echo '<tr>';
    for($x=0; $x<$wid; ++$x)
    {
      $dx = $tilelist[$p][0];
      $dy = $tilelist[$p][1];
      $style = 'background:url("/imagemergetest.png")'." no-repeat -{$dx}px -{$dy}px";
      echo "<td width=$sizex height=$sizey style='".htmlspecialchars($style)."'>";
      ++$p;
    }
    echo '</tr>';
  }
  echo '</table>';
}
print_r($gdata);
The code that finds which images are commonly loaded together and packs them, is not provided, as it's a little too specific for the internal structure of this site.


Combined RSS Feed
Bisqwit/Source/ImageTileMapper last edited by Ilari on 2012-08-14 04:45:10
Page info and history | Latest diff | List referrers | View Source