Print

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

[NW_Kohaku]

I should note that the paper didn't construct a physical network of memristors and instead constructed a simulation (not to mention asserting that such an "algorithm is superior to any existing maze solving methods", I don't know how this measures against pathfinding, though), but the idea of a a physical chip to do this it attractive. Why the small numbers though? I can't find sizes for current memristors, but they're not going to hit consumer market in such a chip if they are macro scale, so by the time one is made we should be able to fit some hundreds, if not thousands, on a chip, even accounting for infrastructure effecting walls and result reading.

The problem with this is that a simulation of memresistors doesn't actually run the same way that a real array of memresistors runs.  A simulation of memresistors has to have your CPU individually model the actions of every single memresistor, which would be worse than simply flood-fill pathfinding. 

If you could take all the advantages of a memresistor without having to actually build a memresistor with no additional cost, then who would want to build a memresistor in the first place?

Crafty players already place doors over bedrooms (regardless of how many occupants they have) and workshops, so that moody dwarves, thieves, wild animals or riots can be contained by locking a couple of doors. Low framerates would serve as a reminder to do so.

I think this is what I have the biggest problem with...

Your choice of where you build doors should not be based upon how you want to exploit the pathfinding program into doing what you want.  You should build doors, "physical constructs" in the DF world, to control physical flows, not to handle meta-game exploits of the way dwarves "think".

We already have a nod towards player control of pathfinding, and that's in traffic designations.  Traffic designations are free, because you don't have to build anything to tell dwarves "this is a bedroom, don't path through it", you just need to make sure people understand it's a bedroom, something architecture the game currently isn't capable of recognizing would probably be best capable of conveying. 

I think node-based pathfinding is a great way to make pathfinding as a whole work better, but either make the computer figure out where the nodes are by itself, or by giving the player an ability to designate, in some hybrid of burrow and traffic-zone-style, the nodes themselves. 

Constructs that are physically built for physical purposes should not have meta-game exploit purposes. 

[zilpin]

...
I think node-based pathfinding is a great way to make pathfinding as a whole work better, but either make the computer figure out where the nodes are by itself, or by giving the player an ability to designate, in some hybrid of burrow and traffic-zone-style, the nodes themselves. 
Constructs that are physically built for physical purposes should not have meta-game exploit purposes.

I agree with your point, overall.
I would further propose that, instead of making the user designate "nodes", the algorithm simply use defined Rooms as the node, and remember paths between them.  After all, you already had to make that bed a Bedroom, that chair an Office, that table a Dining Room.
Hallways are already designated with high-traffic, though I wish there were a few more options for traffic (High, Medium, Normal, Low, Restricted, Forbidden).
Designating one-way tiles would also help, but that's just dreaming.  Right now I create one-way paths using hacked ramps.

Still, I would prefer Toady spent his time on bug fixes than re-writing or adding anything.

[Granite26]

I disagree NW... 

1: Using stairs and doors to optimize pathfinding isn't meta, the pathfinder is simply recognizing them for what they are.  Barriers to separate contiguous areas.  Their effect is the same in game as it is for the player.

2: Optimization of processor time doesn't yield indeterminate solutions.  You are findind the answer faster, not finding a better answer.  Since df is turn based, there is no problem with that.

3:  Players already do ridiculous things to speed up pathfinding, from restricting dwarves to their rooms to laying out traffic zones to killing and skinning hundreds of cats a year.  Putting doors up to separate areas hardly seems worse.

[NW_Kohaku]

I disagree NW... 

1: Using stairs and doors to optimize pathfinding isn't meta, the pathfinder is simply recognizing them for what they are.  Barriers to separate contiguous areas.  Their effect is the same in game as it is for the player.

Wait, what?  Since when are stairs used as barriers to separate areas?  Stairs are used as connections between areas, and I, personally, use more vertical hallway space than horizontal.  Why should a vertical shaft NOT be seen as a hallway that connects to multiple different branching paths?

2: Optimization of processor time doesn't yield indeterminate solutions.  You are findind the answer faster, not finding a better answer.  Since df is turn based, there is no problem with that.

I have no idea how this relates to anything I said...

3:  Players already do ridiculous things to speed up pathfinding, from restricting dwarves to their rooms to laying out traffic zones to killing and skinning hundreds of cats a year.  Putting doors up to separate areas hardly seems worse.

And we shouldn't have to.  Toady doesn't give us any direction on how to do these things, they are all guesses (and usually wrong guesses), and all means of meta-exploit we shouldn't have to do, if the game was better optimized. 

I really don't think what this game needs is a piece of code that optimizes cat-skinning, what this game needs is code that minimizes cats' impact on the game's framerate.  (And Toady, in talking about farming, has said things along the lines of how pests in farms would help stop people from killing all the cats in their fortresses - as in he wants to find a way to stop the cat butchering, the way he found a way to stop the mermaid butchering.)

If the game can parcel out nodes and pathfind from those nodes, then it's a great thing, and we should find ways to do that, but the idea that we should force players to only build their forts in one specific way, or the game will punish them for their deviant stair placement or door arrangement is a completely backwards way of designing a game.

If this is really supposed to be a fantasy sandbox, the game should adapt to the player, you should not force the player to play with only the toys you want them to play with in the way you want to force them to play with them.

[Granite26]

1:  barriers to separate = borders to different, not obstacles to keep apart.  My bad, should've been clearer.

2:  just covering the big potential objections, and code that gives an in-game advantage to players who optimize is a big one.

3  People do crazy stuff already to optimize their forts.  You can't stop that.  What you can do is make the optimizations make sense in game as well as out.  The fact that people with badly laid out forts don't benefit isn't a punishment, any more than fps caps over 10 aren't a punishment for people with slow computers. 

Besides,  I don't think 'use doors to separate areas' is really that onerous of a restriction.  I wasn't suggesting making cat death easier, just pointing out what people already do in order to get fps.

Save a kitten, support pathfinding improvements.

[Shades]

Besides,  I don't think 'use doors to separate areas' is really that onerous of a restriction.

The point is that for a lot of forts it might not help at all, certainly none of the forts I make, which means you've added a lot of code for no good reason. This leads onto the point I think NW_Kohaku was getting at that your adding more ways players can try to optimise their fort rather than solving the problem. I don't think he wanted to stop players choosing to optimise, that after all is up to them, but just to avoid adding more code that only helps those that do and encourages you to.

Stairs would make more sense for my forts, probably, but doesn't sound like it would for NW's as he builds more vertical forts. Either way it doesn't sound like it's a general solution.

Of course I'm still not convinced path finding is the main cause of the frame rate loss, and if it is a single threaded A* search on such a small map should not be taking so long which implies it can be replaced without effecting too much.

[Granite26]

So you don't have a front door to your fortress and have the whole fort on one level?

[Shades]

So you don't have a front door to your fortress and have the whole fort on one level?

I don't havea front door, my only doors are bed rooms and my fort is in detacted sections each section is mostly one level.

[Artanis00]

3:  Players already do ridiculous things to speed up pathfinding, from restricting dwarves to their rooms to laying out traffic zones to killing and skinning hundreds of cats a year.  Putting doors up to separate areas hardly seems worse.

To put this bluntly: A fort that doesn't build doors or butcher stray cats at all should have just as many FPS as a fort that does.

This isn't game play or meta, but proper game design. The only reason butchering cats and building doors everywhere is necessary right now is because it's a workaround for a bug that cripples game play.

Traffic zones are explicitly designed to alter pathfinding, so a fort that uses them properly should run more smoothly than a fort that doesn't, which in turn should run smoother than one that does, but incorrectly (like making all your major hallways restricted, and all your bedrooms high traffic).

[Sunken]

3:  Players already do ridiculous things to speed up pathfinding, from restricting dwarves to their rooms to laying out traffic zones to killing and skinning hundreds of cats a year.  Putting doors up to separate areas hardly seems worse.

To put this bluntly: A fort that doesn't build doors or butcher stray cats at all should have just as many FPS as a fort that does.

This isn't game play or meta, but proper game design. The only reason butchering cats and building doors everywhere is necessary right now is because it's a workaround for a bug that cripples game play.

This.

Now, there is nothing wrong with using the structure of the forts people build in order to help pathfinding efficiency. We have to - or otherwise live with a system that is completely unbiased and thus completely unintelligent. But the biases, the heuristics we put in can be more or less well-designed and more or less general with regard to the range of forts they work well in. If our heuristc is "use doors" then it's going to work poorly for a fort that has no doors, or that places them differently from how we assumed. If our heuristic is "find choke points" the it's going to work poorly for a fort with lots and lots of uniformly wide tunnels. If we elect to let the player set nodes himself the solution will be as intelligent - or as dumb - as the player can be bothered to be. Any combination that tries to make the best of many different methods will work well for a wider range, probably at the cost of a bigger overhead and (thus) worse performance in cases that aren't covered.

This is not to criticize or propound any specific option. I just want to point at the trade-off we must deal with. We will never find a solution that deals optimally with all possible forts. A player who digs a Labyrinth of Knossos on every z-level can't expect good FPS and we can't design for his benefit. Can we design for players who don't want doors? Probably; should we? Whose Dwarf Fortress are we going to bias for?

[NW_Kohaku]

Why is it that vertical hallways should be treated differently from horizontal hallways?  Especially when people have differing ideas on what constitutes a room?  I like multi-floor "rooms", even if the game doesn't recognize them as such. (And I don't use stonesense, either, I just keep a very good image of my fort in my mind.) There is nothing logical about having a bias for mostly-flat fortresses which only have one central hallway.

You're talking about how "players already optimize" in just one particular way, but I certainly don't play that way, and it seems to me that what you are basing this on is, "I play this way, so everyone else should, too."  How do you know how many people play that way, and how do you know that people will want to play that way?

Do something for me - rebind your up and down z-level keys to 5 and 0, and play like that for a while.  I have a theory that all this obsessively horizontal building is an artifact of people simply not wanting to use > and < to go up and down since it takes a repositioning of the hands to do so.

If they are only playing that way specifically because they want to optimize, then we can optimize for whatever crazy-ass methods we want, and those people are going to do whatever is optimal, anyway, so why should we keep things exactly the same just because this is what people are doing because they feel they have to do it, regardless of how much they like it right now?

Again, I'm not saying that we shouldn't be using nodes, but that we shouldn't be doing strange things like assuming we could never have anything but a single central stairwell fortress design, and punishing any player who designs another type of fort.

Rooms/nodes, however, should be defined in ways that don't have to do with doors.  This IS possible, and it is possible by using (hopefully, eventually multi-level) either zoning abilties in the game, or the game being able to naturally infer from narrow chokepoints where the nodes connect.

[Granite26]

Horizontal is different because A: It's all on one screen, and B: digging out a square allows you to move horizontally and still put stuff there, which is something you can't do with stairs.  Think about B for a minute.  If you want to go up or down stairs, that's all you can do with a space.  I'd like to see what you are thinking of as a two story room.  It's either a room with a high ceiling, or two rooms with stairs between them.  In the first case, pathfinding to the second z level is unnecessary (unless you think we shouldn't optimize for people who stay on the ground?).  In the second case, the stairs make a natural dividing point between rooms.  Even if you are building something like the old human taverns, where it's a big two story building with a hole in the middle, it's good for the pathfinding algorithm to know if it needs to use the stairs or not.  It may be 'all one room' to the human eye, but that doesn't mean you won't see speed improvements by the pathfinding algorithm thinking of it as two.  Note: pathfinding algorithm.  Just because the computer is thinking of it one way behind the scenes, doesn't mean anything.  Unless you are building a room where every square that doesn't have furniture has stairs; If you are arguing that that case is just as valid a target for optimization as any other, we'll have to agree to disagree.

I'm basing players' optimization on actually listening to what other people talk about doing.  I've got a fast enough computer that I don't need to kill cats to play the game at speed.  So, I'm making no assumptions about what other people do.  Cruise on over to the Dwarf Mode forums, see what people say... Kill cats, build doors to lock your moody dwarfs in, build bridges to block off the outside (something else I don't do), kill excess dwarves. 

The algorithm isn't 'optimized for a single shaft design'.  It's optimized for large cut out areas being connected by narrow passageways.  I'm willing to bet that the majority of forts exhibit that kind of behavior.  I also think optimization should focus on the majority of forts, because nobody is coming up with anything too bright for the general case.

[NW_Kohaku]

What about vertical hallways?  How is that not a vertical room?  Why should they be treated differently from horizontal hallways?

Also, why can't I have multi-story rooms at some future point?  Why not have a sloped room, with ramps in it?  Why not have a mezzanine with eight separate stairwells in eight corners of an octagonal balcony in a dining hall?

It makes no sense not to consider rooms with ramps, or long spiral inclines as somehow a set of unconnected tiles while anything flat is a hallway unless it has doors.  That's not the way most people build forts.  And the way that you keep mentioning, as if everyone uses drawbridges to close off sections of the forts, isn't the most popular method of building a fort - it's something people advertise because they feel it isn't done enough.

Besides which, there's no reason to build the game around the exploits people have built around the game's current status.  If you change the game's pathfinding algorithms, once again, they will change to adapt to the new situation.

You keep thinking that all single-tile chokepoints are covered in doors or stairs, but that's not the case.  You just need to make the game search for the actual chokepoints, instead of harping on this misconception that all stairs and doors are single tiles.

[Granite26]

Why are you so upset at the thought of the processor thinking of a room as something different from what you think of a room?

That's all I'm seeing.  No argument that it would behave worse for you, just that what I'm calling a room doesn't match your definition, as if what you (or I, or any other meatbag) thinks of as a room matters in the slightest for pathfinding.

Who cares if the pathfinder cuts your Escherian construction into 3-4 rooms in the.background?

I've explained why (I think) arbitrary nodes are a bad idea.

It's also naive or disingenuous to claim that blocks of stairs, lines of ramps, etc couldn't be handled as a single entity, seeing as we've already covered that case.

[NW_Kohaku]

Why are you so upset at the thought of the processor thinking of a room as something different from what you think of a room?

That's all I'm seeing.  No argument that it would behave worse for you, just that what I'm calling a room doesn't match your definition, as if what you (or I, or any other meatbag) thinks of as a room matters in the slightest for pathfinding.

Who cares if the pathfinder cuts your Escherian construction into 3-4 rooms in the.background?

I've explained why (I think) arbitrary nodes are a bad idea.

It's also naive or disingenuous to claim that blocks of stairs, lines of ramps, etc couldn't be handled as a single entity, seeing as we've already covered that case.

The increasingly personal nature of your statements aside, you actually haven't covered any of those things as a single entity, and have been specifically arguing against handling ramps and blocks of stairs as a single entity. 

You have been arguing that we should be hitting players who do not use stairs sparingly and doors as means of designating traffic flow with lower FPS on purpose, as a means of forcing players to make certain types of fort layouts, simply because you are convinced your particular way of designing forts is popular because you once saw someone agree with you.

I also don't see any reason why arbitrary node definition, or at least, a different style of manual definition or interpretation are infeasable.