Spectre

program.cs

// This software is released into the public domain under the CC0 1.0 Universal license.
// 
// You can copy, modify, distribute, and use it for any purpose, without any conditions, 
// unless required by law.
//
// To the extent possible under law, the author(s) disclaim all copyright and related 
// or neighboring rights to this work.
//
// See: https://creativecommons.org/publicdomain/zero/1.0/

/* Demonstration of Wave function collapse algorithm
 *  in a terminal
 *
 *  Place the spectre logo in middle and from it grow
 *  a grid structure using the Wave function collapse
 *  Watch this: https://www.youtube.com/watch?v=rI_y2GAlQFM
 *
 *  Place sparks in the grid and move them around for
 *  extra flair
 */

using System.Text;
using System.Numerics;
using static System.Math;
using static System.Diagnostics.Debug;
using System.Diagnostics;

const float TimeStep      = 0.175F;
const float EndTime       = float.PositiveInfinity;
const float DesiredFPS    = 60.0F;
const float DesiredDelay  = 1.0F/DesiredFPS;

const string logo = """
  ╭──┐┌─╨╮╭─┴┐╭╨─┐╭─┴──┐┌─╨╮╭─┴┐
  │╭─╯│╭╮││╭─╯│╭─╯╰─╮╭─╯│╭╮││╭─╯
  ┤└─╮│└╯││└─╮││    ┤│  ┤└╯││└─┬
  ╰─╮││╭┬╯│╭─╯│╞    ││  │┌╮││╭─╯
  ╭─┘│││  │└─╮│└─╮  │╞  │││││└─╮
  └─╥╯└╯  ╰┬─┘╰─╥┘  └╯  └╯╰┘╰┬─┘
  """;

Shape[] shapes =
  [
    MakeShape( ' ', 0b0000, 0b0000, 10)
  , MakeShape( '─', 0b1010, 0b0000, 10)
  , MakeShape( '│', 0b0101, 0b0000, 10)
  , MakeShape( '┌', 0b0011, 0b0000, 10)
  , MakeShape( '┐', 0b1001, 0b0000, 10)
  , MakeShape( '└', 0b0110, 0b0000, 10)
  , MakeShape( '┘', 0b1100, 0b0000, 10)
  , MakeShape( '├', 0b0111, 0b0000, 10)
  , MakeShape( '┤', 0b1101, 0b0000, 10)
  , MakeShape( '┬', 0b1011, 0b0000, 10)
  , MakeShape( '┴', 0b1110, 0b0000, 10)
  , MakeShape( '┼', 0b1111, 0b0000, 10)

  , MakeShape( '╭', 0b0011, 0b0000, 8 )
  , MakeShape( '╯', 0b1100, 0b0000, 8 )
  , MakeShape( '╮', 0b1001, 0b0000, 8 )
  , MakeShape( '╰', 0b0110, 0b0000, 8 )

  , MakeShape( '═', 0b0000, 0b1010, 10)
  , MakeShape( '║', 0b0000, 0b0101, 10)
  , MakeShape( '╔', 0b0000, 0b0011, 10)
  , MakeShape( '╗', 0b0000, 0b1001, 10)
  , MakeShape( '╚', 0b0000, 0b0110, 10)
  , MakeShape( '╝', 0b0000, 0b1100, 10)
  , MakeShape( '╠', 0b0000, 0b0111, 10)
  , MakeShape( '╣', 0b0000, 0b1101, 10)
  , MakeShape( '╦', 0b0000, 0b1011, 10)
  , MakeShape( '╩', 0b0000, 0b1110, 10)
  , MakeShape( '╬', 0b0000, 0b1111, 10)

  , MakeShape( '╒', 0b0001, 0b0010, 5 )
  , MakeShape( '╓', 0b0010, 0b0001, 5 )
  , MakeShape( '╕', 0b0001, 0b1000, 5 )
  , MakeShape( '╖', 0b1000, 0b0001, 5 )
  , MakeShape( '╘', 0b0100, 0b0010, 5 )
  , MakeShape( '╙', 0b0010, 0b0100, 5 )
  , MakeShape( '╛', 0b0100, 0b1000, 5 )
  , MakeShape( '╜', 0b1000, 0b0100, 5 )
  , MakeShape( '╞', 0b0101, 0b0010, 5 )
  , MakeShape( '╟', 0b0010, 0b0101, 5 )
  , MakeShape( '╡', 0b0101, 0b1000, 5 )
  , MakeShape( '╢', 0b1000, 0b0101, 5 )
  , MakeShape( '╤', 0b0001, 0b1010, 5 )
  , MakeShape( '╥', 0b1010, 0b0001, 5 )
  , MakeShape( '╧', 0b0100, 0b1010, 5 )
  , MakeShape( '╨', 0b1010, 0b0100, 5 )
  , MakeShape( '╪', 0b0101, 0b1010, 5 )
  , MakeShape( '╫', 0b1010, 0b0101, 5 )

  , MakeShape( '╴', 0b1000, 0b0000, 1 )
  , MakeShape( '╵', 0b0100, 0b0000, 1 )
  , MakeShape( '╶', 0b0010, 0b0000, 1 )
  , MakeShape( '╷', 0b0001, 0b0000, 1 )
  ];

Dictionary<char, Shape> shapesDictionary = shapes.ToDictionary(s => s.Value);

var   Width  = Console.WindowWidth;
var   Height = Console.WindowHeight;
Cell[] cells = Enumerable
  .Range(0, Width*Height)
  .Select(i => new Cell
    {
      X         = i%Width
    , Y         = i/Width
    , CellType  = CellType.Grid
    })
  .ToArray()
  ;



Console.OutputEncoding = Encoding.UTF8;

float fadeOut         = (float)Math.Log10(20);
var screen            = new StringBuilder(1<<16);
//var random          = new Random(19740531);
var random            = Random.Shared;
var priorityComparer  = new ShapePriorityComparer();


{
  // Paste Logo into cells
  var lines     = logo.Split('\n');
  var maxWidth  = lines.Max(l => l.Length);

  if (!(maxWidth <= Width && lines.Length <= Height))
  {
    Console.WriteLine($"Terminal not large enough, need to be at least {maxWidth}x{lines.Length}");
    Environment.ExitCode = 99;
    return;
  }

  var startX = (Width-maxWidth     )/2;
  var startY = (Height-lines.Length)/2;

  for (var y = startY; y < startY+lines.Length; ++y)
  {
    var l = lines[y-startY];
    var yOff = y*Width;

    for (var x = startX; x < startX+maxWidth; ++x)
    {
      var cell = cells[yOff+x];
      if (x-startX >= l.Length) break;

      var s = l[x-startX];
      if (s <= ' ') continue;

      cell.Shape      = s;
      cell.CellType   = CellType.Logo;
    }
  }
}

{
  // Initial freedoms
  for (var y = 0; y < Height; ++y)
  {
    var yOff = y*Width;
    for (var x = 0; x < Width; ++x)
    {
      var cell = cells[yOff+x];
      if (cell.Shape == 0)
      {
        var freedom = 0;
        freedom += GetFreedom(cell, -1, 0);
        freedom += GetFreedom(cell,  1, 0);
        freedom += GetFreedom(cell,  0,-1);
        freedom += GetFreedom(cell,  0, 1);
        cell.Freedom = freedom;
      }
      else
      {
        cell.Freedom = 0;
      }
    }
  }
}

{
  // Wave function collapse algorithm
  //  Watch this: https://www.youtube.com/watch?v=rI_y2GAlQFM
  var candidateCells  = new List<Cell>();
  var candidateShapes = new List<Shape>();

  while (true)
  {
#if DEBUG_WFC
    {
      // Print current cell state

      screen.Clear();
      for (var y = 0; y < Height; ++y)
      {
        var yOff = y*Width;
        for (var x = 0; x < Width; ++x)
        {
          var cell = cells[yOff+x];

          if (cell.Shape == 0)
          {
            screen.Append(cell.Freedom);
          }
          else
          {
            screen.Append(cell.Shape);
          }
        }
        screen.Append('\n');
      }

      Console.Write(screen);
    }
#endif

    var minFreedom      = 1000;
    var undecidedCells  = 0;
    for (var i = 0; i < cells.Length; ++i)
    {
      var cell = cells[i];
      if (cell.Shape == 0)
      {
          minFreedom = Min(minFreedom, cell.Freedom);
          ++undecidedCells;
      }
    }

    if (undecidedCells == 0)
    {
      // All cells have been decided. We are done
      break;
    }

    // Find all cells that have the minimum freedom and have no shape
    candidateCells.Clear();
    for (var i = 0; i < cells.Length; ++i)
    {
      var cell = cells[i];
      if (cell.Freedom == minFreedom && cell.Shape == 0)
      {
          candidateCells.Add(cell);
      }
    }

    Assert(candidateCells.Count > 0);
    // Pick on cell out of those randomly
    var pickedCell = candidateCells[random.Next(0, candidateCells.Count)];
    Assert(pickedCell.Shape == 0);

    var left    = Connection.Undecided;
    var top     = Connection.Undecided;
    var right   = Connection.Undecided;
    var bottom  = Connection.Undecided;

    // Check the picked cell connection status in all directions
    left    = DetermineConnection(pickedCell, 0b0010, -1,  0);
    right   = DetermineConnection(pickedCell, 0b1000,  1,  0);
    top     = DetermineConnection(pickedCell, 0b0001,  0, -1);
    bottom  = DetermineConnection(pickedCell, 0b0100,  0,  1);

    Assert(left   != Connection.Undecided);
    Assert(top    != Connection.Undecided);
    Assert(right  != Connection.Undecided);
    Assert(bottom != Connection.Undecided);

    // Find a shape that matches the connection status
    candidateShapes.Clear();
    for (var i = 0; i < shapes.Length; ++i)
    {
      var shape = shapes[i];

      var good = true;

      good &= CheckShape(shape, left   , 0b1000);
      good &= CheckShape(shape, top    , 0b0100);
      good &= CheckShape(shape, right  , 0b0010);
      good &= CheckShape(shape, bottom , 0b0001);

      if (good)
      {
        var copy = shape;
        copy.Priority += random.Next(0, 10);
        candidateShapes.Add(copy);
      }
    }

    if (candidateShapes.Count == 0)
    {
      // No shape found, default to *
      pickedCell.Shape   = '█';
      pickedCell.Freedom = 0;
    }
    else
    {
      // If sort candidate shapes according to priority
      candidateShapes.Sort(priorityComparer);
      var pickedShape     = candidateShapes[0];
      // Update the shape
      pickedCell.Shape    = pickedShape.Value;
      pickedCell.Freedom  = 0;
    }

    // Finally reduce freedom of adjacent cells
    ReduceFreedom(pickedCell,-1, 0);
    ReduceFreedom(pickedCell, 1, 0);
    ReduceFreedom(pickedCell, 0,-1);
    ReduceFreedom(pickedCell, 0, 1);
  }


}

{
  // Finally let's draw grid

  // Clear screen
  Console.Write("\x1B[2J");

  var candidateCells  = new List<Cell>(4);

  // Main loop
  var sw          = Stopwatch.StartNew();
  var sleepFor    = 0;
  while (!Console.KeyAvailable)
  {
    Thread.Sleep(sleepFor);
    var before= sw.ElapsedMilliseconds;
    var time  = before/1000.0F;

    {
      // Move sparks around
      var sparkHeads = 0;
      for (var i = 0; i < cells.Length; ++i)
      {
        var cell = cells[i];
        switch(cell.CellType)
        {
        case CellType.SparkHead:
          if (cell.CellTypeEnd < time)
          {
            // Move the spark head
            var nextToLogo = false;

            if (shapesDictionary.TryGetValue(cell.Shape, out var shape))
            {
              var connections = shape.ConnectionSingle|shape.ConnectionDouble;

              candidateCells.Clear();
              // Find a place to move to
              if ((0b1000 & connections) != 0) FollowConnection(cells, time, cell, candidateCells, ref nextToLogo, -1,  0);
              if ((0b0010 & connections) != 0) FollowConnection(cells, time, cell, candidateCells, ref nextToLogo,  1,  0);
              if ((0b0100 & connections) != 0) FollowConnection(cells, time, cell, candidateCells, ref nextToLogo,  0, -1);
              if ((0b0001 & connections) != 0) FollowConnection(cells, time, cell, candidateCells, ref nextToLogo,  0,  1);

              Assert(candidateCells.Count <= 4);
              if (!nextToLogo && candidateCells.Count > 0)
              {
                var c = candidateCells[random.Next(0, candidateCells.Count)];
                MakeSparkHead(
                  time
                , c.X
                , c.Y
                , allowSparkTail: true
                , timeOffset: 0
                );
              }

            }

            cell.CellType      = CellType.SparkTail;
            cell.CellTypeBegin = time;
            cell.CellTypeEnd   = time+TimeStep*16;
          }

          ++sparkHeads;
          break;

        case CellType.SparkTail:
          if (cell.CellTypeEnd < time)
          {
            cell.CellType      = CellType.Grid;
            cell.CellTypeBegin = time;
            cell.CellTypeEnd   = EndTime;
          }
          break;
        default:
          break;
        }
      }

      // Add spark heads to board if needed
      for (var i = sparkHeads; i < 20; ++i)
      {
        var timeOffset = (float)(TimeStep*Hash(i+time+123.4));
        MakeSparkHead(
            time
          , random.Next(0, Width)
          , random.Next(0, Height)
          , allowSparkTail: false
          , timeOffset
          );
      }

      var after = sw.ElapsedMilliseconds;
      if (after > before)
      {
        var diff  = after-before;
        sleepFor  = Max(0,(int)(DesiredDelay*1000 - diff));
      }
      else
      {
        sleepFor = (int)(DesiredDelay*1000);
      }
    }


    {
      // Print current cell state

      var fWidth  = 1.0F*Width;
      var fHeight = 1.0F*Height;
      var iWidth  = 1.0F/fWidth;
      var iHeight = 1.0F/fHeight;
      var iHeight2= 0.5F/fHeight;

      var ch = new StringBuilder(64);

      screen.Clear();
      // Goto top, hide cursor
      screen.Append("\x1B[H\x1B[?25l");
      for (var y = 0; y < Height; ++y)
      {
        if (y > 0)
        {
          screen.Append('\n');
        }

        var py = (-fHeight+2.0F*(y+0.5F))*iHeight;
        var yOff = y*Width;
        for (var x = 0; x < Width; ++x)
        {
          var px = (-fWidth+2.0F*(x+0.5F))*iHeight2;
          var p = new Vector2(px, py);
          var cell = cells[yOff+x];

          Assert(cell.Shape >= ' ');
          var col = Palette(x*iWidth+y*iHeight+time);
          var gridFade = Mix(0.25F, 0.005F, (float)Tanh(p.LengthSquared()));
          switch(cell.CellType)
          {
          case CellType.Grid :
            col *= gridFade;
            break;
          case CellType.Logo :
            col = Vector3.SquareRoot(col);
            break;
          case CellType.SparkHead:
            col = Vector3.One;
            break;
          case CellType.SparkTail :
            var fade  = Exp(-fadeOut*(time-cell.CellTypeBegin)/(cell.CellTypeEnd-cell.CellTypeBegin));
            col       += new Vector3((float)(0.5*fade*fade));
            col       *= Mix(gridFade, 1, (float)fade);
            break;
          default            :
            // Red for error
            Assert(false);
            col = new Vector3(1,0,0);
            break;
          }

          col = Vector3.Clamp(col, Vector3.Zero, Vector3.One);
          col = Vector3.SquareRoot(col);

          screen.Append($"\x1B[38;2;{(byte)Round(col.X*255)};{(byte)Round(col.Y*255)};{(byte)Round(col.Z*255)}m{cell.Shape}");
        }
      }
      screen.Append("\x1B[0m");
      Console.Write(screen);
    }
  }

  // Show cursor
  Console.Write("\x1B[?25h");
}

static float Mix(float a, float b, float x)
{
  return a + (b-a)*x;
}

static double Fract(double x)
{
  return x-Floor(x);
}

static double Hash(double co)
{
  return Fract(Sin(co*12.9898F) * 13758.5453F);
}

static Vector3 Palette(float a)
{
  return 0.5F*(new Vector3(1)+Vector3.Sin(new Vector3(0,1,2)+new Vector3(a)));
}

static Shape MakeShape(char v, int connectionSingle, int connectingDouble, int Priority) =>
  new Shape
  {
    Value             = v
  , ConnectionSingle  = connectionSingle
  , ConnectionDouble  = connectingDouble
  , Priority          = Priority
  };

void MakeSparkHead(
    float time
  , int   x
  , int   y
  , bool  allowSparkTail
  , float timeOffset
  )
{
  if (x < 0 || x > Width - 1)
  {
    return;
  }

  if (y < 0 || y > Height - 1)
  {
    return;
  }

  var cell = cells[x+y*Width];

  switch (cell.CellType)
  {
  case CellType.SparkTail:
  case CellType.Grid:
    if (cell.CellType == CellType.SparkTail && !allowSparkTail)
    {
      break;
    }
    cell.CellType      = CellType.SparkHead;
    cell.CellTypeBegin = time;
    cell.CellTypeEnd   = time+timeOffset+TimeStep;
    break;
  default:
    break;
  }
}

void FollowConnection(
    Cell[]      cells
  , float       time
  , Cell        cell
  , List<Cell>  cellCandidates
  , ref bool    nextToLogo
  , int         deltaX
  , int         deltaY
  )
{
  int x = cell.X + deltaX;
  int y = cell.Y + deltaY;

  if (x < 0 || x >= Width)
  {
    return;
  }

  if (y < 0 || y >= Height)
  {
    return;
  }

  var c = cells[x + y*Width];
  switch(c.CellType)
  {
  case CellType.Grid:
    break;
  case CellType.SparkTail:
    if (c.CellTypeBegin + TimeStep*2 < time)
    {
      break;
    }
    else
    {
      return;
    }
  case CellType.Logo:
    nextToLogo = true;
    return;
  default:
    return;
  }

  cellCandidates.Add(c);
}

int GetFreedom(
    Cell  cell
  , int   deltaX
  , int   deltaY
  )
  {
  int x = cell.X + deltaX;
  int y = cell.Y + deltaY;

  if (x < 0 || x >= Width)
  {
    return 1;
  }

  if (y < 0 || y >= Height)
  {
    return 1;
  }

  var neighbour = cells[x+y*Width];

  return neighbour.Shape == 0 ? 1 : 0;
}

bool CheckShape(
    Shape       shape
  , Connection  connection
  , int         test
  )
{
  Assert((shape.ConnectionSingle&shape.ConnectionDouble) == 0);

  switch(connection)
  {
  case Connection.Free:
    return true;
  case Connection.NoConnection:
    return (test & shape.ConnectionSingle) == 0 && (test & shape.ConnectionDouble) == 0;
  case Connection.ConnectedToSingle:
    return (test & shape.ConnectionSingle) != 0;
  case Connection.ConnectedToDouble:
    return (test & shape.ConnectionDouble) != 0;
  default:
    Assert(false);
    return false;
  }
}

void ReduceFreedom(
    Cell  cell
  , int   deltaX
  , int   deltaY
  )
{
  int x = cell.X + deltaX;
  int y = cell.Y + deltaY;

  if (x < 0 || x >= Width)
  {
    return;
  }

  if (y < 0 || y >= Height)
  {
    return;
  }

  var updateCell= cells[x+y*Width];

  if (updateCell.Freedom > 0)
  {
    --updateCell.Freedom;
  }
}


Connection DetermineConnection(
    Cell  cell
  , int   test
  , int   deltaX
  , int   deltaY
  )
  {
  int x = cell.X + deltaX;
  int y = cell.Y + deltaY;

  if (x < 0 || x >= Width)
  {
    return Connection.Free;
  }

  if (y < 0 || y >= Height)
  {
    return Connection.Free;
  }

  var neighbour  = cells[x+y*Width];
  var shape      = neighbour.Shape;
  if (shape == 0)
  {
    return Connection.Free;
  }
  else
  {
    if(!shapesDictionary.TryGetValue(shape, out var f))
    {
      return Connection.Free;
    }

    var connectionToSingle = f.ConnectionSingle;
    var connectionToDouble = f.ConnectionDouble;
    Assert((connectionToSingle&connectionToDouble) == 0);

    var hasSingle = (test & connectionToSingle) != 0;
    var hasDouble = (test & connectionToDouble) != 0;
    Assert(!(hasSingle&&hasDouble));

    if (hasSingle)
    {
      return Connection.ConnectedToSingle;
    }
    else if (hasDouble)
    {
      return Connection.ConnectedToDouble;
    }
    else
    {
      return Connection.NoConnection;
    }
  }
}

struct Shape
{
  public char    Value            ;
  public int     ConnectionSingle ;
  public int     ConnectionDouble ;
  public int     Priority         ;
}

class ShapePriorityComparer : IComparer<Shape>
{
  public int Compare(Shape x, Shape y)
  {
    return y.Priority.CompareTo(x.Priority);
  }
}

enum CellType
{
    Null
  , Grid
  , Logo
  , SparkHead
  , SparkTail
}

enum Connection
{
    Undecided
  , Free
  , NoConnection
  , ConnectedToSingle
  , ConnectedToDouble
};

class Cell
{
  public int      Freedom       = 0   ;
  public char     Shape         = '\0';
  public int      X             = 0   ;
  public int      Y             = 0   ;
  public CellType CellType      = 0   ;
  public double   CellTypeBegin = 0   ;
  public double   CellTypeEnd   = 0   ;
}