Print

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

[tylor]

I remember doing quasi-threaded pathfinding in Flash. Game is called Garden Raider, and mobs there are moving using A*. If some mob wants a path, it addstask in queue, and wait. Then each frame some pathes are calculated for some limited time. That way sometimes mobs where standing there doing nothing, but that's better than lags, I think.

I think same aaproach could work for DF too...

[immibis]

Sure, if the main thread has nothing to do for a while. But I don't see why not to run it in a (or multiple) separate thread/s too, especially on multi-core machines.

[Impaler[WrG]]

I've shoot down multi-threading so many times in this thread but certain people just will not drop it, it's starting to get very very old.  I'd also like to point out on a more basic level that "doing stuff when DF is paused" should never be something to build/plan around, not only for the anticipation problem that Hand points out, but for the simple fact that its a terrible idea to force that much pausing in the UI and I consider it a flaw that should be fixed.

tylor:  I already have something like that I call it 'interrupt-able' A*.  Each search and all of its nodes remain in memory until some kind of completion is reached (a full path or failure) only then are resources freed.  The actual node expansion loop is controllable, I can tell it to run for some number of expansions or until completion.  At any time I can query the search to get back the best partial-path found so far.

But I still need work out having an agent that started moving on that partial path smoothly transition to the final one if it turns out that the initial path was flawed and the agent was sent in the wrong direction, most likely I'd just request another path from scratch.

For those of you not in the know, the overall effect is simply to 'smooth' that 'hang' that occurs when a larger number of agents all start pathing simultaneously.  Though their are some potential side benifits, like terminating searches when they grow past a certain length but that get a bit more complex.

[tylor]

Yeah, I implementedsuch thing also when I found that lot of mobs tend to want pathfinding at the same moment:)

Btw, where can I check current state and source of Pathfinder?

[Impaler[WrG]]

Khazad SourceForge repository, in my Sig

[Draco18s]

I remember doing quasi-threaded pathfinding in Flash. Game is called Garden Raider, and mobs there are moving using A*. If some mob wants a path, it addstask in queue, and wait. Then each frame some pathes are calculated for some limited time. That way sometimes mobs where standing there doing nothing, but that's better than lags, I think.

Sort of reminds me of AI War: Fleet Command.  The more units there were, the less often each one performed a targeting update.  The game is in fact so slick it can run 2,000 unit on 2,000 unit combats with no slowdown over a networked game (was just doing that an hour ago, actually, though my computer did chug when there were a huge number of ships traveling through wormholes, likely due to the number of ships and the transparency computation).

[tylor]

Hmm, will it be possible to have a smooth-working fortresses of 2000 dorfs anytime soon?

Hierarchical pathfinding algorithms boas up to 10x performance optimization, so it seems possible...

[Teiwaz]

I couldn't find the current algorithm (is there one? Conversation seems to go in circles a lot) but anyway, an observation:

I think generating a complete path to your destination is a waste. You're too likely to have the path invalidated (by map changes, something getting in the way, Dwarf deciding he's thirsty and dropping his current task, etc.)

Generate zones (areas of limited size which are contiguous for the most limited movement type possible in them - i.e. a normal floor area would be part of a zone where the entire area is contiguous for a creature which can walk but not open doors, an area of water for one which can swim but not open doors, a tile with a door on it for creatures which can walk and open doors, etc) with connectivity links (not specific paths, just info that they zones are connected) to adjacent zones. Generate an initial path on this (comparatively very simple) zone network, and then just generate a path to reach the next adjacent zone as you need it.

You'll end up generating a lot more paths, but the cost will be diffused over time, (this doesn't seem so important in DF as in games that demand a smooth framerate - but caravans and sieges arriving can still cause huge, nasty hitches from the cost of the initial long pathfind for a bunch of new creatures entering the map all at once) and with relatively small zones the individual paths should be fairly trivial to solve. Additionally, as you know you are only pathing as far as the next adjacent zone, you can limit pathfinding to within your current zone - so in the worst case, of a failed pathfind, you'll only floodfill your current zone. (Though this should never happen if your connectivity info is good.) Shorter pathfinds also reduce the number of paths which are invalidated and have to be regenerated when the map changes (a map change would only affect creatures currently pathfinding in the same zone, and would only affect creatures pathfinding through the zone but not currently in it if the connectivity changes).

Also, I'd put aside multi-tile creatures for now. They're an edge-case, and even when they're there, there will generally be very few of them. It's not worth optimizing for this at the cost of a better algorithm for single-tile creatures. Not to mention the current lack of multi-tile creatures...

[immibis]

Not to mention the current lack of multi-tile creatures...

Aren't wagons considered creatures? (except the one you embark with)

[bombcar]

Not to mention the current lack of multi-tile creatures...

Aren't wagons considered creatures? (except the one you embark with)

Yes, traders' wagons are 3x3 creatures, but they really travel around the "heart" of the wagon; you can see this in "D" mode. The starting wagon is treated as a creature in some ways; you can get error messages on some embarks that make this obvious.

[praguepride]

Wouldn't it be a natural evolution to have all multi-tile creatures operate that way? Have a "heart" (or head) that it travels around?

[CobaltKobold]

Not to mention the current lack of multi-tile creatures...

Aren't wagons considered creatures? (except the one you embark with)

Yes, traders' wagons are 3x3 creatures, but they really travel around the "heart" of the wagon; you can see this in "D" mode. The starting wagon is treated as a creature in some ways; you can get error messages on some embarks that make this obvious.

This is why the fire trick works, indeed. It just does the DePOT-ACCESSIBLE thing for them to determine pathable space, I'm imagining.

[immibis]

Yes, traders' wagons are 3x3 creatures, but they really travel around the "heart" of the wagon; you can see this in "D" mode. The starting wagon is treated as a creature in some ways; you can get error messages on some embarks that make this obvious.

This is why the fire trick works, indeed. It just does the DePOT-ACCESSIBLE thing for them to determine pathable space, I'm imagining.

What's the fire trick?

[Shades]

3. Pathfinding is one of the slowest parts of DF.

Has anyone actually tested this? Because the pathfinding for a hundred or so critters on a map as small as we have should not be such a bottleneck, if it is a problem then simply improving the implementation of the A* used might be all that is needed.

[praguepride]

I'm thinking that perhaps reducing the amount of pathfinding needed might also help FPS. More intelligent hauling, reducing pathfinding of non-important animals etc.

But I guess that's another arguement for another thread...