Potential optimization for `collides_with_wall()`

[MavethGH]

https://github.com/manuelVo/foundryvtt-routinglib/blob/f580b97bace2d28f8684272a29a44f53579d7bbe/rust/src/pathfinder.rs#L163-L168

There is a faster way to do this, since we don't care about the actual location of the intersection. Here is an implementation of it:

/// Checks if the line segments AB and CD intersect
fn intersects(a: Point, b: Point, c: Point, d: Point) -> bool {
    ccw(a, c, d) != ccw(b, c, d) && ccw(a, b, c) != ccw(a, b, d)
}

/// Checks if the points ABC are in a counterclockwise order
fn ccw(a: Point, b: Point, c: Point) -> bool {
    (c.y - a.y) * (b.x - a.x) > (b.y - a.y) * (c.x - a.x)
}

The algorithm used is from here: https://bryceboe.com/2006/10/23/line-segment-intersection-algorithm/

This is also relevant to implementing walls that can be passed through if going one direction, but not the other. As illustrated in this diagram, for a line segment CD going from left to right, if AB is intersecting it from below, ACD will be clockwise, and if it's intersecting from above, ACD will be counterclockwise.

In code, that would look like this:

fn intersects_from_above(a: Point, b: Point, c: Point, d: Point) -> bool {
    ccw(a, c, d) && !ccw(b, c, d) && ccw(a, b, c) != ccw(a, b, d)
}

fn intersects_from_below(a: Point, b: Point, c: Point, d: Point) -> bool {
    !ccw(a, c, d) && ccw(b, c, d) && ccw(a, b, c) != ccw(a, b, d)
}

[MavethGH]

This was basically me procrastinating doing my actual job by messing around with math. Perhaps at some point I'll make a PR for this as well.

[manuelVo]

That's actually a pretty neat idea for an algorithm and improving the hot loop of the gridless pathfinder is always worthwhile. However I'm not quite sure if the ccw-Algorithm is actually faster than the current algoirthm. I guess it comes down to the question whether eight multiplications are faster than one division plus one multiplication; I'm not quite sure about this. Do you have any insights on that?

[MavethGH]

Well, the main advantage is that this one should be branchless, but I'm not how well the compiler can optimize the current code, so that might not be as big of a deal as it seems.

[manuelVo]

I guess being branchless could indeed be beneficial to performance. In addition to that I did some reading and apparently a multiplication can be done in 1-2 clock cycles while a division can require anywhere from 20 to 40 clock cycles, so even just getting rid of the division could prove beneficial.

I'll do some benchmarking of your suggestion and let you know how it turns out.

[manuelVo]

I've done some benchmark testing and your suggestion improves the pathfinding speed quite a bit. With the current code, my test path takes roughly 4.4 seconds to compute when the caches are empty. Replacing the intersection algorithm with the one you proposed reduces that time to 3.7 seconds, and removing the bounding rectangle check further decreases the route calculation to 3.0 seconds. Nice!

I'll definitely include this change in the next version of routinglib (most of the code is already written for benchmarking, but there's still some cleaning up to do before I publish that).