Thiago P.

Mind Map Obeservations

Posted in Programming

← back to the blog



I've recently just finished a quick freelance project for a client and I'm jotting down some notes and observations here.

The project involved creating a browser prototype mind map application allowing the user to

  1. Create text nodes by clicking
  2. Drag the nodes around
  3. Make connections between the nodes

It was to be made using the HTML canvas and EaselJs library.

Seems simple enough right. The catch is that the nodes in the map must not intersect/overlap each other, meaning they must collide with each other and move out of the way. Also, the connections/lines connecting nodes must also not intersect other nodes (though they can intersect other lines).

The canvas rendering aspect of the project was already determined by the client, it was to be done with the EaselJs library, so how about the node collisions and line avoidance of nodes.




Collisions = physics = physics library

While I would have loved to write my own physics library, however simple it may have been, I don't think the client would have appreciated me wasting their time and money exploring the ins and outs of how to create a physics library, so off I was to choose an already existing physics library.

There quite a few physics libraries out there but in the end I chose Matter.js. At the time it appeared to have the most active community, best documentation, and be the most mature out of all the others.

Some other libraries had active communities and decent documentation but they were either too large for a project of this scope, had too many restrictions, or had poor documentation.



How to get lines to avoid nodes? Why pathfinding of course.

I chose to keep it simple and just use A* pathfinding for the time being.

The process went something like this

  1. Create a grid from the canvas, including the boundaries of the all the nodes.
  2. Feed the grid into the pathfinding algorithm have the algorithm plot a path of points from nodeA to nodeB.
  3. Then have a connection create a line following those points.

It worked just fine, except for the fact that the browser came to a screeching halt anytime a node moved or a connection was made.



The Problem

A node being dragged around must have its connections fallow it around. Because node movement - and pretty much all other physics and rendering - is processed many times a second, the pathfinding process gets called many times a second, for each connection, on a grid that is usually 800x600 in size. The result is the browser coming to a complete halt. It gets even worse when a node being dragged collides with other nodes, and now every connection of every colliding node must be updated.

The Solution

Grid Caching

The first and obvious solution was to cache the grid. No need to recalculate the grid if nothing moved.

Grid Resolution

The second solution, and probably the most significant boost to performance, was to decrease the resolution of the grid.

All the points on the grid (the canvas) would be scaled down to fit into a smaller grid. All calculations would be performed on that smaller grid, and then the results would be scaled back up to be used by the connections to plot a path.

This significantly reduces the processing time and garbage collection costs of recreating the grid in exchange for an almost unnoticeable drop in pathfinding accuracy. Even at 10% of the original resolution, the accuracy drop was. almost completely unnoticeable.

That means turning 800x600 sized grid into an 80x60 sized grid, using the 80x60 grid for pathfinding, then scaling the results back up and having results that almost appear as if they were calculated on an 800x600 grid.

Straight Lines

Even with grid caching and a reduced grid resolution, recalculating connection paths every physics tick while dragging around a node still had performance dips that were intolerable.

So to further boost performance, all a nodes' connections would turn into straight lines (no pathfinding) while the node was being dragged, and then calculate and use an appropriate path when the node was dropped.