Support to select different heuristics

[peterchenadded]

Thinking to use this implementation to draw lines between connectors, which means we favour nice looking lines.

At the moment I can see it is hard coded to use Manhattan distance when diagonal support is disabled.

Is it possible to also add below heuristics and update to allow selecting the heuristic from python?

1. only y diff

abs(current.y - goal.y)

2. only x diff

abs(current.x - goal.x)

3. Breaking ties

dx1 = current.x - goal.x
dy1 = current.y - goal.y
dx2 = start.x - goal.x
dy2 = start.y - goal.y
cross = abs(dx1dy2 - dx2dy1)
heuristic += cross*0.001

See http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

Not sure if possible to even allow defining the heuristic in python without affecting performance.

The code change is minimal as you would know.

[hjweide]

Thanks for taking the time to think about this. I see two different considerations regarding performance:

1. Asking the Python interpreter to evaluate every call to the heuristic function would clearly be too expensive. Thus, the heuristic passed from Python would have to be evaluated in C++, but I don't know how to marshall an arbitrary Python function object to C++ or if this is even possible. (A Python function object is much more complex than the simple array I marshall in the current implementation.) Let me know if you know of any way to do this.
2. Changing the heuristic may introduce a performance penalty if, for example, the new heuristic underestimates the cost and becomes less effective at eliminating expensive paths. I see the motivation for breaking ties above (I guess you have a uniform costs and prefer straight paths?), but what is the motivation for considering only the distance in x or y?

[peterchenadded]

Thanks @hjweide

Will check further on 1, I doubt it is possible.

Regarding 2.

Yes, we prefer straight lines. We need to trade some performance for what looks nice in drawings.

You can't get anymore straight then just x or y. It's really just about giving options for users to pick. I don't think we can ever have a single heuristic that looks nice to everyone. Beauty is in the eye of the beholder...

Just x or y is easy to reason about. For the drawings we have, it's not just about connecting a single source and destination, there will be lots of sources, destinations and obstables, and we also want to avoid crosses.

[hjweide]

Yes, we prefer straight lines. We need to trade some performance for what looks nice in drawings.

This makes sense. I suppose we could have a few heuristic functions implemented in C++ and let the user select one from Python by passing an argument. This wouldn't allow arbitrary heuristics, but would allow the user some flexibility without a performance penalty.

I don't expect that I'll have much time to work on this soon, would you be interested in submitting a PR? I'd be happy to provide guidance if needed.

[peterchenadded]

Thanks @hjweide

Yes, that was the exact approach I was thinking.

Will send through a PR when ready. I wonder if also there penalty to passing more arguments to the Heuristic, the breaking ties one in particular needs to know alot more properties.

Cheers

[hjweide]

I wonder if also there penalty to passing more arguments to the Heuristic, the breaking ties one in particular needs to know alot more properties.

In terms of computational overhead I think any arguments you might add are negligible compared to the np.ndarray, but of course we should (a) keep the interface backwards-compatible and (b) try not to add unnecessary arguments.

I haven't thought about this in detail, but I was thinking something like:

1. new argument indicating which heuristic to use (defaults to existing choices of heuristic based on allow_diagonal)
2. new argument indicating tiebreak strategy (default to nothing)
3. new argument indicating tiebreak penalty coefficient (defaults to 0.)

[peterchenadded]

@hjweide, sorry for the delay didn't get much time

Can you check below PR

#35

and let me know if you want to make some other changes?

I will probably need to add one more heuristic, that prefers going outward first and then making turns rather than making turns straight away i.e. not optimal path.

[blackdimund]

I made a program to get through obstacles, and this project already brought down the python method I was using from 5 seconds to 0.05 seconds and without having to resize the original to 1/10th. If you added a heuristic that preferred going outwards for a bit first, that would make it even better because it takes a few seconds for me to turn. I appreciate your guys work.

[peterchenadded]

Not sure if outward is actually needed, you can always create some obstacles in the weights to make sure it goes outward.

[blackdimund]

what about distance consequences for being N pixels close to borders, to encourage staying away from black pixels?

[peterchenadded]

what about distance consequences for being N pixels close to borders, to encourage staying away from black pixels?

That would be expensive to calculate inside a heuristic function, best to just add that as obstacles in the grid.

If you added a heuristic that preferred going outwards for a bit first, that would make it even better because it takes a few seconds for me to turn. I appreciate your guys work.

Updated, orthogonal x and y, so that it changes direction in the middle rather than at the end. For drawing good outward lines from one node to another node, check what side is the starting point:

• If left or right side, select orthogonal x
• if top or bottom side, select orthogonal y

This should give good outward lines and work well with lines coming back as well.

[hjweide]

what about distance consequences for being N pixels close to borders, to encourage staying away from black pixels?

best to just add that as obstacles in the grid.

Right. The heuristic is meant to eliminate bad solutions quickly to find the optimal solution faster. It is not meant to define what the optimal solution looks like. If you don't want to go near walls, raise the cost of those areas.

[peterchenadded]

Closing this as it is supported now