Print

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

[Draco18s]

Can I assume that that is blazing "set the atmosphere on fire" fast?

Not quite.  We'd have to get down to roughly 0.01 milliseconds per tile first.

[CobaltKobold]

.01 ms...10000 cycles per tile?

[Impaler[WrG]]

Draco got it, sorry I thought it would be obvious what I was referring too.  I'm now about 5x faster then before the optimization and I'm running 500 test paths in the suite in roughly the same time it took to do 100 when I started. 

The problem is it's unknown what the equivalent speed in DF would be, I suspect were still a good deal slower because theirs are a few layers of indirection necessary to retrieve the Connections and Edge Costs from the Grid.  This has to be their because were going to use a Client/Server structure ware as DF probably integrates all this into the map structure and thus has less indirection.  So even fully optimized I don't think the simple AStar will be equal to DF, but the Hierarchical solution will be and the Cache on top of that will be another gain so by the end we could be looking at an order of magnitude better performance.

.01 ms...10000 cycles per tile?

Remember this is per tile in the FINAL PATH, as you can see on the output were expanding ~18 nodes per path tile and examining the graph ~70 times, this is actually rather good considering what something like Dijikstra's algorithm would do.  I'm testing on a map with a relatively large and complex fort which is generating plenty of dead ends and maze like structures for the Pathfinder to get lost in.

UPDATE:

Got the performance down to 0.19 by using an Object Pool, I think is as good as it will get without using real profiling tools which I'm not experienced with.  I'm going to move towards the Hierarchical approaches and to create a path Corridor through which to run a slightly modified AStar through, this should reduce the nodes being expanded to make things faster.

[Impaler[WrG]]

I'm happy with the current performance level for now, the bulk test suite runs at about 0.20 milliseconds per step and if I manual run a path that's very easy (in the open no obstacles) it can clock in at 0.04.

Today I reworked the AStar implementation into one which is interpretable, basically the main loop is function call with a second layer determining the number of times to loop the inner portion.  I can call for a specific number of Nodes to be expanded or for it to continue until the path is found or found to be impossible.  And because everything is saved I can at any time request a 'best path'.  The plan is to have moving agents spread their path finding calculations over time which will help prevent those 'lag spikes' when every dwarf rushes out of the fort to pickup a sock.

Next I'm going to work on the MovementController class and see if I can get a whole slew of constantly moving agents running around and following paths.

[qwertyuiopas]

What will it do when DF is paused?

When it runs out of pending paths to calculate?

[cooz]

What will it do when DF is paused?

Could it keep caching some random point-to-point paths so they can be used when you unpause game? On the other hand it might not be so great idea in DF universe where everything's constantly changing...

[Foa]

What will it do when DF is paused?

Could it keep caching some random point-to-point paths so they can be used when you unpause game? On the other hand it might not be so great idea in DF universe where everything's constantly changing...

It'd probably finish all pathfinding in that particular frame, unless you unpause before that, but a path is only defined for one instance, AND I DO MEAN EXACTLY ONE!

[Impaler[WrG]]

Trying to anticipate path requests from the Client is a fools errand, If the client isn't requesting anything the Server shouldn't be stealing cycles on useless busy work.

Though were allowing the Client to request and receive a full path the preferred interaction is going to be through the movement controller which would be called every time an agent needs to know what direction to move in.  The Client would request a Controller for each agent which would then keep the pointer to its own private Controller, it of course has to input current location and goal but after that the Controller is just a black box from the Clients perspective.

[PermanentInk]

Regarding comparison with the actual DF pathfinder, I think that's the critical missing piece.  Ideally what we'd have is a framework (like the one you've posted screenshots of) where we can easily plug and play different implementations, and also have the reference implementation (the current DF pathfinder) and the current best user implementation to compare against.  If we all get on the same page with a consistent metric (a benchmark set of pathing tests), that allows anyone interested to download the whole mess and muck around with it to their heart's content.  If someone generates a genuine improvement, that's easy to verify by looking at the benchmark performance.  It'd be a lot less ambiguous way to communicate about different algorithms than just talking about them on here.

[Impaler[WrG]]

An accurate representation isn't possible without a LOT more detail on how DF paths and even then it wouldn't be the same because the lower level grid storage systems are probably nothing alike, DF's are probably not flexible enough to be of any use in a library which is a requirement here.  The only thing we do know is DF uses Astar, has dynamic non-connected region rejection ability, and dose not use hierarchy's or caches.

[Pie]

Despite not being a programmer (and thus not understanding much of what has been), this thread has fascinated me. Pathfinding is one of those things which I can see would make a huge difference to performance, which in turn provides a huge boost in the possible scale of projects and forts.

To those brave souls who dare to accept this challenge, I salute you (especially Impaler, who seems to have got down and made progress, which is always difficult with a project of this magnitude).

[Vigilant]

I don't know if anyone's tackled this but one of the other major slowdowns on DF is when no path exists it keeps trying to find one anyways. What needs to happen is potentially request future requests for that path for some time before allowing searches again. The problem is making sure a path is impossible takes a lot of time to verify, which means it has to be done at little as possible. So when you find a dead path you want to either put a time-based hold on it, or put a hold on it until there's (any) change in that world that might mean the path is free.

Btw, this offer isn't usually the kind people like, but I'm kinda a rogue programmer that drifts in and out. I can't really commit to a project but if you guys run into problems I can often come up with something useful

[Footkerchief]

I don't know if anyone's tackled this but one of the other major slowdowns on DF is when no path exists it keeps trying to find one anyways. What needs to happen is potentially request future requests for that path for some time before allowing searches again.

The game does prevent repeated requests in most cases -- the ones where it doesn't are bona fide bugs, like these:

# 000184 □ [dwarf mode][creatures]   animals locked in a room lag the game heavily from path-finding, additional lag can be caused by assigning them to be butchered
# 000631 □ [dwarf mode][idle behavior]   (Report) forbidding pet passage through the door of an enclosure creates lag

[Nadaka]

IIRC, the pet at forbidden door lag is caused by the hacked nature of pet forbidden doors. A PFD is treated as a valid path for a pet, and pathfinding passes through easilly, but when the animal attempts the step, it can not, and does pathfinding again, finding the same path because it had not moved. It seems that this happens every frame (possibly more than once a frame, I am not sure) instead of once every move (based on average movement speed a pet would be generating 10 times as many pathing requests as normal when cought next to a PFD).

[Footkerchief]

^^^ Or A* notices that the pet isn't allowed to pass and cancels the pathfind, which would still cause plenty of lag.  IIRC they show up several thousand at a time on the announcement screen.  But yeah, either way it's a deficiency stemming from the map component system, although it could be greatly alleviated by a working cooldown timer.