Print

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

[Lexender]

A simple idea for making pathfinding more efficient and less fps-comsuming just popped in my head, and I wanted to submit it here, not because I think it is great, but because I want to see how you guys are going to horribly, violently rape my suggestion and make a small, gory poodle of it.

What if, in the same way traffic control works right now, you could design traffic areas in your fortress where pathfinding would be pre-determined. Let me explain with an example:

Code: [Select]

A

++++++++++++++++++++

                   B
Where dwarf wants to get from A to B, and +'s are the designed road. Normally, as I understand it, the pathfinding algorythm (no idea what this word means) "blooms" around A, until it reaches B, wasting precious resources. Same thing would happen in my idea, only it reaches to the designated trafic area, then B does the same thing. Since the pathfinding between every single point of the road has already been made, it does not need to do the rest of the math.

In the eventuality where two points are not connected by a road, no problem, the pathfinding goes on as normal. If for a certain reason the designed path is blocked, a warning anouncement is sent and the dwarf pathfinds as normal from there.

So, tell me, how would that not work?

[Slappy Moose]

Actually, that's a good idea.

I don't code much at all, but I'm not retarded and I think that this would be fairly easy to do, Toady could even just modify the military patrol code to work one way or something.

However, it would take a lot of time to manage paths for dwarves.

[Jim Groovester]

Yeah, I don't know. People could make some pretty retarded superhighways (This is what I'm calling your suggestion.) just to mess with their dwarves, though that's not a reason to shoot the suggestion down. The only problem that is obvious to me, is that instead of the dwarf just doing one 'blooming' pathfinding algorithm, the dwarf has to do two: One to the superhighway, and another where the superhighway ends.

There's also a problem about how a dwarf paths onto the superhighway. Does it do so at the end points? Or can the dwarf get onto any point and somehow magically find the right exit point? Would the dwarf prefer the superhighway over a shorter route?

I'm not a programmer, and I don't intend to be, but I don't see how these questions could be easily resolved.

[JoRo]

From previous threads, I'm given to understand that the dynamic nature of pathing is what makes it really resource intensive.  What happens if you lock a door somewhere between A and B?  What if the path is clogged with dwarves?  What if the path is clogged with goblins, or lava, or a bronze collosus?

[Footkerchief]

I think in practice this would be rather similar to route caching, except with paths manually "cached" by the player.

[Rift]

yea, i'm not sure if this would be worth the time to implement. Since its a dynamic system where the routes could be changed at any time, which means you would have to keep checking each route to see if its changed...
While it could perhaps, be faster on average, i doubt it would be much faster.
As someone who has actually programmed with A* search alogrithms in the past, i really doubt this would solve the problem. [4th year comp-sci major]
I can think of a couple optimizations that i *think* would work, and wouldn't take me on one of my projects that use A* very long to implement. A few would sacrifice accuracy for huge performance gains, a few would just offer lesser performance gains without sacrificing everything.
I am not 100% sure how toady designed his pathfinding, however i'm pretty sure that if he "desired" to make it much, much, faster, he could, perhaps in a very short period of time*.

*[i suspect the most time-consuming issues arrise from the fact toady didn't take programming classes and learn how to code in 'good' ways, meaning easy to change/fix ways]

[Volfram]

Yeah, I don't know. People could make some pretty retarded superhighways (This is what I'm calling your suggestion.) just to mess with their dwarves

I fail to see the problem there.

It's an interesting suggestion.  I'm no expert on pathing algorithms, and I'm not entirely sure how flexible predefined pathing on roads could be made, but I think it merits looking into.

[Lexender]

There's also a problem about how a dwarf paths onto the superhighway. Does it do so at the end points? Or can the dwarf get onto any point and somehow magically find the right exit point? Would the dwarf prefer the superhighway over a shorter route?

That's why:
A-Pathfinding operates from the dwarf and from the destination. The shortest route from the destination would be the exit point from the highway.
B-Pathfinding would go as normal until it reaches the highway or the destination, so no problem of pathfinding in non-designated areas.

From previous threads, I'm given to understand that the dynamic nature of pathing is what makes it really resource intensive.  What happens if you lock a door somewhere between A and B?  What if the path is clogged with dwarves?  What if the path is clogged with goblins, or lava, or a bronze collosus?

If the highway is blocked by a door, cave-in, monster, etc, it would be quite the same as if you blocked the path of a dwarf that has already started moving (thus has the pathfinding already done). It just starts again from scratch (or cancel the job). The clogging would require special "highway architecture skill" from the player, so that these roads are wide enough, and varied enough (maybe do two different roads, so that dwarves coming from wither side would take different paths).

I think in practice this would be rather similar to route caching, except with paths manually "cached" by the player.

Yeah, that's pretty much the idea, although what is described in this thread would only work with very repetitive activities, and would probably not be very efficient. Not that I say my idea would be, but bleh.

yea, i'm not sure if this would be worth the time to implement. Since its a dynamic system where the routes could be changed at any time, which means you would have to keep checking each route to see if its changed...
While it could perhaps, be faster on average, i doubt it would be much faster.
As someone who has actually programmed with A* search alogrithms in the past, i really doubt this would solve the problem. [4th year comp-sci major]
I can think of a couple optimizations that i *think* would work, and wouldn't take me on one of my projects that use A* very long to implement. A few would sacrifice accuracy for huge performance gains, a few would just offer lesser performance gains without sacrificing everything.
I am not 100% sure how toady designed his pathfinding, however i'm pretty sure that if he "desired" to make it much, much, faster, he could, perhaps in a very short period of time*.

*[i suspect the most time-consuming issues arrise from the fact toady didn't take programming classes and learn how to code in 'good' ways, meaning easy to change/fix ways]

My diploma in absolutely-nothing tells me that you're probably right. I based all that on the fact that the pathfinding algorythm "blooms" (as said in first post), so I may be totally wrong, if that's not even how DF handles it.

[macdonellba]

My diploma in absolutely-nothing tells me that you're probably right. I based all that on the fact that the pathfinding algorythm "blooms" (as said in first post), so I may be totally wrong, if that's not even how DF handles it.

Here's a nice (simple) explanation of how A* works that I keep bookmarked for moments like this: http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html 

That's why:
A-Pathfinding operates from the dwarf and from the destination. The shortest route from the destination would be the exit point from the highway.
B-Pathfinding would go as normal until it reaches the highway or the destination, so no problem of pathfinding in non-designated areas.

The entity still needs to path as normal to determine whether the pre-defined highway is worthwhile or not, plus you have to add a check on each tile for whether you've hit a highway, which overall is a net speed loss. The use of connection maps or route caching avoids this by pre-computing this sort of info (of course, you could pre-compute it in your idea too, but then it would be only a moribund and less effective version of the automatic methods.)

[Rift]

yea, when push comes to shove, most "highways" or straight ways are actually incredibly quick for A* to solve, to the point its not much of a optimization to make routes for that sort of thing. It's things like backtracking and spirals/mazes that really cause a* problems.
A* is still used it most games, although there are alternatives.
I don't think trying to figure out how to optimize the a* alrgorithm will help nearly as much as simply optimizing the amount of times it needs to run by making it run less often. or by having all pathfinding done on a "constant" basis, where you take so much cpu time and devide it up for each dwarf, then have each dwarf use that time 'all the time' to be computing pathing. While it might seem like that would take more cpu, it would take far less on average, and get rid of any 'bloom'.
The earlier would take a few hours tops to change, the later might require a complete rewrite of all pathfinding related code. If it's modular[the way professionals are taught to write], that still wouldn't take longer then a day, but i suspect it's not very modular.

[Martin]

I think in practice this would be rather similar to route caching, except with paths manually "cached" by the player.

Well, if route caching goes in, he should add that as well. Doors, hatch covers, and bridges should automatically generate a cached path since they are game-defined bottlenecks and are used to define rooms. For purely arbitrary paths, taking the patrol route code from soldiers and allowing the player to define preferred paths would do the trick - you'd just lay down points on a path to be automatically cached. Once caching goes in, Toady would have a number of options to choose from to allow players to influence their pathing load, if they were willing to do the steps.

Caching's cost is memory, and I have no clue what his memory constraints are, but I've yet to see anyone complain about that.

[Shoku]

Seems like as the number of dwarves goes up you could also make pathfinding just a bit less dynamic by lightening up on how hard a time they have moving through tiles occupied by other dwarves and animals (like maybe they get used to crowds?)

[Lexender]

Macdonellba and Rift, you two are pretty much right, at least I think you are. I didn't think the algorythm was this developped, but A* seems to completely negate my idea. Thank you for the lesson

You all should continue this "pathfinding brainstorm", though. Maybe something real good will get out of it and Toady can use it...

[Stray Elvis (Tame)]

Just a quick question for the veterans here--do any of you happen to remember a pathfinding thread where Toady actually chimed in? I'm curious what his thoughts are.

[Rysith]

You can do this now: set the "high" designation to be cost 0, and things should work themselves out. While it has a "high" designation to follow, it won't follow anything else.