Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  
Pages: [1] 2 3 ... 9

Author Topic: The threaded pathfinding thread with the previously unhelpful title.  (Read 14291 times)

Optimizt

  • Bay Watcher
    • View Profile

Hi all,

I've been lurking the forum for a while now, and I come asking a question that probably only Toady would know the answer to.  Like many hopefuls, I look to the day when Dwarf Fortress will run multi-threaded with huge performance gains, but he has been stated in the past that he doesn't know how to implement this and that multi-threading is not a huge priority right now.

So my question is this: is the pathfinding code of Kobold Quest similar to DF's?  I have looked at the source code for KQ and come to the conclusion that parallelization of the pathfinding code would probably be possible, so I was going to gut KQ so it consisted of nothing more than a ton of creatures pathfinding to random locations and try to get it running (somewhat) smoothly using multi-threading techniques.  On my machine, DF has no problem with weather, temperature, and flows, but when useless migrants and their rather fertile cats decide it's their Armok given right to clog up my hallways and rooms, my FPS takes a huge hit. In theory, speeding up pathfinding would bring giant leaps in FPS.

Would multi-threading the KQ pathfinding code help Toady at all? If so, I'll get busy on implementing both multi-threaded CPU and GPU pathfinding (for you CUDA enabled folks).  Hopefully it will be of some use somewhere down the road.

This is provided that a new version of DF doesn't come out before I finish, because then I won't be getting anything done in my life (pathfinding included ;) )
« Last Edit: January 09, 2009, 02:48:21 pm by Optimizt »
Logged

corvvs

  • Bay Watcher
    • View Profile
Re: Beating the corpse of Urist Degatöl, "Urist Wayfind", Horse (Tame)
« Reply #1 on: January 08, 2009, 09:13:17 pm »

I was actually thinking about writing a sort of "demonstration program" that would do flows similar to how I imagine they're implemented in DF using CUDA. Pathfinding would probably be an even bigger improvement though. :)
Logged

Jay

  • Bay Watcher
  • ☼Not Dead Yet☼
    • View Profile
Re: Beating the corpse of Urist Degatöl, "Urist Wayfind", Horse (Tame)
« Reply #2 on: January 08, 2009, 10:02:06 pm »

I'm fairly certain they are, although I seriously doubt that you'll get a good answer on it here, as much as he's trying to protect the DF source...
A PM might work.  No guarantees.
But yes, if you can get Toady a demonstration of it in his terms (a la Baughn and the graphics optimizations & Battle Champs) it seems more likely to happen.
Logged
Mishimanriz: Histories of Pegasi and Dictionaries

nagual678

  • Bay Watcher
  • Noble Sam says: I want YOU for the Fortress Guard!
    • View Profile
Re: Beating the corpse of Urist Degatöl, "Urist Wayfind", Horse (Tame)
« Reply #3 on: January 08, 2009, 10:32:13 pm »

Best of luck, hopefully something like the graphics optimization will happen.
Logged

Thndr

  • Bay Watcher
    • View Profile
Re: Beating the corpse of Urist Degatöl, "Urist Wayfind", Horse (Tame)
« Reply #4 on: January 08, 2009, 11:28:12 pm »

Most likely it is similar to the one used by Dwarf Fortress.

Toady, while not wanting to make DF completely open source, seems to make smaller games using similar/same coding to demonstrate how he knows how to do something. This is something we have been seeing with the current graphical enhancement project.

I suggest retooling the Kobold Quest pathfinding code into a more efficient example and test it here on the forums, to see if compared to the original, people are getting less slowdown for the same amount of pathfinding. This is how the graphical patch using Battle Champs did it.
Logged

bhelyer

  • Bay Watcher
  • The kart iz not movink!
    • View Profile
Re: Beating the corpse of Urist Degatöl, "Urist Wayfind", Horse (Tame)
« Reply #5 on: January 09, 2009, 12:39:37 am »

I think emailing Toady with this kind of query would prove a much better source of answers.
Logged

Optimizt

  • Bay Watcher
    • View Profile
Re: Beating the corpse of Urist Degatöl, "Urist Wayfind", Horse (Tame)
« Reply #6 on: January 09, 2009, 01:54:18 am »

Yeah, I didn't think he would check this thread; I was just feeling the waters I guess.
Logged

Tormy

  • Bay Watcher
  • I shall not pass?
    • View Profile
Re: Beating the corpse of Urist Degatöl, "Urist Wayfind", Horse (Tame)
« Reply #7 on: January 09, 2009, 07:41:37 am »

Good luck with this mate. Let's hope that your experiment will work out perfectly. Multi-threaded pathfinding would be awesome to have in DF.  :)
Logged

chaoticag

  • Bay Watcher
  • All Natural Pengbean
    • View Profile
Re: Beating the corpse of Urist Degatöl, "Urist Wayfind", Horse (Tame)
« Reply #8 on: January 09, 2009, 01:59:19 pm »

Things to keep in mind about the Dwarf Fortress pathfinding:

-It should be able to handle multiple z-levels
-It is dynamic, not static (because building walls and locking doors messes things up).
-It should know when an job is innaccessable

Also, the title doesn't seem too helpfull.
Logged

Sowelu

  • Bay Watcher
  • I am offishially a penguin.
    • View Profile
Re: Beating the corpse of Urist Degatöl, "Urist Wayfind", Horse (Tame)
« Reply #9 on: January 09, 2009, 02:07:34 pm »

Does KQ have the same time system as DF, where there's numerous 'ticks' between when one critter moves and another one moves?  It's a very minor complication to parallelizing your pathfinding but it's an important one, because it means unless you play with the time a little, you might not have as many things to run in parallel as you would like.
Logged
Some things were made for one thing, for me / that one thing is the sea~
His servers are going to be powered by goat blood and moonlight.
Oh, a biomass/24 hour solar facility. How green!

Optimizt

  • Bay Watcher
    • View Profile
Re: Beating the corpse of Urist Degatöl, "Urist Wayfind", Horse (Tame)
« Reply #10 on: January 09, 2009, 02:38:23 pm »

Does KQ have the same time system as DF, where there's numerous 'ticks' between when one critter moves and another one moves?  It's a very minor complication to parallelizing your pathfinding but it's an important one, because it means unless you play with the time a little, you might not have as many things to run in parallel as you would like.
I don't think that would be a problem.  The main issue is computing the actual path, which would be sped up by threading. Every creature that needs a path recalculation would put a request in a "queue" saying "I want to get here, please tell me how." The pathfinding handler would wait for every creature to put their request into the queue, crunch the numbers, and then tell each creature the appropriate path after it finishes.

Things to keep in mind about the Dwarf Fortress pathfinding:

-It should be able to handle multiple z-levels
-It is dynamic, not static (because building walls and locking doors messes things up).
-It should know when an job is innaccessable

Also, the title doesn't seem too helpfull.

1. I've thought about the z-level problem. Basically, even though the system appears to be 3d, it can be represented as a single 2D graph (the graph theory kind, not the y=3x kind) with edges connecting where the stairs/ramp/etc. should be.
2 and 3. It seems that creatures already recalculate their path every time they move, so that wouldn't be a problem. All the pathfinding algorithm needs to know is if a spot is passable or not; it doesn't care if it's impassible because of a door, wall, or cave-in that conveniently destroyed a caravan of elves.

Also, about the title: I was trying to be clever (beating the dead pathfinding horse) but those crazy Dwarves don't have a word for "path."
« Last Edit: January 09, 2009, 02:46:08 pm by Optimizt »
Logged

Optimizt

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #11 on: January 09, 2009, 03:44:05 pm »

Just got an email reply from Toady. Basically he mentions that the pathfinding code uses a different algorithm in DF (A*) than KQ's (Dijkstra). The algorithm switch isn't the problem, I'm familiar with both. Toady mentions that there are some specific peculiarities with DF's pathfinding code versus a simple A* implementation and that creating a test program ŕ la Battle Champs would be a bit more involved.  Still, I think I get the gist of how it is implemented in DF and will see what I can work with.
Logged

Thndr

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #12 on: January 09, 2009, 04:53:37 pm »

Glad you got a reply back and hopefully you tread a decent amount of ground towards awesome code. Looking forward to any results you may have, even if it doesn't get implimented in DF, it still could inspire Toady.
Logged

Baughn

  • Noble Phantasm
  • The Haruhiist
  • Hiss
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #13 on: January 09, 2009, 07:00:20 pm »

I was pondering pathfinding some months ago, and had this idea - it takes a lot of time to pathfind several squares through otherwise empty (or mostly empty) rooms, such as outside, dining rooms, or whatever.

It'd be a major optimization to aggregate these to single nodes on your graph where possible, then pathfind locally once the creature actually gets there; going from one end to another of such an aggregate, A* would run extremely quickly; not so much in the initial pathfinding, when it isn'T certain it'll end up using that path at all.

Oh, and graph theory graphs aren't 2D. They don't have dimensions at all. Actually representing them on paper (or in a hologram, or a 7D figure for that matter) is a major not-quite-solved problem. :P
Logged
C++ makes baby Cthulhu weep. Why settle for the lesser horror?

Kardos

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #14 on: January 09, 2009, 10:56:44 pm »

I don't really know anything about coding, but would the path finding be at all similar to hashing?  If this is true, Baughn's node idea would be a great help, especially if a Dwarf is only forced to reevaluate a path if the borders of a node are changed.
Setting node borders would be like adding protocols on how to handle changes to an environment.  If a door is locked/unlocked, if a ramp is removed or constructed, if's there's a cave-in in a node or if a Dwarf's task changes could all be protocols that mandate the path be re-evaluated.  Furthermore, if multithreading were implemented, multiple possible paths could be calculated.  So if there's a shorter path to a Dwarf's destination, but a door on that node's border is locked, that particular path could be cached, and if the door is later unlocked, the Dwarf's path is changed.  Assuming of course that the new path is still x-tiles shorter then the old path. 

Edit:  If a successful node-based path-system could be implemented, the largest problem would probably be coming up with a complete list of all path-interrupt protocols, such as doors, flowing water, construction, traffic weights and other entities in a Dwarf's path, especially in crowded hallways or Dining rooms. 
« Last Edit: January 09, 2009, 11:08:03 pm by Kardos »
Logged
Pages: [1] 2 3 ... 9