Dwarf Fortress, a video game was built by Tarn Adams - hold your breathe, he single handedly developed and maintained the code for 15 plus!
This is an epitome of modern economy where one brilliant man develops something spectacular while most of humanity is content being "users" and not learn anything from his brilliance. We indeed like in Huxley's Brave New World where Wall-E's are rare.
Interview with Tarn Adams here:
Q: What are the challenges in developing a single project for so long? Do you think this is easier to do by yourself? That is, because you wrote every line, is it easier to maintain and change?
A: It’s easy to forget stuff! Searching for ‘;’, which is a loose method but close enough, we’re up to 711,000 lines, so it’s just not possible to keep it all in my head now. I try to name my variables and objects consistently and memorably, and I leave enough comments around to remind myself of what’s going on when I arrive at a spot of code. Sometimes it takes several searches to find the exact thread I’m trying to tug on when I go and revisit some piece of the game I haven’t touched for a decade, which happens quite a bit. I’d say most changes are focused only on certain parts of the game, so there is kind of an active molten core that I have a much better working knowledge of. There are a few really crusty bits that I haven’t looked at since before the first release in 2006.
Regarding the relative ease of doing things by myself, certainly for me, who has no experience working on a large multi-person project, this is the way to go! People obviously get good at doing it the other way, for example over in the AAA games context, and clearly multiple engineers are needed over there to get things done on time. I’d be hesitant to say I can go in and change stuff faster than they can, necessarily, since I haven’t worked in that context before, but it’s true that I don’t have any team-oriented or bureaucratic hurdles to jump through when I want to make an alteration. I can just go do it. But I also have to do it alone.
[---]
Q: I’ve seen other games similar to DF die on their pathfinding algorithms.What do you use and how do you keep it efficient?
A: Yeah, the base algorithm is only part of it. We use A*, which is fast of course, but it’s not good enough by itself. We can’t take advantage of some of the innovations on that (e.g. jump point) since our map changes so much. Generally, people have used approaches that add various larger structures on top of the map to cut corners, and because of the changing map, these just take too long to maintain, or are otherwise a hassle. So our approach has been to just keep track of connected components reachable by walking. These are pretty easy to update even when the map changes quickly, though it does involve some flood-filling. For instance, if water cuts the fortress in half, it needs to flood out from one side and update a whole half of the fortress to a new index, but once that’s done, it’s good, generally. Then that allows us to cut almost all failed A* calls from the game—our agents just need to query component numbers, and if the component numbers are the same, they know the call will succeed.
It’s fast to maintain, but the downside is that the component indices are maintained for walking only. This means that flying creatures, for instance, don’t have global pathfinding intelligence that’s any different from a walker. In combat and a few other situations, we use short-range flood fills with their actual logic to give them some advantages though. But it’s not ideal for them.
I’m not sure we’ll attempt other structures here to make it work any better. For our map sizes, they’ve all failed, including some outside attempts. Of course, it might be possible with a really concerted effort, and I’ve seen other games that have managed, for instance, some rectangular overlays and so forth that seem promising, but I’m not sure how volatile or large their maps were.
The most simple idea would just be something like adding a new index for fliers, but that’s a large memory and speed hit, since we’d need to maintain two indices at once, and one is bad enough. More specific overlays can track their pathing properties (and then you path through the overlays instead of the tiles), but they are hard and slow to maintain as the map changes. There are various other ideas floating around, like tracking stairs, or doing some limited path caching, and there are probably some gains to be made there. We are certainly at the edge of what we can currently support in terms of agents and map complexity, so something’ll have to give if we want to get more out of it.
Q: On that note, you’re simulating a lot of things all at once—how do you manage so many so many actors asynchronously (or do you)?
A: If we’re talking about asynchronous as in multithreading, then no, we don’t do any of that, aside from the graphical display itself. There’s a lot of promise here, even with microthreading, which the community has helped me out with, but I haven’t had time to dive into. I don’t have any experience and it’s a bug-prone thing.
No comments:
Post a Comment