Find one that can manipulate bitmaps (.bmp) with optional support for other formats :)

For each class ClassName you write in library/src, write a corresponding tester class ClassNamerTester in test/src. Fill this class with methods of the form testFeature which test certain features, using assert among other testing statements to express expected outputs. Use stdout to log (std::cout or printf or something), you can call the tester program and pipe the output to a file for logging if neccessary. For example, have something like SolverTester with a method called void testMinEntropyHeuristic().

What tests to write? Try to write tests that make sure key functionality is working. Use maximizing code coverage as your guideline. The more of the code is tested (higher coverage scores), generally will decrease bugs if the tests are actually verifying for correctness.

You can write public helper methods in the library classes to access class internals using the #ifdef directive. Right now, we are compiling the test program with the CMAKE_BUILD_TYPE set to 'Debug'. I added a compile definition called TEST_DEBUG which is added when this is the build type. You can do something like

#ifdef TEST_DEBUG

InternalData getInternals();

#endif

And then use that method in your tests. This method will be ignored when compiling the library for production. It won't affect coverage since you should write these because you need to use them anyway.

A class which takes as input an image (.bmp) and a pixel size n. It splits the input image into 2D tiles of size n_x_n pixels. It should also keep track of the adjacencies between the tiles. Look at #1 for definitions of the Side type and the Direction enum. The tiles should be returned as an std::map<int, Tile> or maybe even just a std::vector<Tile>, and the adjacencies should be returned as a std::map<std::pair<int, Direction>, std::vector<int>>. Tile could be a resource holder class which stores the tile image data in-memory, or maybe references a file in the filesystem which is created by the Extractor, whichever makes more sense. For every n_x_n slice of the image, it should create a tile for all rotations of that tile (0, 90, 180, 270 degrees). The adjacencies can be decided two ways:

• If two n_x_n tiles are adjacent in the input tile map, make note of that adjacency.
• If the colors match pixel by pixel on opposing sides, two n_x_n tiles are adjacent.

Maybe an enum or bool to decide the adjacency policy.

Can add a series of tests to a CMakeLists.txt file, which is just a program. Has profiling info.

Can make a test suite per class, to be its own executable. And the whole suite comprise all of the unit tests.

ITERATION1:
A class implementing the WFC algorithm for 2D grids. It uses an auxiliary Grid class to abstract the details of the grid. A Direction enum could help:

enum Direction { UP, DOWN, LEFT, RIGHT };

typedef std::pair<int, Direction> Side; //tile and direction for constraints

class Grid {
public:
  Grid(int N);
  inline int get(int i, int j);
  inline int set(int i, int j);
};

class Solver {
public:
  Solver(std::vector<int> tiles, std::map<Side, std::vector<int>> constraints, int seed=0);
  void setSeed(int seed);
  Grid solve(int N);

  //calls registered function with tile in collapsed grid slot
  void onCollapse(std::function<void(int, int, int)> callback);

  //calls registered function with possible tiles in collapsed grid slot
  void onPropagate(std::function<void(std::vector<int>, int, int)> callback); 
};

ITERATION 2:
Add a template parameter to determine the tile type. Makes callbacks easier to use. Options for choosing custom collapse heuristic instead of the min entropy heuristic:

template<typename T>
class Solver {
public:
  Solver(std::map<int, T> tiles, std::map<Side, std::vector<int>> constraints, int seed=0);
  void setSeed(int seed);
  Grid<T> solve(int N); //Grid parameterized in the obvious way

  //low level function to change heuristic (change vector to a span/iterable through templating?
  void setHeuristic(std::function<int(std::vector&<int>)> );
  void setHeuristic(std::function<int(std::vector&<int>, std::map<int, T>& tiles)> );

  //calls registered function with tile in collapsed grid slot
  void onCollapse(std::function<void(T, int, int)> callback);

  //calls registered function with possible tiles in collapsed grid slot
  void onPropagate(std::function<void(std::vector<T>, int, int)> callback); 

private:
   std::map<int, T> tiles
};

Something like the Bridge pattern. The Solver class would define an interface for interacting with a more algorithmically focused, lower level WFC class. Due to the way that the WFC algorithm works (expensive iterations inside one call to the algorithm), the classical Object Oriented Bridge pattern works well here, as a singular virtual call to Solver::solver will have minimal overhead compared to the runtime of WFC as a whole. That said, any polymorphism with respect to the WFC class itself would have to be template-based as to avoid virtual method calls. This would be a compile-time polymorphic instance of the Strategy pattern, a concept for WFC would be good here. The Template Method pattern would work well here to limit the way inheritance can change the implementation (certain things are necessary like initializing first and filling the grid last).

An outline:

#include <Position.h>

template<typename T>
concept WFC = requires(T wfc)
{
      {wfc.initialize( std::size_t() ) } -> void;
      {wfc.reset( ) } -> void;

      {wfc.isCollapsed( ) } -> bool;
      {wfc.isContradiction( ) } -> bool;
      
      {wfc.getMinEntropyPosition( ) } -> Position;
      {wfc.collapseAt(Position) } -> void;
      {wfc.propagate(Position) } -> void;
      
      {wfc.fill(Grid&) } -> void;
      
      //stream API (look up syntax later)
      {operator>>(const T,  Position&)} -> T&;
      {operator<<(T,  Position)} -> T&;
      {wfc.bool()} -> bool
};

template<WFC T>
class Solver {

friend class T; //T has access to the Solver's internals!

public:
    void solve(size_t N, Grid& grid) {
         wfc.initialize(N);
         this->run();
         wfc.fill(grid);
    }
...
protected:
    virtual void run() {
         while (wfc.isCollapsed()) {
              Position p = wfc.getMinEntropyPosition();
              wfc.collapseAt(p);
              wfc.propagate(p);
         }
    }

    T wfc;
};

/**
* Naive restart solver outline (can be inlined if the superclass call has virtual overhead) (might be irrelevant)?
*/
template<WFC T>
class RestartSolver : public Solver<T> {
protected:
    virtual void run() override {
         do {
              wfc.reset();
              Solver<T>::run();
          } while (wfc.isContradiction())
    }
};

/**
* Naive backtrack search solver outline
*/
template<WFC T>
class BacktrackSolver : public Solver<T> {
protected:
    virtual void run() override { 
         wfc.initialize(N);

         std::stack<T> grids;
         
         grids.push(this->wfc);
         
         while (!grids.empty()) {
              T cur = grids.pop();
              
              Position p;
              while (cur >> p) {
                   T neighbor = *this;  //copy
                   neighbor << p;
                   if (neighbor.isCollapsed()) {
                        this->wfc = std::move(neighbor);
                        return;
                   }
                   if (!neighbor.isContradiction())
                        grids.push(neighbor);
              }
         }
    }
};

WFC might have the current implementation using tile keys and vectors, or one using dynamic bitsets which would be more efficient I think.

This helps users integrate the library into their projects effectively, to avoid name collisions with other classes (since some of our names are common, such as Direction, Solver, Position, Grid, etc)

Not a big concern at the moment. But it should be done.

A class which holds the data for a tile. Can be in-memory, as a resource handle for a file in the filesystem, whatever. Make sure that it can be queried for information relevant to the algorithm, i.e. for pixel data at the edges of each side, for example. Maybe have something like a

class Tile {
public:
     bool matchesColors(Tile other, Direction d);
};

or something like that as the interface, and using whatever bitmap manipulation image library we are using to utilize the pixel color data in the implementation.

Modify an std::array buffer passed by reference instead of returning a newly allocated vector

Under directory "test"

alternatively a dynamic bitset (Boost) for dynamic size. Templating can be used to use std::bitsets whenever a fixed static size is given.

Support for a standardized representation or controller for constraints. Should facilitate communication between Solver and Extractor.

Also a helper class for serializing/deserializing constraints to/from json. Using a format like:

[{
0 : {
"up": [0,...]
"left": [0,...]
"down": [0,...]
"right": [0,...]
},
...]

A class which takes a Grid and generates an image from it. See #2 for info about the Tile class. It should hold info about tile image data. The Synthesizer takes a Grid and generates a final image, then saves it to disk, or returns a resource holder object for it.

This and #2 should use a library for reading/writing bitmap images. A single header library or a CMake-integrated library would work.

Under a demo directory, to be compiled apart from the coverage maximizing unit tester