Print

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

[thompson]

I have a very technical question that is very important for FPS optimization.

How exactly are pathing maps implemented in fort mode? Presumably there are maps showing which tiles can be traversed and describing movement penalties. Are they contiguous along the x-axis, then built up along y and z axes respectively in memory? Is the map sub-divided into smaller contiguous arrays coinciding with embark zones?

I'd like to minimize memory traffic between the CPU and RAM, so if anyone knows this I'd appreciate the help.

[Fleeting Frames]

It's modified A*, with, indeed, topologies of connected shapes. Unlike with dwarf relationships, all paths are bidirectional.

The initial stuff is often picked as the dwarf digs, though.

The map is subdivided into smaller 16x16 block columns, but not for pathing but cavein/reveal calculations.

Oh yeah, there's static pathing map generated on embark/reclaim/unretire, which plays nice with construction but not so well with digging.

[PatrikLundell]

As far as I understand, restricting the number of potentially available paths is beneficial to the FPS, which results in a recommendation to close off sections of the fortress where no activity should take place with locked doors (or a wall). When dorfs bump into each other they repath (apparently to the place where they met, rather than to the destination), so well traveled passages should be at least two tiles wide (you can get silly results with two available single tile paths where both parties meeting turn around, bump into each other in the other passage, turn around...). If there's no available path (or the alternative is too long a detour [I don't know how far "too long" is]), one of them lies down on the ground while the other one climbs over the prone one when they meet.

In many cases it seems the selection of the target is done as the dorf digs, and the path is then calculated properly to that location. It also seems multiple targets are selected according to the "as the dorf digs" method based on the starting position rather than the position of the previous position on the path (e.g. picking up food and then a table at which to eat it). There is, or at least was, a stack based tendency, i.e. the latest rock dug being picked up for processing rather than the closest one. This was tempered by the jobs rewrite 1 ½ years ago, however.

The above obviously doesn't answer the question (Fleeting Frames did that), but it's relevant to what I think you are trying to achieve.

[Hyndis]

As far as I understand, restricting the number of potentially available paths is beneficial to the FPS, which results in a recommendation to close off sections of the fortress where no activity should take place with locked doors (or a wall).

Go for constructed walls rather than doors. Pets may try to path through doors, and building destroyers will see doors as juicy targets. A constructed wall is an impassable barrier to everyone.

The other thing is that items are all calculated with pathing as well. One of the best things you can do to keep your FPS high is to limit the number of items you produce. This means you want your stocks menu to be as lean as possible. You want as few metal bars, as few stones, as few clothing items as possible. Make just as many as you need, but no more. Any excess dump into the magma chute.

Note that you can have your clothing stockpile also be a refuse stockpile, which will automatically rot away all stored clothing to nothing. It vanishes. You do have to continually produce new clothing though. If a dwarf needs new clothes they will pick it up immediately as its produced. Any excess will be stored and decay away to nothing.

[PatrikLundell]

- Pets will see doors that are pet unpassable only (but passable by dorfs) as passable, and thus subjected to the pathing bug.
- If the enemy has reached the deep internals of my fortress to attack doors there I've lost anyway, and it's not to FPS.

The number of items in a fortress affects the FPS, yes, but the pathing part is "only" as the dorf digs, and I suspect other maintenance of items (such as wear) is a larger drain on your FPS than pathing to the items.
Regardless, keeping the number of items down is good for the FPS, although I dispose of junk via the garbage truck service (a.k.a. caravans).

[Fleeting Frames]

I think Hyndis meant the building destroyers will see doors across map as juicy target, not that they'll be able to actually reach it.

I'm not sure how pathing and items relate, but it is clear that paths are calculated whenever you decide to pick materials to build something, and probably at least something is done in stocks menu, given the lag when you scroll over 10k logs in items or whatnot.

[PatrikLundell]

The stocks menu has to count the items as a minimum, and I wouldn't be surprised if it built the detailed item list at that time (rather than waiting until you tab to it).

[Fleeting Frames]

The item lists are already kept and sorted at df.global.world.items.others, though I suppose maybe it does rebuild evrytim due bookkeeper.

[Thisfox]

Note that you can have your clothing stockpile also be a refuse stockpile, which will automatically rot away all stored clothing to nothing. It vanishes. You do have to continually produce new clothing though. If a dwarf needs new clothes they will pick it up immediately as its produced. Any excess will be stored and decay away to nothing.

I tend to box my XclothingX up and sell it to the merchants. Is that causing mayhem with my FPS, or when sold, is it gone as good as when it disappears in a refuse stockpile or magma pool?

[Hyndis]

I tend to box my XclothingX up and sell it to the merchants. Is that causing mayhem with my FPS, or when sold, is it gone as good as when it disappears in a refuse stockpile or magma pool?

Selling stuff to merchants also works. Once its off the map or destroyed its gone. Dumping into the magma ocean is also a great way of permanently getting rid of items.

Having too many items can really bog down your FPS. For example, if you have 10,000 metal bars, every frame every smelter and forge will check all of the available metal bars to see what can be pathed to in order to fulfill those active jobs. This pathing check is inevitable, but trying to path to 100 bars is a lot easier than 10,000. Same goes with stone and workshops that use stone, stored plants and plant using workshops, etch. It multiplies out by how many workshops you have and how many items the workshop is looking at. Having lots of workshops and/or lots of items causes this to balloon out of control rapidly. Keep those stockpiles as small as possible and try to use as few workshops as you can manage.

Clever use of the job manager screen lets you set up a just in time system where items are produced on demand but only as needed, and even better this system can run automatically so long as you set up your job conditions correctly.

[Quietust]

For example, if you have 10,000 metal bars, every frame every smelter and forge will check all of the available metal bars to see what can be pathed to in order to fulfill those active jobs.

I'm pretty sure that's wrong - for regular workshop jobs, the game only checks for available items when it needs to, which is when the job actually starts (and after each individual item is brought to the workshop), when a configured Work Order's conditions are being checked (every 1200 frames for a "daily" order), when "automatic job" standing orders are checked (e.g. Auto Loom, which I believe is once every 100 frames), or when you open the "Add Job" menu (so it can show the job names in Red if you can't perform them).

Furthermore, it's not going to be doing real pathfinding - all it's going to do is check if each item's coordinates are in the same "connected region" as the workshop and/or worker, and said "connected region" information is only updated when the map itself changes (e.g. when you dig a tile, build a construction, or open/close a door, hatch, floodgate, or bridge).

[thompson]

Thank you all for the suggestions. It's given me a few more ideas for optimising fort design. I was a little concerned that the game would try and load too much of the map in memory at once, but if I understand it correctly the pathing algorithm should only require the relevant regions in the connected shape once it has already determined large-scale movement.

 Essentially: Minimise pathable area and minimize item count.