Print

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

[Moddan]

IIRC, pathing is already precached on a z-level basis (assuming I'm correctly interpreting what that is.) Doing it in 3D is much more difficult.

Pathing is one of the most ludicrously difficult problems in mathematics to solve without just exhaustively going through every possible path.

I'd love to read about some quest where Toady One encounters one of the greatest mathematicians alive on the planet, who has become an alcoholic or something and has nothing to do, and drafts him into service as a math thrall who gives him the magic to make all this FPS stuff from pathing just go away by giving him the scrolls of fast and slow in exchange for a bottle of rotgut.

The fact that it is even as good as it is is a testament to his own math genius.

What's Perelman doing at the moment?

[Reelya]

The answer to better pathing through a fortress might not be just to pre-cache everything, it's to chunk rooms etc together into a graph, then use generic A* to search that graph. Then you weight the edges at the high level against which paths worked last time. For example if you chunk areas together into 16x16 blocks then you're dealing with only 1/256th of the actual nodes to traverse at the "planning" level.

Then, you only use grid-based A* when trying to hit your destination within a node, which means that the data structure for that actually stays really small, e.g. 16x16.

[Putnam]

Quadtree pathfinding?

[Bumber]

Is that really suited to the small corridors of most DF forts?

Consider:

Code: [Select]

▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
++++++++++++++++▓ 17 tiles wide
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓+▓
▓+++++++<+++++++▓
▓+▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓+▓▓▓▓▓▓▓▓▓▓▓>+++
▓+▓▓▓▓▓▓▓▓▓▓▓+▓▓▓ No connection to other path
▓+▓▓▓▓▓▓▓▓▓▓▓+▓▓▓
What do?

[Reelya]

I was more thinking of something more akin to voronoi diagrams than Quadtree.

You flood-fill connected regions to make "nodes" then have a node-to-node graph. If the terrain in one node changes you just need to change that node and the ones it connected to, possibly splitting or merging nodes. That would be more of a "fluid" graph system that automates pathing around the actual architecture. Each node could have a number of pre-recorded "exits" to other nodes and it keeps a table of the exit-to-exit distances so that when path-finding the agent can use those as the metric.

But with the disconnected area, and e.g. pre-coding 16x16 blocks, you can in fact 'color' each non-connected area. e.g. the big area is zone 0, smaller unconnected part is zone 1, which is local addressing. So you can say "zone 0 of block 31/14 connects to the south to zone 1 of block 31/15" as your graph information. The most disconnected zones one block could have is 1/4 of the number of tiles - e.g. in a 16x16 block there could be no more than 64 stairways that pass through. So you'd need 6 bits for the zone code per tile.

[Bumber]

That might be close to how it already works. Found this post here: http://gamedev.stackexchange.com/a/32831

[Reelya]

Yeah that's the sort of thing i had in mind, but I didn't read any articles on it, I should probably read those.

Another cool thing is "flow fields". Basically, a flow field is often used in RTSs, "Tycoon" games, or anywhere many agents might want to path to the same goal. It works by doing Dijkstra's algorithm on the whole map starting from the goal, then any agent who wants to go to that goal simply looks for a lower number than their current tile and follows that.

For example, a good use of Flow Fields for a DF-type game might record "distance to the edge of the map" in every tile. Then whenever a new tile is opened or one is closed off, any adjacent tiles have their flow field recalculated, and if they change, then every adjacent tile to them is also added to the list of tiles to recheck.  Another flow field could be used for "distance to the trade depot". Then, anyone either heading to the trade depot or heading off the map never need to actually compute paths: those paths are pre-stored for the entire map. I've noticed a slight lag when large fortress sections are opened up, that might be because these sort of cached distance information values are being update in DF already.

[Bumber]

Flow fields are probably too much memory overhead, though. Too many places to go to.

[Reelya]

IDK, not too much these days. Say the flow field is 32 bits, and your map is 256x256. Then there are 64K locations per z-level, meaning 256 KB RAM per z-level. With a 256-level deep map then the total flow field memory would be 64 MB of RAM. If you make other assumptions about the bit depth, e.g. that distances over 65536 tiles are extremely unlikely - basically if there's a single tunnel that winds itself back and forth the entire length of the map 256 times, then we'll just do normal pathfinding, then you can use 16 bits per flow-field and only need 32 MB of RAM for 256 x 256 x 256 x 2 bytes. So, 32 MB per "place to go" under that scheme.

But there are other optimizations. e.g. knowing the distance to the goal isn't really important, because you already know "this is the shortest way". Flow fields only really need to encode direction. That reduces the need to 3 bits per field. Then, you can say that e.g. if my current field say "left" and the one to the left says "down" then i can look at that tile and just go diagonally down/left. Therefore you don't need to encode diagonals at all. This reduces the need to 2 bits per tile per flow field, so each "place to go" is reduced to 1/4th of a byte per tile. This means our 256x256x256 flow field can be boiled down to 4 MB per "place to go", and that's assuming we don't do any other clever optimizations that we could think of, such as heirarchical systems etc.

[Bumber]

Depends on how many "places to go" you end up having. Some 32-bit DF users have out-of-memory crashes already.

[Reelya]

Well in those cases they're sacrificing speed in order to squeeze out a slightly bigger map. It's questionable whether that's worth it. e.g. a 2-bit flow field to the edge of the map could take only 4 MB for a 256x256x256, and it prevents any agent who needs "leave the map" e.g. traders, visitors or invaders from ever having to run pathfinding, which itself takes quite a bit of memory. If you're having trouble running a map of that size in 4 GB of RAM then perhaps it's not the 4 MB for that flow field which is the limiting factor.

[MrWiggles]

Its not. Its the reveal tile and number of discrete objects on the map. Invasion take a performance hit nt because so many agents are trying to path, its part of it, but because the number of increase object.

[MorsDux]

just made a little test on my current fort with interesting results:
fort of 350 dwarves, 300 pastured animals and 30k items at steady 8 fps. When i destroyed 60% of items, fps was still steady 8. After that I destroyed 200 dogs and cats, and fps increased to steady 13 fps. Dogs and cats were each in 1-1 10x10 rooms pastured with tightly closed doors.

[Shonai_Dweller]

just made a little test on my current fort with interesting results:
fort of 350 dwarves, 300 pastured animals and 30k items at steady 8 fps. When i destroyed 60% of items, fps was still steady 8. After that I destroyed 200 dogs and cats, and fps increased to steady 13 fps. Dogs and cats were each in 1-1 10x10 rooms pastured with tightly closed doors.

Pet proof doors are known to be bugged. Pets try to path through them, kill fps.

[KillzEmAllGod]

The game runs pretty great since 64 bit came out, I remember back when I tried 16x16 ages ago I got less then one fps now on 16x16 areas I get close to the cap (being 150) but most of the time its around 40 due to animals pathfinding and can stutter a fair bit when new creatures enter the map.

Overall the game runs better then it use to and it helps to have a new system, I did end up with an i7 6700k and overclocked it to 4.4 ghz and disabled hyperthreading. Way better then that AMD Phenom II X6 1090T I had it was running at 3.72 ghz, even the i7 at the base speed was running 60% better.

The only real way to deal with fps death outside of the way you play the game or with mods that cut out the useless and redundant things is to get the hardware to deal with everything the game wants to check and recheck.