Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Draco18s]

But even with the a* algorithm, you could have a node in every second square instead of every single square. That would be faster whatever algorithm you use.

Please....please....please actually read the arguments as to why that is a bad idea.

[sockless]

Well you would still be able to move orthogonally, but it will be able to assume that there's a walkable space between 2 connected nodes.
The point about the sword is an interesting one, but right now the dwarf would just look at the nearest as-the-ghost-flies distance and decide to pick up that sword, so with sparser nodes, that wouldn't be affected, it would be the same as if you were pathing to a lever. It would just grab the swords co-ords, then randomly choose a pathable space next to it. Then the dwarf would path to that square, then walk the one square different.

[Draco18s]

Well you would still be able to move orthogonally, but it will be able to assume that there's a walkable space between 2 connected nodes.

So now not are you storing nodes, your storing node connections, rather than being able to infer connections because the two nodes are neighboring.

[Max White]

Dosn't the great Toady one himself have degrees in mathamatics, or softwere or something of that nature? I mean I'm sure he has given this plenty of thought.

[sockless]

Yes that is what I'm doing, so you build a graph at the start of the game, then as you mine stuff, it adds it to the graph.

[thijser]

Of course a third methode for pathing past obstacles is that whenever the computer finds a obstacle it will start to try path next to it. That way it won't have to store as much data.

[Silverionmox]

Currently the pathfinding is like an amnesiac autist: do everything step by step, include every little detail, and repeat it every time you have to go somewhere.

- Dwarves could pathfind within burrows first, as that is the most likely place to find stuff. Animals could do something similar, at least the territorial ones. Cows/sheep should path to the leading bull/ram of the herd, but don't need much else.
- Dwarves could store frequently used paths, such as from their bedroom to the first high traffic zone (probably a staircase or important connecting corridor). It would be great if the computer could detect central staircases and prefer them for pathfinding.
- Dwarves performing routine tasks should use the above. If something pulls them out of their routine, they could revert to the ordinary, more flexible pathfinding. Adventurer mode will have townsfolk perform routine tasks anyway, so the same code can be reused.

[NW_Kohaku]

Wouldn't storing pathfinding results for "most common paths" lead to a massive consumption of memory, though?  Not that having an ability to trade processor time for memory space is a bad thing, but it can potentially exchange one problem for another if you have enough creatures walking around the map.

I'd expect it would really help with workshops, though, if you have a "prefer items from this stockpile" command that would tell workers to only search for the materials in one particular stockpile before they do a general map search of every single item of that type in the entire fortress, and compare how to path to each one.  You could even store the pathfinding from workshop to stockpile and back, which I'm sure is THE most frequent pathfinding function you perform.

[tps12]

I'd expect it would really help with workshops, though, if you have a "prefer items from this stockpile" command that would tell workers to only search for the materials in one particular stockpile before they do a general map search of every single item of that type in the entire fortress, and compare how to path to each one.

I don't think the game paths to each item in that case. It finds the closest item by Cartesian distance and then paths to that one only.

[Draco18s]

Currently the pathfinding is like an amnesiac autist: do everything step by step, include every little detail, and repeat it every time you have to go somewhere.

It's a computer program.  Computers can't generalize, at all, ever.  They must perform the repetitive, excessive detail, tasks every time because that's how computers work.  The only way to skip code is to be less accurate or find some way to infer the data without looking at it (i.e. a process that takes less cycles but comes to the same result, such as "that tile is a food stockpile tile" skipping the check that asks if each item in that tile is a stone or not*).

*There could be a stone in that tile, but odds are there isn't.

[NW_Kohaku]

I'd expect it would really help with workshops, though, if you have a "prefer items from this stockpile" command that would tell workers to only search for the materials in one particular stockpile before they do a general map search of every single item of that type in the entire fortress, and compare how to path to each one.

I don't think the game paths to each item in that case. It finds the closest item by Cartesian distance and then paths to that one only.

I know, but that's not the main reason why the game lags, the game lags because every time a stonecrafter at a workshop wants to find something, he has to access a list of every single stone in the fort to then test cartesian distance of each one to find the closest, even if there are tens of thousands of stones to choose from.

If you were restricting the dwarf to searching only the contents of a single stockpile first, then only searching the rest of the entire fortress if he couldn't find what he needed in the stockpile, then you could potentially trim that list of search targets down by quite a bit, and improve overall speed.

[Nadaka]

every square is a node, it isn't stored as a graph though. It is stored as an array of node entry costs IIRC. Connectivity between nodes is implicit from adjacency.

Its been a while since I got in on one of these pathfinding discussions.

IIRC the path from unit to goal is recalculated at every step, if each unit stored its current path you would cut path finding costs by a factor approximately equivalent to half the length of the average path divided by the frequency that a path becomes invalid. You could check each step to make sure the path is valid and still get a significant boost, or follow the path until it becomes immediately obstructed and save even more time. This does cost some memory, but isn't likely to be significant.

Cutting the number of nodes by 4 is only a linear speadup, comes with some abstraction issues and won't save on memory. It is the same reason that parallel path processing isn't going to be that useful, the average cpu count right now is close to 2.

[Draco18s]

every square is a node, it isn't stored as a graph though. It is stored as an array of node entry costs IIRC. Connectivity between nodes is implicit from adjacency.

Precisely my earlier point.

[NW_Kohaku]

The path isn't recalculated with every step.  You can test this to a degree by placing obstacles in the way of a dwarf who has already on deciding to go somewhere.  Locking a door in front of a dwarf when he is intent on going somewhere, like, say, to pick up a sock from a dwarf who died in a goblin ambush, will cause him to smack head-first into the door before he realizes it is now locked (or try to walk into deep water before he realizes his path has flooded), and then try to find a way to path around the obstacle the dwarf now suddenly realizes is in the way.

edit: In fact, when they realize a path is blocked, they will stand still for a while and flash a "?" sign to signify they just walked face-first into a locked door.

[Jacob/Lee]

There was a whole topic on the pathfinding algorithm some time ago.