Version 0.17.49

[FactorioBot]

Bugfixes

• Fixed sprite batching issue when drawing many inserters with circuit connectors. (61861)
• Fixed construction robot working shadow. (71909)
• Fixed using repeat_count in RotatedAnimation definition would cause crash. (71939)
• Fixed rail signal consistency in case of reserved signal being invalidated by building a rail that puts both sides into same block.
• Fixed rail crash related to marking reserved signal for deconstruction.
• Fixed that programmatically set locale for autoplace controls didn't work. (71933)
• Fixed that scrollpane consumed the mouse wheel events even when not activated, which blocked the other (parent) scrollpane. (69766)
• Fixed that re-pathing in chain signal sequence didn't respect the need for green exit when the re-pathing was based on manual change of target station. (71371)
• Fixed that changing state of rail signal by circuit network didn't properly update state of parent circuit signals. (71731)
• Fixed that rail signal disabled by circuit network didn't prevent train passing by it if it guards a block that is already reserved/occupied by the same train. (71839)
• Limited of usage of tab/shift-tab to move between textboxes as other objects didn't support it and it seems like it isn't worth to try to support it for everything. (69656) (71556)
• Reduced the UPS impact of a large number of biters trying to pathfind. (71865)
• Fixed that tabbing could move to invisible or disabled widgets.

Use the automatic updater if you can (check experimental updates in other settings) or download full installation at http://www.factorio.com/download/experimental.

[BattleFluffy]

Reduced the UPS impact of a large number of bitters trying to pathfind.

Awesome, thanks for looking at this Oxyd ! :D
Pathfinder was using 1ms in my game in 0.17.48, I'm waiting for the patch to appear on Steam so I can see what my new times are. :>

I did a little bit of reading back in old FFF's about the last time pathfinding was looked at. One suggestion that came up then was to use Jump Point Search instead of A*.

I had a look at some videos of this method online and it seems like it would be a great match for Factorio bitters. Sounds like a really sneaky algorithm :> According to one video I watched about it, on short paths it's not that different from A*, but for longer paths, especially with obstacles, it can be 20x or even 200x faster.

Anyway, I was wondering if you ever gave some thought to JPS ? :>

[th0]

Thanks.
I don't see it on Steam. Is it my problem or general?

[SchniSchnaSchnuck]

Thanks.
I don't see it on Steam. Is it my problem or general?

I have the same problem

[Loewchen]

It's on steam now.

[jamezhall]

Limited of usage of tab/shift-tab to move between textboxes as other objects didn't support it and it seems like it isn't worth to try to support it for everything.

The one thing I can't stand is not being able to TAB when changing train colors. Most of the time i'm typing in an rgb code and I have to type in a number -> move the mouse -> click in the next feild, repeat, repeat. Is this part of that?

[programaths]

[...]
Anyway, I was wondering if you ever gave some thought to JPS ? :>

This looks indeed a nice thing! It's also nicely explained here : https://zerowidth.com/2013/05/05/jump-p ... ained.html

But as I understood, it requires a jump table too. There is some time to pour to analyse the feasibility in Factorio.

Now, when you build a structure, Factorio probably mark the cell as busy. With JPS, there would be extra work to update the jumping table.

This extra work may be to costly! So, they would need to get metrics on how much structures people build over time and experiment.
Some people have auto expanding factories, which looks like one of the worse case scenario for JPS.

But it is still an option they could consider. Also, they can probably have an hybrid approach. But that would mean to have some heuristic and being able to correct it online :-\

It's though material here!

[Dominik]

Anyway, I was wondering if you ever gave some thought to JPS ? :>

That looks good! I am surprised that nobody thought of that earlier.

[mrvn]

[...]
Anyway, I was wondering if you ever gave some thought to JPS ? :>

This looks indeed a nice thing! It's also nicely explained here : https://zerowidth.com/2013/05/05/jump-p ... ained.html

But as I understood, it requires a jump table too. There is some time to pour to analyse the feasibility in Factorio.

Now, when you build a structure, Factorio probably mark the cell as busy. With JPS, there would be extra work to update the jumping table.

This extra work may be to costly! So, they would need to get metrics on how much structures people build over time and experiment.
Some people have auto expanding factories, which looks like one of the worse case scenario for JPS.

But it is still an option they could consider. Also, they can probably have an hybrid approach. But that would mean to have some heuristic and being able to correct it online :-\

It's though material here!

JPS seems to only work around inefficiencies in the priority queue. Specifically adding a tile to the queue multiple times because it can be reached over multiple paths. JPS makes some paths preferred and only that path adds the tile saving the cost to check the priority queue for the tile for all alternate paths. But why not simply add a flag to each tile marking it when the tile was added to the priority queue? Then A* can check in O(1) if the tile is already present in the priority queue. You get the same saving without needing to build any jump tables or complex tests for obstacles in adjacent tiles.

But lets consider the special case of aliens in factorio. They do live far outside the base. In the wilderness. There won't be any user placed entities near the aliens usually for several chunks. It looks to me like the game could pre-process chunks to see if there are paths from one chunk to the other. Or is there a lake or a wall that splits the chunk in 2? Then aliens could first search for a path on the chunk level and then refine it on the tile level as needed. Paths around lakes would then be just a few chunks long instead of hundreds of tiles.

Obviously the chunk-chunk paths change when the user builds stuff. The simplest solution would be to mark chunk-chunk paths as obsolete in every chunk that changes (only significant changes like landfill or entities placed / removed). Then recalculate the chunk-chunk paths as needed. Most of the interior chunks of the players domain won't be interesting to aliens and don't need the chunk-chunk paths recalculated.

[programaths]

[...]Then recalculate the chunk-chunk paths as needed. Most of the interior chunks of the players domain won't be interesting to aliens and don't need the chunk-chunk paths recalculated.

So, basically, "layered A*" if I understood properly.

[slippycheeze]

[...]
Anyway, I was wondering if you ever gave some thought to JPS ? :>

This looks indeed a nice thing! It's also nicely explained here : https://zerowidth.com/2013/05/05/jump-p ... ained.html
But as I understood, it requires a jump table too. There is some time to pour to analyse the feasibility in Factorio.

JPS seems to only work around inefficiencies in the priority queue. Specifically adding a tile to the queue multiple times because it can be reached over multiple paths. JPS makes some paths preferred and only that path adds the tile saving the cost to check the priority queue for the tile for all alternate paths. But why not simply add a flag to each tile marking it when the tile was added to the priority queue? Then A* can check in O(1) if the tile is already present in the priority queue. You get the same saving without needing to build any jump tables or complex tests for obstacles in adjacent tiles.

Executive summary: JPS is far better than you think, Factorio would benefit from it, or perhaps works built on it (if any) that I'm not familiar with yet.

If you really want to get into it, this has been my go-to for A* optimization for a while now. In short, though, no: JPS isn't just addressing "inefficiencies in the priority queue" as you describe. The optimization properties are significantly greater than your proposal, unsurprisingly.

At the time of discussion in my linked note (and, I think, the referenced blog posts) it had some properties that made JPS hard to apply in all sorts of contexts ... unless you had a game with uniform path-cost on the grid. Always a nice property in context. Anyway, it and successors have definitely moved since but I haven't bothered to review it. I assume by now they can apply something similar in variable weight grids, non-rectangular grids, and almost certainly without assumptions like "zero width agent"

But lets consider the special case of aliens in factorio. They do live far outside the base. In the wilderness. There won't be any user placed entities near the aliens usually for several chunks. It looks to me like the game could pre-process chunks to see if there are paths from one chunk to the other. Or is there a lake or a wall that splits the chunk in 2? Then aliens could first search for a path on the chunk level and then refine it on the tile level as needed. Paths around lakes would then be just a few chunks long instead of hundreds of tiles.

Obviously the chunk-chunk paths change when the user builds stuff. The simplest solution would be to mark chunk-chunk paths as obsolete in every chunk that changes (only significant changes like landfill or entities placed / removed). Then recalculate the chunk-chunk paths as needed. Most of the interior chunks of the players domain won't be interesting to aliens and don't need the chunk-chunk paths recalculated.

A* is a simple (ha!) dynamic programming problem. Like any dynamic programming problem you make it faster one of four ways:

1. You trade time for space through some form of precomputation.
2. You do less work by restructuring your problem to make it smaller.
3. You do less work by making better guesses about what to try first.
4. Micro-optimizations.

We can dismiss micro-optimizations because they (like your proposal for a priority queue with O(1) membership testing) are fundamentally uninteresting in general; I don't have the Factorio source or enough info on target hardware and data size to make smart comments here on if, eg, an O(1) membership test demanding random memory access has a higher constant than a more computationally expensive queue that doesn't require access outside L2 cache.)

Your second proposal is either 1 or 2: precompute pathing data and cache it by chunk, using more space but less time since you can reuse it, or restructuring your problem to make it smaller. As in, if you only A* on chunks for some part of the problem you get to deal with 32^2 less candidate chunks to test, as long as you have an efficient way to determine if the entire chunk is passable or not, and assume you don't care *how* you get through it.

JFS is a much, much smarter version of 3 - the heuristics turn out to give theoretically optimal results with vastly lower time investment. That is absolutely not what you get from either a faster priority queue, or by routing on the chunk level. It is, theoretically at least, far far better, because it does an order of magnitude less work most of the time. (Again, if and only if the heuristics work in your problem space.)

PS: whoever asked why nobody thought of this before, answer is simple: dynamic programming problems have the fun property that almost any innovation looks so completely obvious in hindsight you are stuck wondering why nobody thought of it before. Clearly, the answer is "don't know why, but nobody *did* think of it, so hey, welcome to the new and better future..."

PPS: I dabble, and that only because the game related stuff is usually more fun to read than the other graph problem applications (which I do care about) of this stuff. Don't read me as saying JFS is the best solution, or even the best JFS-like algorithm today, just that it is definitely not "only" a better priority queue.

[mrvn]

[...]
Anyway, I was wondering if you ever gave some thought to JPS ? :>

This looks indeed a nice thing! It's also nicely explained here : https://zerowidth.com/2013/05/05/jump-p ... ained.html
But as I understood, it requires a jump table too. There is some time to pour to analyse the feasibility in Factorio.

JPS seems to only work around inefficiencies in the priority queue. Specifically adding a tile to the queue multiple times because it can be reached over multiple paths. JPS makes some paths preferred and only that path adds the tile saving the cost to check the priority queue for the tile for all alternate paths. But why not simply add a flag to each tile marking it when the tile was added to the priority queue? Then A* can check in O(1) if the tile is already present in the priority queue. You get the same saving without needing to build any jump tables or complex tests for obstacles in adjacent tiles.

Executive summary: JPS is far better than you think, Factorio would benefit from it, or perhaps works built on it (if any) that I'm not familiar with yet.

If you really want to get into it, this has been my go-to for A* optimization for a while now. In short, though, no: JPS isn't just addressing "inefficiencies in the priority queue" as you describe. The optimization properties are significantly greater than your proposal, unsurprisingly.

At the time of discussion in my linked note (and, I think, the referenced blog posts) it had some properties that made JPS hard to apply in all sorts of contexts ... unless you had a game with uniform path-cost on the grid. Always a nice property in context. Anyway, it and successors have definitely moved since but I haven't bothered to review it. I assume by now they can apply something similar in variable weight grids, non-rectangular grids, and almost certainly without assumptions like "zero width agent"

One thing I don't see as useful in JPS for factorio. JPS looks ahead in one direction until it hits an obstacle or the end of the map. I assume it also stops when the next step no longer brings it closer to the goal. It does this horizontal and vertical and only then goes diagonal. Right? So in factorio in the desert with with no rocks or trees for miles wouldn't JPS search horizontal and vertical for miles and miles? Doesn't that give a huge search area making each step in the JPS take forever? Sure there are far fewer steps but in the end what really costs time is fetching all the tiles from memory to check them.

The other thing is the path it finds. For example in an open desert doesn't JPS go horizontal or vertical at the start and finish with a diagonal. Right? Counting tiles that is a shortest path. But going in a straight line (alternative horizontal/vertical and diagonal moves) would be much more natural and expected. So even if JPS is faster would the result even look right?

[slippycheeze]

[...]
Anyway, I was wondering if you ever gave some thought to JPS ? :>

This looks indeed a nice thing! It's also nicely explained here : https://zerowidth.com/2013/05/05/jump-p ... ained.html
But as I understood, it requires a jump table too. There is some time to pour to analyse the feasibility in Factorio.

JPS seems to only work around inefficiencies in the priority queue. Specifically adding a tile to the queue multiple times because it can be reached over multiple paths. JPS makes some paths preferred and only that path adds the tile saving the cost to check the priority queue for the tile for all alternate paths. But why not simply add a flag to each tile marking it when the tile was added to the priority queue? Then A* can check in O(1) if the tile is already present in the priority queue. You get the same saving without needing to build any jump tables or complex tests for obstacles in adjacent tiles.

Executive summary: JPS is far better than you think, Factorio would benefit from it, or perhaps works built on it (if any) that I'm not familiar with yet.

If you really want to get into it, this has been my go-to for A* optimization for a while now. In short, though, no: JPS isn't just addressing "inefficiencies in the priority queue" as you describe. The optimization properties are significantly greater than your proposal, unsurprisingly.

At the time of discussion in my linked note (and, I think, the referenced blog posts) it had some properties that made JPS hard to apply in all sorts of contexts ... unless you had a game with uniform path-cost on the grid. Always a nice property in context. Anyway, it and successors have definitely moved since but I haven't bothered to review it. I assume by now they can apply something similar in variable weight grids, non-rectangular grids, and almost certainly without assumptions like "zero width agent"

One thing I don't see as useful in JPS for factorio. JPS looks ahead in one direction until it hits an obstacle or the end of the map. I assume it also stops when the next step no longer brings it closer to the goal. It does this horizontal and vertical and only then goes diagonal. Right? So in factorio in the desert with with no rocks or trees for miles wouldn't JPS search horizontal and vertical for miles and miles? Doesn't that give a huge search area making each step in the JPS take forever? Sure there are far fewer steps but in the end what really costs time is fetching all the tiles from memory to check them.

The other thing is the path it finds. For example in an open desert doesn't JPS go horizontal or vertical at the start and finish with a diagonal. Right? Counting tiles that is a shortest path. But going in a straight line (alternative horizontal/vertical and diagonal moves) would be much more natural and expected. So even if JPS is faster would the result even look right?

I checked - it is much easier if you adjust the per-step delay waaay up to like a second or two in the JS code of that demo, because JPS is so fast, but no: it proceeds in the optimal direction for the target initially. So, a diagonal is chosen if that is the "cone approximating the target vector best", both initially, and after an obstacle, even when you have to reverse direction before resuming pathing. (Which, of course, is the definition of optimal, which is a property of the final result of JPS.)

So ... as long as your idea is "some approximation of the shortest path" for natural movement, it'll do OK. I'd personally guess that you do best with a shortest path for guiding the things, and then introduce random perturbations using strictly local information (as in, within a 10 tile radius or whatever) to vary from it a little, and/or other environmental reactions.

Ultimately, though, they pay Wube the big bux to figure that bit out, and not me. Which is probably a very, very good choice, because I'm not actually good at the bits like "natural feeling movement", compared to things like JFS is a strictly superior pathfinding method to A* if you meet the requirements, and as far as I can tell from the outside, Factorio does meet them.

I assume that vanilla A* must be OK enough for this because, well, unless this thread misleads, that is what is used today. JFS should give literally identical path output, given the same input, just faster. Certainly, I was unable to find a counterexample of that in the toy.

[mrvn]

This looks indeed a nice thing! It's also nicely explained here : https://zerowidth.com/2013/05/05/jump-p ... ained.html
But as I understood, it requires a jump table too. There is some time to pour to analyse the feasibility in Factorio.

JPS seems to only work around inefficiencies in the priority queue. Specifically adding a tile to the queue multiple times because it can be reached over multiple paths. JPS makes some paths preferred and only that path adds the tile saving the cost to check the priority queue for the tile for all alternate paths. But why not simply add a flag to each tile marking it when the tile was added to the priority queue? Then A* can check in O(1) if the tile is already present in the priority queue. You get the same saving without needing to build any jump tables or complex tests for obstacles in adjacent tiles.

Executive summary: JPS is far better than you think, Factorio would benefit from it, or perhaps works built on it (if any) that I'm not familiar with yet.

If you really want to get into it, this has been my go-to for A* optimization for a while now. In short, though, no: JPS isn't just addressing "inefficiencies in the priority queue" as you describe. The optimization properties are significantly greater than your proposal, unsurprisingly.

At the time of discussion in my linked note (and, I think, the referenced blog posts) it had some properties that made JPS hard to apply in all sorts of contexts ... unless you had a game with uniform path-cost on the grid. Always a nice property in context. Anyway, it and successors have definitely moved since but I haven't bothered to review it. I assume by now they can apply something similar in variable weight grids, non-rectangular grids, and almost certainly without assumptions like "zero width agent"

One thing I don't see as useful in JPS for factorio. JPS looks ahead in one direction until it hits an obstacle or the end of the map. I assume it also stops when the next step no longer brings it closer to the goal. It does this horizontal and vertical and only then goes diagonal. Right? So in factorio in the desert with with no rocks or trees for miles wouldn't JPS search horizontal and vertical for miles and miles? Doesn't that give a huge search area making each step in the JPS take forever? Sure there are far fewer steps but in the end what really costs time is fetching all the tiles from memory to check them.

The other thing is the path it finds. For example in an open desert doesn't JPS go horizontal or vertical at the start and finish with a diagonal. Right? Counting tiles that is a shortest path. But going in a straight line (alternative horizontal/vertical and diagonal moves) would be much more natural and expected. So even if JPS is faster would the result even look right?

I checked - it is much easier if you adjust the per-step delay waaay up to like a second or two in the JS code of that demo, because JPS is so fast, but no: it proceeds in the optimal direction for the target initially. So, a diagonal is chosen if that is the "cone approximating the target vector best", both initially, and after an obstacle, even when you have to reverse direction before resuming pathing. (Which, of course, is the definition of optimal, which is a property of the final result of JPS.)

So ... as long as your idea is "some approximation of the shortest path" for natural movement, it'll do OK. I'd personally guess that you do best with a shortest path for guiding the things, and then introduce random perturbations using strictly local information (as in, within a 10 tile radius or whatever) to vary from it a little, and/or other environmental reactions.

Ultimately, though, they pay Wube the big bux to figure that bit out, and not me. Which is probably a very, very good choice, because I'm not actually good at the bits like "natural feeling movement", compared to things like JFS is a strictly superior pathfinding method to A* if you meet the requirements, and as far as I can tell from the outside, Factorio does meet them.

I assume that vanilla A* must be OK enough for this because, well, unless this thread misleads, that is what is used today. JFS should give literally identical path output, given the same input, just faster. Certainly, I was unable to find a counterexample of that in the toy.

Even if you go diagonal first if that is the better start as far as I understood the explanation you would still go diagonal as long as possible. So baring obstacles you get one diagonal and one straight section. On the other hand with A* every tile along the way is added to the priority queue. And I think the distance to the goal is taken "as the crow flies". So as you drift away from the "as the crow flies" path the distance estimation doesn't go down 1 tile as you advance a tile. The combined cost goes up and the more natural path becomes cheaper. This causes A* to approximate the "as the crow flies" path.

As for the final movement: If you take the path and follow it tile to tile (center to center) the units would make a sharp turn in the center of each tile whenever it changed from straight to diagonal. Doesn't look good. A simple way to smooth that out is to not go to the center of the next tile but head towards the center of the tile 1 (2, 3, 4, ..) steps ahead. The more you look ahead the more you clip corners though and might hit obstacles. But even 1 tile look ahead makes a huge difference how the movement looks. For more lookahead it makes sense to only do it when not rounding an obstacle.

PS: going diagonal costs sqrt(2) in factorio. I'm not sure how that affects JPS.

[slippycheeze]

Even if you go diagonal first if that is the better start as far as I understood the explanation you would still go diagonal as long as possible.

Look, JPS is an optimization for A* on an equal weight grid map. It produces the same - optimal - output. It is literally just a performance improvement that doesn't change the outcome. At this point I don't know how else to explain that, so I'm just gonna step away.

[mrvn]

Even if you go diagonal first if that is the better start as far as I understood the explanation you would still go diagonal as long as possible.

Look, JPS is an optimization for A* on an equal weight grid map. It produces the same - optimal - output. It is literally just a performance improvement that doesn't change the outcome. At this point I don't know how else to explain that, so I'm just gonna step away.

The problem is defining "optimal". For the algorithm moving one tile straight has cost 1. Moving diagonal has cost sqrt(2). Moving across an equal weight grid has many many paths of equal costs. So any one of them would be optimal for both A* and JPS. People have other ideas.

So are you saying on an empty grid JPS won't result in a path that has at most one direction change?

[slippycheeze]

Even if you go diagonal first if that is the better start as far as I understood the explanation you would still go diagonal as long as possible.

Look, JPS is an optimization for A* on an equal weight grid map. It produces the same - optimal - output. It is literally just a performance improvement that doesn't change the outcome. At this point I don't know how else to explain that, so I'm just gonna step away.

The problem is defining "optimal". For the algorithm moving one tile straight has cost 1. Moving diagonal has cost sqrt(2). Moving across an equal weight grid has many many paths of equal costs. So any one of them would be optimal for both A* and JPS. People have other ideas.

So are you saying on an empty grid JPS won't result in a path that has at most one direction change?

No. On an equal weight grid there are one-or-more possible "optimal" paths, where optimal is defined in A* as "lowest cost possible."

A* gives an "optimal" result, which is to say that it will always return one of the set of paths that have equal cost, and where that is the lowest possible cost to navigate from the start to the finish on the current map.

Nothing in A* defines how to pick from a set of equal weight paths. The JS demo A* implementation earlier tends to favor the left , which is an implementation detail: if the data structure for holding the candidates was more efficient when it returned "right first" nodes as the next one to check, it'd favor that.

Path selection among equal weight candidates is an implementation detail, and that in turn is usually an artifact of the data structure used to hold the candidates, and the person writing the code. It probably has some correlation to which country they live in, I'd wager, since there is a tendency to start left or right based on what side the road you drive, haha.



Anyway, to A*-with-JPS: it'll tend to pick candidates that have long lines, yes, if there are multiple equal weight paths. So will vanilla A*, depending on the implementation. A* definitely does not deliberately avoid that pathing. In fact, since it is more obviously "correct", people being human, implementations probably tend to favor that.


So, in summary, point is: JPS is no better, and no worse, than any A* implementation for picking "unnaturally direct" paths. The JS example is one choice of A* implementation. As far as I can tell, in-game A* tends toward the direct paths with minimal turns. AAI Programmable Vehicles, which visualize the route for AI-driven vehicle, clearly show that. (Which uses the in-game pathing that is associated with "character" actions.)

Factorio A* seems to handle an obstacle at the end of the path really unnaturally, BTW: it makes a really strange set of turns favoring top-left when the obvious-to-people path would be right. It isn't wrong, though: the path is optimal, just strange when you can see the whole thing, and have a big heuristic pathfinding system between your ears working on it.


The final question is: does A* with, or without, JPS produce a "natural" path that is good for gameplay?

Meh. Question is unanswerable, because it depends on humans too much. I'm pretty sure people would be mad that their "send a tank here" didn't go in a direct line, turning many times, but that "send a bug here" went too directly, despite both being the same entity-action, "go to this place" with something in the same general context of "...and kill what is there".

I think it benefits significantly from "fixing it in post" though: once you have the optimal path you can use local (and this, cheap) randomness to add more natural movement to things. Extra, unnecessary, turns and diversions a small way off the optimal path, and fixing them with a very limited A* or whatever to navigate around obstacles your diversion added.

Unless they are robots. Robots should just go in a very direct line, because everyone "knows" robots do that. Because people be like that.

[mrvn]

Even if you go diagonal first if that is the better start as far as I understood the explanation you would still go diagonal as long as possible.

Look, JPS is an optimization for A* on an equal weight grid map. It produces the same - optimal - output. It is literally just a performance improvement that doesn't change the outcome. At this point I don't know how else to explain that, so I'm just gonna step away.

The problem is defining "optimal". For the algorithm moving one tile straight has cost 1. Moving diagonal has cost sqrt(2). Moving across an equal weight grid has many many paths of equal costs. So any one of them would be optimal for both A* and JPS. People have other ideas.

So are you saying on an empty grid JPS won't result in a path that has at most one direction change?

No. On an equal weight grid there are one-or-more possible "optimal" paths, where optimal is defined in A* as "lowest cost possible."

A* gives an "optimal" result, which is to say that it will always return one of the set of paths that have equal cost, and where that is the lowest possible cost to navigate from the start to the finish on the current map.

Nothing in A* defines how to pick from a set of equal weight paths. The JS demo A* implementation earlier tends to favor the left , which is an implementation detail: if the data structure for holding the candidates was more efficient when it returned "right first" nodes as the next one to check, it'd favor that.

Path selection among equal weight candidates is an implementation detail, and that in turn is usually an artifact of the data structure used to hold the candidates, and the person writing the code. It probably has some correlation to which country they live in, I'd wager, since there is a tendency to start left or right based on what side the road you drive, haha.



Anyway, to A*-with-JPS: it'll tend to pick candidates that have long lines, yes, if there are multiple equal weight paths. So will vanilla A*, depending on the implementation. A* definitely does not deliberately avoid that pathing. In fact, since it is more obviously "correct", people being human, implementations probably tend to favor that.


So, in summary, point is: JPS is no better, and no worse, than any A* implementation for picking "unnaturally direct" paths. The JS example is one choice of A* implementation. As far as I can tell, in-game A* tends toward the direct paths with minimal turns. AAI Programmable Vehicles, which visualize the route for AI-driven vehicle, clearly show that. (Which uses the in-game pathing that is associated with "character" actions.)

Factorio A* seems to handle an obstacle at the end of the path really unnaturally, BTW: it makes a really strange set of turns favoring top-left when the obvious-to-people path would be right. It isn't wrong, though: the path is optimal, just strange when you can see the whole thing, and have a big heuristic pathfinding system between your ears working on it.


The final question is: does A* with, or without, JPS produce a "natural" path that is good for gameplay?

Meh. Question is unanswerable, because it depends on humans too much. I'm pretty sure people would be mad that their "send a tank here" didn't go in a direct line, turning many times, but that "send a bug here" went too directly, despite both being the same entity-action, "go to this place" with something in the same general context of "...and kill what is there".

I think it benefits significantly from "fixing it in post" though: once you have the optimal path you can use local (and this, cheap) randomness to add more natural movement to things. Extra, unnecessary, turns and diversions a small way off the optimal path, and fixing them with a very limited A* or whatever to navigate around obstacles your diversion added.

Unless they are robots. Robots should just go in a very direct line, because everyone "knows" robots do that. Because people be like that.

The natural path would be units going any direction and not just 90° or 45° steps. The game has a grid and path finding will work along the grid which tends to produce unnatural paths. One way to compensate that is to have A* prefer the natural direction. It's not always clear or doesn't always work but you want a path that stays near a direct line from obstacle to obstacle. What I have seen of JPS does the opposite. That's why I think it's a really bad choice.

But I had another look at JPS again. If you look at it another way what it does is identify obstacles, right? Only the tile needed to get past the obstacle is added to the search queue because it knows (if this path turns out to be the right way) the many equally optimal paths must pass through this tile. So it might be possible to actually define the resulting path just in terms of those obstacle tiles and move the unit in straight lines from each obstacle to the next. I don't see any reason why JPS must favour the path with long lines or return a path with tile-by-tile instructions.

So it might be that actually a modified JPS would be a great choice. Not because of any speed improvement (although that would be nice) but because it would allow finding natural paths. Paths that are optimal without a grid.

[slippycheeze]

The natural path would be units going any direction and not just 90° or 45° steps.

[...]

So it might be that actually a modified JPS would be a great choice. Not because of any speed improvement (although that would be nice) but because it would allow finding natural paths. Paths that are optimal without a grid.

I can't quite tell what is going wrong with our communication, but Imma take a stab at another possibility:

I think you have zoomed in on the image so far that all you see are the giant pixels. If you zoom out you will realise that you can't possibly draw an actual circle on a regular grid, but you can approximate one. If your pixels are small enough, people can't tell the difference. This is how your monitor can draw "circles" and other curves, despite being a physical grid. [1]

Analogously, pathfinding on a grid has one inescapable constraint: every square has 8, identically positioned, neighbours. Four of them are at 90 degrees, and four of them are at 45 degrees, center-to-center by the shortest possible line.

So no pathfinding algorithm on a grid can ever, ever move to anything but a new square that is horizontal, vertical, or diagonal, from the current square. You cannot possibly change that no matter what algorithm you use.

Thought exercise: draw this out on graph paper, and draw a line at 13 degrees. Which square did you end up in?


Instead, what you do is approximate the "natural" system that allows arbitrary directions of movement by ... keeping the pixels, or grid squares, small enough that it "looks" close enough to the human. Want to travel at 37 degrees? Do that by moving the combination of 90 degree or 45 degree movements that minimize error from 37 degrees. Again, the finer the grid the less you can see the deviations.


No algorithm in the universe can permit arbitrary directions of movement when you define the "place that movement happens" as a regular grid. You have to change how the data (ie: not a grid) or you have to approximate it.


So, a "JPS variant" won't help you out here, because JPS-as-is (and vanilla A*, which gives identical results) will already approximate the path at whatever arbitrary angle is required. The shortest path is, by definition, not constructed of 45 and 90 degree lines at the highest level. At the lowest level, it will approximate that, minimizing error compared to the perfect angle because error, in this case, is also the amount that the path costs compared to moving at the unconstrained angle.



[1] for the purposes of analogy this is close enough to true. I know that some displays do vary.

[mrvn]

The natural path would be units going any direction and not just 90° or 45° steps.

[...]

So it might be that actually a modified JPS would be a great choice. Not because of any speed improvement (although that would be nice) but because it would allow finding natural paths. Paths that are optimal without a grid.

I can't quite tell what is going wrong with our communication, but Imma take a stab at another possibility:

I think you have zoomed in on the image so far that all you see are the giant pixels. If you zoom out you will realise that you can't possibly draw an actual circle on a regular grid, but you can approximate one. If your pixels are small enough, people can't tell the difference. This is how your monitor can draw "circles" and other curves, despite being a physical grid. [1]

Analogously, pathfinding on a grid has one inescapable constraint: every square has 8, identically positioned, neighbours. Four of them are at 90 degrees, and four of them are at 45 degrees, center-to-center by the shortest possible line.

So no pathfinding algorithm on a grid can ever, ever move to anything but a new square that is horizontal, vertical, or diagonal, from the current square. You cannot possibly change that no matter what algorithm you use.

Thought exercise: draw this out on graph paper, and draw a line at 13 degrees. Which square did you end up in?


Instead, what you do is approximate the "natural" system that allows arbitrary directions of movement by ... keeping the pixels, or grid squares, small enough that it "looks" close enough to the human. Want to travel at 37 degrees? Do that by moving the combination of 90 degree or 45 degree movements that minimize error from 37 degrees. Again, the finer the grid the less you can see the deviations.


No algorithm in the universe can permit arbitrary directions of movement when you define the "place that movement happens" as a regular grid. You have to change how the data (ie: not a grid) or you have to approximate it.


So, a "JPS variant" won't help you out here, because JPS-as-is (and vanilla A*, which gives identical results) will already approximate the path at whatever arbitrary angle is required. The shortest path is, by definition, not constructed of 45 and 90 degree lines at the highest level. At the lowest level, it will approximate that, minimizing error compared to the perfect angle because error, in this case, is also the amount that the path costs compared to moving at the unconstrained angle.



[1] for the purposes of analogy this is close enough to true. I know that some displays do vary.

I know that you have to approximate the perfect line by pixels. But don't forget that a tile is 32x32 pixels. And the GPU can even draw entities at e.g. 1/4 pixel offset. So entities don't have to move from tile center to tile center. They can move pixel by pixel (or even finer). So if a bitter has to move to a tile 10 tiles to the east and 5 tiles to the south with no obstacles it can move at a 30° angle cutting across tiles. Close enough to a straight line not to matter. If it moves from tile to tile though then you would see a series of east and south-east moves which look unnatural.

That's what I'm talking about. If the path finding returns a path "e se e e se e e se e e se e e se e" that would be the closest approximation of a line through tiles. The best A* can return. But if you can detect that there are no obstacles along that line the path finding can return "go 10e+5s" leading to that 30° movement. Much nicer.