Bay 12 Games Forum

Please login or register.

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

Author Topic: Spin the pathfinding off to other threads.  (Read 7579 times)

aha

  • Bay Watcher
    • View Profile
Re: Spin the pathfinding off to other threads.
« Reply #45 on: July 06, 2012, 07:31:19 pm »

You may actually be fine if you actually write a program to inject code rather the redistributing DF with your changes in it, but it still doesn't hurt to read it at least. Granted, this sort of worry is still a long way off. I was just curious myself he'd actually put in his copyright so I went and looked it up.

I never intended to redistribute DF - not sure where you got that idea from. I will write the thing and release it as dfhack/foreman et. al. are released. Code injection will happen at the runtime - it's possible to do it with a running process.

You may want to look at this thread, specifically this simulator someone already wrote. When we say that pathfinding has been discussed extensively, we're really not kidding. :)

This link is interesting and I bookmarked it for a reference for the future when I do the final optimisation of the pathfinder. Cursory glance at it does indicate that the guy doesn't have a right heuristic, for the DF. He should add a diagonal distance (one outlined @ http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html will work for 2d map). I derived a formula suitable for df from this - it's important to have H and G in balance, otherwise you don't get the shortest path or the pathfinding will be slow.
Anyway I have a workable pathfinding algorithm implemented - caching the paths and proper invalidation of the cache will be the hardest part - after all, cache invalidation and naming things are two most difficult problems in programming;)
Logged
tail -f -n 10 df_27_176_38a/gamelog.txt

Andeerz

  • Bay Watcher
  • ...likes cows for their haunting moos.
    • View Profile
Re: Spin the pathfinding off to other threads.
« Reply #46 on: July 06, 2012, 08:13:01 pm »

Oooo!  This is a neat thread minus the bickering bullcrap.  Anyway, Aha, I like where you are going with this.  I also am interested in the opinions of people as knowledgeable as you with regard to a suggestion I posted earlier regarding rectifying time across game modes.  Stuff like you are suggesting would be quite helpful if not necessary for a suggestion like mine to have any chance of working. 
Logged

thisisjimmy

  • Bay Watcher
    • View Profile
Re: Spin the pathfinding off to other threads.
« Reply #47 on: July 07, 2012, 05:57:37 pm »

Cursory glance at it does indicate that the guy doesn't have a right heuristic, for the DF. He should add a diagonal distance (one outlined @ http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html will work for 2d map). I derived a formula suitable for df from this - it's important to have H and G in balance, otherwise you don't get the shortest path or the pathfinding will be slow.

Toady said in 2008 that DF uses the manhattan distance for the heuristic (h = abs(dx) + abs(dy)).  This isn't an admissible heuristic, so it's not guaranteed to find the shortest path.  However, in practice, the paths it generates are fairly close to optimal.  Close enough that you likely never noticed its effects in DF.  This heuristic has a performance advantage over admissible heuristics since it will search fewer tiles.

So it comes down to a trade-off: slighty shorter paths or slightly faster performance.
Logged

thisisjimmy

  • Bay Watcher
    • View Profile
Re: Spin the pathfinding off to other threads.
« Reply #48 on: July 09, 2012, 09:34:56 pm »

As an example of what I meant about the choosing the heuristics, here are two images:


The first uses the Manhattan distance, and the second uses euclidean distance.  In this case, they both find paths of the same length, but the euclidean heuristic has to search more than twice as many tiles.  So while the Manhattan distance isn't guaranteed to find the shortest path, it tends to be more greedy and faster (not to mention it's very fast to compute).
« Last Edit: July 10, 2012, 08:18:11 pm by thisisjimmy »
Logged

Andeerz

  • Bay Watcher
  • ...likes cows for their haunting moos.
    • View Profile
Re: Spin the pathfinding off to other threads.
« Reply #49 on: July 12, 2012, 04:08:51 pm »

Oh wow!  This is quite helpful!
Logged

No1

  • Bay Watcher
    • View Profile
Re: Spin the pathfinding off to other threads.
« Reply #50 on: July 13, 2012, 05:40:57 pm »

One question is how useful is the multi threading if there are only a few entities trying to path in each time-frame. The units move in a turn based fashion but due to the way the game uses entities speed to determine if a unit is allowed to move creates a uncertainty if more then one unit is ready to make a move and requires a path. I guess the game could find a path for units before they get to move but not sure if it would work.

Another question is how much of the computing is the path finding as we all know that "keeping track of items" is a FPS-devourer as well. Even things like stone seems to affect the game. I assume that the loop that checks if an item is under an effect is doing that by going through every item, which probably is unaffected by the speed factor and therefore could possibly be easier to multi-thread.
Logged

WJLIII3

  • Bay Watcher
    • View Profile
Re: Spin the pathfinding off to other threads.
« Reply #51 on: July 16, 2012, 12:47:56 am »

I know this is an oft-repeated thread, but still, I wish to give it my support.
Logged
Pages: 1 2 3 [4]