So yeah, what's the deal with pathing? Why do people rarely take a straight path? I notice frequently people will travel in an arc to get to a destination rather than going straight to it. I hope other people know what I mean. Not necessarily a perfect arc but I mean they will rarely just go in a straight line from point A to point B.
I didn't think much of it but it recently caused me some major issues when I was attempting to send some guys around a group of mechanoids and had they traveled in a straight line they'd not have been noticed, but for some reason the pathing drew a path that arced towards the mechanoids even though it was not the most efficient travel route.
I'm mostly just curious what controls pathing and why colonists don't necessarily always travel in a straight line even if that would be the shortest distance?
Not sure any game logic checks it for their decision-making, but did you look at the walk speeds of the surfaces in question? Perhaps that was the fastest route?
You know what, I didn't even think about that. You may be correct and it's probably just that simple.
It's hard to explain the details of it if you aren't familiar with pathfinding algorithms, but the short version is that it intentionally doesn't try very hard to find the shortest path and strongly favors moving towards the destination, even when there are things in the way.
And to answer the question you didn't ask, try my Better Pathfinding mod here: https://ludeon.com/forums/index.php?topic=26563.0
Quote from: AnActualDuck on November 01, 2016, 11:55:19 PM
So yeah, what's the deal with pathing? Why do people rarely take a straight path? I notice frequently people will travel in an arc to get to a destination rather than going straight to it. I hope other people know what I mean. Not necessarily a perfect arc but I mean they will rarely just go in a straight line from point A to point B.
I didn't think much of it but it recently caused me some major issues when I was attempting to send some guys around a group of mechanoids and had they traveled in a straight line they'd not have been noticed, but for some reason the pathing drew a path that arced towards the mechanoids even though it was not the most efficient travel route.
I'm mostly just curious what controls pathing and why colonists don't necessarily always travel in a straight line even if that would be the shortest distance?
colonists use best terrain to travel. so if there is gravel at a mountain foot, they will go close to mountain instead through the middle of a swamp
I don't believe this is a matter of terrain type. I've been aware of this behaviour for as long as I've been playing and it drives me mildly crazy.
It's especially annoying when you go through the trouble of constructing tile roads or paths between buildings, for example, but your colonists refuse to use them, instead opting for slower diagonal scenic routes through your cornfields.
Quote from: Zhentar on November 02, 2016, 12:57:57 AM
It's hard to explain the details of it if you aren't familiar with pathfinding algorithms, but the short version is that it intentionally doesn't try very hard to find the shortest path and strongly favors moving towards the destination, even when there are things in the way.
And to answer the question you didn't ask, try my Better Pathfinding mod here: https://ludeon.com/forums/index.php?topic=26563.0
I'll definitely check your mod out, thanks!
Quote from: ChimpX on November 02, 2016, 05:10:18 AM
It's especially annoying when you go through the trouble of constructing tile roads or paths between buildings, for example, but your colonists refuse to use them, instead opting for slower diagonal scenic routes through your cornfields.
(https://image-store.slidesharecdn.com/969b5c48-a694-4f79-a3ff-33de71306cd0-large.jpeg)
Thats actually called desire path and the best way of designing a park or something like that is taking the shortests ways in account, instead of the "nice looking" things.
https://en.wikipedia.org/wiki/Desire_path
Cool, that was an interesting read.
Actually my point is that the tiled path I'm referring to *is* the shortest, direct, straight-line route between points A and B, but I see my colomists regularly wander off it, through unpaved (slower movement rate) terrain, then back onto it, meandering their way from A to B.
I've been seeing them do this even before beer and drugs were in the game, so it can't be that.
Maybe it's by design to have a certain randomness in the pathing. Still, it doesn't seem right.
Quote from: ChimpX on November 02, 2016, 10:06:22 AM
Actually my point is that the tiled path I'm referring to *is* the shortest, direct, straight-line route between points A and B, but I see my colomists regularly wander off it, through unpaved (slower movement rate) terrain, then back onto it, meandering their way from A to B.
I've been seeing them do this even before beer and drugs were in the game, so it can't be that.
Maybe it's by design to have a certain randomness in the pathing. Still, it doesn't seem right.
I caught what you meant. Definitely check out that mod that was linked, it seems to address the issue. I haven't gotten to mess with it yet but if it works as described it should help.
Quote from: ChimpX on November 02, 2016, 10:06:22 AM
Actually my point is that the tiled path I'm referring to *is* the shortest, direct, straight-line route between points A and B, but I see my colomists regularly wander off it, through unpaved (slower movement rate) terrain, then back onto it, meandering their way from A to B.
I've been seeing them do this even before beer and drugs were in the game, so it can't be that.
Maybe it's by design to have a certain randomness in the pathing. Still, it doesn't seem right.
Could you provide some examples of your paths? Are colonists just going for a walk, or doing work tasks?
Quote from: ZestyLemons on November 03, 2016, 12:50:27 AM
Quote from: ChimpX on November 02, 2016, 10:06:22 AM
Actually my point is that the tiled path I'm referring to *is* the shortest, direct, straight-line route between points A and B, but I see my colomists regularly wander off it, through unpaved (slower movement rate) terrain, then back onto it, meandering their way from A to B.
I've been seeing them do this even before beer and drugs were in the game, so it can't be that.
Maybe it's by design to have a certain randomness in the pathing. Still, it doesn't seem right.
Could you provide some examples of your paths? Are colonists just going for a walk, or doing work tasks?
There is little point to make a screenshot, as it's really simple to see this "problem".
Tynan is also perfectly aware of this. Pawn always go for the "straight" path, and on anything but short path choice, they won't use the path you could expect.
For instance,
If you have a (B)ase, an (E)ntrance, a mountain in front of it (at some distance, say 100 tiles) and only one quick way to go trough it with a straight line from your base to this way.
BBBBB E BBBBBB
------------------
------------------
------------------
------------------
MMMM W MMMMM
-1----------------
(1) if the thing they want isn't aligned, they ignore the straight line and go in diagonal to be the CLOSER possible quickly to (2). Then the path system find they can't just keep in diagonal to reach it because of the (M)ountain, check around, find the (W)ay and go to it (in diagonal, again). In the end, they avoid using a straight line, regardless of the speed.
On a very short range, they do try to avoid being slow, but on long range as they don't "see" really far.
The mod help a lot for this, but also impact the performance. Obviously it impact a lot during raid, but as you are likely stuck with the normal speed, it's not THAT much a big deal.
Quote from: Zhentar on November 02, 2016, 12:57:57 AM
It's hard to explain the details of it if you aren't familiar with pathfinding algorithms, but the short version is that it intentionally doesn't try very hard to find the shortest path and strongly favors moving towards the destination, even when there are things in the way.
And to answer the question you didn't ask, try my Better Pathfinding mod here: https://ludeon.com/forums/index.php?topic=26563.0
Does your mod use standard Dijkstra algorithm? If so I'll definitely consider checking it out although I resist modding. The default pathfinding in this game is one of the few things that seriously bugs me.
Quote from: bclewis on November 04, 2016, 11:58:36 AM
Quote from: Zhentar on November 02, 2016, 12:57:57 AM
It's hard to explain the details of it if you aren't familiar with pathfinding algorithms, but the short version is that it intentionally doesn't try very hard to find the shortest path and strongly favors moving towards the destination, even when there are things in the way.
And to answer the question you didn't ask, try my Better Pathfinding mod here: https://ludeon.com/forums/index.php?topic=26563.0
Does your mod use standard Dijkstra algorithm? If so I'll definitely consider checking it out although I resist modding. The default pathfinding in this game is one of the few things that seriously bugs me.
Dijkstra is fkin slow. He uses A* (basically Dijkstra but with a heuristic - as such not searching the obviously bad paths).
Cool, even better, thanks, though I take some issue with your characterization of the slowness of Dijkstra :)
Quote from: bclewis on November 04, 2016, 12:35:28 PM
Cool, even better, thanks, though I take some issue with your characterization of the slowness of Dijkstra :)
Hm, what? You dont think Dijkstra is slow? https://www.youtube.com/watch?v=cSxnOm5aceA#t=42s for the first, very simple example... you can see that dijkstra takes more than 30 times as many steps as A*. If that isnt slow then I dont know what is.
Sure, every modern computer can still do that in a very short time, given a small grid and just one path to calculate. However in rimworld the grid is huge and there are potentially hundreds of paths to be calculated each second, so if you'd use Dijkstra the game would probably run with little more than 1 FPS even on good CPUs.
Also note that the "concurrent dijkstra" that is also shown there is not really a thing, if you allow dijkstra to check multiple cells per step then you can just do the same with A* - checking multiple cells is pretty much the same as doing another step so there is no real gain in terms of actual speed.
Quote from: Lys on November 04, 2016, 01:28:42 PM
Hm, what? You dont think Dijkstra is slow?
I think it's slower than A* and variants for a lot of real-world practical cases, but no, I don't think it's fair to blanket call it "slow", and I'm surprised it would make a significant user-noticeable time difference in practice for graphs as small as Rimworld maps (I deal with pathfinding in much larger road networks).
Also note that saying "30 times as many steps" is not really meaningful when talking about algorithmic time complexity (Big-O).
In more abstract cases, A* won't necessarily give better results than Dijkstra (e.g. imagine if teleportation squares were introduced in Rimworld that allowed a colonist to jump from a teleport booth in one square to another; in that case the currently used A* heuristics would break down).
(I do agree that as it stands, A* is a great choice for Rimworld pathfinding, though if I were doing the implementation I'd probably start with plain old Dijkstra and see if it was "good enough" in practice, though A* heuristics are not that much more complicated to add. Without actually trying it, I'd expect either method would take on the order of milliseconds to compute all-pairs shortest paths).
Quote from: bclewis on November 04, 2016, 02:13:47 PM
(I do agree that as it stands, A* is a great choice for Rimworld pathfinding, though if I were doing the implementation I'd probably start with plain old Dijkstra and see if it was "good enough" in practice, though A* heuristics are not that much more complicated to add. Without actually trying it, I'd expect either method would take on the order of milliseconds to compute all-pairs shortest paths).
Not only is plain old Dijkstra too slow, plain old A* is too slow. That's why Vanilla chooses such poor paths - it uses an inadmissable heuristic, causing it to behave as a greedy best-first search in most cases, but also expanding very few nodes as a result.
Quote from: bclewis on November 04, 2016, 02:13:47 PM
In more abstract cases, A* won't necessarily give better results than Dijkstra (e.g. imagine if teleportation squares were introduced in Rimworld that allowed a colonist to jump from a teleport booth in one square to another; in that case the currently used A* heuristics would break down).
Mine wouldn't ;D
The difference between Vanilla pathfinding and my pathfinding mod is the heuristic. Rather than use a simple admissable distance heuristic (which is enormously expensive on long paths), it uses the region system (which forms a graph several orders of magnitude smaller, and each node usually has significantly fewer edges) to calculate fairly high accuracy heuristic which in addition to accounting for obstructions, can weigh in factors like terrain costs and door opening speeds.
The outcome is that A* with an admissable octile distance heuristic searches high and low (http://imgur.com/MNe4oZv.jpg) looking for the faster path the heuristic claims is there, while my heuristic heads straight towards the goal (http://imgur.com/4yBw0jh.jpg), ignoring dead ends and rough terrain (and on top of that, the new version which I should be releasing this weekend expands less than half as many nodes as the one that screenshot is from).
Sounds cool, I'll definitely check it out. (Drives me crazy when colonists take paths that are both longer in distance AND cover higher-cost terrain)
Out of curiousity, do you have some real approximate numbers for:
- how many point-to-point path queries are made per second in RimWorld?
- how fast did attempted implementations of A*/Dijkstra perform?
I'm interested to know if numbers match my experience (I've implemented both A* and Dijkstra in Java and C#, although that was more than 10 years ago).
The rate of pathfinding requests is variable; often there are none or only one or two. But there can be clusters of hard queries, for example when raiders attack from a map edge.
I just commented out the heuristic (so pretty much turning it into dijkstra's), and then pathed all the way across a 400x400 map. 151,840 cells were popped from the priority queue, so pretty much the entire map, and it took 147ms with my i5-6600.
Quote from: Zhentar on November 04, 2016, 08:20:26 PM151,840 cells were popped from the priority queue, so pretty much the entire map, and it took 147ms with my i5-6600.
Yep, that actually meshes with my experience pretty well!
On further reflection I also realize (this probably should have been obvious) that finding optimal-cost paths should NOT be the ideal goal in Rimworld, where we really want to model imperfect human behaviour. Colonists really should use heuristics, not compute Dijkstra in their heads!
The trick is to find heuristics that are likely to make the same sort of errors that real people do (unlike the Vanilla pathfinding!). Mechanoids may be an exception to this :)
Edit: Another thought: for raiding parties you might be able to optimize by the computing path for one raider, and then incorporating that raider's path into the A* heuristic for other raiders (i.e. prefer tiles that are close to that path). For "unusually clever groups" you could split the raiding party into several subgroups and do the same for each subgroup.
I have no idea what that heuristic would look like, unfortunately. When mine overestimates path costs, the first degradation to appear is zig zags at region boundaries.
Raiding parties actually already do something along that line, at least in some cases, where some "leaders" will path somewhere and others will just follow them.
I've been using your mod for a week or so now, and I no longer notice any obviously-bad pathing or obvious slow-downs. Nicely done!
Here's an example path using the mod, illustrated in blood ;)
http://steamcommunity.com/sharedfiles/filedetails/?id=810813559