Bay 12 Games Forum

@Rakushun

It's not for Toady's sake, it's for us as suggesters.  It's more akin to "You're offering that guy some expensive Dwarf socks, but there's no way he could afford them-- why not offer something less expensive in hopes of actually making a sale?"  It's directed to the seller, not the buyer.

@Andeerz
Just to give you and anyone else some supah-useful info as a CS major (if you're at all interested), pathfinding literally translates to traversing a graph of nodes, in an attempt to find the path from one node to another.  Given N nodes, the worst case number of operations (of arbitrary size) is N^2, just due to the way the algorithm works out (it's thoroughly studied in computer science, and that's the best anyone on the planet can come up with.)  It's generally much less than this, say if a dwarf is only moving to a nearby cell, but the worst case gives both an idea of how expensive the algorithm is and an accurate approximation for whenever dwarves travel far away (all the time, I think.)   Mainly, polynomial complexity of the algorithm prevents DF from doing it in a very straightforward manner (the straightforward manner being each cell considered a node in the graph... if there are 10,000 cells in an area, you couldn't possibly calculate this every tick and not cause tremendous lag, because it'd be 10,000*10,000 operations worst case.)  So DFs solution to this is to redefine what a "node" is-- suppose DF can break the game world into "zones" (rooms, hallways, etc), then each zone, rather than each cell in it, comprises the graph-- instead of 10,000 nodes, you get maybe 50!  I imagine DF is already doing this or something better, and Toady has likely poured tons of time into optimizing it.  This is an extremely difficult problem, one that he's probably already spent months on, and it's likely the algorithm couldn't be sped up without significantly changing a game mechanic (like allowing dwarves to teleport through walls, thereby eliminating the need for pathfinding altogether.  Instead maybe mark some zones, like unexplored ones, as "unenterable to all dwarves" so dwarves never teleport there-- would be an instant lookup (polynomal time of 1 ))

If by any chance Toady hadn't done something similar yet, I was thinking a great way to speed up the pathfinding would be to have "graphs of graphs of graphs of..." however many levels as determined by the current number of total nodes.  Partitioning the graphs into distinct nodes would be fairly expensive (N^2 * log2(N) I think... check http://en.wikipedia.org/wiki/Graph_partition), but the beauty is that it only has to be calculated infrequently.  You could think of the graphs layers as being "regions->locations->structures->rooms->cells", though the number of layers higher than "cells" would actually be determined dynamically as the fortress took shape.  With a tree like structure, I think traversing the graph would change from N^2 to (N/B)^2 / logB(N), where N is your node count and B is your number of nodes per partition.  With N=10,000 and B=25, you'd go from 100,000,000 operations to about 56,000!  In uh, non-geek terms, it's the difference between searching through neatly organized folders and folders scattered all over the floor   I hope that wasn't too jargony

As far as an "accessibility map" goes, I think what the premise was might translate roughly to "caching" frequently calculated paths (I might have misunderstood).  It'd only work if the number of nodes could be generalized to some degree, like in a hierarchical graph system (caching every possible path would be (cell count)^2 otherwise, so with tens of thousands of cells, you wouldn't have enough RAM).  Basically, caching paths for every room combination is feasible, but paths between every cell combination isn't.  So the aforementioned zone system would work well with it, and that super-meta-graph thing I cludged together would work REALLY well with it!

Hope that wasn't too rambly, just thought it might be good to give an idea of what kinda stuff would have to go into this idea   I really like the idea, I hope I didn't give an impression to the contrary, I just thought it'd be good for people to know what they were asking for

EDIT:  On the offchance Toady reads this, apparently Fibonacci heaps are good with Dijkstra's shortest path algorithm: http://en.wikipedia.org/wiki/Fibonacci_heap.  You should add one if possible: you'll totally feel like a badass if you do.

EDIT again:  Apparently choice of heap also depends on how "dense" the graph is.  You could dynamically check densities and swap between Fib heaps (for dense) and Binary heaps (for sparse) depending on the situation.  http://stackoverflow.com/questions/504823/has-anyone-actually-implemented-a-fibonacci-heap-efficiently  (I happen to be on the subject of heap selection for a research project, haha)

Yeah, definitely deserves a spot on eternal list

@Andeerz:
I definitely think the problem is pathfinding.  You're right about the speed of dwarves increasing it-- 72 times faster movement = 72 times the number of pathfinding calculations (since dwarves would be reaching their destinations and recalculating 72 times as often.)  Well, unless the paths are cached somehow   Then player intervention might actually be a factor in increasing it.  A teleporting scheme *might* help if... well, I don't know how DF currently does it, but intelligently defining path nodes that are known to connect, then partitioning the graph of nodes into subgraphs that are known to connect, could provide gratuitous speedups, since dwarves could just teleport through the outermost graph layer and not have to wander through littler graphed details.  That's assuming if it's even possible to create a tree of subgraph partitions efficiently... I think at worst case it'd be like N^3 * ln(L)/ln(B) operations (really frickin bad), where N is your node count, L is the number of layers, and B is the nodes per layer.  You probably couldn't run the algorithm smoothly with every block place/removal... not that I have any idea what I'm talking about

Eh, a slow motion mode would technically be less clock cycles per second, but the reality is it would be far more clock cycles overall.  Also, it would free up the CPU in the mean time, sure, but what would that accomplish?  I wasn't under the impression combat was a CPU intensive thing (I could be wrong.)  I believe things that eat clock cycles are pathfinding, weather, and fluid mechanics-- all else held equal, they'd each be reduced significantly, BUT by nature of wanting an accurate simulation, weather and fluid mechanics would be ramped up accordingly (pathfinding is up in the air.)  So the benefit would be day and night cycles, and the sacrifice would be... a LOT in terms of Toady's time, especially when bugs and additional, potentially broken mechanics are introduced.

Think about dwarves moving in abstract, long term time, then the player going slow motion-- should the dwarves speed up accordingly with respect to time?  Well, that'd horribly break the abstraction!  Players would constantly manipulate it to their benefit (probably not a fun mechanic.)  So you'd have to change the way dwarves move in the abstract... but there's no clear way to do that without absolutely wrecking CPU cycles   Also, as GreatWyrmGold described, you'd have to add some sort of automatic low level fortress management, but... that'd be both a questionable and difficult mechanic to add to the game.

Personally, I love the idea of a day and night cycle, but I don't think this is the way to approach it.  Instead, you could just have 5-10 days and nights per month, and be done with it.  As for a "sped up" mode, I think something as simple as opening a dialogue that says "Wait how long?" as in Adventure mode would be appropriate, with similar interruption mechanics, and a loading-ish screen while the game runs Fortress mode as usual, with the exception of no framerate cap or world being rendered, possibly with further abstraction upon the game mechanics in order to speed things up (only to the extent it'd be a good use of Toady's time.)

I think viewing Fortress mode as an attempt to simulate things in real time fails to do it justice.  No one cares about the abstraction-  the important thing is that it's fun and playable.  Since recoding everything would be an absolute nightmare (several months of coding, minimum), I say Toady stick to the  "loose" abstraction of time that DF currently has and run with it, only caring for realism in that respect to the extent that it's either fun or hilarious

What are good ways to manage your inventory in Adventure mode?  Tips, tricks, techniques, and ideas would all be helpful!

For example, trading all yer crap for gems to reduce your inventory weight, or dropping everything in your hands after massive trades by holding down '*' in the drop menu then tapping "A"->"D" every time the screen reaches the bottom (fractions of a second between each press, goes purdy fast).

The reason I ask is both for personal knowledge and to create a nice reference for everyone (I think it'd be a great Wiki page.)

My personal dilemma: after looting a million highwood crossbows and copper low/high boots from a castle, AND totally buying out every shopkeeper I knew had much more value-dense items, I'm still having difficulty moving around the place!  And my inventory takes forever to scroll through to boot (no pun intended.)  Wealth certainly has a high price...

EDIT:  I'm in v0.34.02, the trick above with dropping recently traded items became irrelevant a patch or two later, since traded items were modified to transfer to your backpack rather than your hands