Bay 12 Games Forum

Please login or register.

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

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

Thndr

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #30 on: January 11, 2009, 02:56:30 pm »

The only problem I see with this is if you have hundreds of dwarfs on a really slow computer, you may have dwarfs that think so long they get nothing done because they'd get hungry/tired before finishing and then have to calculate a path to their bedroom/dining room and sit in the queue again waiting to die.

Of course, if your processor is so busy that this happens, you probably have other issues besides thinking dwarfs.
Yes that is exactly what would happen.  If the FPS_CAP was set high enough the main thread would churn along at that rate and starve the pathing threads of processing time.  Because the main thread keeps going the dwarf gets hungry, thirsty, and sleepy while awaiting a path.  Then has to cancel that path thread and start another.  Things like this are part of the reason why multi threading hasn't been done.

Isn't that when you make it so that if the pathing thread times out you have it force computation on the main thread instead of just cancel the request and request another path? Sure that it would basically be worthless if all of the pathing goes on the main as it would just result in what we already have in the game, but it provides compatability for multi-threading in which would speed it up on capable computers.

You could also have it auto-detect multi-threading when the program starts so it doesn't have to wait for timeouts on older computers. This way the minimum requirements stay the same as they are now, with the consiquence that if you don't support multiple threading, the pathing slowdown will be immense.

Although all the talk about multi-threading is great and all, but I assume there are other ways to calculate all those paths that could be implemented along side threading support.

But hey, I'm not much of a programmer (read: not one at all), so I may be thinking about this completely wrong.
« Last Edit: January 11, 2009, 07:00:47 pm by Thndr »
Logged

Baughn

  • Noble Phantasm
  • The Haruhiist
  • Hiss
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #31 on: January 11, 2009, 04:53:08 pm »

In this case, it'd be pretty simple.

When the main thread actually wants to /use/ the pathfinding results, it locks a mutex (or similar); if the pathfinding thread isn't actually done, it'll just block until it *is*. Using no CPU time, which leaves any remaining time to be used by the pathfinding thread.
Logged
C++ makes baby Cthulhu weep. Why settle for the lesser horror?

Ampersand

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

I like all this talk of using CUDA and multithreading to render an ascii graphics game faster. It amuses me.
Logged
!!&!!

Optimizt

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

I dunno, I think you guys are looking too deep into this. The way I'm working on it, the main thread creates (n - 1) worker threads, where n is the number of threads requested. The main thread does its share of computation no different than the worker threads. For example, on a quad core, the main thread would compute a fourth of the paths and the three worker threads would also compute a fourth of the paths.
Logged

Thndr

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

I like all this talk of using CUDA and multithreading to render an ascii graphics game faster. It amuses me.
We're actually talking about it to do quicker pathfinding and more pathfinding at one time. Nothing to do with graphics at all

It's just analogous to the graphics because BC used DF graphics while KQ uses DF-esque pathfinding.

I dunno, I think you guys are looking too deep into this. The way I'm working on it, the main thread creates (n - 1) worker threads, where n is the number of threads requested. The main thread does its share of computation no different than the worker threads. For example, on a quad core, the main thread would compute a fourth of the paths and the three worker threads would also compute a fourth of the paths.
So we only can assume you just plan on putting down framework to have the pathing system multi-threaded, and not any improvements other than more paths calculated at once?
Logged

Andir

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #35 on: January 11, 2009, 10:34:55 pm »

I dunno, I think you guys are looking too deep into this. The way I'm working on it, the main thread creates (n - 1) worker threads, where n is the number of threads requested. The main thread does its share of computation no different than the worker threads. For example, on a quad core, the main thread would compute a fourth of the paths and the three worker threads would also compute a fourth of the paths.
Are you manually setting the number of worker threads or is it dynamic?  I ask because I know the windows APIs will report WAY more threads than the processor can actually handle.
Logged
"Having faith" that the bridge will not fall, implies that the bridge itself isn't that trustworthy. It's not that different from "I pray that the bridge will hold my weight."

Optimizt

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

So we only can assume you just plan on putting down framework to have the pathing system multi-threaded, and not any improvements other than more paths calculated at once?
Right now, yes. Like I said, I don't know exactly how Toady has the map and creatures represented and handled internally, so any optimizations beyond more crunching may or may not be helpful. I'm trying to develop my framework so that it is a little similar to KQ as DF uses a modified KQ engine. Toady is a little busy with other matters and can't create a Battle Champs type example, so right now we'll just have to make do.

When I get done with the basic framework, I'll release the source so that any other coders can see what they can come up with.

Are you manually setting the number of worker threads or is it dynamic?  I ask because I know the windows APIs will report WAY more threads than the processor can actually handle.
Manually right now.  I'm concerned with keeping the game cross-platform, so I'm not doing any Windows API magic so that Mac dwarfers can take advantage of any optimizations, too.

Logged

dreiche2

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

You might also have a look at this thread, maybe it helps.
Logged

SmileyMan

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

Cool idea - hope I can help, since I do lots of multithreaded programming.

A thought on strategies - since you have many units pathfinding over a relatively static graph, it makes sense to use a cache of paths.  However, since you have a very large number of nodes, it would be very expensive in terms of memory to store a path to every other node.

My idea might be that you use some sort of paint algorithm to determine regions (you'd probably need to specialise it to determine rooms and corridors).  Then for each node within a region, you store the optimal path to each other node within the region, and for each region you store the path to other regions (via edge nodes).

This way, you only need to recalculate for a particular region when it is modified (ie mining, furniture, building) and you only need to recalculate for interregion pathing when edge nodes change.  Add in multithreading (because the entire path recalc can be done in parallel), or make it on-demand and that should be really really fast.
Logged
In a fat-fingered moment while setting up another military squad I accidentally created a captain of the guard rather than a militia captain.  His squad of near-legendary hammerdwarves equipped with high quality silver hammers then took it upon themselves to dispense justice to all the mandate breakers in the fortress.  It was quite messy.

shaver

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #39 on: January 12, 2009, 09:26:07 am »

Are you manually setting the number of worker threads or is it dynamic?  I ask because I know the windows APIs will report WAY more threads than the processor can actually handle.
Manually right now.  I'm concerned with keeping the game cross-platform, so I'm not doing any Windows API magic so that Mac dwarfers can take advantage of any optimizations, too.
I'd recommend looking at something like John Ratcliff's JobSwarm, and then just incrementally adding more things that can be done as microjobs.  It's fabulously easy.  It only runs on Windows right now, but the other platforms are underway. (Intel's TBB is nice too, but it's GPLv2 and so not really appropriate for DF.)

Other things could also be parallelized similarly, once the basic micro-job framework is in place, such as happiness calculations, flows, temperature effects, applying wear/rot, &c.  Parallelizing work isn't as good as avoiding work (with caches or path sharing, f.e.), but it would certainly let the system scale better and improve responsiveness on many systems.

Writing a job-scheduling thing from scratch atop thread-control primitives is a fun project, so I'm not trying to dissuade you from that, but if your goal is "shortest time to something parallel" then starting with existing game-oriented code is probably worthwhile.
Logged

Sowelu

  • Bay Watcher
  • I am offishially a penguin.
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #40 on: January 13, 2009, 01:48:44 pm »

Toady mentioned that the map is broken down into 16 x 16 x 1 sections of tiles. If each section could keep track of what other section it is linked to through open tiles, ramps, or stairs it would be possible to calculate which sections creature must go through before it worries about what tiles to go through. The only issue I can see with this is that though section X might be linked to section Y and Z, it may not be able to go from section Y to section Z through section X on the tile scale, if that makes sense.

Hmm.  Was thinking on this.  It might be useful to generate a "flow" (not a DF flow, more of a floodfill) along each border of the cell, with corners assigned to one of the four same-z-level sides, and mark which other borders you can NOT exit through.  The key is to prune as much as you can, as quick as you can, so it's okay if some of the data seems a little confusing.  Just knowing "oh, there's no way to enter from the south and leave to the north" is nice.  Might help the most when it comes to the up/down borders.

Though I'm not totally convinced that N/E/S/W borders will almost ever show up as "can't go here from there" in the middle of an average fortress.  Well, meh.
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!

Draco18s

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #41 on: January 13, 2009, 05:54:15 pm »

It's called a flood fill.  It's how MS Paint's Paint Bucket works.
Logged

Soralin

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #42 on: January 13, 2009, 06:19:24 pm »

I think the problems he's talking about are something like this, how would you handle cells like this?
Code: [Select]
................
................
................
................
................
................
................
XXXXXXXX........
.......X........
.......X........
.......X........
.......X........
.......X........
.......X........
.......X........
.......X........
. = ground X = wall
You can enter from the west side, and leave to the east from some tiles, but not others.  If this is the corner of a fortress wall, and the dwarf is inside and looking for a path to the east, it's going to enter the cell from the southwest and run into problems.

Or similar ones:
Code: [Select]
XXXXXXXX..XXXXXX    ......X...X.....
XXXXXXXX..XXXXXX    ......X...X.....
..........XXXXXX    ......X...X.....
..........XXXXXX    ......X...X.....
XXXXXXXXXXXXXXXX    ......X...X.....
XXXXXXXXXXXXXXXX    XXXXXXX...XXXXXX
XXXXXXXXXXXXXXXX    ................
XXXXXXXXXXXXXXXX    ................
XXXXXXXXXXXXXXXX    ................
XXXXXXXXXXXXXXXX    XXXXXXX...XXXXXX
XXXXXXXXXXXXXXXX    ......X...X.....
XXXXXXXXXXXXXXXX    ......X...X.....
................    ......X...X.....
................    ......X...X.....
XXXXXXXXXXXXXXXX    ......X...X.....
XXXXXXXXXXXXXXXX    ......X...X.....

If you tried to navigate by cells, you might run into situations where it just jumps over the top of walls.  There might be a path from the south side to the north side of the cell, except that path can't be reached from where the dwarf would enter the cell in this particular instance.
Logged

Sowelu

  • Bay Watcher
  • I am offishially a penguin.
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #43 on: January 13, 2009, 06:28:11 pm »

In Soralin's 2nd example, it's still useful to tell DF that you CAN'T enter from the east wall, and leave from the north, or vice versa.  So you still get something out of it.
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!

Andir

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #44 on: January 13, 2009, 06:58:40 pm »

You could setup regions using the flood fill.  When the fill hits a door, river, etc. it stops creating the "region" and creates a "connector region" that is another flood fill.  If it hits a wall, channel or rock formation, it aborts.  If you wanted, you could even cache the items or wall contents in the region and query regions for items.  When querying the region, it can either store the items in a container object that has item management functions to "give" items to dwarfs that pick it up or it can use a "link array" to identify which of the items in "item array" is contained therein.  You could setup a region class that has functions to combine regions or split them based on building a door or digging a channel in the region if needed.  Each of these fills is placed in a node array that can be quickly navigated without checking each tile in the region.  The following map sets up regions A, B, and C and uses door [ + ] (connector region) to connect A-B and B-C.  These are separated by # wall.  When looking for stone, the program doesn't have to check each tile for stone, but you can query the region for the stone content.  Then you step to the next region until you build a list of "directions" that the dwarf can follow to get to the stone.  You'd only need to path check the regions in the node array.
Code: [Select]
AAAAAAAAAAAAAAAAAAAA
AAA#######AAAAAAAAAA
AAA#BBBBB#AAAAAAAAAA
AAA+BB#+##AAAAAAAAAA
AAA#BB#CC#AAAAAAAAAA
AAA#BB#CC#AAAAAAAAAA
AAA#######AAAAAAAAAA
AAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAA

This would rely on doors or transition areas.  Identifying transitions in open areas is another thing.  You could possibly setup the flood fill to cap regions at a certain width/length, then transition to a new region.

Edit:  Connector regions are nothing more than a regular region.  I just didn't label them to try to keep the complexity of the diagram down.
« Last Edit: January 13, 2009, 07:02:26 pm by Andir »
Logged
"Having faith" that the bridge will not fall, implies that the bridge itself isn't that trustworthy. It's not that different from "I pray that the bridge will hold my weight."
Pages: 1 2 [3] 4 5 ... 9