Інтерактивний граф з нуля у Flutter: фізика, анімації та CustomPainter

💡 Усі статті, обговорення, новини про Mobile — в одному місці. Приєднуйтесь до Mobile спільноти!

Привіт! Мене звати Олексій. Більше десяти років займаюсь мобільною розробкою, а останні п’ять зосереджуюсь переважно на Flutter. Час від часу в роботі трапляються завдання, які захоплюють настільки, що хочеться поділитися досвідом.

У цій статті я розповім, як створював інтерактивний Knowledge Graph з нуля — повністю на Flutter, без сторонніх графічних чи фізичних бібліотек.

Хочу розповісти про свій досвід створення інтерактивного Knowledge Graph. Він зроблений повністю на Flutter, без використання сторонніх графічних чи фізичних бібліотек.

Спочатку пару слів про те, що це все таке.

Уявіть, що у вас є спрощена база знань про ваше життя та контакти. У ній є лише люди, місця, події та групи, що обʼєднують людей. Усі ці сутності пов’язані між собою звʼязками. Наприклад, ми знаємо, що John Doe зі своєю дочкою Emily відвідав концерт DJ Nebula, що проходив у клубі "Cosmic Pulse". З цього можна скласти такий датасет:

Так ось, задачею було створити графічне відображення такого датасету з базовими можливостями для редагування і, бажано, з фізикою, схожою на Graph View в Obsidian.

Фінальний код проєкту ви можете роздивитись за цим посиланням.

Фізика

У Graph View в Obsidian ноди поводять себе так, наче з’єднані пружинами. Тож я вирішив спробувати реалізувати просту пружинну механіку. ChatGPT нагадав закон Гука, який описує поведінку пружини, і зробив простенький приклад.

Насправді все досить просто. Cила, що діє на тіло, прямо пропорційна подовженню пружини:

force = stiffness * deltaLength

Оскільки ми працюємо у двовимірному просторі, то додаємо ще напрямок сили у вигляді нормалізованого вектора:

forceVector = normalizedVector * stiffness * deltaLength

Силу можна вважати прискоренням, тому легко вирахувати зміну швидкості тіла і, в свою чергу, його координати.

velocity = currentVelocity + force * deltaT (час з попередньої ітерації)

position = currentPosition + velocity * deltaT

Останній штрих. Треба додати затухання (damping), щоб ця система з часом сповільнювалася і врешті-решт зупинялася. Тому швидкість в останній формулі варто ще помножити на exp(-deltaT * damping)

velocity = (currentVelocity + force * deltaT) * exp(-deltaT * damping)

Тож були створені моделі для тіл і пружин:

class Body {
  String id;
  Offset position;
  Offset velocity;

}

class Spring {
  String id;
  String body1Id;
  String body2Id;
  double targetLength;
  double stiffness;
  double damping;
}

...і PhysicsEngine з таким інтерфейсом:

abstract interface class PhysicsEngine extends ChangeNotifier {
  Map<String, Body> get bodies;
  Map<String, Spring> get springs;
  String? ignoreBodyId;            // коли тягнемо ноду, то вона має ігнорувати фізику
  void addBody(Body body);
  void addSpring(Spring spring);
  void removeSpring(String id);
  void removeBody(String id);
  Offset getBodyPosition(String id);   // для малювання
  List<({String id, double distance})> getNearestObjects({    // для пошуку найближчої ноди під пальцем/курсором
    required Offset position,
    required double distance,
  });
  void updateBody(String id, {Offset? position, Offset? velocity});
}

Всередині також є приватний метод _updateWorld, який виконує описану вище математику для кожної пружини та тіла на кожному кроці часу (deltaT).

void _updateWorld(Duration elapsed) {
  final deltaT = (elapsed.inMilliseconds - _latestTick) / 1000;
  _latestTick = elapsed.inMilliseconds;
  if (deltaT <= 0) return;
  // iterate over all springs to update bodies velocities
  for (final spring in _springs.values) {
    final firstBody = _bodies[spring.body1Id];
    final secondBody = _bodies[spring.body2Id];
    if (firstBody == null || secondBody == null) continue;
    final displacement = secondBody.position - firstBody.position;
    // avoid division by zero
    final currentLength =
        displacement.distance == 0 ? minimumDistance : displacement.distance;
    final deltaLength = displacement.distance - spring.targetLength;
    final normalizedVector = displacement / currentLength;

    final forceVector =
        normalizedVector * spring.stiffness * deltaLength / 2.0;
    final deltaVelocity = forceVector * deltaT;
    Offset firstBodyVelocity = firstBody.velocity + deltaVelocity;
    Offset secondBodyVelocity = secondBody.velocity - deltaVelocity;
    // apply spring damping
    firstBodyVelocity *= exp(-deltaT * spring.damping);
    secondBodyVelocity *= exp(-deltaT * spring.damping);
    // update both bodies velocity
    updateBody(spring.body1Id, velocity: firstBodyVelocity);
    updateBody(spring.body2Id, velocity: secondBodyVelocity);
  }

  // iterate over all bodies to update their positions and apply global damping
  bool isChanged = false;
  for (final body in _bodies.values) {
    final velocity =
        body.velocity * exp(-deltaT * _damping); // apply global damping
    final position = body.position + velocity * deltaT;
    isChanged =
        isChanged ||
        position.dx.round() != body.position.dx.round() ||
        position.dy.round() != body.position.dy.round() ||
        velocity.distance > minimumSignificantSpeed;
    updateBody(
      body.id,
      position: position,
      velocity: velocity,
    );
  }

  // stop ticker if no significant changes were made
  if (!isChanged) {
    _ticker.stop();
  }

  notifyListeners();
}

Розміщення нод

Тепер потрібно було придумати, як розмістити ноди з датасету і як до них застосувати фізику. Придумав таку схему:

• Усі ноди прикріплені до своїх «місць» пружинами з нульовою довжиною. Для цього виділив окремий вид пружини, яка з’єднує не тіло з тілом, а тіло з фіксованими координатами (анкер).
• Ноди, що знаходяться близько одна до одної, об’єднані слабкими пружинками, щоб, коли тягнеш одну, сусідні трохи тягнулися за нею.

Це вже дало гарний результат, який видно на початку відео. Але ще потрібно було, щоб при віддаленні зуму ноди обʼєднувалися в групи, а також придумати механізм селекту нод, який би гарно показував їхні власні звʼязки. Для цього реалізував механізм активації/деактивації пружин по типу. В пружини додались такі поля:

final SpringType type;

final bool isActive;

Тепер при створенні пружини їй давався тип, який описує її призначення, а саме описані вище anchor і nearest, а також нові groupAnchor і selected.

А в PhysicsEngine зʼявилися такі методи:

void removeSpringsByType(SpringType type);
void setSpringActive(String id, {required bool active});
void setSpringsActiveByType(SpringType type, {required bool active});
void setSpringsActiveByBodyId(String id, {required bool active});

Таким чином при певному значенні зуму я деактивую всі пружини з типами anchor і nearest, і одночасно активую з groupAnchor, які з самого початку були додані неактивними. Так само коли я роблю селект певної ноди, то для кожної, повʼязаної з нею ноди я деактивую всі пружини і додаю пружину з тегом selected, яка пересуне ноду в потрібне мені місце.

Дуже прикольно було цим всім керувати! Ти вмикаєш, вимикаєш пружинки, а далі фізика все робить автоматично. Навіть додавання і видалення нод запрацювало майже з коробки. Просто видаляєш всі пружини і прораховуєш та додаєш нові, а рушій робить свою магію.

Вʼюпорт

Спочатку думав покласти все це у InteractiveViewer (Flutter-віджет для скролу і зуму), але не вийшло. Мені потрібна була можливість рухати ноди і тапати їх і це конфліктувало з GestureRecognizer самого InteractiveViewer. Довелося створити власний Viewport з єдиним GestureRecognizer, який відповідає за все:

• tap по ноді;
• drag ноди;
• drag всього вʼюпорту;
• zoom;
• rotate.

Тут зʼявилися додаткові челенджі:

• правильно конвертувати координати з простору екрану у простір вʼюпорту і назад;
• забезпечити плавність руху вʼюпорту (з інерцією);
• для мобільних жестів поворот робити навколо центру між двома пальцями;
• для десктопа — зум робити відносно позиції курсора.

Складно, але цікаво. Щоб отримати плавність, я використав той самий PhysicsEngine і для вʼюпорту. В нього поклав лише одне тіло, позиція якого відповідає зміщенню вʼюпорту. Коли тягнеш вʼюпорт, то фактично просто змінюєш позицію цього тіла, а після відпускання воно рухається по інерції і поступово зупиняється завдяки фізиці.

Коли ж ми селектимо певну ноду, то нам треба перемістити вʼюпорт так, щоб ця нода опинилася посередині екрану. Тоді я додаю сильну пружину нульової довжини між тілом вʼюпорту та необхідним офсетом. Вʼюпорт плавно «підлітає» до потрібного місця, а ця пружина через 1 секунду видаляється.

Анімації

Які ще анімації?! Все ж і так вже анімується!

Виявилося, що мені потрібні додаткові:

• анімація розміру ноди при додаванні/видаленні;
• анімація появи оверлею при селекті ноди.

А оскільки малювання всієї вʼюхи виконується CustomPainterами на канвасі, то ми не можемо тут використовувати Animated віджети. Тому я зробив простий механізм анімованих параметрів з таким інтерфейсом:

abstract interface class AnimatedParams extends ChangeNotifier {
  double? get(String key);
  void addAnimation(
    String key, {
    required double from,
    required double to,
    required Duration duration,
    Curve curve = Curves.linear,
    void Function()? onComplete,
  });
}

Тепер я міг додавати анімовані параметри мати доступ до їх поточного значення всередині пейнтера.

final nodeRadius = defaultRadius * viewportState.scale * (animatedParams.get('${node.id}-scale') ?? 1.0);

Все разом

Маємо:

• основний фізичний рушій для нод;
• ще один для вʼюпорту;
• та анімовані параметри.

Кожен має власний Ticker. У віджеті KnowledgeGraphView є головний Ticker, який перевіряє, чи є зміни хоча б в одному рушії — і якщо так, ініціює перемальовку. Фізичний рушій вимикає свій Ticker, якщо всі швидкості тіл менші за певний поріг. Інакше прорахунок і перемальовка відбувається постійно навіть коли нічого не рухається, що призводить до зайвих витрат батареї і нагрівання пристрою.

Я спеціально не описую тут малювання CustomPainter — це звичайні лінії, кола та звичайна шкільна геометрія. Цього багато, але зовсім не так страшно, як здається 😉

Додатково

Не згадував про це, але звʼязки в датасеті мають напрямки, і їх можна змінювати:

Також я додав трохи «викривлення простору», щоб запобігти пустому простору всередині при віддаленні і накладанню при віддаленні:

Підсумок

У результаті вийшов свій Graph View, який:

• працює на чистому флаттері;
• має фізику з пружинами, інерцію і плавні анімації;
• підтримує drag/zoom/rotate і виділення нод.

Сподіваюсь, цей досвід буде комусь корисний.