Version 0.17.49

[peternlewis]

On the page linked, the A* and JPS do not produce equal results, and neither produces the “natural result” for the simple case of no obstacles. Here are the results:



As far as I can see, the A* algorithm is only guaranteed to produce any of the equally weighted paths (the grey area in the left image). The JPS will always choose a path on one edge of the equally weighted path area. A natural path will go down the middle of the equally weighted area. I believe the A* algorithm can very easily be weighted slightly to always produce the natural path (by including a very small weight component relative to the crow flies distance from the target), at least in the zero obstruction case.

It would be likely that the JPS algorithm, which produces long path segments, could probably be used and then have the actual path taken be either: The path suggested by the next path segment; or cut the corner by taking the direct path from the current point to the next next segment end, if there are no obstacles along that route. This latter test is relatively trivial. Since the JPS algorithm would never generate a case where the route turns one way and then turns back except in the presences of an obstacle, this should result it a good approximation of natural path.

But I haven't played Factorio in a while, and mostly ignore the bugs, so I don't know how much of an issue it is with the current path finding for bugs taking unnatural paths.

[mrvn]

On the page linked, the A* and JPS do not produce equal results, and neither produces the “natural result” for the simple case of no obstacles. Here are the results:



As far as I can see, the A* algorithm is only guaranteed to produce any of the equally weighted paths (the grey area in the left image). The JPS will always choose a path on one edge of the equally weighted path area. A natural path will go down the middle of the equally weighted area. I believe the A* algorithm can very easily be weighted slightly to always produce the natural path (by including a very small weight component relative to the crow flies distance from the target), at least in the zero obstruction case.

It would be likely that the JPS algorithm, which produces long path segments, could probably be used and then have the actual path taken be either: The path suggested by the next path segment; or cut the corner by taking the direct path from the current point to the next next segment end, if there are no obstacles along that route. This latter test is relatively trivial. Since the JPS algorithm would never generate a case where the route turns one way and then turns back except in the presences of an obstacle, this should result it a good approximation of natural path.

But I haven't played Factorio in a while, and mostly ignore the bugs, so I don't know how much of an issue it is with the current path finding for bugs taking unnatural paths.

Nice picture. In the JPS case all the grey arrows mean the JPS knows there is no obstacle. So I now think that the "if there are no obstacles along that route" would fall naturally out of the JPS algorithm. Any obstacle would mean the grey box would appear earlier, at the height of the obstacle.

Proof me wrong but can there ever be an obstacle on the straight line for 2 segments in the JPS result that isn't next to the start or end tile?

[peternlewis]

I think you are correct. However, distant obstacles far off the path affect the path segmenting, which will affect the utility or the complexity of implementing it.

[slippycheeze]

I think you are correct. However, distant obstacles far off the path affect the path segmenting, which will affect the utility or the complexity of implementing it.

You do know, like, that the properties of these algorithms are well documented. Including on the page that JS simulation runs on. You don't have to "think" anything. You can literally read how it works in simple terms on that page, and then know what the behaviour is.

If you intend to discuss this anywhere else, I would strongly advise that, to avoid accidentally promoting wildly incorrect speculations about the behaviour of the algorithms.

[mrvn]

I think you are correct. However, distant obstacles far off the path affect the path segmenting, which will affect the utility or the complexity of implementing it.

Yeah. That's the part I still don't get about JPS, or if that is special to factorio. Because in factorio if you go far enough you will hit a tree (or other 1 tile obstacke). So assuming there are no lakes or cliffs near then JPS would not skip any tiles. Because there being a tree in each row and column (eventually) it might be necessary to make a turn in every row or column to get around a tree optimally.

If you hit an alien nest you can skip a few tile or a lake even more so. But forests seem to be the worst for JPS.