Print

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

[sockless]

I'n not sure exactly how pathfinding is done, but I'm going to take a wild guess and say that every single piece of ground you can walk on is a node and that the entire fortress just makes a giant graph. If this is the case, then I'm not surprised that pathfinding is so slow. I potential solution to this slowness would be for every second square to be a node.

OXOXOXO
XOXOXOX
OXOXOXO
XOXOXOX

Like that.

That way, there would be half as many nodes. After figuring the route out this way, it would be rudimentary to figure out how to get from one node to another, as if they are connected in the graph, then there's a way to get from one to the other.

[Max White]

That might make finding a lever a little tricky if it is on an odd node, would it not?

[sockless]

You could just make the dwarf path to a random node 1 square away from the lever, then walk the one extra square to the lever. Perhaps not 100% efficient, as you might have to walk another couple of squares to get to it.

I guess stairs would have to have a node attached to them as well, regardless of whether they would or not usually.

[Max White]

Ok, a level was a bad example, because you can set the location when you give the order.

What if, for example, there was a sword on the ground in an odd node, and the dwarf wanted to find the closest sword so he could arm himself. He can't just path to the closest even node, on the basis that then every even node would have to check if the required object was next to it, and all it all the process would take longer.

[NW_Kohaku]

What if you had to travel through a single-tile-wide hallway to get to where you were going most efficiently?  If you build a pathfinding system where only diagonal moves are allowed, you wouldn't be able to see horizontal hallways, which are the most common types of hallways built in DF.

You know, there have been quite a few threads on trying to find more efficient pathfinding methods, maybe you could search for and read some of them. 

---

I can't remember a good search term for it, but there was one post that I kept seeing links to that explained how the pathfinding currently works, although obviously I didn't take it well enough to heart to remember a good search term.

[thijser]

Perhaps there is a better system using this to fill in areas that are not next to walls and simply making every tile next to a wall a node. That way pathing should always work. a bit like this

OXOXOXOXOX
XOXOXOXOXO
OXOXOXOXOX
XXXXXXXXXX
wwwwwwww
w=wall
X=node
O=open space

[NW_Kohaku]

How do you know where a wall is?  You have to test it to find out, which is just as costly as testing a node.

[thijser]

You could lay out this grid during the game itself as the walls are revealed/build. This would add another map but it could also be combined with the travel pathing cost map (low trafic high trafic ext.).

[sockless]

Another potential way to have less nodes is to cut them down even more, so that you only have a node at every corner/intersection/stair. E.g.

N=node
                +-+
                |N|
                |  |
-----------+ +---------------+
                 N                     N|
-----------+ +------------+  |
                |  |                  |  |

This way you'd have a rather small number of nodes.
Since the nodes are at every point where a dwarf have to make a decision, they don't have to calculate things that would be definite, the problem though, is that it would have difficulty doing large halls, as dorfs would have a tendency to just stick to walls.

[NW_Kohaku]

Don't forget that pathfinding in DF prefers to use diagonals whenever possible, which means that in corners like the one you just illustrated, they actually never step on those node tiles.  Plus, players tend to have plenty of doors along hallways.

Still, that's an improvement, you're still only trying to make a linear growth improvement, but it's moving towards fitting the practical problem.  One could even try to to turn it into a fractal map where you have larger hub nodes that feed smaller capilary pathfinding nodes, which would be better for pathfinding in labyrinthine dwarf tunnels, but poor for pathfinding in open areas. 

Don't forget that we have both open areas and twisting mazes, and we need a system that works well for both.

Look, while it's great that you want to help, if you're going to really improve something, you have to understand the system that DF is using, and try to work out a better core algorithm.  Dwarf Fortress apparently uses a modified A* pathing function with a manhattan distance heuristic function, and saved accessible/inaccessible states for tiles.

You should look at this thread, at the very least:
http://www.bay12forums.com/smf/index.php?topic=43265.0

and look up the A* and manhattan systems to understand their methods.

DF players (and Toady) know their stuff, and pathfinding has been a known problem for years.  If you have some sort of very simple solution to try to solve pathfinding that doesn't require a detailed knowledge of the inner workings of the algorithm, odds are someone else has thought of it already, and it either is already in use, an improved version of it is in use, or it will not work for one reason or another.

[thijser]

Maybe we could split inside and outside pathing? That way we can use an efficent methode for both.

[NW_Kohaku]

You can make large, open environments even "inside", though.  Some people even make large hallways consisting of nothing but up/down stairs so that dwarves can "fly" by moving in every possible direction, since that optimizes pathfinding for A*. 

[Draco18s]

One could even try to to turn it into a fractal map where you have larger hub nodes that feed smaller capilary pathfinding nodes, which would be better for pathfinding in labyrinthine dwarf tunnels, but poor for pathfinding in open areas.

I think we visited this once, where we broke the grid down into chunks of 3x3 grids, and determined all of the possible layouts of 3x3 tiles and their connectivity.
(And the longest path on a 3x3 grid is 5 tiles IIRC)

[thijser]

You can make large, open environments even "inside", though.  Some people even make large hallways consisting of nothing but up/down stairs so that dwarves can "fly" by moving in every possible direction, since that optimizes pathfinding for A*.

But on average outside will be more open then inside. 

Another interesting question is how you are going to do ramps vs stairs.

[sockless]

How is DF meant to use Manhattan Geometry when dwarves can go in diagonals? Isn't very essence of Manhattan distance that you can only move orthogonally?

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.

I guess if you did have a node at every corner, like you said, it would suffer horribly in open spaces, as dwarves would just stick to the side.

Really, the best solution, I've decided, would be to just invest time into making the game multi threaded. That would make the game run a lot faster for most people. It's not a solution, but it fixes the symptoms.

Or you could prove that P=nP

PS. thijser, Vous êtes Français?