Print

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

[FearfulJesuit]

Why shouldn't it be possible to have the computer calculate some lines that follow the best path fairly closely, and then the dwarf just goes along those lines and doesn't have to recalculate until it reaches the end of the line? Then the dwarf doesn't have to figure out where it's going again every time it takes a step. It'd make a 200-dwarf fort a snap.

[Mohican]

Why shouldn't it be possible to have the computer calculate some lines that follow the best path fairly closely, and then the dwarf just goes along those lines and doesn't have to recalculate until it reaches the end of the line? Then the dwarf doesn't have to figure out where it's going again every time it takes a step. It'd make a 200-dwarf fort a snap.

how do you know if a line follow a path if you don't know the path?

[Niseg]

Why shouldn't it be possible to have the computer calculate some lines that follow the best path fairly closely, and then the dwarf just goes along those lines and doesn't have to recalculate until it reaches the end of the line? Then the dwarf doesn't have to figure out where it's going again every time it takes a step. It'd make a 200-dwarf fort a snap.

My Path caching scheme does exactly that!

 check this example . If you click "find path using waypoints" you'll notice it visits the waypoint. If you  clicked "smoothed path using waypoints" you'll see it doesn't use the waypoint anymore(same path finding with smoothing algorithms ran twice ). You can play with source and destination waypoints and shape . Take note that you'll have to update path cache after removing waypoints (a bug I didn't fix yet) and after changing the structure of the maze ( I don't validate cached paths yet before using them).

The waypoint save full cache to every other waypoint and try to go S->w1->w2->D unless w1==w2 and then it does A*. It's currently pretty dumb and I don't validate much, the smoothing scheme is also getting some improvements.

There are still problem with waypoint selection but it's intended for a system where the user selects the waypoint and he/she can pick optimal ones himself. Other waypoints can be used for invaders who enter at a fixed point

If you got a band of  "goblins" for example that waits for an open entry into the fort you can put 2 waypoints like this

########
+w#W++X#
########

the "goblins" can wait until there is a valid path between w and W which won't get updated too often (A* worst case where there is no path) and they only start moving when that's true.

how do you know if a line follow a path if you don't know the path?

With path smoothing that doesn't really matter. if you keep paths between certain key points it can be adjusted to lead to other points. close to them.

[tps12]

Why shouldn't it be possible to have the computer calculate some lines that follow the best path fairly closely, and then the dwarf just goes along those lines and doesn't have to recalculate until it reaches the end of the line? Then the dwarf doesn't have to figure out where it's going again every time it takes a step. It'd make a 200-dwarf fort a snap.

That's already how it works, it's just that figuring out the path that one time for each journey is relatively expensive.

[ji11]

Apart from improving the algorithm, shouldn't pathfinding be highly parallelizable? Could it be split between several of the computer's cores and run at the same time?

Right now it seems like only one (of 3) of the DF processes is active taking only one of my cores at a time

Sorry if this has been discussed before...

[Sunken]

This would mean that, you would find a route that goes through St. Louis, and then you search for more direct paths by cutting out whatever "middlemen" you can, resulting in a much more direct route.

Well, whether it's much shorter or merely cuts the very tip of the wedge next to St. Louis depends wholly on the coarseness of the map, doesn't it? If there are always at least two cities between the first and second "leg" of the trip, this modification won't make any difference.

Except it doesn't just trim off the very tip.  It compares every step of the journey for a shorter route between every point along the line.  This means that it will only path up to St. Louis if it has to go that far to find the correct relative distances in the tree for comparison, and then it could theoretically lop off that pathfinding all the way down to a simple path directly from one city to the other.

Let's take an example of two cities on opposite sides of a state boarder.  When you want to go across that state border into the next town, you would be transitioning not just cities, but also states.  This means you hop up from a street level to a city level to a state level to a national level of travel, then zoom back down to the city and street level.  But you don't need to travel back to state capitals to get there, you just need to check for the best lateral connection on the tree, which would involve simply driving down the nearest road across the border.

I was talking about only the tree-based pathfinding here, without also imposing the hierarchical scheme you suggested subsequently. If all you have are cities, not states or any larger groups, you'll still have the problem I describe. Just clarifying.

This works well if there are only a few entry points into a sub-map. There are only so many ways to enter St. Louis (on a major highway at least). But it will be worthless if there are loads and loads of entry points, such as will be the case for a general quadtree square over a DF map. And for anything larger-scale than individual rooms, which *may* have only a few doors out of it, it will be a monumental task coming up with an algorithm to decide the right way to subdivide the map into a large-scale clustering which minimizes the number of entry points.

This goes back to that hierarchical pathfinding thing I was talking about about ten pages earlier in the thread.

You can draw up all the pathways in and out of a node, but you really don't need all of them.  As long as you are pathing "through" St. Louis, and not actually going to some point inside of it, it doesn't matter that there are routes through St. Louis that aren't the Interstate, as long as the Interstate is the BEST path, that's all you need to remember.

You can check for plenty of routes from one point to another, but you only need to store the best route from one exit to another exit.  You can keep storing the different entry points, but these would only matter if you were looking for a specific point inside of St. Louis you wanted to reach where it might make a difference.

No, you misunderstand. I really meant passing-through. If St. Louis has only, say, 10 major entry points you need to store 45 costs. All well and good. But what about the state of Missouri? It will likely have hundreds of entry points, meaning thousands of costs to pre-compute and store.

I'll reiterate my main point: Hierarchical representations only help you if the world conforms to that hierarchy. Cities are natural clusters as far as pathfinding is concerned -states are not. Nor, as I said, are any Dwarf Fortress subdivisions except for "room" that I've heard proposed.
Star shaped topologies help you only if the world is star-shaped.
Quad trees help you only if the world has large square chunks of free space/occupied space. And if you impose a quad tree over a DF map, you're going to have an entry point count that is proportional to the length of the sides, meaning O(L^2) costs to be precomputed.

Basically: No free lunch. The only way to beat unbiased tile-by-tile BFS is to bias the search. A* biases in favor of worlds with straight-ish paths. Room-based nodes bias in favor of worlds which actually have rooms. Your tree search approach biases (heavily) in favor of worlds with a star-shaped topology. Your hierarchical search biases in favor of worlds with scale invariance.
Nothing wrong with any of this - one just have to go into it with open eyes. It happens to be my belief that both the star-shaped world assumption and the scale invariance assumption will be quite off in many, if not most Dwarf Fortress maps.

[Sunken]

Just a minor clarification: The no free lunch theorem mostly talks about time complexity. When you exclude a subspace of solutions as with your tree pathfinding you get around this and can be faster, but you still pay - in the quality of solutions. There's always a tradeoff somewhere.

[Sunken]

I pressed A* and got a slightly "off" path though, so I'm wondering: what is the actual cost function you're using? one step costs 1? That would explain the path I saw but that makes several of the heuristics inadmissible.

there is currently no weights or adjustment to A* to fit DF exactly it's not really the point but I can add it along with traffic zones if I put my mind to it

The current default heuristic function is a vector magnitude sqrt(dx² +dy² ) it should be admissible i might want to Math.floor it to avoid floating point .

That's not admissible if the step cost is 1. 4 steps diagonally would cost 4 in reality, but that heuristic is higher (4*sqrt(2)). The heuristic must be equal or lower. Same goes for some of the others.

Also, there's another heuristic that might be relevant:
sqrt(2)*max(abs(dx),abs(dy)) + (1-sqrt(2))min(abs(dx),abs(dy))
that is, the smallest distance possible if you may only walk at 45 degree increments (which is true for dwarfs in DF, though not for projectiles).

I can easily add that one it's pretty simple to add heuristic functions to my program.

You can do a path smoothing after A* should give you a better result . I also improved path smoothing by drawing reverse lines - helps me avoid hitting walls but it's generally a work-around that seem to work .[/quote]
Thinking more about performance than aesthetics, smoothing afterwards is too late - an inaccurate heuristic means the A* itself will take longer than necessary.
That said, certainly when A* yields a suboptimal path smoothing may give you something less suboptimal.

[Sunken]

The first option is that you can start from geometric isolation:
This means starting with splitting the map into cubes of geographic areas, and then looking to make sure that all nodes in those cubes connect with one another, and splitting of any cubes which do not have connectivity.  You then stitch together trees out of the nodes that are still in those geographic areas have connectivity, and then you build the next level of hierarchy as a way to get from one geographic area to the others.

Whoa, hold there. Let's assume without loss of generality that *all* the free space in the map is connected. What then? Just being connected can't be used as criterion for splitting space up - that would be meaningless! Space that isn't connected shouldn't be part of the same tree on *any* level!
You have to divvy space up on the basis of choke points, or maximum convex regions or some other heuristic. Which one though?

Of course they aren't part of the same tree if they aren't connected.

This isn't a problem at all - if you cannot find a connection for some reason, you just start building another tree.  Only connected nodes are connected to the same tree.  Connection on a tree IS the implication of connectivity on the map, after all.

Sure, disconnected trees aren't the problem. But you can't use connectedness as the criterion for splitting up space like in the quote. You have to make something else up, some heuristic - there's no free lunch.

The other option is that you can start from an arbitrary point somewhere in the "middle" of the map:
This works best with the innate nature of a tree data structure, upon further thought, since it relies upon some of its basic principles, and assumes some dynamic ability to shift to changing nodes.

Pick a node, any random node on the map. 

Now, you have to start connecting all its adjacent nodes to it as branches, and start building a tree.

During this process, the tree needs to "balance" itself, which is a basic function of many trees.  This means that the "root node" will change to be the node with the most roughly-equidistant leaf nodes hanging off of it.  (This means that you don't want a lopsided tree, if a branch becomes larger than the rest of the tree, the start of that branch becomes the new root, and the old root becomes a branch of the new root.)

Once you hit a certain point of complexity, say ten tiers on the tree structure, it is time to build the next level of hierarchy.  In this, the root node becomes not only a root node for the level-1 tree that we were building before, but also the root node of the level-2 tree, which acts as the geographical equivalent of moving from a city-level to a state-level of travel.  Each of those other level-1 trees becomes filled out with new root nodes for their level-1 trees, based upon the fastest connection to the root node of the level-2 tree.  Each of these new level-1 trees is now a branch of the level-2 tree.  You then keep on going, populating the level-1 trees until they have to simply split off, and make a new level-1 tree which they are connected to.

Could you draw a picture of that? *scratches head* Does every subtree become a single node in the L2 tree or multiple nodes? If multiple, how is the L1 tree subdivided to make L2 nodes?

I'm going to make my diagram "upside down", just for consistency in making people understand the concept of a "tree", where "higher tier" means "up", for those who aren't familiar with the customary way of dealing with trees in Computer Science.
[/quote]
I'm only a computer scientist by adoption, but I must say I've almost never seen a tree diagram that way up - it was you who was talking about going "down" when moving towards the root, before. But anyway, we know what we mean.

Spoiler: large image (click to show/hide)

Anyway, it's not that much more complex than a regular tree - instead of a tree node containing a single map node's data, it contains a link to another tree (the red lines).  It's just using a minor bit of recursion in the data structure. 

If you understand trees at all, it's just a fairly simple extension of the concept.

That doesn't really answer my question. How do you create that tree from a L1 tree? Could you draw the original next to it? Because, I'll be frank, it seems to me that you've missed some logical steps. Why didn't all the children of the original root node become L2 nodes, but only 3 of them?
(If the original root is St. Louis, how come some of its neighbors get to be states and some not..?)

[NW_Kohaku]

I'm going to break off answering this into discrete chunks at this point...

I was talking about only the tree-based pathfinding here, without also imposing the hierarchical scheme you suggested subsequently. If all you have are cities, not states or any larger groups, you'll still have the problem I describe. Just clarifying.

Well, the thing is that the tree-based pathfinding is optimized for finding a path with the least amount of processor time consumed possible.

It is NOT trying to find the optimal path for a dwarf to get from point A to point B in the shortest number of steps.  It IS trying to make the processing-time-optimal calculation to find ANY valid path.

You are complaining that the form of the function that isn't concerned at all with distance optimization isn't distance optimized.  Of course it isn't - it's not even supposed to be!

It's only the alternate versions, where we aren't optimizing one over the other that you have something closer to distance-optimization.  But it's still a tradeoff. 

It's like seeing a boat, and complaining about how it's really hard to handle on the Interstate.  It wasn't ever built to accomplish that function in the first place.

No, you misunderstand. I really meant passing-through. If St. Louis has only, say, 10 major entry points you need to store 45 costs. All well and good. But what about the state of Missouri? It will likely have hundreds of entry points, meaning thousands of costs to pre-compute and store.

I'm not misunderstanding, this is exactly what I was talking about.

Missouri might have 100 entry points, but you don't need to actually record all of them.  That's what I said about recording only the best of them. 

Missouri is only connected to, what, 5, 6 different states?  All you need to record is the best path if you are traveling through Missouri from one state to another.  Typically, this means you just stay on the Interstate the whole way through.

Yes, this means you'd have to pre-compute which paths are "best", but you'd either have to pre-compute them or else have to perform on-the-fly pathfinding no matter what pathfinding method you use, anyway.  The only question in which one is best depends mostly on the probability of the map becoming dramatically changed vs. how often dwarves will pathfind through those areas.

I'll reiterate my main point: Hierarchical representations only help you if the world conforms to that hierarchy. Cities are natural clusters as far as pathfinding is concerned -states are not. Nor, as I said, are any Dwarf Fortress subdivisions except for "room" that I've heard proposed.
Star shaped topologies help you only if the world is star-shaped.
Quad trees help you only if the world has large square chunks of free space/occupied space. And if you impose a quad tree over a DF map, you're going to have an entry point count that is proportional to the length of the sides, meaning O(L^2) costs to be precomputed.

Basically: No free lunch. The only way to beat unbiased tile-by-tile BFS is to bias the search. A* biases in favor of worlds with straight-ish paths. Room-based nodes bias in favor of worlds which actually have rooms. Your tree search approach biases (heavily) in favor of worlds with a star-shaped topology. Your hierarchical search biases in favor of worlds with scale invariance.
Nothing wrong with any of this - one just have to go into it with open eyes. It happens to be my belief that both the star-shaped world assumption and the scale invariance assumption will be quite off in many, if not most Dwarf Fortress maps.

But this is, again, completely ignoring some of the solutions to these exact problems I've already outlined.

If you want to optimize for direct paths, you have to use a method which trades performance in terms of processor power and memory storage in exchange for better distance pathfinding optimization.

I've already discussed different gradients of ways to do this - duplicate-information storage in the tree WILL enable trees to become less "star-shaped" by having the "star" overlap on top of itself. 

This is specifically HOW to avoid the "going to St. Louis to get to Pasadena" problem you were talking about - but you don't seem to be paying it any attention at all.

[Sunken]

I'm going to break off answering this into discrete chunks at this point...

I was talking about only the tree-based pathfinding here, without also imposing the hierarchical scheme you suggested subsequently. If all you have are cities, not states or any larger groups, you'll still have the problem I describe. Just clarifying.

Well, the thing is that the tree-based pathfinding is optimized for finding a path with the least amount of processor time consumed possible.

It is NOT trying to find the optimal path for a dwarf to get from point A to point B in the shortest number of steps.  It IS trying to make the processing-time-optimal calculation to find ANY valid path.

You are complaining that the form of the function that isn't concerned at all with distance optimization isn't distance optimized.  Of course it isn't - it's not even supposed to be!

It's only the alternate versions, where we aren't optimizing one over the other that you have something closer to distance-optimization.  But it's still a tradeoff. 

It's like seeing a boat, and complaining about how it's really hard to handle on the Interstate.  It wasn't ever built to accomplish that function in the first place.

Good, we're on the level then. I just wanted it clear for the record that, on its own, the tree pathfinding though fast won't produce optimal paths (unless the map is star-shaped). Which is why you propose modifications/additions to it, to smooth that bias out. Nothing wrong with that.

I'm not misunderstanding, this is exactly what I was talking about.

Missouri might have 100 entry points, but you don't need to actually record all of them.  That's what I said about recording only the best of them. 

Missouri is only connected to, what, 5, 6 different states?  All you need to record is the best path if you are traveling through Missouri from one state to another.  Typically, this means you just stay on the Interstate the whole way through.

OK, sorry if I misunderstood; it looked like you were talking about within-unit pathing.

But this is not a solution if you think about it.
What's the "best" path from Arkansas through Missouri to Kansas? Looking at Google Maps, it looks like that's Bella Vista to Galena - about 25 miles.
What's the "best" path from Tennessee through Arkansas to Missouri? Crossing at Blytheville you can do it in 20 miles.
So - this proves you can get from Tennessee to Kansas in less than 50 miles. Or? I'm not being facetious here - try it yourself. If you had some other definition of "best" path in mind, what is it?

Keeping only one through-state(node) path cost is a major simplification which - unless there is only one entry point into each state "node" - will make for some completely wild paths. Plus, it would be near impossible to come up with an admissible heuristic for A* if you want to use that.

[Sunken]

I'll reiterate my main point: Hierarchical representations only help you if the world conforms to that hierarchy. Cities are natural clusters as far as pathfinding is concerned -states are not. Nor, as I said, are any Dwarf Fortress subdivisions except for "room" that I've heard proposed.
Star shaped topologies help you only if the world is star-shaped.
Quad trees help you only if the world has large square chunks of free space/occupied space. And if you impose a quad tree over a DF map, you're going to have an entry point count that is proportional to the length of the sides, meaning O(L^2) costs to be precomputed.

Basically: No free lunch. The only way to beat unbiased tile-by-tile BFS is to bias the search. A* biases in favor of worlds with straight-ish paths. Room-based nodes bias in favor of worlds which actually have rooms. Your tree search approach biases (heavily) in favor of worlds with a star-shaped topology. Your hierarchical search biases in favor of worlds with scale invariance.
Nothing wrong with any of this - one just have to go into it with open eyes. It happens to be my belief that both the star-shaped world assumption and the scale invariance assumption will be quite off in many, if not most Dwarf Fortress maps.

But this is, again, completely ignoring some of the solutions to these exact problems I've already outlined.

If you want to optimize for direct paths, you have to use a method which trades performance in terms of processor power and memory storage in exchange for better distance pathfinding optimization.

I've already discussed different gradients of ways to do this - duplicate-information storage in the tree WILL enable trees to become less "star-shaped" by having the "star" overlap on top of itself. 

This is specifically HOW to avoid the "going to St. Louis to get to Pasadena" problem you were talking about - but you don't seem to be paying it any attention at all.

That's a pretty uncharitable thing to say. I've said that the "shortcut" solution you suggested won't cut it unless you can show how it is combined with your hierarchical scheme, and to my mind you haven't yet. That's not "not paying attention".
I keep asking questions because I think you will find things far more difficult than might be first imagined if you really get down to the details. That's my experience at least: I've spent hundreds of hours trying to implement similar things, most of that time on things I'd never have expected to be so hard.

[MercuryP]

But this is not a solution if you think about it.
What's the "best" path from Arkansas through Missouri to Kansas? Looking at Google Maps, it looks like that's Bella Vista to Galena - about 25 miles.
What's the "best" path from Tennessee through Arkansas to Missouri? Crossing at Blytheville you can do it in 20 miles.
So - this proves you can get from Tennessee to Kansas in less than 50 miles. Or? I'm not being facetious here - try it yourself. If you had some other definition of "best" path in mind, what is it?

I confess I'm not particularly engaged in this topic, but wouldn't doing things this way defeat the whole purpose of having nodes in the first place?  The whole point of nodes is to pick out important positions on the map and find paths according to those.  Namely, these important positions would be the centerpoints of each node.  So finding a path from Arkansas through Missouri to Kansas would require said path to travel through the center of Missouri.  I'm thinking it would probably need to be relative to the centerpoints of Arkansas and Kansas, too.

You can smooth things out later by doing regular intranode pathfinding at each node along the way.  If the nodes make sense, this should be a larger quantity of very cheap calculations relative to what the game does now, and the cheapness should more than make up for the larger quantity.

[Draco18s]

You can smooth things out later by doing regular intranode pathfinding at each node along the way.  If the nodes make sense, this should be a larger quantity of very cheap calculations relative to what the game does now, and the cheapness should more than make up for the larger quantity.

Quite.  Smaller search space.

[NW_Kohaku]

That's a pretty uncharitable thing to say. I've said that the "shortcut" solution you suggested won't cut it unless you can show how it is combined with your hierarchical scheme, and to my mind you haven't yet. That's not "not paying attention".

But I HAVE shown it, in four different ways.  Two had pictures.  I'm running out of different ways to show it.  I've never mentioned this shortcut method in any setting OTHER than in the setting of a list of nodes produced from a tree.

Look, I'll just draw another picture:

Spoiler (click to show/hide)

The pathfinding constitutes a list of nodes it has to traverse to find A path to the destination node from the green node on the left to the green node on the right.  (All nodes not involved in this linked list (which would not be formed in tree form any longer, but a linked list) are removed. It has to cross into a level 2 search, going from blue nodes into the larger black, level 2 nodes, like in the last picture.  It then starts testing each and every node it had to cross to see if there are shortcuts, paths between the nodes that you had to cross in order to find a quicker way - and that's what the cyan line is. 

It finds a connection stored in the node (not the data tree's list of "higher nodes") that is a connection from one level 1 node to another level 1 node in a different pair of level 2 nodes.  It then cuts out all the middlemen and jumps directly across the data structure, finding a much shorter path that doesn't involve those other level 2 node areas at all.


And the reason my tone is getting rather frustrated at this point is that you keep trying to tell me the things I just explained to you, as if they were a problem.

I KNOW there is no free lunch, I just explained that. 

I know what the limitations are, I was the one who pointed them out first, while I was explaining them.  That's why I came up with solutions and workarounds.