Print

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

[NW_Kohaku]

I like optimizing for rooms.  Every area surrounded by doors is a room, node map concentrates on room connectivity, pathfinding is just to the next room.  (each room contains traverse costs). 
Recalc your zones when digging, but only the affected ones.  Same with new doors

Doesn't this have the same problem as using stairs?

Wouldn't that depend a lot on how many doors you have in your fortress?

I know that early on, my industrial areas are basically just a wide open soil layer that I'll later repurpose into a major stockpile when I actually get my industrial sectors dug out.  I don't use doors then, since I have more important things to work on.

Later on, I tend to throw doors over everything.  Often, doors two layers thick, just in case one gets blocked open.

Plus I know I'm not the only one who does odd playstyles, so there could be all sorts of odd ways people use or don't use doors.

What if people don't use doors, they use lots and lots of stairs to designate rooms?

Using something like stairs and doors to judge player intent requires that you assume what a player's intent for those objects were whenever you see them use doors and stairs.  That's an assumption that's going to fail at some point.

[Granite26]

Huh?

There's no player intent involved.  Doors just leverage enclosed spaces with entryways no more than 2 spaces wide.  It's a way to define areas that are minimally connected.

Even if all you do is cut out pathfinding through the bedrooms, you'll see an improvement.

Find some way to not look outside or in caverns unless you know you need to go there and it's a sevond boost. 

Note that this doesn't assume anything.  No doors just means that you've got one big room the same as now with a little bit of extra overhead when you dig.(i.e. check the 'room' code of the 26 surrounding squares) or build a new door.

[NW_Kohaku]

What about something like this?

= is a wall
+ is a door

+=++=++=++=++=++=+

Along one side of a wall.

Or using the door bug to make a string of doors that make up an entire wall.

In order to say "don't check the bedrooms", you have to figure out which ones are the bedrooms, and which ones are the hallways... and doors don't necessarily help you figure that part out.

By saying that players should adapt their door-placing decisions to manipulate pathfinding, you're suddenly talking about doing something fairly unusual in placing furniture to designate an inent in pathfinding, wheras we already have a "traffic zone" menu that is explicitly for pathfinding control.  Wouldn't a reworking of traffic zones to have "This is a hallway" be a better way to show intent?  (And isn't that what the high-traffic designation is already supposed to do, if it is not strictly as efficient at it?)

[Granite26]

I think you are making this more complicated than intended.  The doors aren't magical or anything.

  Just take the first square in the upper left of the surface.  Path to everywhere you can without going through a door.  Add any doors to the list of connections for that zone.  That is zone A.  Now for each door, check the first open space on the other side.  If that doesn't have a zone, path to all available spaces, adding doors as connections.  That is zone B.

Thats how you generate your zones.  After it is complete, you only need to change when digging or building doors, or constructing path-blocking items.

The reason bedrooms get cut off is that they only have one connection.

[NW_Kohaku]

Well, like I said, you have to plan for how it handles the most complicated, worst-case scenario.  That means that you have to make it as complicated as possible, and see how it handles.

If all we are doing is looking for narrow chokepoints, then you don't need a door at all.  (And what if you have a large bunkroom bedroom with hallways going through it?)

You just need a way to recognize narrow chokepoints, and then create "nodes" out of the abstract areas between each chokepoint, and to possibly also recognize during the connectivity map updates that one specific node has not been altered.  In other words, it's the node-based pathfinding maps suggestion.

[Granite26]

 You are making the algorithm out to be more complicated, not throwing too complicated of a case at the algorithm.

Sure, if you build two long S paths with a shortcut going back and forth, you can game the system to make it choose a longer path.  But that takes effort to do anything non-trivial

The reason bedrooms are a good example is because dwarves complain if they don't have enclosed rooms.  They also complain when people march through their bedrooms.  That means, in a well designed fort, there are guaranteed  opportunities for this to pay off.

The reason doors are good is that they don't occur in nature, it's free to check(you know where one is and you know when you add one) and it's subject to player optimization.  Checking for choke points in a cavern is expensive.

It's guaranteed to give you AN answer, and will most often give you the best answer.

If you think multiple doors leading to non optimal solutions are a danger, just collapse any two rooms with multiple connect points into a single zone.

[NW_Kohaku]

So you are seriously saying only bedrooms in these calculations? What about the mass bunking systems?  To simply say that anyone who is using that system is playing the game wrong seems a little on the odd side.  What about workshops that are only used by one specific worker (and the haulers), and are in their own specific room.

Would collapsing rooms with multiple connection points into a single area really less costly than checking for chokepoints? 

What about the large numbers of creatures roaming the caverns?  Those have plenty of chokepoints that can be optimized.

[Granite26]

A zone/room is any contiguous area containing all points that can be pathed to without using a door.  Bedrooms are a useful example, because in order to make dwarves happiest, they should be enclosed and nothing should be pathing through them.  That is, they are a leaf on the connectivity tree(as designed, and without the system knowing thqt its a bedroom or storeroom or whatever.)  I'm using the existance of these leaves to make the claim 'this method will pay for itself.'  Specifically, the node maintainance costs are recouped by the A* never pathing through leaves (bedrooms, or any other dead end)

My justification for possibly collapsing:  imagine a large (50x50) open area with a walled of area 30x30 in the middle, with doors in all faces.  In this instance, a dwarf passing from one side to the other may path around the outside rather than take the shortest path through the center.  A path is still found, but it might be crappy.  (there are a number of these flaws, all solvable, but not necessarily better than straight A*.  i.e. when you hit a door on the inner path, go back to the nodes map)

The reason I like doors is that it's a non-greedy solution that's easy to impliment.  Finding zones through chokepoints would prolly be better, but there's a LOT of special cases to think about, and I'm no longer willing to claim the overhead is worth it. (by non-greedy, I mean that when it doubt, just use A* and huge zones.)

A* is really good at straight paths, it's the dead ends that kill it.  Teach it to ignore deadends and you get a boost.

[Artanis00]

So, this article on memristors and maze solving came across my feeds a few days ago. The paper it reports on is a surprisingly easy read (and the pictures at the end are enlightening), so consider reading it.

Basically, some guys built an array of memristors, overlaid a maze (the walls broke connections between the adjacent memristors), chose start and end points and ran a current through them.

Memristors hold a memory of the current that flows over them. Current in one direction increases the resistance, current in the other direction reduces it. If you start from a clear array (minimum resistance) then the path will be marked by a series of memristors with high resistance compared to no change for the memristors not on the path.

In scenarios in which a maze has multiple solutions, the array finds all viable paths with the shortest marked with the highest resistance, the longest with the lowest resistance (but not 0, which is no path), and other paths in between depending on length.

This process can be modeled in software, and as each memristor performs a single, identical operation, this can be easily parallelized.

You can probably imagine how this might be useful in DF:

• Each pathable tile in the DF map is a node on the memristor array. Filled tiles (walls, buildings, locked doors, etc.) do not have a node, and no connections are made through it.
• An operation that creates an pathable tile adds a new node (mining, unlocking a door, draining an pond, building stairs, lowering/extending a bridge, etc., etc.), with the appropriate neighbor connections
• The reverse removes a node (building a wall, locking a door, raising a bridge, etc., etc.).

The maze constructed in the paper is a straight grid, but DF connects tiles that share a corner, so rather than the four memristors per node in the paper, in DF this would need to be eight.

From there, when a units wants a path, it uses its current position as the start point, and the desired location as end, and the memristor algorithm does it's thing and now you have every path to the destination, sortable by length. To fully take advantage of this, such an algorithm should be multi-threaded (not just it's own thread, but possibly multi-threaded itself), but this is a long-desired enhancement to DF in general.

The current system's traffic designation system can still be implemented: once you have a list of paths (which are themselves lists of tiles), the traffic designations on those tiles can be taken into account (so, sort by length, then by cost; or cost, then length, whichever produces better results).

As far as I can tell, it shouldn't be a problem to make this 3D: stairs and ramps would simply connect to the appropriate node in an adjacent level. This method should be highly expandable in terms of features: 4D connections should work the same way as stairs and ramps, so those "magic world" suggestions, gateways into them could be enabled by simply making another connection between a node in the 'real' world and the 'magic' world, and shortcuts in a single world would merely be an additional connection between the two end points of the shortcut, which may or may not have it's own memristor nodes in it (depending on how long it is to be).

[Sunken]

You're missing a couple of crucial things.
It's not the memristor function that solves the maze. Even with ordinary resistors, the current would find the best path(s). All the memristors do is store that path so that it's easily readable.
And there's the rub. While the work the memristors do is indeed simple (it's a sort of integral or sum), that's neither here nor there. What's needed is to solve for the current through the maze. Nature, being massively parallel - here basically every valence electron is doing computation for you - does it easily. Doing it in software would be hellish, as you'll appreciate if you've ever tried to figure the current through a complex parallel-and-serial network of electronic components.

[Sunken]

...that said, this does have potential in hardware. Perhaps specialized maze-solving hardware will be available; fast 4-to-4, 8-to-8, 10-to-10 or 26-to-26 grids with configurable connection costs rated at "solutions per second"... that would probably end our pathfinding troubles once and for all!

[Draco18s]

You're missing a couple of crucial things.
It's not the memristor function that solves the maze. Even with ordinary resistors, the current would find the best path(s). All the memristors do is store that path so that it's easily readable.
And there's the rub. While the work the memristors do is indeed simple (it's a sort of integral or sum), that's neither here nor there. What's needed is to solve for the current through the maze. Nature, being massively parallel - here basically every valence electron is doing computation for you - does it easily. Doing it in software would be hellish, as you'll appreciate if you've ever tried to figure the current through a complex parallel-and-serial network of electronic components.

[mszegedy]

I hate you. xkcd is drawn by a lazy asshole. It is not a good comic.

[Artanis00]

...that said, this does have potential in hardware. Perhaps specialized maze-solving hardware will be available; fast 4-to-4, 8-to-8, 10-to-10 or 26-to-26 grids with configurable connection costs rated at "solutions per second"... that would probably end our pathfinding troubles once and for all!

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.

I hate you. xkcd is drawn by a lazy asshole. It is not a good comic.

You're in luck! There's a website for you and people that think like you: http://xkcdsucks.blogspot.com/

(Actually, I drop by there too; it's nifty to get another take on things like this.)

[Felblood]

Carping about highly idiosyncratic play-styles aside, room based nodes have a lot of advantages and very few drawbacks (such as requiring us to all own coprocessors that haven't been invented yet).

They provide easy hooks for workshop-to-room relationships that players can leverage intuitively. Currently, a workshop works best with a built in stockpile, and stairs to matching stockpiles above an below, but checking for items within the path node first would make for the same efficiency without the bizarre architecture. (If you don't currently build optimal workshops, that would make it easier to learn, if you ever wanted to.)

Treating hatches and floodgates as doors for purposes of recalculation would provide for three dimensional separations and a level of water system awareness.

I'm already placing locked doors over unused mine  shafts, to prevent them from bogging down pathing, this would allow me to leave those doors unlocked. (I don't remember my numbers, but I did test that this had an effect on complex exploratory tunnels near population centers.)

Even if the system only recognized player designated areas, like burrows, zones and rooms, the potential gains would be respectable. Even just cataloging "dead end" rooms, with only one exit, would be a considerable boon.

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.


That said, like so much else, it isn't perfect.

The largest drawback that I see is actually the four way intersection. Some forts place a door at the corner where four walls meet, connecting four nodes with a singe door. To compensate, the code simply needs to allow for this, for example, treating the door themselves as nodes.

Code: [Select]

...O...
...O...
...O...
OOO+OOO
...O...
...O...
...O...

Additionally, treating stairs as nodes has some merit, but many forts use large blocks of stairs, which would lead to tracking an awful lot of stairs and possible memory problems.