Failed Attempt at Wave Function Collapse in AGS Script

[eri0o]

So, I wanted to see if it was possible to do Wave Function Collapse in AGS Script. Because I was lazy, I decided to try to port the code of this C version here: https://github.com/krychu/wfc/blob/master/wfc.h

Now this did NOT work, it runs and takes some long time, but the result at the end is wrong... Anyhow, decided to leave my try it out here in case someone really wants to take the challenge. Probably the best approach is to actually read the papers and figure a strategy that is better suited for the concepts available in AGS.

wfc.ash

Code: ags

// new module header

#define MAX_TILES 1024

enum WfcDirection {
  eWfcDir_Up = eDirectionUp, 
  eWfcDir_Down = eDirectionDown, 
  eWfcDir_Left = eDirectionLeft, 
  eWfcDir_Right = eDirectionRight 
};

enum WfcMethod {
  eWfc_Overlapping, 
  eWfc_Tiled, 
};

managed struct WfcCell {
  int Tile[MAX_TILES];                  // Possible tiles in the cell (initially all)
  int TileCount;

  int FrequencySum; // Sum of tile frequencies used to calculate
                    // entropy and randomly pick a tile when
                    // collapsing a tile.

  float Entropy;    // Shannon entropy. Cell with the smallest entropy
                    // is picked to be collapsed next.
};

managed struct WfcProp {
  int SrcCellIdx;
  int DstCellIdx;
  WfcDirection direction;
};

struct Wfc {
  WfcMethod method;
  int seed;
  
  DynamicSprite* Input;
  int TileWidth;
  int TileHeight;  
  bool FlipTilesX;
  bool FlipTilesY;
  bool RotateTiles;
  
  DynamicSprite* TilesSprite[];
  int TilesFrequency[]; // count of tile occurrences in the input image.
  int TilesCount;
  
  /* output */
  
  DynamicSprite* Output;
  WfcCell* Cell[];
  int CellCount;
  int FrequencySum;
  
  /* in-use */
  
  WfcProp* Prop[];
  int PropCount;
  int PropIdx;
  
  int CollapsedCellCount;
  
  bool allowed_tiles[1048576];
  
  
  /* API */
  
  import void Init(DynamicSprite* output, int input_sprite, int tile_width, int tile_height, bool xflip_tiles = true, bool yflip_tiles = true, bool rotate_tiles = true, bool expand_input = false);
  import void Restart();
  import void RegenerateOutput();
  import void Run(int max_collapse_cnt);
  import void RepeatedlyUpdate(int times = 1);
  bool Generated;
  
  protected int _Rp_CellIdx;
  protected int _Rp_MaxCollapseCnt;
  
  import protected void _SwapTiles(int a_idx, int b_idx);  
  import protected void _RemoveDuplicatedTiles();
  
  import protected void _CreateProps();
  import protected void _CreateCells();
  import protected void _CreateTiles();
  
  import protected void _AddProp(int src_cell_idx, int dst_cell_idx, WfcDirection direction);
  import protected void _AddPropUp(int src_cell_idx);
  import protected void _AddPropDown(int src_cell_idx);
  import protected void _AddPropLeft(int src_cell_idx);
  import protected void _AddPropRight(int src_cell_idx);
  import protected bool _IsTileEnabled(int tile_idx, int cell_idx, WfcDirection direction);
  import protected bool _IsPropPending(int cell_idx, WfcDirection direction);
  
  import protected bool _PropagateProp(WfcProp* p);
  import protected bool _Propagate(int cell_idx);
  import protected bool _Collapse(int cell_idx);
  import protected int _NextCell();
  import protected void _InitCells();
   
  import protected void _ComputeAllowedTiles();
  import protected void _CreateTilesOverlapping(int tile_width, int tile_height, bool expand_image, bool xflip_tiles, bool yflip_tiles, bool rotate_tiles);
};

wfc.asc

Code: ags

// new module script

int _DirToIdx( WfcDirection direction)
{
  switch (direction) {
    case eWfcDir_Up:    return 0; break;
    case eWfcDir_Down:  return 1; break;
    case eWfcDir_Left:  return 2; break;
    case eWfcDir_Right: return 3; break;
  }
  return 0;
}

WfcDirection _IdxToDir(int d)
{
  switch (d) {
    case 0: return eWfcDir_Up; break;
    case 1: return eWfcDir_Down; break;
    case 2: return eWfcDir_Left; break;
    case 3: return eWfcDir_Right; break;
  }
  return eWfcDir_Up;
  
}

// Return 1 if the two images overlap perfectly except the edges in the given direction, 0 otherwise.
bool _SprCmpOverlap(DynamicSprite* dynspr_a, DynamicSprite* dynspr_b, WfcDirection direction)
{
  int a_offx, a_offy, b_offx, b_offy, width, height;

  switch (direction) {
    case eWfcDir_Up:
      a_offx = 0; a_offy = 0;
      b_offx = 0; b_offy = 1;
      width = dynspr_a.Width;
      height = dynspr_a.Height-1;
      break;
    case eWfcDir_Down:
      a_offx = 0; a_offy = 1;
      b_offx = 0; b_offy = 0;
      width = dynspr_a.Width;
      height = dynspr_a.Height-1;
      break;
    case eWfcDir_Left:
      a_offx = 0; a_offy = 0;
      b_offx = 1; b_offy = 0;
      width = dynspr_a.Width-1;
      height = dynspr_a.Height;
      break;
    case eWfcDir_Right:
      a_offx = 1; a_offy = 0;
      b_offx = 0; b_offy = 0;
      width = dynspr_a.Width-1;
      height = dynspr_a.Height;
      break;
    default:
      AbortGame("WFC Error: Invalid Direction");
      return false;
  }

  DrawingSurface* surf_a = dynspr_a.GetDrawingSurface();
  DrawingSurface* surf_b = dynspr_b.GetDrawingSurface();

  for (int y=0; y<height; y++) {
    for (int x=0; x<width; x++) {

      int a_x = a_offx + x;
      int b_x = b_offx + x;
      int a_y = a_offy + y;
      int b_y = b_offy + y;

      if(surf_a.GetPixel(a_x, a_y) != surf_b.GetPixel(b_x, b_y)) {
        return false;
      }
    }
  }
  
  surf_a.Release();
  surf_b.Release();
  
  return true;
}

 bool noloopcheck _SprEqual(DynamicSprite* dynspr_a, DynamicSprite* dynspr_b)
{
  if(dynspr_a.Width != dynspr_b.Width || dynspr_a.Height != dynspr_b.Height) {
    return false;
  }
  
  if(dynspr_a == dynspr_b) return true;
  
  int width = dynspr_a.Width;
  int height = dynspr_a.Height;
  
  DrawingSurface* surf_a = dynspr_a.GetDrawingSurface();
  DrawingSurface* surf_b = dynspr_b.GetDrawingSurface();
  
  for (int y=0; y<height; y++) {
    for (int x=0; x<width; x++) {
      if(surf_a.GetPixel(x, y) != surf_b.GetPixel(x, y)) {
        return false;
      }
    }
  }
  
  return true;
}

DynamicSprite* noloopcheck _GenerateOutput(int width, int height,  WfcCell* cells[], DynamicSprite* tiles[])
{
  DynamicSprite* spr = DynamicSprite.Create(width, height);
  DrawingSurface* surf = spr.GetDrawingSurface();
  
  for (int y=0; y<height; y++) {
    for (int x=0; x<width; x++) {
      WfcCell* cell = cells[y*width+x];
      
      int component = 0;
      for(int i=0; i<cell.TileCount; i++) {
        DynamicSprite* tile = tiles[cell.Tile[i]];
        DrawingSurface* tmp_surf = tile.GetDrawingSurface();
        component += tmp_surf.GetPixel(0, 0);
        tmp_surf.Release();
      }
      
      surf.DrawingColor = component/cell.TileCount;
      surf.DrawPixel(x, y);
    }
  }
  
  surf.Release();
  return spr;
}

void _AddOverlappingImages(DynamicSprite* tiles_dynspr[], int tiles_freq[], DynamicSprite* img, int xcnt, int ycnt, int tile_width, int tile_height)
{
  int tile_cnt = xcnt * ycnt;
  DrawingSurface* surf = img.GetDrawingSurface();
  
  for (int y=0; y<ycnt; y++) {
    for (int x=0; x<xcnt; x++) {
      int i = y*xcnt + x;
      
      tiles_freq[i] = 1;
      tiles_dynspr[i] = DynamicSprite.CreateFromDrawingSurface(surf, x, y, tile_width, tile_height);
    
    }
  }
}


void _AddFlippedImages(DynamicSprite* tiles_dynspr[], int tiles_freq[], int tile_idx, eFlipDirection flip_dir)
{
  for (int i=0; i<tile_idx; i++) {
    int src_idx = i;
    int dst_idx = tile_idx + i;
    
    tiles_freq[dst_idx] = 1;
    DynamicSprite* spr_src = tiles_dynspr[src_idx];
    tiles_dynspr[dst_idx] = DynamicSprite.CreateFromExistingSprite(spr_src.Graphic, true);
    DynamicSprite* spr_dst = tiles_dynspr[dst_idx];
    spr_dst.Flip(flip_dir);    
  }
}


void _AddRotatedImages(DynamicSprite* tiles_dynspr[], int tiles_freq[], int tile_idx)
{
  
  for (int i=0; i<tile_idx; i++) {
    int src_idx = i;
    DynamicSprite* src_spr = tiles_dynspr[src_idx];
    
    for (int j=0; j<3; j++) {
      
      int dst_idx = tile_idx + i*3 + j;
      tiles_freq[dst_idx] = 1;
      
      tiles_dynspr[dst_idx] = DynamicSprite.CreateFromExistingSprite(src_spr.Graphic, true);
      DynamicSprite* spr_dst = tiles_dynspr[dst_idx];
      
      if(j != 0) {
        spr_dst.Rotate(j*90);
      }
    }
  }
}

protected void Wfc::_SwapTiles(int a_idx, int b_idx)
{
  int tmp_freq = this.TilesFrequency[a_idx];
  DynamicSprite* tmp_spr = this.TilesSprite[a_idx];
  
  this.TilesFrequency[a_idx] = this.TilesFrequency[b_idx];
  this.TilesSprite[a_idx] = this.TilesSprite[b_idx];
  
  this.TilesFrequency[b_idx] = tmp_freq;
  this.TilesSprite[b_idx] = tmp_spr;
}

protected void Wfc::_RemoveDuplicatedTiles()
{
  int unique_cnt = 1;
  for (int j=1; j<this.TilesCount; j++) {
    bool unique = true;
    for (int k=0; k<unique_cnt; k++) {
      if(_SprEqual(this.TilesSprite[j], this.TilesSprite[k])) {
        unique = false;
        this.TilesFrequency[k]++;
        break;
      }
    }
    
    
    if (unique) {
      if (unique_cnt != j) {
        this._SwapTiles(j, unique_cnt);        
      }
      
      unique_cnt++;
    }
  }

  for(int i=unique_cnt; i<this.TilesCount; i++) {
    this.TilesFrequency[i] = 0;
    this.TilesSprite[i] = null;
  }
  
  this.TilesCount = unique_cnt;
}

#define WFC_MAX_PROP_CNT 1000

////////////////////////////////////////////////////////////////////////////////
//
// WFC: Solve (Method-independent)
//
////////////////////////////////////////////////////////////////////////////////


protected void noloopcheck Wfc::_CreateProps()
{
  int prop_max = this.CellCount * WFC_MAX_PROP_CNT;
  this.Prop = new WfcProp[prop_max];
  
  for(int i=0; i<prop_max; i++)
  {
    this.Prop[i] = new WfcProp;
  }
}

protected void noloopcheck Wfc::_CreateCells()  
{
  int cell_cnt = this.CellCount;
  this.Cell = new WfcCell[cell_cnt];
  
  for (int i=0; i<cell_cnt; i++)
  {
    WfcCell* cell = new WfcCell;
    this.Cell[i] = cell;

    if(i==0) continue;
    
    int tile_count = this.TilesCount;
    
    cell.TileCount = tile_count;
  }
}

protected void Wfc::_CreateTiles()
{
  int tile_cnt = this.TilesCount;
  this.TilesFrequency = new int[tile_cnt];
  this.TilesSprite = new DynamicSprite[tile_cnt];
  
  for (int i=0; i<this.TilesCount; i++) {
    this.TilesFrequency[i] = 0;
    this.TilesSprite[i] = null;
  }
}
  
protected void Wfc::_AddProp(int src_cell_idx, int dst_cell_idx, WfcDirection direction)
{
  WfcProp* prop = this.Prop[this.PropCount];
  
  prop.SrcCellIdx = src_cell_idx;
  prop.DstCellIdx = dst_cell_idx;
  prop.direction = direction;
  
  this.PropCount++;
}

protected void Wfc::_AddPropUp(int src_cell_idx)
{
  int dst_cell_idx = src_cell_idx - this.Output.Width;
  if(dst_cell_idx < 0) return; // can't go to upper cell,  in first line
  
  this._AddProp(src_cell_idx, dst_cell_idx, eWfcDir_Up);
}

protected void Wfc::_AddPropDown(int src_cell_idx)
{
  int dst_cell_idx = src_cell_idx + this.Output.Width;
  
  if(dst_cell_idx > this.CellCount) return; // can't go to down cell,  in last line
  
  this._AddProp(src_cell_idx, dst_cell_idx, eWfcDir_Down);    
}

protected void Wfc::_AddPropLeft(int src_cell_idx)
{
  int dst_cell_idx = src_cell_idx - 1;
  
  if(src_cell_idx % this.Output.Width == 0) return;
  
  this._AddProp(src_cell_idx, dst_cell_idx, eWfcDir_Left);   
}

protected void Wfc::_AddPropRight(int src_cell_idx)
{
  int dst_cell_idx = src_cell_idx + 1;
  
  if(src_cell_idx % this.Output.Width == this.Output.Width - 1) return;
    
  this._AddProp(src_cell_idx, dst_cell_idx, eWfcDir_Right);
}

protected bool Wfc::_IsTileEnabled(int tile_idx, int cell_idx, WfcDirection direction)
{
  WfcCell* cell = this.Cell[cell_idx];
  int tile_cnt = this.TilesCount;

  for(int i=0, cnt=cell.TileCount; i<cnt; i++)
  {
    if(this.allowed_tiles[_DirToIdx(direction)*this.TilesCount+tile_idx]) return true;
  }
  
  return false;
}

// Checks whether particular prop is already added and pending, in which
// case there is no point of adding the same prop again.
protected bool Wfc::_IsPropPending(int cell_idx, WfcDirection direction)
{
  for (int i=this.PropIdx+1; i < this.PropCount; i++) {
    WfcProp* prop = this.Prop[i];
    
    if(prop.SrcCellIdx == cell_idx && prop.direction == direction) return true;    
  }
  
  return false;
}


// Updates tiles in the destination cell to those that are allowed by the source cell
// and propagate updates
protected bool Wfc::_PropagateProp(WfcProp* p)
{
  int new_cnt = 0;
  
  WfcCell* dst_cell = this.Cell[p.DstCellIdx];
  
  // Go through all destination tiles and check whether they are enabled by the source cell
  for (int i=0, cnt=dst_cell.TileCount; i<cnt; i++) {
    int possible_dst_tile_idx = dst_cell.Tile[i];
    
    // If a destination tile is enabled by the source cell, keep it
    if(this._IsTileEnabled(possible_dst_tile_idx, p.SrcCellIdx, p.direction)) {
      dst_cell.Tile[new_cnt] = possible_dst_tile_idx;
      new_cnt++;
    } else {
      int freq = this.TilesFrequency[possible_dst_tile_idx];
      float p_f = IntToFloat(freq) / IntToFloat(this.FrequencySum);
      
      dst_cell.Entropy += p_f*Maths.Log(p_f);
      dst_cell.FrequencySum -= freq;
      
      if(dst_cell.FrequencySum == 0) return false;
    }
  }
  
  if(new_cnt == 0) return false;
  
  if(dst_cell.TileCount != new_cnt) {
    int dst_cell_i = p.DstCellIdx;
    if(new_cnt == 1) this.CollapsedCellCount++;
    if(p.direction != eWfcDir_Down && this._IsPropPending(dst_cell_i, eWfcDir_Up)) this._AddPropUp(dst_cell_i);
    if(p.direction != eWfcDir_Up && this._IsPropPending(dst_cell_i, eWfcDir_Down)) this._AddPropDown(dst_cell_i);
    if(p.direction != eWfcDir_Right && this._IsPropPending(dst_cell_i, eWfcDir_Left)) this._AddPropLeft(dst_cell_i);
    if(p.direction != eWfcDir_Left && this._IsPropPending(dst_cell_i, eWfcDir_Right)) this._AddPropRight(dst_cell_i);    
  }
  
  dst_cell.TileCount = new_cnt;
  
  return true;
}

protected bool Wfc::_Propagate(int cell_idx)
{
  this.PropCount = 0;
  
  this._AddPropUp(cell_idx);
  this._AddPropDown(cell_idx);
  this._AddPropLeft(cell_idx);
  this._AddPropRight(cell_idx);
  
  for(int i=0; i<this.PropCount; i++)
  {
    this.PropIdx = i;
    WfcProp* p = this.Prop[i];
    
    if(!this._PropagateProp(p)) {
      return false;
    }
  }
  
  return true;
}


protected bool Wfc::_Collapse(int cell_idx)
{
  WfcCell* cell = this.Cell[cell_idx];
  
  int remaining = Random(cell.FrequencySum);
  
  for(int i=0; i<cell.TileCount; i++) {
    int tile_idx = cell.Tile[i];
    int freq = this.TilesFrequency[tile_idx];
    
    if(remaining >= freq) {
      remaining -= freq;
    } else {
      cell.Tile[0] = cell.Tile[i];
      cell.TileCount = 1;
      cell.FrequencySum = 0;
      cell.Entropy = 0.0;
      this.CollapsedCellCount++;
      return true;
    }
  }
  
  return false;  
}

protected int Wfc::_NextCell()
{
  int min_idx = -1;
  float min_entropy = 3402823466.0;
  
  for (int i=0; i<this.CellCount; i++) {    
    WfcCell* cell = this.Cell[i];
    
    // Add small noise to break ties between tiles with the same entropy
    float entropy = cell.Entropy + (IntToFloat(Random(4096))/8388608.0);
    
    
    if (cell.TileCount != 1 && entropy < min_entropy) {
      min_entropy = entropy;
      min_idx = i;
    }
  }
  
  return min_idx;
}

protected void noloopcheck Wfc::_InitCells()
{
  int sum_freqs = 0;
  
  for(int i=0; i<this.TilesCount; i++) {
    sum_freqs += this.TilesFrequency[i];
  }
  
  this.FrequencySum = sum_freqs;
  
  float sum_plogp = 0.0;
  for (int i=0; i<this.TilesCount; i++) {
    float p_f = IntToFloat(this.TilesFrequency[i])/IntToFloat(sum_freqs);
    sum_plogp += p_f*Maths.Log(p_f);
  }
  
  float entropy = -sum_plogp;
  
  for(int i=0; i<this.CellCount; i++)
  {
    WfcCell* cell = this.Cell[i];
    
    cell.TileCount = this.TilesCount;
    cell.FrequencySum = sum_freqs;
    cell.Entropy = entropy;
    
    for(int j=0; j<this.TilesCount; j++) {
      cell.Tile[j] = j;
    }    
  }
  
  this.PropCount = 0;
}

protected void noloopcheck Wfc::_ComputeAllowedTiles()
{
  int tile_cnt = this.TilesCount;
  
  for (int d=0; d<4; d++) {
    for (int i=0; i<tile_cnt; i++) {
      for (int j=0; j<tile_cnt; j++) {
        int idx = d*i*tile_cnt+j;
        
        this.allowed_tiles[idx] = _SprCmpOverlap(this.TilesSprite[i], this.TilesSprite[j], _IdxToDir(d));
      }
    }
  }
}

protected void Wfc::_CreateTilesOverlapping(int tile_width, int tile_height, bool expand_image, bool xflip_tiles, bool yflip_tiles, bool rotate_tiles)
{
  int xcnt = this.Input.Width - tile_width + 1;
  int ycnt = this.Input.Height - tile_height + 1;
  
  if(expand_image) {
    xcnt = this.Input.Width;
    ycnt = this.Input.Height;
    int w = this.Input.Width;
    int h = this.Input.Height;
    this.Input.Resize(w + tile_width - 1, h + tile_height -1);
  }
  
  int tile_cnt = xcnt*ycnt;
  
  if(xflip_tiles) tile_cnt *= 2;    
  if(!(xflip_tiles && rotate_tiles) && yflip_tiles) tile_cnt *= 2;
  if(rotate_tiles) tile_cnt *= 4;
  
  this.TilesCount = tile_cnt;
  this._CreateTiles();
  
  _AddOverlappingImages(this.TilesSprite, this.TilesFrequency, this.Input, xcnt, ycnt, tile_width, tile_height);
  
  int base_tile_cnt = xcnt * ycnt;
  
  if(xflip_tiles) {
    _AddFlippedImages(this.TilesSprite, this.TilesFrequency, base_tile_cnt, eFlipLeftToRight);
    base_tile_cnt *= 2;
  }
  
  if(!(xflip_tiles && rotate_tiles) && yflip_tiles) {
    _AddFlippedImages(this.TilesSprite, this.TilesFrequency, base_tile_cnt, eFlipUpsideDown);
    base_tile_cnt *= 2;
  }
  
  if(rotate_tiles) {
    _AddRotatedImages(this.TilesSprite, this.TilesFrequency, base_tile_cnt);
    base_tile_cnt *= 4;
  }
  
  this._RemoveDuplicatedTiles();
}

void Wfc::Restart()
{
  this.CollapsedCellCount = 0;
  this.Generated = false;
  this._InitCells();
}

void Wfc::Init(DynamicSprite* output, int input_sprite, int tile_width, int tile_height, bool xflip_tiles, bool yflip_tiles, bool rotate_tiles, bool expand_input)
{
  this.Output = output;
  this.Input = DynamicSprite.CreateFromExistingSprite(input_sprite, true);
  this.method = eWfc_Overlapping;
  this.CellCount = this.Output.Width * this.Output.Height;
  this.TileWidth = tile_width;
  this.TileHeight = tile_height;
  this.TilesCount = 0;
  this.FlipTilesX = xflip_tiles;
  this.FlipTilesY = yflip_tiles;
  this.RotateTiles = rotate_tiles;
  
  this._CreateTilesOverlapping(tile_width, tile_height, expand_input, xflip_tiles, yflip_tiles, rotate_tiles);
  
  this._ComputeAllowedTiles();
  
  this._CreateCells();
  this._CreateProps();
    
  this.Restart();
}

void Wfc::RegenerateOutput()
{
  DynamicSprite* out = _GenerateOutput(this.Output.Width, this.Output.Height, this.Cell, this.TilesSprite);
  
  DrawingSurface* surf = this.Output.GetDrawingSurface();
  
  surf.Clear();
  surf.DrawImage(0, 0, out.Graphic);
  surf.Release();
}

void Wfc::Run(int max_collapse_cnt)
{
  int cell_idx = Random(this.Output.Height * this.Output.Width);
  this._Rp_CellIdx = cell_idx;
  this._Rp_MaxCollapseCnt = max_collapse_cnt;
}

void Wfc::RepeatedlyUpdate(int times)
{
  for(int i=0; i<times; i++) {
    int cell_idx = this._Rp_CellIdx;
    int max_collapse_cnt = this._Rp_MaxCollapseCnt;
    
    if(cell_idx == -1 || this.CollapsedCellCount == max_collapse_cnt) {
      this.Generated = true;
      return;
    }
    
    if(!this._Collapse(cell_idx)) return;  
    if(!this._Propagate(cell_idx)) return;
    
    cell_idx = this._NextCell();
    this._Rp_CellIdx = cell_idx;
    
    if(cell_idx == -1 || this.CollapsedCellCount == max_collapse_cnt) {
      this.Generated = true;
      return;
    }
  }
}

Usage

Code: ags

Wfc wfc;
Overlay* ovr;

function room_RepExec()
{
  wfc.RepeatedlyUpdate(8192);
  
  if(wfc.Generated) {
    if(ovr == null) {
      wfc.RegenerateOutput();
      ovr = Overlay.CreateGraphical(32, 32, wfc.Output.Graphic, true);
    }
  }
}

function room_Load()
{
  wfc.Init(DynamicSprite.Create(48, 48, true), 1, 3, 3, true, true, true, false);
  wfc.Run(2048);
  
}

function room_AfterFadeIn()
{

}

[eri0o]

Reading the original code today here: https://github.com/mxgmn/WaveFunctionCollapse

There's an explanation of the algorithm in the readme I think I am almost understanding it. I think I will try later to base it from here.

I tried to look for tutorials but most of what I found uses a pre-made library and it's more about using and experimenting than implementing the algorithm.

[Khris]

Had to give this a go and ended up with this:



I hardcoded overlapping 3x3 tiles, and you can see there's a few dark gray pixels that didn't resolve. It's also pretty slow, but watching it grow is pretty cool

Not sure I'll publish the code, it's a bit messy. And there's still room for optimization.

[eri0o]

Amazing @Khris !!! I am really impressed! Usually once one get into a code that at least works, getting it optimized and cleaning up is the easy part - if you share yours I wouldn't mind scrubbing it's edges.

But anyway, great work, really impressed! 

[Khris]

Thanks

Here's the module: https://drive.google.com/file/d/18yazRkEYt8IW9OLML2pDMXfcFoBfGDCe/view?usp=share_link

And an example room script:

Code: ags

// room script file

DrawingSurface* ds;

DynamicSprite* output;

function room_Load()
{
  ds = Room.GetDrawingSurfaceForBackground();
  ds.DrawImage(100 - Game.SpriteWidth[1] - 5, 90 - Game.SpriteHeight[1] / 2, 1);
  ds.Release();
  
  output = DynamicSprite.Create(48, 48);
  
  WFC.Init(1, true, 7);
  WFC.SetOutput(output);
}

bool failed;

function room_RepExec()
{
  if (!failed) {
    failed = WFC.Pass();
    ds = Room.GetDrawingSurfaceForBackground();
    ds.DrawImage(100, 66, output.Graphic);
    ds.Release();
  }
}

void on_key_press(eKeyCode key) {
  if (key == eKeyEscape) {
    QuitGame(0);
    output.Delete();
  }
}

[eri0o]

@Khris it's amazing!



I can force at least 4 passes in my CPU, per frame, so I can do it 4x faster than the gif.

I thought maybe GetPixel and SetPixel are too slow... And they are, so I made a hacked version where they are slightly faster, using a hack for set pixel get pixel internally.

Code: ags

((int*)ds->GetAllegroBitmap()->line[y])[x]

Still, because you used GetPixel and SetPixel quite smartly, they don't appear to matter that much currently.

Now I was curious about why the sequence is 8 pixels instead of 9 for 3x3 tile, and wondered if this could matter for the missing dots in the final image. I hacked around the code for this but apparently it doesn't matter, so my guess is you have the center pixel stored separately to save ram. I will read the code more carefully later. 

[Khris]

Thanks

I'm storing the center pixel and the surrounding eight ones separately, yes. Not to save memory though but simply because they are needed for different purposes. The eight border pixels are checked against the neighboring pixels, the center one I only need when drawing a pixel.

Also yes, I'm reading the source image into a bunch of arrays at the start then never use it again, and each pixel of the output is only set once, so the impact should be minimal.

I'm currently checking all pixels each pass though so ideally there should be a list of blank ones that slowly gets reduced to zero.

[eri0o]

I am having a hard time figuring out these steps in your code

Observation:
Find a wave element with the minimal nonzero entropy. If there is no such elements (if all elements have zero or undefined entropy) then break the cycle (4) and go to step (5).
Collapse this element into a definite state according to its coefficients and the distribution of NxN patterns in the input.
Propagation: propagate information gained on the previous observation step.

Sorry if I am an idiot, but how do you name entropy?

I'm currently checking all pixels each pass though so ideally there should be a list of blank ones that slowly gets reduced to zero.

I am trying to figure kind of this, essentially the ones that are left. 

[Khris]

It's called .matchCount; I'm using it in the loop at line 170 to find the pixels with the lowest tile matches.
Starting from line 182 I go over all pixels again, putting the ones with the lowest .matchCount into a list. Then I pick a random pixel and populate it with a random tile (i.e. I've ignored the part of the algorithm that tries to maintain the distribution).
I've also just noticed that the ops in lines 195 and 197 are not necessary.

[eri0o]

Can I ask one more thing about the code? In line 176, inside the if clause, you do count = 1;, instead of an increment. Now I tried to do an increment, and visually it looked the same. But this means only 1 point per pass is more constrained than lc? Now I mention this because if this is true, I wonder if it's an opportunity for optimization.

Edit: Nevermind, now I found two lines up.

Edit2: on line 112 to 119, not sure you know, but you can use alt+shift to select the x and y stuff in the vertical block to paste on top of line 154 to 161.

[Khris]

you can use alt+shift to select the x and y stuff in the vertical block

That's neat, I didn't know that!

[eri0o]

@Khris it will take me a bit to go back to this, I am trying to look into some other things right now for a game idea. Thank you for the module you made.