# HG changeset patch
# User unC0Rr
# Date 1736718527 -3600
# Node ID 9ad74696ddec40b75e7ee0d0d8e7ee73d599d305
# Parent  2d65bd46c92fb1d8fd70df8e5c13273b2a2c3e15
Add some progress on hhtracer

diff -r 2d65bd46c92f -r 9ad74696ddec tools/hhtracer/Main.qml
--- a/tools/hhtracer/Main.qml	Fri Jan 10 17:37:34 2025 +0100
+++ b/tools/hhtracer/Main.qml	Sun Jan 12 22:48:47 2025 +0100
@@ -32,6 +32,10 @@
           stepTimer.stop();
         }
       }
+
+      Label {
+        text: "Best: %1".arg(tracer.bestSolution)
+      }
     }
   }
 
@@ -55,7 +59,7 @@
   Timer {
     id: stepTimer
 
-    interval: 1500
+    interval: 120
     repeat: true
     running: false
     triggeredOnStart: true
@@ -70,14 +74,14 @@
       id: baseImage
 
       Layout.fillWidth: true
-      Layout.preferredHeight: 128
+      Layout.preferredHeight: 32
       fillMode: Image.PreserveAspectFit
     }
 
     GridLayout {
       Layout.fillWidth: true
       Layout.fillHeight: true
-      columns: 10
+      columns: 50
 
       Repeater {
         model: tracer.solutions
diff -r 2d65bd46c92f -r 9ad74696ddec tools/hhtracer/main.cpp
--- a/tools/hhtracer/main.cpp	Fri Jan 10 17:37:34 2025 +0100
+++ b/tools/hhtracer/main.cpp	Sun Jan 12 22:48:47 2025 +0100
@@ -9,10 +9,6 @@
 
   QQmlApplicationEngine engine;
 
-  // Tracer tracer;
-  // engine.rootContext()->setContextProperty(QStringLiteral("tracer"),
-  // &tracer);
-
   QObject::connect(
       &engine, &QQmlApplicationEngine::objectCreationFailed, &app,
       []() { QCoreApplication::exit(-1); }, Qt::QueuedConnection);
diff -r 2d65bd46c92f -r 9ad74696ddec tools/hhtracer/tracer.cpp
--- a/tools/hhtracer/tracer.cpp	Fri Jan 10 17:37:34 2025 +0100
+++ b/tools/hhtracer/tracer.cpp	Sun Jan 12 22:48:47 2025 +0100
@@ -3,18 +3,18 @@
 #include <QRandomGenerator>
 #include <QSvgGenerator>
 
-Tracer::Tracer(QObject* parent)
+Tracer::Tracer(QObject *parent)
     : QObject{parent},
       palette_{{Qt::black,
                 Qt::white,
+                {"#9f086e"},
                 {"#f29ce7"},
-                {"#9f086e"},
                 {"#54a2fa"},
                 {"#2c78d2"}}} {}
 
 QList<QColor> Tracer::palette() const { return palette_; }
 
-void Tracer::setPalette(const QList<QColor>& newPalette) {
+void Tracer::setPalette(const QList<QColor> &newPalette) {
   if (palette_ == newPalette) return;
   palette_ = newPalette;
   emit paletteChanged();
@@ -22,43 +22,84 @@
 
 double Tracer::bestSolution() const { return bestSolution_; }
 
-void Tracer::start(const QString& fileName) {
+void Tracer::start(const QString &fileName) {
   qDebug() << "Starting using" << fileName;
 
   bestSolution_ = 0;
   solutions_.clear();
   generation_.clear();
-  image_ = QImage{};
+  referenceImage_ = QImage{};
 
   if (palette_.isEmpty()) {
     qDebug("Empty palette");
     return;
   }
 
-  image_.load(QUrl(fileName).toLocalFile());
+  referenceImage_.load(QUrl(fileName).toLocalFile());
 
-  if (image_.isNull()) {
+  if (referenceImage_.isNull()) {
     qDebug("Failed to load image");
     return;
   }
 
-  for (int i = 0; i < 100; ++i) {
+  for (int i = 0; i < 600; ++i) {
     generation_.append(Solution{{32, 32}, palette_});
   }
 }
 
 void Tracer::step() {
+  const auto size = generation_.size();
+  const auto keepSize = 10;
+  const auto replaceSize = 50;
+  const auto kept = generation_.mid(0, keepSize);
+  generation_ = generation_.mid(0, size - replaceSize);
+
+  for (int i = 0; i < replaceSize; ++i) {
+    generation_.append(Solution{{32, 32}, palette_});
+  }
+
+  auto rg = QRandomGenerator::global();
+
+  for (qsizetype i = 0; i < size; i += 4) {
+    const auto first = rg->bounded(size);
+    const auto second = rg->bounded(size);
+
+    if (first != second) {
+      generation_[first].crossover(generation_[second]);
+    }
+  }
+
+  std::for_each(std::begin(generation_), std::end(generation_),
+                [this](auto &s) { s.mutate(palette_); });
+
+  std::for_each(std::begin(solutions_), std::end(solutions_),
+                [this](const auto &fn) { QFile::remove(fn); });
   solutions_.clear();
 
-  for (auto& solution : generation_) {
-    const auto fileName = newFileName();
-    solutions_.append(fileName);
+  generation_.append(kept);
 
-    solution.render(fileName);
+  for (auto &solution : generation_) {
+    solution.render(newFileName());
+
+    solution.calculateFitness(referenceImage_);
+
+    solution.fitness += solution.cost() * 100;
   }
 
-  qDebug() << solutions_;
+  std::sort(std::begin(generation_), std::end(generation_),
+            [](const auto &a, const auto &b) { return a.fitness < b.fitness; });
+
+  std::for_each(std::begin(generation_) + size, std::end(generation_),
+                [](const auto &s) { QFile::remove(s.fileName); });
+  generation_.remove(size, kept.size());
 
+  bestSolution_ = generation_[0].fitness;
+
+  std::transform(std::begin(generation_), std::end(generation_),
+                 std::back_inserter(solutions_),
+                 [](const auto &a) { return a.fileName; });
+
+  emit bestSolutionChanged();
   emit solutionsChanged();
 }
 
@@ -71,12 +112,48 @@
       QStringLiteral("hedgehog_%1.svg").arg(counter, 3, 32, QChar(u'_')));
 }
 
-Solution::Solution(QSizeF size, const QList<QColor>& palette) : size{size} {
+Solution::Solution(QSizeF size, const QList<QColor> &palette) : size{size} {
   fitness = 0;
-  primitives = {Primitive(size, palette)};
+  primitives = {Primitive(size, palette), Primitive(size, palette)};
 }
 
-void Solution::render(const QString& fileName) const {
+void Solution::calculateFitness(const QImage &target) {
+  QImage candidate{fileName};
+
+  if (candidate.isNull()) {
+    fitness = 1e32;
+    return;
+  }
+
+  // Both images assumed same size, same format
+  double diffSum = 0;
+  int width = target.width();
+  int height = target.height();
+
+  for (int y = 0; y < height; ++y) {
+    auto candScan = reinterpret_cast<const QRgb *>(candidate.scanLine(y));
+    auto targScan = reinterpret_cast<const QRgb *>(target.scanLine(y));
+    for (int x = 0; x < width; ++x) {
+      // Compare RGBA channels
+      const QRgb cPix = candScan[x];
+      const QRgb tPix = targScan[x];
+      // const auto ca = qAlpha(cPix) / 255.0;
+      const auto ta = qAlpha(tPix) / 255.0;
+      const auto dr = qRed(cPix) - qRed(tPix);
+      const auto dg = qGreen(cPix) - qGreen(tPix);
+      const auto db = qBlue(cPix) - qBlue(tPix);
+      const auto da = qAlpha(cPix) - qAlpha(tPix);
+      diffSum +=
+          qMax(qMax(qMax(dr * dr, dg * dg), db * db) * ta, da * da * 1.0);
+    }
+  }
+
+  fitness = diffSum;
+}
+
+void Solution::render(const QString &fileName) {
+  this->fileName = fileName;
+
   const auto imageSize = size.toSize();
 
   QSvgGenerator generator;
@@ -90,7 +167,7 @@
   painter.begin(&generator);
   painter.setRenderHint(QPainter::Antialiasing, true);
 
-  for (const auto& primitive : primitives) {
+  for (const auto &primitive : primitives) {
     painter.setPen(primitive.pen);
     painter.setBrush(primitive.brush);
     painter.resetTransform();
@@ -120,7 +197,98 @@
                          [](auto a, auto p) { return a + p.cost(); });
 }
 
-Primitive::Primitive(QSizeF size, const QList<QColor>& palette) {
+void Solution::mutate(const QList<QColor> &palette) {
+  if (primitives.isEmpty()) {
+    return;
+  }
+
+  auto rg = QRandomGenerator::global();
+  double mutationRate = 0.05;
+
+  if (rg->bounded(1.0) > mutationRate) {
+    return;
+  }
+
+  for (auto &prim : primitives) {
+    // Pen width
+    if (rg->bounded(1.0) < mutationRate) {
+      prim.pen.setWidthF(prim.pen.widthF() * (rg->bounded(1.5) + 0.5) + 0.05);
+    }
+
+    // Origin
+    if (rg->bounded(1.0) < mutationRate) {
+      prim.origin += QPointF(rg->bounded(10.0) - 5.0, rg->bounded(10.0) - 5.0);
+    }
+
+    if (prim.type == Polygon) {
+      // Points
+      for (auto &pt : prim.points) {
+        if (rg->bounded(1.0) < mutationRate) {
+          prim.origin +=
+              QPointF(rg->bounded(10.0) - 5.0, rg->bounded(10.0) - 5.0);
+        }
+      }
+    } else {  // Circle/ellipse
+      if (rg->bounded(1.0) < mutationRate) {
+        prim.radius1 *= rg->bounded(0.4) + 0.8;
+      }
+      if (rg->bounded(1.0) < mutationRate) {
+        prim.radius2 *= rg->bounded(0.4) + 0.8;
+      }
+      if (rg->bounded(1.0) < mutationRate) {
+        prim.rotation = rg->bounded(90.0);
+      }
+    }
+  }
+
+  if (rg->bounded(1.0) < mutationRate) {
+    auto i = rg->bounded(primitives.size());
+
+    Primitive p{size, palette};
+    primitives.insert(i, p);
+  }
+
+  if (rg->bounded(1.0) < mutationRate) {
+    auto i = rg->bounded(primitives.size());
+
+    primitives.remove(i);
+  }
+}
+
+void Solution::crossover(Solution &other) {
+  const auto n = qMin(primitives.size(), other.primitives.size());
+
+  auto rg = QRandomGenerator::global();
+
+  if (rg->bounded(1.0) < 0.02) {
+    if (n <= 1) {
+      return;
+    }
+    // swap tails
+    const auto cp = rg->bounded(1, primitives.size());
+    const auto ocp = rg->bounded(1, other.primitives.size());
+
+    const auto tail = primitives.mid(cp);
+    const auto otherTail = other.primitives.mid(ocp);
+
+    primitives.remove(cp, primitives.size() - cp);
+    other.primitives.remove(ocp, other.primitives.size() - ocp);
+
+    primitives.append(otherTail);
+    other.primitives.append(tail);
+  } else {
+    if (n < 1) {
+      return;
+    }
+    // swap one element
+    const auto cp = rg->bounded(primitives.size());
+    const auto ocp = rg->bounded(other.primitives.size());
+
+    qSwap(primitives[cp], other.primitives[ocp]);
+  }
+}
+
+Primitive::Primitive(QSizeF size, const QList<QColor> &palette) {
   auto rg = QRandomGenerator::global();
   auto randomPoint = [&]() -> QPointF {
     return {rg->bounded(size.width()), rg->bounded(size.height())};
@@ -134,8 +302,8 @@
   } else {
     type = Circle;
 
-    radius1 = rg->bounded(size.width());
-    radius2 = rg->bounded(size.width());
+    radius1 = rg->bounded(size.width() * 0.2) + 2;
+    radius2 = rg->bounded(size.width() * 0.2) + 2;
     rotation = rg->bounded(90);
   }
 
diff -r 2d65bd46c92f -r 9ad74696ddec tools/hhtracer/tracer.h
--- a/tools/hhtracer/tracer.h	Fri Jan 10 17:37:34 2025 +0100
+++ b/tools/hhtracer/tracer.h	Sun Jan 12 22:48:47 2025 +0100
@@ -23,11 +23,14 @@
   QList<Primitive> primitives;
   double fitness;
   QSizeF size;
+  QString fileName;
 
   explicit Solution(QSizeF size, const QList<QColor>& palette);
-  void calculateFitness(const QImage& image);
-  void render(const QString& fileName) const;
+  void calculateFitness(const QImage& target);
+  void render(const QString& fileName);
   double cost() const;
+  void mutate(const QList<QColor>& palette);
+  void crossover(Solution &other);
 };
 
 class Tracer : public QObject {
@@ -64,7 +67,7 @@
   QStringList solutions_;
   QList<Solution> generation_;
   QTemporaryDir tempDir_;
-  QImage image_;
+  QImage referenceImage_;
 
   QString newFileName();
 };