Bay 12 Games Forum

Please login or register.

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

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

Roara Wolf

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #60 on: January 16, 2009, 02:02:44 am »

A few thoughts I've had on the issue:

First, making something multithreaded doesn't actually make it more efficient, to my knowledge - it just means that if you have multiple processors, they can each focus on a part of the task, rather than just handing it to one processor while the rest do unimportant background stuff. This means making something multithreaded will likely be an amazing speed boost for someone who has multiple processors - for someone who doesn't, not only will it not have any improvement, but it's possible that it'd go even slower from the additional system overhead.

I happen to be one of those people who doesn't have multiple processors, so I hope you can all understand as I try to cunningly switch this topic in the direction of more efficient pathfinding, rather than or perhaps in addition to multithreaded pathfinding.

That said, I'm not too experienced on matters of pathfinding. I think I understand the A* model of pathfinding enough to talk about it, but in truth my ideas are a little more generic.

One issue I see with A* pathfinding is that while it's amazing to find the path for situations where you really don't know, beforehand, where you'll start and where you'll end, in DF, you tend to figure that most dwarves who go through a hallway (particularly a 1-width hallway) will go a very specific route; straight through. With just using A* pathfinding over and over again, you're essentially calculating commonly-used routes over and over again.

So I was thinking... why not have some method to remember those routes, or possibly precalculate potential routes. In games where the map doesn't change, you could easily precalculate all sorts of things, but unfortunately, at least in fortress mode, DF's map does change (unless you're playing elves or something, but who would want to play those?)

Therefore, that splinters my idea around a bit. First, I thought... why not have the routes slowly come into existance, through some almost evolution-based method, coming into existance randomly based on moving units, changing/branching off into clone routes/etc., and dying off when other routes are used in favor of them.

For this method, it wouldn't take very long to give some control of this feature to the player - both in general settings (since this is a sort of diversion from CPU power to memory, this would allow people with lots of memory to just say "eh, screw it, let's make thousands of routes", or something), and in actually making the routes. This could even be used as traffic control, by allowing routes having customizable costs as well, as far as the pathfinder is concerned (the end result would function like the current traffic costs, except applied to a sort of pre-created path rather than the tiles that path is made up from.)

Another idea, one that I don't see any easy way to do at all, would be to predetermine these so-called routes based on some algorithm, and as the map changes, to rewrite the routes. I'm sure others have ideas that look like this one, only better in every way.

For those who have no idea what I just said, but have some understanding of A* pathfinding, let's take an example. # are walls, . are floors, 1 and 3 are beginnings of the route, 2 and 4 are the respective route ends, @ is a dwarf, and D is his destination.

Code: [Select]
#..#####
#..#####
#.23..4D
#..#####
#.1#####
#@.#####

In this case, the calculation time saved isn't that much (about three iterations, probably), but, depending on the exact values used, an A* method would likely take the routes from 1 to 2, then 3 to 4, then to D anyway. Using routes, 1 would effectively also lead to 2 (in addition to all the adjacent tiles), and likewise 3 would lead to 4. If going from 1 to 2 seems the most viable, it'll apply the pre-constructed path, as if it had calculated it itself, and continue from there.

I'm unsure of any flaws in this method, having only just gotten the idea last night and not having managed to test it in practice yet, so if there are any obvious ones, or if it's a fairly old trick that's long had its guts removed and has long been considered obsolete, then please say something. I'm really uneducated in this crazy pathfinding business; all I know is that, assuming DF's using standard A* pathfinding (or something comparatively like it), there're probably thousands of cases where it's recalculating the same thing over and over.

One final thought, unrelated to all this, is... who says there needs to only be one path finding method? There could be more, if, for example, strictly land-based pathfinding methods can be made more efficient than a flyer's pathfinding method. Another thought is that perhaps less intelligent creatures could use less efficient pathfinding methods (that is, in time it takes to get from point A to point B, as opposed to CPU efficiency).
Brainless undead could use a simplistic "go in the best direction" method, and just sit there uselessly, or give up on that goal and find another place to try to go, when they run into a dead end, etc. It is characteristic of them, afterall!
Logged

sneakey pete

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #61 on: January 16, 2009, 06:09:53 am »

I happen to be one of those people who doesn't have multiple processors, so I hope you can all understand as I try to cunningly switch this topic in the direction of more efficient pathfinding, rather than or perhaps in addition to multithreaded pathfinding.

Unfortunately, this is the way the world is going. Its also hard to make a more efficient single core processor, but we can just tack on more cores. With dual core processors becoming really cheap these days (an intel E5200, which is a nice peice of kit, is only 64USD as of next month, or a Q8200 quad core CPU for only 168USD), i really do think that people who have a single core processor will become so uncommon in the next 2-3 years that it will no longer be a real problem.

Of course, efficiency is *always* good, but i have a feeling that multithreading would probably benefit the majority of people the most, and would do so into the future.

Anyway, i'll let all you genius programmers get back to it :p
« Last Edit: January 16, 2009, 06:15:49 am by sneakey pete »
Logged
Magma is overrated.

MuonDecay

  • Bay Watcher
  • Say hello to my little μ
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #62 on: January 16, 2009, 07:06:51 pm »

Multicores are pretty common, especially for gaming.

Currently to get the same current-generation game performance in a single core that I get with my low-end dual core would cost more money than the dual-core does.

That in itself should serve as a pretty distinct indicator of the direction hardware is going in. Duals are not even very expensive anymore. Midrange dual cores are notably cheaper than the upper end single core processors, despite offering more processing power when used with multithreaded software.

The more powerful configuration is currently cheaper. Also, people with dual cores are currently experiencing a CPU bottleneck in DF where people with fast single cores are not. That is to say, that DF is falling behind the technological curve to such a drastic degree that those who adopted dual cores a couple years ago are actually being punished for it with performance losses.

Someone is volunteering to add in support which will stop people from experiencing performance bottlenecks when running DF on machines which are way beyond the performance needs of the program. Toady isn't having to take his own time to do this, and no, it is not going to make single cores run the program more slowly.

There is absolutely no rational reason to be smashing any looms, here.
Logged

Andir

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #63 on: January 16, 2009, 07:20:52 pm »

it is not going to make single cores run the program more slowly.
Done incorrectly and it could.  But that's like saying that jumping off a building is detrimental to our health.

Also, some higher end processors that have Hyperthreading and similar tech would actually benefit from threading.
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."

Roara Wolf

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

I'm not sure what looms are or why they should be smashed, but if they're what I think they are, I say we throw flaming pick axes at them and let combustion sort it out.

Anyway, I agree that multithreaded support would increase the performance for a lot of people; just not me... and since I'm a selfish jerk or some equivilant thereof, that means I'm more likely to think about how to increase efficiency rather than increase resource usage. Both are important issues, particularly since the game seems to be getting more and more complex with each update.

Unfortunately though, even if I weren't a selfish jerk, I only have basic knowledge of how threads work. On the other hand, while I'm no expert in pathfinding, at least I can try to throw random ideas at the more intelligent people in this thread, and hope one or two of them help inspire them.

Speaking of which, any thoughts on my whole "different pathfinding methods for different intelligence levels or other needs" idea? In particular, I believe someone in this thread suggested to make a sort of cat fortress, where cats just wander around randomly... but it's kind of silly to introduce pathfinding for random wandering in the actual game, when you could just have the thing move randomly. And it still tickles me to have some creatures of lesser (or no) intelligence wandering around clumsily with little foresight. Also, pathfinding could be spaced across multiple ticks of game time based off of intellectual capabilities, with more intelligent creatures taking less game time to find a good path, although that'd be more of a gameplay effect than a method towards efficiency.

On that, as opposed to random wandering for such a prototype, may I suggest the illusion of a task-based system? (perhaps Home, Food, and Work places for each cat, which could easily overlap (particularly Food, Work, and maybe Home), and be decided on the go rather than pre-decided(ala picking the closest Food, or the closest open Work spot, etc.), with the final option for cats who need no sleep, food, nor money to just wander around randomly or explore or something.) Not anything complicated like DF, of course; just something virtual to simulate the movement of dwarves - since that is, afterall, what a large amount of processing power goes to simulate in any given game, most of the time.
Logged

MuonDecay

  • Bay Watcher
  • Say hello to my little μ
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #65 on: January 17, 2009, 12:50:43 am »

I'm not sure what looms are or why they should be smashed, but if they're what I think they are, I say we throw flaming pick axes at them and let combustion sort it out.

That was sort of an obtuse reference to luddites, though it was more tongue-in-cheek than it was a criticism  :P
Logged

Thndr

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

The very notion of using different pathfinding techniques for different animals depending on their priority is kinda silly. Because what if the cats get the current dwarf pathfinding technique? and then you get 200 cats? The cat pathfinding system will bog down the whole fortress while the more efficient dwarven pathfinding system would provide less lag. The animals in Dwarf Fortress move like the dwarves in Dwarf Fortress (task based). *although vermin seem to move randomly*

I also agree that the pathfinding code should also be more efficient as well, but there isn't really a demo from Bay12 that has the same pathfinding code to provide someone an example of how toady does it in DF. KQ uses a different one, and says that the transition between an optimised KQ pathfinding improvement to DF pathfinding improvement would be an easy task, most coders rather want something more akin to the original so they can help improve it a lot more than just hoping the code would work in DF.
So Optimiz is just working on the multi-threading aspect of the coding because it's the quickest and easiest way to give the increasing population of dual core users (and hyperthreading compatible *which came out years ago*) an improvement in the framerate of dwarf fortress.
Logged

Morberis

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

I can't wait for a multithreaded DF, pathfinding at least.

If you manage to get this working and actually integrated in DF in a way that either works with multi-cores uses a graphics card I will drop $100+ in Toadies donation box.
Logged

Tonjevic

  • Bay Watcher
    • View Profile
    • http://tonjevic.net
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #68 on: January 18, 2009, 11:23:39 am »

Could you potentially generate pathing nodes based on traffic through given tiles, culling similar, contiguous nodes as you go to path for hallways which are fairly static?
That is, when traffic density changes between adjacent tiles, generate a new node and merge those which are in close proximity to each other but would lead to different routes.
There might be some issues with assigning nodes to completely new paths (though this might be overcome by pathing to the nearest node to the destination and then using the old tile-by-tile approach), in dealing with the constantly changing traffic data as new tasks, destinations etc. are created (and in making sure that paths don't screw themselves up by consulting new traffic data that is created as a result of their own existence, which could either lead to constant route recalculation or a recurrent effect whereby nodes reinforce themselves and you get a bunch of traffic through a path which isn't necessarily the most efficient one) and there might be a memory issue with storing traffic volume for each tile.

The problem with DF's pathfinding seems to be the presence of *way* too many nodes (that is, every tile), with pathing queries, recalculations, whatever, being made at every one. Surely by reducing the number of these, you'd also reduce the number of calculations and increase DF's speed by orders of magnitude. Admittedly, most of what I said was probably bullshit, as I know next to nothing about pathfinding, but as some other people have said, random ideas thrown around can spark off new thoughts in other people, generating valuable insights, so here's my personal brand of bull for your perusal.
Logged

Jay

  • Bay Watcher
  • ☼Not Dead Yet☼
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #69 on: January 18, 2009, 05:19:24 pm »

Also, some higher end processors that have Hyperthreading and similar tech would actually benefit from threading.
Higher-end single cores?  Doesn't have to be.  I have a low-end processor from 2005 sitting in my basement, 3.0 single, but it had hyperthreading.
Basically, a 3.0 hyperthread runs DF like a 1.5 duo.  Tried and tested with my laptop in parallel, which actually IS a 1.5 duo.  Both got the same performance, +/- a couple FPS.
So hyperthreads can and will benefit from correctly threaded pathfinding.
And as mentioned, single core processors are becoming rarer and rarer.  You can't buy them anywhere I've seen, for one...

As to the person saying we need more efficient code first; if I understand things correctly, basically since we're not copying the code over for multiple cores, just adding on by "telling the computer to use both cores" for what's already there (layman's terms, don't quote me) any changes Toady makes should be able to take place after this with no issues whatsoever.
Granted, there may be SOME incompatibility there, but the huge boost (double FPS for dual-cores is a serious possibility) a majority of us can get far outweighs whatever would need be changed, if at all.

tl;dr: We've got virtually nothing to lose.
Logged
Mishimanriz: Histories of Pegasi and Dictionaries

Footkerchief

  • Bay Watcher
  • The Juffo-Wup is strong in this place.
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #70 on: January 18, 2009, 07:17:14 pm »

tl;dr: We've got virtually nothing to lose.

Except opportunity cost, i.e. programming time that could be used for other things that Toady enjoys more.
Logged

bjlong

  • Bay Watcher
  • [INVISIBLE]
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #71 on: January 18, 2009, 07:29:05 pm »

That should be minimal, with Optimizt doing most of the legwork, right?
Logged
I hesitate to click the last spoiler tag because I expect there to be Elder Gods in it or something.

Footkerchief

  • Bay Watcher
  • The Juffo-Wup is strong in this place.
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #72 on: January 18, 2009, 09:00:57 pm »

That should be minimal, with Optimizt doing most of the legwork, right?

If that works out, yeah.  But it's sounding like it'll take a lot of work for Toady just to make the pathfinding modular enough that he can release the source, and without that, Optimizt will be in the dark -- and even if he produces something, it won't plug in neatly.  That said, I hope we can at least theorize some pathfinding improvements.
Logged

eerr

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #73 on: January 19, 2009, 03:25:18 am »

It would help if toady released the exact DF pathfinding code...
Logged

Sowelu

  • Bay Watcher
  • I am offishially a penguin.
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #74 on: January 19, 2009, 02:36:56 pm »

It's going to be massive work on Toady.  Justified but still huge.  No matter how Optimizt ends up helping out, Toady is going to own the final code, and be the person doing all the maintenance.
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!
Pages: 1 ... 3 4 [5] 6 7 ... 9