is it possible to jump diagonal?

[Dexus]

Hello @mikolalysenko
is it possible to add a option that the way can also diagonal?

Regards
Dexus

[mikolalysenko]

You can get a diagonal path by shearing. I need to write this up, but haven't had time.

[Dexus]

Have you a example for that? I'm not family with it...

[mikolalysenko]

It is a little tricky conceptually, but straightforward to implement. The idea is to apply a shear using the linear map:

(x, y) ->  ( x + y,  x - y )

Then a diagonal shortest path in the (x,y) domain is an L1 shortest path in the warped domain. So you solve the shortest path there, then invert it to get back to the original domain.

[chinedufn]

Hey @mikolalysenko happen to have any plans here? If not, I'd be happy to work on a PR.

Cheers and thanks!

[w35l3y]

It definitely would be great to see implemented.

[gilbert]

I am also interested in diagonal as a feature. Would shearing happen in user-land or library-land @mikolalysenko ?

[mikolalysenko]

User land

[AbegNext]

It is a little tricky conceptually, but straightforward to implement. The idea is to apply a shear using the linear map:

(x, y) ->  ( x + y,  x - y )

Then a diagonal shortest path in the (x,y) domain is an L1 shortest path in the warped domain. So you solve the shortest path there, then invert it to get back to the original domain.

@mikolalysenko , would this limit the movement to only diagonal then? Is there a way to include all (vertical, horizontal, and diagonal) movements on the same search?

[mikolalysenko]

Vertical and horizontal movements are not optimal if the cost of moving diagonally is the same.

[MrFaul]

Hmmm shouldn't be diagonal movement preferred?
Since it moves two "coordinates" at once?
Technically even if the agent moves in a zigzag pattern horizontal or vertical it still reaches the goal in the same time.

[Retera]

Hey guys, I did not read the literature to understand how this algorithm worked but I tried porting it to another language by doing a 1:1 copy, and after I did the copy I wanted diagonals so I removed the thing where it discerns a path between two points but adds one if they are not equal and I told it instead to just go from the one point to the next point.

It is giving me solutions like the following that look good, and it is like a 2 line change instead of doing some linear transformation thing like described above.

Is this trivial solution that appears to work somehow not as trivial as it would appear? Should I think that I broke something horribly that will fail later in an unexpected way? I mean it was literally about a 2 line change. Where we have this stutter:

l1-path-finder/lib/graph.js

Line 93 in 4aa05fd

out.push(head.x, prevY)

I literally only edited the "stutter" when going from {x1, y1} to {x2, y2} so that it does not add a point at {x1, y2} when decoding the solution back in "getPath()". I don't understand why users wouldn't be recommended to remove this "stutter" instead of doing some crazy linear transform, but I also don't understand the inner workings of how this l1 path finder is functioning yet. I need to do more reading on that.

Edit:

Yea don't do what I described here. You probably need to implement the shear as mentioned above. Creating diagonals like I did in the above example results in the selection of non-shortest paths because it assumes that the cost of a diagonal is as large as the L shape right angle movement in the original version.