Print

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

[alfie275]

Basicly if you have an area, sort of designated like a room, that you know won't change for ages you designate it to be 'chached' whereby the computer works out almost every path from one tile to another and saves it to a file, this would pause the game and display a progress percent. Maybe with access nodes that the pathing algorithm can check to get through the zone without calculating the path.

[Footkerchief]

There have been several threads on path caching already -- search the forums for "path caching" and "route caching" to find them.

Your method is essentially brute force and would spend gigantic amounts of processor time and storage calculating paths that will seldom or never be needed.  A smart system that only caches frequently used paths, as discussed in the other threads, would do a far better job of increasing performance.

[alfie275]

Yeah but I don' mind waitng a while to cache it all if I'm not going to change it, I can just do something else whilst it's doing it and then get better FPS.

[Impaler[WrG]]

Footkerchief is right you can't brute force store every possible path, once you get over a non trivial sized area it would exceed the amount of available RAM available on most systems.

[jockmo42]

Correct me if I'm wrong, but even if you were able to store all possible paths a creature can take in an area, wouldn't choosing a path out of the countless combinations be just as expensive at the pathfinding we have now?

[irmo]

Correct me if I'm wrong, but even if you were able to store all possible paths a creature can take in an area, wouldn't choosing a path out of the countless combinations be just as expensive at the pathfinding we have now?

Yes.

[Sowelu]

Correct me if I'm wrong, but even if you were able to store all possible paths a creature can take in an area, wouldn't choosing a path out of the countless combinations be just as expensive at the pathfinding we have now?

No it wouldn't!  If you index all "point A to point B" by length, then picking the shortest one is O(1).

If you wanted to say "Pick the path with the least traffic on it", well, you couldn't say that because you can't predict traffic before you get to a square so this wouldn't help anyway.  If anything, if there's a guy to your east and you want to go east, you'd be picking the fastest paths from the NE, E and SE squares while assuming the whole path is unoccupied, then add a small extra cost to going E.  Still O(1).

If you want to detect whether there's ten guys sitting in a one tile wide passage that's just a little bit shorter than the totally clear path...well, this won't have anything to do with that anyway, so forget it.

To summarize, no, you wouldn't need to brute force search for a best solution.  It'll work good for this actually.

[alfie275]

What I meant was storing it o hard drive, if thats possible, each path has a 4 number adress: Xa,Ya, Xb, Yb. When a creature needs to go from Xa Ya to Xb Yb it looks up the path.

[jockmo42]

Correct me if I'm wrong, but even if you were able to store all possible paths a creature can take in an area, wouldn't choosing a path out of the countless combinations be just as expensive at the pathfinding we have now?

No it wouldn't!  If you index all "point A to point B" by length, then picking the shortest one is O(1).

If you wanted to say "Pick the path with the least traffic on it", well, you couldn't say that because you can't predict traffic before you get to a square so this wouldn't help anyway.  If anything, if there's a guy to your east and you want to go east, you'd be picking the fastest paths from the NE, E and SE squares while assuming the whole path is unoccupied, then add a small extra cost to going E.  Still O(1).

If you want to detect whether there's ten guys sitting in a one tile wide passage that's just a little bit shorter than the totally clear path...well, this won't have anything to do with that anyway, so forget it.

To summarize, no, you wouldn't need to brute force search for a best solution.  It'll work good for this actually.

Of course, I just don't see how this way could possibly be more efficient than the pathfinding we have now. I can't see how caching every single possible path and choosing one every time a dwarf needs to move, and then recaching every single possible path every time the map changes... I don't get it. Maybe I don't get how this game works, but a method like this doesn't seem fast at all.

[irmo]

No it wouldn't!  If you index all "point A to point B" by length, then picking the shortest one is O(1).

Sure, if the path cache contains only paths that aren't blocked. This requires you to test every path when generating the cache, which you have to do every time the blocking state of the map changes.

[alfie275]

I did say "that you know won't change for ages".

[Sowelu]

Okay, ouch.  Good point on the map changing.

What I meant was storing it o hard drive, if thats possible, each path has a 4 number adress: Xa,Ya, Xb, Yb. When a creature needs to go from Xa Ya to Xb Yb it looks up the path.

BAD point.  Never, ever store things to hard drive when you're trying to make them faster.  Hard drive is around the order of, what, a thousand times slower than RAM access?  Maybe slower than that?  It can read at a good clip if it's reading a big consecutive chunk, but put "hard drive" out of your head.  It won't fly.

Besides.  Let's say you have a 2x2 tile map, and you only use the ground-floor Z-level.  Each tile is 49x49.  There's 92 million pairs of squares here.  Let's say each square just points in the direction of the next square on the list...that's still 3 bits, so 34.5 megabytes which I guess isn't too bad.

Now expand that to a 6x6 map, 15 z-levels.  1.3 million squares on the map.  1.7 trillion pairs.  4 bits for each one, because now up/down is also available.  Got 800 gigabytes handy?  Even if you did, it won't even fit in 32-bit addressing anymore.

[jockmo42]

I did say "that you know won't change for ages".

Still, we can't expect players to make a conscious effort to help the game pathfind. Telling them that they must designate areas for caching, and redesignate them every time they change, and if they don't, their game will slow down? That would piss me off.

[irmo]

I did say "that you know won't change for ages".

Still, we can't expect players to make a conscious effort to help the game pathfind. Telling them that they must designate areas for caching, and redesignate them every time they change, and if they don't, their game will slow down? That would piss me off.

There are probably some sensible heuristics you could use, e.g. if there are no dwarves working in an area and no fluid flows, go ahead and cache it. It doesn't cost anything to de-cache it later. On the other hand, those areas probably don't have much traffic anyway.

This is a fundamental problem with a game in which (1) pathing is highly diverse, with lots of creatures trying to find paths between lots of different points, and (2) the map itself is highly dynamic. There's really nothing to cache.

[sweitx]

Okay, ouch.  Good point on the map changing.

What I meant was storing it o hard drive, if thats possible, each path has a 4 number adress: Xa,Ya, Xb, Yb. When a creature needs to go from Xa Ya to Xb Yb it looks up the path.

BAD point.  Never, ever store things to hard drive when you're trying to make them faster.  Hard drive is around the order of, what, a thousand times slower than RAM access?  Maybe slower than that?  It can read at a good clip if it's reading a big consecutive chunk, but put "hard drive" out of your head.  It won't fly.

Assuming 2 GHz with IPC of 1 (instruction executed per cycle).  with typical hard-drive random access rate of 5.6 milliseconds
Typical Hard-drive access: 1,000,000+ cycles
Typical memory access:    10~20 cycles
Typical L2 cache access:   2~5 cycles (depend on architecture)
Typical L1 cache access:   1~2 cycles (depend on architecture)
In short, you want all cached path to reside in L1 cache (typically 64 kB) and L2 cache (typically 1 MB).
Interesting thing of note.  Memory access tend to be very fast if you access consecutive memory in a certain chunks (I think it's 64 bytes with starting addresses with lower 6 bits of zeros).  However, since optimal memory read length is variable, the best bet is to keep data structures that need to be read frequently in powers of 2 blocks (16, 32, 64, 128, etc).
Of course, there's a condition called cache thrashing, which occurs when you access the memory in an interesting interval (every 64 bytes for example).  So the best bet is try to avoid memory access (in short, when you starting working in a block of data, try to avoid touching another large block of data until your're done).

EDIT:

Of course, since the computer we use to run Dwarf Fortress is varied, Toady probably should not worry much about this.  Beside, cache manager in modern processor is much more advanced and can now handle a lot of complicated memory access efficiently (even pre-caching).