Bay 12 Games Forum

Hey Reasonableman, could you use your mod powers to dig out the chasm for us, when no one's signed on? I guess someone thought it was supposed to be a brook and flooded it with water--but the plan is it's going to be a map-bottom depth chasm. So I drained the water and it's ready for digging--which would take a very long time by hand.

This list is not 8, you even list how some of the flags combine to make others (amphibious would just have both walker and swimmer set for example) seems excessive to record them as well.

....

As we only have one critter larger than a tile I'd suggest just doing the current pathfinding for it as needed, if we come up with a clever system great but otherwise just ignore it for now.

About your first point: if you read the HAA* paper, the important thing to take away from it is that each creature is able to move over only a part of the map. A "movement type", as I defined it, is a set of rules from which you can figure out whether or not a creature can move through a tile (given that you have all the information that DF currently stores about tiles). By using these "movement types", you construct the abstract "high level" path graph, where the annotations of edges include information defining which one (and only one) of the "movement types" is valid for that edge. That information could take the form of a byte which stores flags (1 flag for each of the 8 movement types I defined).

For the low-level tile-map (which already exists inside DF), you obviously wouldn't store that flag annotation byte, since you would be duplicating information already present in the tile map. Instead, you'd just rely on the information that DF already provides, and have a function that takes a tile and spits out a byte (or word or whatever) with the flags for which "movement types" are valid for that tile.

About your second point: The HAA* paper already has a clearly defined method for handling multiple tile creatures. Perhaps you should read it? That said, we could always special-case them, by just letting them use regular old A* without any enhancements. However, since the point of this project is to improve the current pathfinder, we might as well use the HAA* method for multiple-tile creatures.

About dragons, and other creatures that don't clearly fall into a single "movement type": we can just let them use regular A*, because having to store an abstract path graph for each possible permutation of tiles that a creature can move through would quickly eat up all of our memory. My list of movement types was an attempt to shoehorn all the common creatures into as few categories as possible.

Here's a link to the HAA* website with accompanying paper that I'm referring to: here.

Just want to chime in that this is awesome. Whoever's in charge should make a post in DF General discussion with a link to this thread--the other visualizers all have their own threads there.

Also, whoever's in charge should send a non-threatening email to Toady to let him know that this kind of graphics is quite possible, and already works(!!!), with DF. Also let him know that since this is BSD licensed, he does not have to worry at all about any copyright issues. It might convince him to add some helper functions to the main executable so this graphics library could be used as part of an official future release. He seems willing enough to accept graphics help (see DF 40D##).

Here is a very, very helpful resource that outlines a pathfinding system:

http://harablog.wordpress.com/2009/01/29/clearance-based-pathfinding/
http://harablog.wordpress.com/2009/02/05/hierarchical-clearance-based-pathfinding/

I was planning to implement his system in a personal project, but alas this semester has a heavy workload. He has done performance analysis on his implementation of the system, and shows it to be much more efficient than straight up A* for long path-lengths. One of the big elements this paper does not cover is the method of updating the pathfinding graph based on changes to the game world, but it looks like a relatively easy problem to solve. The code also does not address extending this 2D system to 3D, but that problem is also not terribly difficult to solve.

The system handles hierarchical pathfinding (finding paths at a high level and low level), multi-tile creatures, and multiple travel domains (walking, swimming, amphibious, flying, etc.). Connected components checking (currently used by DF) can be done relatively quickly by inserting the path start and end nodes into the abstract graph and finding an abstract path between them. This new form of CC checking would even work for flying monsters, unlike the current code!

Definitely worth a read as a starting point for designing the system.

I liked the talk about the Eternal Suggestions. What additions or changes to the game have you considered making sometime soon in order to address the suggestions in the Eternal Suggestion poll (specifically, improved mechanics, graphics support, and improved hauling)?

How about next version with non-generic statues

... good point. Dwarves will make statues that resemble a ton of different things. We'll probably just have to settle with a couple different generic statue models that don't reflect the subject matter of the statue.

well i dont have any custom stuffs, just downloaded 40D13 and same error mesasge, guess it still needs to be fixed.

Sounds like it's a computer-specific bug, because myself, as well as others running standard 40D13 have used the program without that particular problem.

Oh god I can't wait. Little dwarven bedrooms and legendary dining halls, here we come! Ooh ooh, will 3D models for supports be included? And can we maybe make smoothed single tiles with no adjacent walls look like pillars?