The shortest distance between two points is straight line (Pathing question)

[Lys]

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).

[bclewis]

Cool, even better, thanks, though I take some issue with your characterization of the slowness of Dijkstra

[Lys]

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.

[bclewis]

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).

[Zhentar]

(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.

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 

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 looking for the faster path the heuristic claims is there, while my heuristic heads straight towards the goal, 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).

[bclewis]

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).

[Zhentar]

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.

[bclewis]

151,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.

[Zhentar]

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.

[bclewis]

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!

[bclewis]

Here's an example path using the mod, illustrated in blood

http://steamcommunity.com/sharedfiles/filedetails/?id=810813559