Print

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

[Arx]

Good pathfinding is computationally expensive. Dijkstra's Algorithm, which will find a perfect path, runs in O(E + V*log(V)). In layman's terms, if your world is represented by tiles, and computing moving between two tiles takes 0.05 seconds, then running Dijkstra over a 4x20 room would take about 30 seconds.

(2*78 + 4*2 + 78*2 + 80*ln(80)) * 0.05

Of course, the computation runs much fast than that, but something like Rome: TW uses many more tiles. So people cut corners, usually with the A* algorithm, which can run a lot faster (a lot faster; Dijkstra is very slow, I just picked it because it produces an optimal path) depending on exactly how it's done. But of course, as you cut less corners, your time complexity goes up...

R:TW also has the quirk that as quite an old game, it was written for systems that would struggle to run expensive pathfinding algorithms. Your computer could probably handle significantly more complex pathfinding, but a ten (good grief, that's 2007? Alright, maybe 15) year old PC would grind.

[Neonivek]

One aspect is also that perfect pathfinding is also very... artificial. How many times when you watch people walk from point A to point B do you see them try to shave off every freeken inch?

[Felissan]

Oh come one, there's nothing wrong with a whole legion walking on a same line.

[Helgoland]

Actual human pathfinding is mostly local, no? And sort-of-local pathfinding should be less resource-intensive to boot. Maybe we should nag Toady about it...

[scrdest]

Also, at least the way it seems to me, human local pathfinding is less focused on optimizing for least distance, and more on minimizing sharp turns or avoiding high-cost moves (although A* can and for the latter, does, handle that too).

Hell, most modern game AIs use A* for the AI, not the sensu stricte pathfinding.

[wierd]

Local pathing means recalcing the path many times as obstacles are encountered though. That means dwarves could get stuck trying to dodge each other in the hallway. It also means more compute cycles burned to derive a path in total.

In humans, each human has discrete computational capacity that does not impact other humans. Dwarves have a shared computing engine they get time slices on.

Very important difference here.

[Helgoland]

Ah, but one could simply make the dwarves dumber when the CPU starts running hot.

[wierd]

Or, suggest toady implement local pathing as a multi threaded process, since each dwarf is acting independently, and thus finally get some multicore love in DF.

[Sergarr]

Good pathfinding is computationally expensive.

It can be made to be memory expensive for the end user, by using pre-computed experience-derived heuristics, which should make the computation costs roughly linear to the distances involved while still resulting in optimal or nearly-optimal paths. And memory is much cheaper than computation at this point.

[Egan_BW]

Or, suggest toady implement local pathing as a multi threaded process, since each dwarf is acting independently, and thus finally get some multicore love in DF.

So, population limit = number of cores in your machine. Great.

Good pathfinding is computationally expensive.

It can be made to be memory expensive for the end user, by using pre-computed experience-derived heuristics, which should make the computation costs roughly linear to the distances involved while still resulting in optimal or nearly-optimal paths. And memory is much cheaper than computation at this point.

But, because in DF the map can be altered during play, you'd have to remake the map every time a single tile is mined out or built on.

[Frumple]

... that sounds like something that would balloon either RAM or hard drive requirements. Possibly do horrible things to loading times. Please don't give them ideas. Devs don't need yet another excuse to throw efficiency out the window ;_;

E: In question news, anyone happen to know of a way to auto-append stuff to the end of web addresses from specific sites? General would be nice, firefox specific would be good enough. The specific scenario is I'd like to be able to stop manually typing &nohtml5=1 at the end of youtube addresses, since something or another they did quite few months back left that the only consistent way to keep that bloody godawful html5 shit from trying to boot up, and the various extensions that intend to force flash for the site are... not very good.

[Parsely]

Good pathfinding is computationally expensive.

It can be made to be memory expensive for the end user, by using pre-computed experience-derived heuristics, which should make the computation costs roughly linear to the distances involved while still resulting in optimal or nearly-optimal paths. And memory is much cheaper than computation at this point.

Lots of luck to the guy who gets to implement it.

[Sergarr]

Good pathfinding is computationally expensive.

It can be made to be memory expensive for the end user, by using pre-computed experience-derived heuristics, which should make the computation costs roughly linear to the distances involved while still resulting in optimal or nearly-optimal paths. And memory is much cheaper than computation at this point.

But, because in DF the map can be altered during play, you'd have to remake the map every time a single tile is mined out or built on.

Actually, no, you wouldn't have to remake anything. I'm not talking about pre-computed paths, I'm talking about pre-computed heuristics. Those are basically guiding functions that tell the pathfinding algorithm how long it'll take to reach point B from point A and, as long as the situation is close enough to what has been used during the pre-computation, it should remain valid with the map changes. At worst there'll be a minor increase in computation time as the pathfinding gets out of the newly created local minimum, but that's something the existing heuristics already deal with all the frikking time.

Good pathfinding is computationally expensive.

It can be made to be memory expensive for the end user, by using pre-computed experience-derived heuristics, which should make the computation costs roughly linear to the distances involved while still resulting in optimal or nearly-optimal paths. And memory is much cheaper than computation at this point.

Lots of luck to the guy who gets to implement it.

That's be probably Google. They've been moving quite fast with AI techniques, and their latest work, AlphaGo, has relied extensively on what was essentially a pre-computed heuristic, only instead of estimating a cost of the path remaining, it estimated the chances of victory. They should be able to easily move the results of their work into pathfinding proper.

[Andres]

From an ideological point of view, why do nazis and communists hate each other?

[Arx]

Good pathfinding is computationally expensive.

It can be made to be memory expensive for the end user, by using pre-computed experience-derived heuristics, which should make the computation costs roughly linear to the distances involved while still resulting in optimal or nearly-optimal paths. And memory is much cheaper than computation at this point.

Fair enough. R:TW is still probably too old to have high-quality pathfinding available though.