Print

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

[JSilva]

I'm curious about the algorithms and data structures used in the game, and I was wondering if Toady wouldn't matter giving us some idea of what he uses.

 What kind of concerns do you have with computational complexity (Big-O, etc.) when choosing data structures for using in DF?  E.g. the classic "O(n) for plain linked lists vs. O(log n) for balanced binary trees".

 In Fortress mode, the size of the map and the amount of hauling had me thinking about how do you do represent the map for pathfinding purposes.  Do you consider every square when doing pathfinding or do you use a graph to represent the connectivity of "areas" (rooms, corridors, etc.)?

[axus]

He said something about not liking to talk about programming here:
http://www.bay12games.com/cgi-local/ultimatebb.cgi?ubb=get_topic&f=5&t=000120

I'm pretty curious myself!

[Disruptive Idiot]

The other day Toady mentioned on IRC that he once took CS classes, and he found them utterly boring, so let's not bring up Big O or specific programming practices, I would think Toady is a very pragmatic programmer who just does it for fun, not efficiency or anything.

That said, I'd think that he uses the A* algorithm for pathfinding with a very simple heuristic.

[Toady One]

Yeah, I just use something that I think is A*ish for path finding (I don't know the specs for A*, but it seems like what I'm doing last I read anything about it) with a Z-buffering type clear routine so that I only have to reset the buffer very infrequently.

There are lots of lookups for the creatures and so on, so I store them in order by id number in a vector I can binary search and traverse easily.  Other things that aren't subject to searches but get created/deleted frequently get placed in linked lists, or lazily in vectors.  I only use trees in a few places, like the channels, and there are probably other places where they should be used, but I'm not in a rush to change anything.