Dynamic penalties for Manhattan Router

[coyoteecd]

The manhattan router has a penalties option that returns an options with neighbor penalties for each direction.
This option can be an object or a function, however it's always resolved at the start of the routing, presumably for performance reasons.

I would like to change this config option to a function that accepts arguments, and call it every time so that we can improve the suggested routes. Something like this:

var neighborPenalty;
if (typeof opt.penalties === 'function') {
  var penalties = opt.penalties(isStart, currentPoint, neighborPoint);
  neighborPenalty = penalties[directionChange];
} else {
  // default behavior (for backwards compatibility)
  neighborPenalty = isStart ? 0 : opt.penalties[directionChange]; // no penalties for start point
}

What's the benefit:

• I can use currentPoint + isStart to determine which of the startDirections we're processing (of course, ideally the arguments would be one of dia.OrthogonalDirection, but that's a much bigger change) and to add a small penalty when starting from points that should not be "preferred". For example, all else being equal, I prefer that a link starts at the bottom of the rectangle shape, even though startDirections can be left/right/bottom. However I do not want to force it, since there are some corner cases where the route from the bottom ends up uglier than a route on the left direction. When penalties is dynamic, I can add an extra penalty for all start points except bottom.
• Combined with isPointAccessible and a custom obstacle map (available from Manhattan router should exclude invisible(collapsed) elements #1412), I could try tweaking the routes to "avoid" crossing existing routes. I do not want this to be a yes/no question (i.e. completely forbid crossing other routes) because it's unlikely to work in practice. But I'm thinking that adding a penalty when the path from current to neighbor crosses an already-routed link path would guide the pathfinding to choosing routes that are longer but contain less crossings, while still accept routes with crossings when there are no other possibilities. Right now I am using a larger penalty for a 90deg direction change to basically force straighter and longer routes.

@kumilingus, thoughts?

[kumilingus]

Sounds good 👍

The penalties option can stay as is. But if defined as a function it could return a function (a function returning function).

Since I'm not sure where else it might be useful, I'd suggest merging the parameters into a single entry (to make it easier to provide more data).

var neighborPenalty;
if (typeof opt.penalties === 'function') {
  var penalties = opt.penalties({ isStart, currentPoint, neighborPoint, direction /* possible more */ });
  neighborPenalty = penalties[directionChange];
} else {
  // default behavior (for backwards compatibility)
  neighborPenalty = isStart ? 0 : opt.penalties[directionChange]; // no penalties for start point
}

[coyoteecd]

Unfortunately it turned out my idea did not help improve our routing much and had to fall back to dynamically enforcing different startDirections in the router options. I don't think it's a good idea to push this option in the joint library without at least one consumer actually using it, so I'm abandoning it.

Leaving the discussion open for other people that may consider it for tweaking the manhattan router paths.