Do it like this:
Find all walkable tiles, cluster into nodes (we'll treat workshops differently in a moment).
Then find all swim-able tiles, cluster into additional nodes with the "swim only" modifier (tiles that are in both, which I think is 3/7, are their own node).
(Do the same for magma).
Then find all remaining empty tiles, cluster into nodes, with the note "fly only."
Connect all neighboring nodes, the node connections will also carry the walk/fly/swim flags.
Done.
Here's something I've been thinking about, however - if you are drawing a map where you only make local updates, not global ones, odds are, you're going to start with a wide open field and some caverns and a functionally wide open HFS. You can basically start by just drawing a big grid over the land surface, and cutting up "rooms" every 12x12 set of tiles or something. Basically, everything starts out connected (excepting rivers or cliffs), so it should start out as a big grid with some unconnected grids down in the caverns. Obviously, you have to make separate rooms when you cannot path from one corner of these starting "rooms" to another, and may have to split things up if there are two different z-levels stacked over one another on the surface somehow or in caverns, but basically, it should look like a grid layed out over a varied set of slopes with some inaccessable tiles here and there because of trees or cavern walls.
Then, the instant you start digging into the earth, you basically start modifying or creating new rooms. If we go with doors creating their own nodes, and segregating rooms, we might have a situation where there is an entrance way, then the door nodes, then the hallway behind it, with all the little rooms or warehouses sprayed off of it.
If you just go by trying to make up 12x12x12 cubes, and looking for what paths are blocked (while having to make doors and drawbridges and floodgates and the like their own nodes, since they can be locked), then you'd wind up naturally adding bits and pieces into the simple starting map gradually. (Maybe, you'd need to have some sort of sanity check mop-up, maybe at the new year's, with all those other checks and calculations that make the whole thing take a long time processing, anyway, that another second checking to optimize the connection map wouldn't really be noticed.)
The map would probably wind up looking similar to Granite26's idea, with most of the inside-the-fort stuff being determined by doors and based upon z-levels, but it would have the capacity to react to having water or multi-z-level rooms (like if we eventually get proper flying unit pathing).
We just need to have a stored connectivity map that works in those area-nodes levels at that point, with an assumption we can A* to anything "local" within those nodes. Simply having a current location in the same node as a destination inherently implies not only connectivity, but a very short and probably direct pathfinding call. Then we can throw away the current version of the connectivity map, which makes the hierarchical nodal pathfinding structure capable of competing head-to-head with the current A* connectivity map in terms of memory - only the fact that you will need duplicate layers of connectivity maps for things like "flying only" or "water-based movement possible" or "swim only" really drags it down.
see my post here
http://www.bay12forums.com/smf/index.php?topic=76278.msg2091518#msg2091518.
I would like that everyone stop posting their idea on how to do pathfinding cause THIS is the best method (see navigation mesh).
Instead try to point out:
-what we may have forget to take in consideration (like workshops or the need to represent all the tiles, even the unwalkable)
-how to easily implement one part of this method, or improving the current idea of implementation.(like using 3d shape instead of 2d, using a flag system for easily representing the different types of nodes)
This is only like this we'll have a serious suggestion that Toady may try to read.
I don't have a good english , so I would want that someone who understand the method post a summary each time someone post a potential improvement.
Here is the first summary:
-We represent the map with rectangular cuboid of tile of the same type (walkable/swimable/digable/flyable/magma/workshops)
-the map can now be represented as a graph where a node is a cuboid , and 2 nodes are connected if the cuboids they represent are touching.
-we use A* on this graph, this will give us a "basic" path, we'll know through what cuboid the path come, not what tiles.
-We have to use the funnel algorithm to knowing the exact path (
http://digestingduck.blogspot.com/2010/03/simple-stupid-funnel-algorithm.html).
-At this point we have a set of points leading to destination , the dwarf only need to go in straight line between each points (There is no internal pathfinding, rectangular cuboid are CONVEX, the shortest path between 2 points is without any calculation the straight line)
-A straight line is defined as going diagonal (starting from starting point) until reaching one of the two coordonates of the destination then going horizontal or vertical.
-Each time a change is done on the map (digging, closing a door, building a wall etc...), we have to (slightly) change our graph.
-A function than can do this only need to be able to:
-add a node
-merge 2 nodes (if 2 cuboids have a common side)
-split a node (when we build a wall for example)
-changing the type of a node(digable->walkable)
With this method the entire map could be represented whith only few hundreds nodes instead of millions with the current method. And the more important thing, if we only look at the fortress (not the entire map), I think almost all pathfinding occur here, a friendly designed fortress could be represented with a dozen of nodes, and with only a depth of 4 nodes: the surface (surroundings by fortification) , the stairs , the main hall , all the other rooms linked to the main hall.
And finding a path in this type of graph is very fast.
) which is more or less O(1). If it hit the wall it would switch to A* and try to find it's "way in".
What you've posted is basically a repeat of what others have said, except in a few cases that don't make much sense, like the funnel algorithm.