Print

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

[Blue_Dwarf]

I'm thinking of a possible solution to the FPS death. Perhaps the A* pathfinding could be assisted by a waypoint network with pre-caculated pathfinding.

Let's say you place waypoints A and B. The game finds the optimal path between the two, or the player forces a path he wants. When a dwarf gets a job near A, he only needs to A* to the waypoint A, which will send him to the fixed path to B.

Although it kinda seems too simple to not have a catch.

[Bumber]

You can already use traffic designations to this effect. The only issue is outsiders ignore your traffic designations (because it'd be too exploitable.)

[Blue_Dwarf]

If I'm not mistaken, even with traffic designations dwarves have to path every step of the way. I don't know if that makes a huge difference though.

[Dirst]

If I remember correctly, the game does a version of this when there are choke points, for example a one-tile wide hallway.  Somehow the algorithm learns the choke point the first time it paths thru it, and treats it like one high-cost step in subsequent pathing... at least until a map tile changes in some way forcing a recalculation.

Designated waypoints could have similar "known best paths" between them (these are called skyline paths for obscure mathy reasons), that might help out the A* pathing.  Just needs to recognize if it's backtracking from the distant waypoint, which might be nontrivial.

[omega_dwarf]

You can already use traffic designations to this effect.

Yeah, that's still not efficient. They're still pathing though every tile individually. What the OP is suggesting is hierarchical pathfinding, in which there's an abstracted graph of sparsely-placed points connected by possible paths. The exact path is figured out after an approximate feasible route is determined (jumping from point to point), and can even be done in pieces later on from the initial decision - much as people often plan their road trips. It's nice; it's smoother; and it's more efficient.

That may not sound straightforward or efficient, but it is compared to simple A*, even with traffic designations - in which the dwarf has no idea what's ahead during each step of his path planning, but instead guesses blindly in all directions, guided only by a constantly-recalculating distance estimate and the obstacles he's bumped into around him. (Not literally, but during the step in which he decides his path.)

That being said, it sounds like Toady has done some things with "swamps" (dead-ends) and choke points, so I don't know the details of what's already implemented. It sounds as if, if the poster up there is correct, there is some precalculation going on, so it might already be hierarchical in some nature - idk.

[Bumber]

You can already use traffic designations to this effect.

Yeah, that's still not efficient. They're still pathing though every tile individually. What the OP is suggesting is hierarchical pathfinding, in which there's an abstracted graph of sparsely-placed points connected by possible paths. The exact path is figured out after an approximate feasible route is determined (jumping from point to point), and can even be done in pieces later on from the initial decision - much as people often plan their road trips. It's nice; it's smoother; and it's more efficient...

Here's what we have on how it currently works:

TA: The dwarves themselves mostly move around with A*, with the regular old street-distance heuristic. The tricky part is that it can't really call A* if they don't know they can get there in advance, or it'll end up flooding the map and killing the processor.

Sometimes in commercial projects the developers do a bit of cheating, and predefine travel paths.

TA: Yeah, that's the hard part. We can't really predefine areas beyond very basic notions because fluids can zip by and block them off, or they can mine a floor out. All it does now, and this isn't ideal, is keep connected component numbers. So if a dwarf is standing in "2", they know they can't get to "3" and don't bother trying. However, they assume they can get to any other "2", and will A* those paths. There are still a few failures, but it's fixable.

There's a price to pay for that though, on a few levels. First, it's a pain to maintain. If a fluid occupies a square, it has to update. If a fluid flows through a passageway and cuts it in half, it has to reindex one or both sides. There are other ways to think about handling it, like keeping track of some sort of rectangles or something, and pathing on those, but the memory cost is too great.

The memory cost here is large, and it's also a speed burden. There are probably a ton of better ways to do it, it's just a very hard problem.

Which amounts to using A* and keeping track of connected zones. The difficulty, I think, is having the opportunity to use any such pre-computed paths, possible difficulty with z-levels, and invalidation by map changes. It's no good for fetching goods out in open spaces. Areas with too many twists and turns causes too many waypoints, which ruins your efficiency. You might see an improvement, you might not.

With the traffic designations we have you can decrease the burden on the A* algorithm without additional memory overhead.

[omega_dwarf]

That's good information, that post.

Traffic designations definitely do help A* run quicker, but it's a fairly elementary improvement. There are many, many others that have been researched and implemented  elsewhere. (One of the coolest, imo, is jump-point-search.) A hierarchical system will almost always be faster than straight A* in the pathfinding process, but, as described above, it takes a performance hit to calculate the hierarchy. That's why relatively small units of hierarchy are beneficial (not large areas that contain lots of potential to change and are expensive to recalculate. That's the same theory that makes chunks relatively small in voxel engines.) Aka, many waypoints. The plus is that, even with many waypoints, it's still much, much faster to use the hierarchy than straight A*. Using a low-resolution path as a guide allows the subsequent A* searches to expand into much smaller radii (meaning much, much smaller areas) than if it was done in a single A* search.

So that's why I'm a proponent of adding a hierarchical system to DF, basically. Liquids and trees complicate things, but there are ways to get around that. (Like postponing recalculation if nobody needs to calculate that path.)

[milo christiansen]

A* has three benefits:

1) It's generic.
2) Its fairly efficient.
3) It's easy to implement.

Aside from those things A* is not all that great, plus #2 only applies when compared to certain algorithms, other are far better in this area.

The problem is, from what I've seen, Toady isn't all that great of a programmer, and strongly disinclined to learn new things when the old one works. A* is currently a real drag on FPS, even with crutches like the connections cache. The path finder needs to be replaced entire with something more advanced, but fat chance of it ever happening.

[omega_dwarf]

The problem is, from what I've seen, Toady isn't all that great of a programmer, and strongly disinclined to learn new things when the old one works.

I don't think that's entirely the case, although I've only been around since DF2012 days. He is, understandably, more interested in adding new features than fixing old ones, but - and he has a point here - it would also be pointless to rewrite one feature before everything it will eventually have to depend on is done. Pathfinding, for instance, might change drastically once he introduces multi-tile creatures and moving fortress parts - which he has indicated he will. Why rewrite with a totally new algorithm if it would have to be rewritten again down the line? It would slow development time in an already almost endlessly in-alpha game. He's also managing a pretty huge code base, and to my understanding, he's doing it by himself. Not an easy task, and the lack of a team of programmers (unless you count the enthusiasts tracking down glitches) also vastly slows development compared to other indie games out there which have teams working on them.

I think in the beginning, he was definitely more focused on just banging something out than doing it perfectly. Now he's focused on doing whatever he does the right way, which takes time; he's learned, or else the project has matured.

So maybe he's not a god among programmers (he would literally have to be superman to make this development cycle go appreciably faster by himself), but he's not a bad one either. He's working slowly and methodically, doing things in a logical order that doesn't always work out for the players. He understands what needs to be done, and the only real problem is his lack of a team, which creates gaps between work on most features, which means he has to re-learn how he did them, etc., which all takes frustrating amounts of time.

(I've been programming and optimizing a voxel engine for two years [admittedly not nearly full-time] and it still only has a little more than the basic features of Minecraft, and less in some areas. Although of course much is planned, it will take me ages to complete by myself in this manner. So it's possible I just sympathize with Toady, but this is how I see it. I can't really criticize him until I've actually seen him work, seen the source code, etc.)

Anyway, sorry for the long post I just like talking about programming.

[milo christiansen]

Anyway, sorry for the long post I just like talking about programming.

Talk about programming? Is there anything else to talk about? :p

I based my opinion on looking at how things are designed as seen by DFHack, lots of data structures are poorly designed and/or interact in strange ways. DF desperately needs some rewriting in some areas... That said some features are (from what I can tell) fairly well done. I guess I just am of the opinion that if something is not quite right you rewrite it until it is (and you'r right, he probably wouldn't have as much done that way... still.).

Anyway, enough derails.

[omega_dwarf]

Ah, you've seen it through DFHack. That's one bottomless pit of programming that I have never ventured into