Print

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

[Idles]

I'd like to ask Toady, or anyone with knowledge from fiddling, some questions about how DF implements features of the game (mostly data structure questions). The reason for this is that I'm toying with a basic game engine in my spare time, and I'd like to see how Toady's methods differ from my approach. And let me assure you, Toady, I'm not attempting to recreate DF by myself, and even attempting to would be an exercise in sheer hubris.

Toady, I totally understand if you'd rather not discuss some of the details, or don't have time to, but I'm pretty sure all of the questions could be answered with either a  yes/no or a short explanation. So I'll endeavor to make each question as easy to answer as possible. Also, if the details of a question could be answered by my perusal of the Kobold Quest code (which I haven't delved into), I would graciously accept that answer as well.

So here's the list of numbered questions:
About map blocks:
1. Do they have a fixed-size (in x,y,z dimensions, not memory)?
2. Contain a 2 (3?) dimensional array of map tile data structures?
3a. Store meta-information about the tiles it contains?
3b. Like the presence of water in at least one of the tiles?  
3c. Or the presence of at least one unit/item?
3d. Or the presence of any walkable tiles?
4. If the answer to 3a is no, how do dwarves go about finding things like drinkable water (assuming they don't just simply scan over every single tile in the map)?

About path finding:
5. Which basic algorithm does it implement, A*?
6. Does it operate on the block-level as well as the tile-level?
7. How is a path that spans Z-levels handled? Does it first look for accessible stairs, then connect the endpoints?

About OpenGL:
8. DF uses OpenGL, right?
9. Renders texture-mapped quads?

[ June 05, 2008: Message edited by: Idles ]

[Toady One]

1.  Yeah, 16x16x1, though when wander around it'll load a 3x3 grid of those at a time.

2.  The blocks contain a few data fields in arrays.

3a-d, 4.  All sorts of stuff like that, yeah, though some parts have more optimizations than others.

5.  Yeah, with the street distance/Manhattan heuristic pushed up so that it's just below the minimum traffic weights, with binary heaps for the node lists.  No doubt it's a crappy implementation.

6.  Nope.  The map is dynamic, and I haven't seen a practical way to do this (ie without burning memory or killing the CPU when the map is altered).  There's going to be stuff to do here, but I haven't done anything yet.

7.  It just runs A* between the goal and destination.  Ramps, stairs, water and flight are just ways to move from tile to tile.  It won't try an A* path if the connected components don't match up, which is where some problems arise (as with flight-modded dwarves in fort mode and so on).  Regular flying creatures use something more like short-range flood fills to combat this, if I remember, but they can't use arbitrary A* if they don't have a component check or else the processor will die on pathing failures.

8, 9.  Yeah.

[Idles]

Thanks for the detailed response.  And your A* implementation sounds like game-standard, rather than crappy.  If there are big improvements to be made with the path finding, it probably won't be made by increasing the efficiency of your A* algorithm.

Oh, more questions:
Path finding:
10. Does each tile have something like an assigned integer value representing a group of tiles which are connected?
11. How do you initially assign those values? Multiple flood-fills?

[ June 06, 2008: Message edited by: Idles ]