Bay 12 Games Forum

Wurm is not 3d.  The mines kind of look like 3d but they're not--try making two tunnels cross each other at different levels if you don't believe me.

Sorry, I was "Archive Binging" and I mistyped/Freudian-slipped trawling.
On the subject of archive binging, I just finished El Goonish Shive, including the fillers and NPs. I am a webcomic addict...
I've read all of the following, in no particular order. Quality may vary, and some of these no longer update.

Spoiler (click to show/hide)

PvP, Penny Arcade, Megatokyo, Applegeeks, User Friendly, Ctrl-Alt-Del, Questionable Content, Schlock Mercenary, Sluggy Freelance, xkcd, Girl Genius, Order of the Stick, Erfworld, The Wotch, The Wotch: Cheer, Geist Panik, Hookie Dookie Panic, Machall, Three Panel Soul, VG Cats, Johnny Wander, Anthem, Angry Zen Master, Accidental Centaurs, and El Goonish Shive.

If you liked El Goonish Shive, you might like DMFA.

Quote from: Sowelu on January 30, 2009, 12:47:43 pm

Room for improvement:  Since "many-to-one" is a bunch of stuff stored in one stockpile which is NOT just one square but many, can't "one-to-many" or "one-to-one" take from, say, two corpses lying literally right next to each other?  Maybe there can be a certain radius inside which you run a VERY short A* to ensure there's connectivity, and then treat them like the same point of origin.  Would only run that to look for other nearby stuff after picking up the first item though, no point in scanning the whole map for items close to each other.

Maybe you mean something different by "connectivity," but if you just mean strict accessibility -- the connected component numbers exist for the purpose of pathfinding feasibility checks, so that shouldn't be necessary.

I think the game uses short-range floodfills for impromptu pathfinding, like for flying creatures attacking from the air -- maybe those would work best for finding nearby haulables.

Yeah, short-range floodfills was what I was after, was just fumbling with the words.  It's well and good to know that there's another prickle berry seed two squares away, but if it's on the other side of a wall, then you're no longer taking them both from the same place and you need to think harder about what you're doing.  When taking haulables from one place and distributing them to many destinations, you probably want to stick with picking up items within a couple steps of your origin.

This is a classic hard computer problem.

"Hauling many thing to one place" is a little simpler.  But there's a huge problem in that dwarves don't know how long it takes to walk from point A to point B.  It's totally believable that a dwarf would say "Okay, I'm picking up this seed from a table, to take to the seed stockpile that's just through that door.  Oh hey!  There's another seed two squares away!  Let me walk over and get that, then take them both to the stockpile."  Except the second seed is only accessible through a very long path.

I guess there's an argument that, as long as you don't carry so much that it reduces your speed, you can't actually increase the total time to get all the items into the stockpile this way (since they're all going to the same place eventually).  Huh.  Yeah, even if there's items laid out like A.....stockpile.....B, then if you pick up A then B then go to the stockpile, it at least can't be any slower than A-stockpile-B-stockpile.  That seems important.  So even in that degenerate case with the two seeds last paragraph, there's no travel time hit overall.

Other issues:

While it's possible to do Travelling Salesman on a small number of items going to the same location, it's still slow if there's real pathfinding involved.  If there's not, it'll be kind of stupid and the worst-case will be no improvement.  I don't know what average-case will be like.

If you allow haulers to carry so much they're slowed down by weight, the worst-case goes from "no improvement" to "huge penalty", and that is VERY not okay.  IE if A.....stockpile.....B is two lead statues instead of seeds.

Trying to figure out "many-to-many" instead of "many-to-one" is much harder, because again, it's quite possible to make the walking distance higher.  Also it's a lot of calculations, because you're saying "Okay I now have item A, going to place M.  What nearby items need to be hauled?  Okay, item C is X distance away, going to N.  I can go ACMN or ACNM.  Which one is better?  Are there better other choices of C and N (other haulable items) that are faster?  Can I chain multiple things?  Now do I want to pick up items ABCDE-MNOPQ or ABECD-OPNQM?"

One-to-many is not too bad; it's about as good as many-to-one.  If you pick up a piece of loot from, say, a body, it's easy to say "what else in this square is haulable".  Then it's a reasonably simple travelling salesman to figure out a one-digit number of destinations, not bad.  One-to-one (all that guy's clothes into one stockpile) might even let you carry a little over the weight penalty level...just a little.  Because you can easily algorithmically establish how much stuff is optimal.

Room for improvement:  Since "many-to-one" is a bunch of stuff stored in one stockpile which is NOT just one square but many, can't "one-to-many" or "one-to-one" take from, say, two corpses lying literally right next to each other?  Maybe there can be a certain radius inside which you run a VERY short A* to ensure there's connectivity, and then treat them like the same point of origin.  Would only run that to look for other nearby stuff after picking up the first item though, no point in scanning the whole map for items close to each other.

I fear that people may be disappointed at first when masons don't grab multiple stone to work on, or farmers don't take multiple seeds in one trip or harvest multiple plants at once--if this is hauling, it's JUST hauling.

If a dwarf goes to nap or eat or drink when on a hauling job, multi-hauling makes it very easy for a hauling job to only move one object FARTHER away from its destination.  This has to be accounted for somehow.

This would tie up more items at once, because there'd be more hauling tasks going on--more items get claimed for hauling at a time.  And it might be a problem if someone starts hauling your only piece of wood, then decides he's also going to take this craft to this stockpile while he's at it, oh and do this other thing before he takes the wood where it's going...


...But still, after looking through the algorithms I'm thinking of, I'm VERY confident that as long as you aren't doing many-origins-to-many-destinations hauling, and your dwarves never go above their encumberance threshold at any time when multi-hauling, you can mathematically guarantee a travel time decrease from very simple algorithms.  Hauling multiple items finally has my thumbs-up (for whatever that's worth).

Oh awesome!  I kinda hope he does release it.  And I think he just might.  I'd love to see what the obfuscations around the SoO and stuff look like in code.

"trolling" as used on newsgroups was originally taken from the fishing term, in the context of "fishing for a response".  It's still valid for any time you're wandering the depths of something murky.

Is it safe to try, say, dropping something when you have no inventory?

I think the player should definitely be of the monster class.  This way it is much easier to enable monsters to interact with the environment and each other the same way the player does.
The only different would be when the monster calls his AI routine, the player should call the input routine.
You should still keep an eye out for additional input, though, so the player can press 'Q' should he bug into a coma and keep missing his turn.

I'd recommend that "player" and "monster" both descend from "creature" in a simple roguelike, myself.  There's enough differences there.  They're controlled by different routines on their turn, they do different things when they get hit or die (like making different messages), different things want to chase/kill them, etc.