Print

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

[Silverionmox]

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.

It's possible to play around with the storage place. If you we're able to link stockpiles to workshops (though IMO stockpiling and workshop tasks could be both optional functions for a room, but that's another matter) then that path could be stored in the workshop. The bedroom to staircase could also be stored at the room's level. I expect these paths to be rather short anyway, but searching a bedroom starting in the storage room area, finding a staircase, and then searching on towards the right bedroom is much, much more CPU intensive that searching from the storage room to a known central staircase, and then retrieving a stored path from the staircase to the room.

The pathfinding could also treat the z-level differently (which makes sense, dwarves can't change z-levels without stairs or the like): check first if the destination is on the same level; if yes, pathfind only on the level; if not, pathfind to a staircase instead. That would make 90% of routes easier, and 5% more difficult, but it's always possible to revert to the standard, cpu-intensive but almost infallible pathfinding.

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.

That's what I mean. Let them use conceptual heuristics, gaining speed at the cost of accuracy. I'd rather have my dwarves make a detour now and then (or get lost) than cut my FPS in half. There's always the option to fall back on the thorough, standard way to do things instead of shortcut.

It's primarily intended for the routine stuff. Invaders, soldiers, scared dwarves, hunters, miners etc. are alert or in an unfamiliar area and pay attention to where they're walking. Scruffgong the food hauler isn't.

[Draco18s]

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.

That's what I mean. Let them use conceptual heuristics, gaining speed at the cost of accuracy. I'd rather have my dwarves make a detour now and then (or get lost) than cut my FPS in half. There's always the option to fall back on the thorough, standard way to do things instead of shortcut.

It's primarily intended for the routine stuff. Invaders, soldiers, scared dwarves, hunters, miners etc. are alert or in an unfamiliar area and pay attention to where they're walking. Scruffgong the food hauler isn't.
[/quote]

There's a difference between "drop every other node" for speed at the expense of accuracy and actually having a better algorithm.

Dropping half the nodes actually makes the speed worse, due to the fact that you can no longer infer node connectivity due to adjacency (thereby requiring you to store the information increasing memor, or to check at function-run-time decreasing speed) among other things.

[tps12]

The pathfinding could also treat the z-level differently (which makes sense, dwarves can't change z-levels without stairs or the like): check first if the destination is on the same level; if yes, pathfind only on the level; if not, pathfind to a staircase instead. That would make 90% of routes easier, and 5% more difficult, but it's always possible to revert to the standard, cpu-intensive but almost infallible pathfinding.

How do you know where staircases are, if not by pathfinding?

[NW_Kohaku]

Actually, I'm more concerned about the assumption that all players will make mostly 2-dimensional forts with rare stairwell access.  What about players who purposefully make their fortress more vertical?  I tend to make things fairly vertical to compres my fortress into being as spheroid as possible whenever I'm not going for more elaborate fractal designs.  It's more efficient that way.

Why should a change in the axis you move along change the way that the game calculates how to get from one point to the other, when it basically is as easy (if not easier) to move vertically than horizontally?

[tps12]

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.

I don't think that would be a significant load on the CPU. Locating an item for a reaction is something that only happens infrequently in terms of simulation steps, even if you're churning out mugs by the binful. And it's cheap: the game only needs to find the closest usable item (it doesn't care by how much A is closer than B, just that it's closer), so it can just compare distance squared for one run through the item list. Since that item list is being iterated all the time anyway, for temperature calculations and decay and whatnot, an additional run-through every hundred steps or so is in all likelihood a drop in the bucket. Though empirical evidence could convince me otherwise.

[NW_Kohaku]

Perform the experiment yourself, if you want: go digging up tens of thousands of stone, while you have a dozen or so stonecrafters constantly working.  Turn off temperature in the raws to exclude it from the experiment.  Now, when you have really, really low FPS, backup a save, alter the boiling point of the major layer stones so that you boil away about 80% of the stone in your fortress, and see what it does to your FPS.  Or just shut off all your workshops, and let dwarves idle.

I personally became very well acquainted with the phenomenon when I altered the trade caravans to have enough cargo capacity for the elves to bring in about 20,000 items onto the map at once, which instantly lopped my FPS down to about a fifth of its previous rate.  Yeah, sure, that was with temperature, but it wasn't all temperature, it was my weavers looking at all that rope reed from across the map every time they went looking for something else to perform their jobs with.

The number of items on the map has huge FPS implications, especially since that "number of items" is in the tens or even hundreds of thousands, and is itereated through each time any character wants to do anything with anything.

[tps12]

Or just shut off all your workshops, and let dwarves idle.

That's the experiment I'd do; everyone a stonecrafter versus everyone with all labors off, same save, queue up a bunch of crafting jobs. Temperature on or off wouldn't matter as long as it's the same for both trials. My hypothesis is there would be very little difference.

I personally became very well acquainted with the phenomenon when I altered the trade caravans to have enough cargo capacity for the elves to bring in about 20,000 items onto the map at once, which instantly lopped my FPS down to about a fifth of its previous rate.  Yeah, sure, that was with temperature, but it wasn't all temperature, it was my weavers looking at all that rope reed from across the map every time they went looking for something else to perform their jobs with.

Probably more likely due to the existence of all the additional items themselves. How many weavers did you have, and how much could they possibly have been weaving?

[NW_Kohaku]

Between all the food and clothing industries, about 40 dwarves would be using the products that were carried in the caravan.  I had a mostly clothing-based economy.

[tps12]

I just tried this out with a community fort from the forums. I turned off all labors except stonecrafting and built enough workshops for everyone, then paused and put repeat rock craft jobs in each one. Then I duped the save and started up two copies of the game and assigned each to its own core. I used Dwarf Therapist to disable all labors in one game, then unpaused both.

The one with all labors disabled initially dropped way down, presumably while they pathed to a meeting zone to idle in. Then both games settled in near the same speed, 20 FPS for the all-stonecrafter game and 18 for the all-idler game.

(My intent was to do the experiment "blind," since I wouldn't know which instance Dwarf Therapist would attach to, but the idler count gave it away.)

This was with around 50 dwarves, of which 30 or so were non-child civilians, and with about 10k stone.

[NW_Kohaku]

Well, if idling takes up more frames than doing work (something, I should point out, NEVER happens for me, I tend to notice that running out of wood and having my carpenters all idle makes my FPS shoot up about 5 to 10 points), then it implies that something entirely different is happening. 

If, as is your hypothesis, there is negligible impact on the time spent on populating lists of objects for the purposes of finding one to pathfind to, then the framerates should be the same - having it actually drop for idling implies something else is suddenly taking up their processor time.

I'd have to ask how much stone there is laying about in the fortress you tested this on, for starters, on the inventory screen.  I'd also have to ask how far away they were going to get it.  Also, what the idlers were actually doing.

[tps12]

I'd have to ask how much stone there is laying about in the fortress you tested this on, for starters, on the inventory screen.  I'd also have to ask how far away they were going to get it.  Also, what the idlers were actually doing.

It was just a random fort I grabbed, but the stone looked like it was "everywhere," just sort of strewn about. I forget the exact number, but it was somewhere in 10-20,000. How far they were going to get it shouldn't make a difference if the CPU load is due to choosing which stone to find.

If, as is your hypothesis, there is negligible impact on the time spent on populating lists of objects for the purposes of finding one to pathfind to, then the framerates should be the same - having it actually drop for idling implies something else is suddenly taking up their processor time.

My guess would be that idle dwarves have to regularly check to see if there are other jobs that need doing (even with labors disabled they can deconstruct or whatever), but whatever it was was enough to, ah, dwarf the cost of looking for stones to craft.

Anyway, that's all for the "further questions" section of the proper lab report. Feel free to reproduce, tweak the experimental design, &c. I'm satisfied that I didn't see any dramatic slowdown due to searching for reaction items.

[Max White]

This still going on?
Yes, stone and other large amount of objects cause lag. I mean I can only assume this is because your computer is busy handling virtual memmory, but that would imply that somehow DF has eatern your ram alive... Well that does sort of sound reasonable.

[Silverionmox]

The pathfinding could also treat the z-level differently (which makes sense, dwarves can't change z-levels without stairs or the like): check first if the destination is on the same level; if yes, pathfind only on the level; if not, pathfind to a staircase instead. That would make 90% of routes easier, and 5% more difficult, but it's always possible to revert to the standard, cpu-intensive but almost infallible pathfinding.

How do you know where staircases are, if not by pathfinding?

Staircases in general don't move that often, so if you can identify the big ones, you can use their location again and again without pathfinding again. The drawback is that your dwarves will act a bit confused when, for example, the staircase collapses... but that only adds to the verisimilitude - when a staircase collapses, it does confuse people.

Actually, I'm more concerned about the assumption that all players will make mostly 2-dimensional forts with rare stairwell access.  What about players who purposefully make their fortress more vertical?  I tend to make things fairly vertical to compress my fortress into being as spheroid as possible whenever I'm not going for more elaborate fractal designs.  It's more efficient that way.

Why should a change in the axis you move along change the way that the game calculates how to get from one point to the other, when it basically is as easy (if not easier) to move vertically than horizontally?

Ah, but dwarves are restricted by gravity and walk on the x-y plane. They don't walk along the y-z or x-z plane. In addition, workshops, stockpiles and the like can't be built vertically.

There should obviously be a limit to the efforts of the program to identify the staircases. If there are too many of them, it becomes pointless to identify them. The same with corridors: if there's a central broad hallway with sideways, it makes sense to identify it; but in a maze, don't bother.

[ullrich]

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.

If he's just using A* with manhattan, regardless of programming optimization, how hard is it to just change the heuristic function, since manhattan weighting can be massively improved with a tie breaker, I have done a project during one of my AI courses which pitted various algorithms against each other on a 2D maze (25x25), these are the results (# of nodes searched to find path):

	End in a Room, 1 entrance, close.	Opposite Side of Map, multiple paths.	Opposite Corners of Map, multiple paths.
Depth-First (not optimal)	78	31	81
Breath-First	376	250	488
A* (Euclidian)	163	94	380
A* (Manhattan)	77	81	340
A* (Vector)	48	72	117

The Manhattan weighting is |x1-x2|+|y1-y2|, in 3D it should be |x1-x2|+|y1-y2|+|z2-z1|.
The vector weighting adds onto Manhattan using the cross product, and modifies the values to be less than 1, thereby allowing 2 nodes of value x to be differentiated from so say 2.1 and 2.2 rather than just 2 & 2 forcing both to be expanded.

The formula in 2D is (the 2 vectors are start-end, and node-end): (0 is start location, 2 = end location, 1 is current location/node)
dx1 = x1-x2
dx2 = x0-x2
dy1 = y1-y2
dy2 = y0-y2
CrossProduct = |dx1*dy2 - dx2*dy1|
For my application this was multiplied by 0.001 to ensure this value was never > than 1 but this could be modified upon map creation by taking the max possible cross product +1 as a divider, however in 3D space the cross product is not scalar but another vector, so I'm not entirely sure how to parse that into something meaningful, perhaps a smaller magnitude of a vector, I'm an engineer I'm sure a Mathy could figure something more useful out for 3D (the goal is the path that is more direct between start and end, so a smaller difference between the 2 vectors).

In 3D it would be:
dx1,dx2,dy1,dy2=same as above
dz1 = z1 - z2
dz2 = z0 - z2
CrossProduct = (dy1*dz2-dz1*dy2)i+(dz1*dx2-dx1*dz2)j+(dx1*dy2-dy1*dx2)k

Basically as long as the additional calculations take up less time than the number of nodes that are expanded (which each require further calculations) it is better, and in general mathematics are faster than node handling anyway on a computer.

[Kumquat]

DF isn't using Manhattan distance.

It is using Max(|x1-x2|,|y1-y2|,|z1-z2|).

If it was using Manhattan then a mason workshop making blocks in a quarry would clear out a diamond-shaped area. Now it clears a square/cube area.