Print

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

[Yourself]

So say a farmer does not need to remember where these stone stockpiles are etc.

Then there will still possibly be multiple dwarves who do need to know that.  There's no way that storing the information with each dwarf could use less memory than having a master list of all paths that at least one dwarf needs (or knows).

[Draco18s]

Math!

Lets see...lets assume that every dwarf needs to know 4 locations:
1 Meeting area
1 Food/booze stockpile
1 Workshop
1 Stockpile with the associated materials for that workshop

And only these 4 locations.  4 locations is 6 paths.

Lets assume there are 400 dwarves.

400 * 6 = 2400.

This is slightly more than 1 master list storing ALL paths between 69 different locations (p = n(n-1)/2) and slightly less than 70 locations.

Realistically though you'll have dwarves that need to know:
1 meeting area
2 workshops
4 associated stockpiles
1 food stockpile
1 booze stockpile
1 Trade Depot
1 bedroom
1 main dining hall

12 locations = 66 paths * 200 dwarves = 13200 => Same memory usage as about 163 locations in a master list (13203 vs 13200 paths).  With 169 locations you could store every location in the fort EXCEPT bedrooms (we can fall back to A* for that as they aren't used often enough to store) and various places in the mines.

Why is this more memory efficient?  Because then you're not storing multiple copies of the data in 100+ different locations (such as Trade Depot to Food Stockpile).

[Impaler[WrG]]

No No No, I'm not talking about storing paths between all the locations the dwarf knows, I said store a Pointer (a C++ memory pointer to the stockpile and area objects).  They then generate paths TO those locations when they want something.    No path data is stored in the dwarf just locations.  Storing paths in each dwarf would indeed be too much.  I'm looking at maybe 10 max locations for each type and 20 types of objects for 200 data points which would be 4 4 byte pointers, 800 bytes per dwarf max possibly some additional overhead for structure.

If their is to be actual path data (probably in the form of an array of nodes/areas to traverse) then the dwarf would need to have a maximum limit on how many they hold.  Each end point of the path would obviously be a known point, when ever theirs a path needed they will look to their path list and see if they know it already, their would be some method to increment paths each time their requested and only the top X most frequently requested paths are stored.  Say the top 100 pairings of start/end points are kept in a list and the top 10 most frequently requested are solved to produce paths, each time the 11th most requested path bumps out the previous 10th place path the old path is forgotten and the new one stored.  Very much like the system posted earlier for global path storage but localized to each dwarf.

[Draco18s]

170 paths stored in memory: some unknown amount.
170 paths stored in memory + 12 1 byte pointers per 100 dwarves: 1200 bytes + some unknown amount.

Negligible amount, but that's storing just the path, if we store states on those locations ("wood stockpile was empty on the 12th of Granite 1053") you're adding another layer of information (figure 2 bytes more, 1 for date and 1 for data) that's another 2400 bytes.

[catpaw]

When dwarves have each their own memory, they should be able to give each other directions... and whats next an information counter dwarf in the main hallway? ... I don't know if I like the direction this approac his heading...

[Refar]

Do we know what internaly data structure is used to represent the map in fortress node ?

Someone mentioned a tool able to read out the map and save it externally - does it use the same data structures ?

[Draco18s]

Someone mentioned a tool able to read out the map and save it externally - does it use the same data structures ?

3Dwarf, yes.  I'm not sure if it reads it from RAM or if it reads the save file.  I haven't quite figured out what it does, but to me it looks like it reads the save, but uses the DF process to help.

[Impaler[WrG]]

3dwarf reads from RAM when the game is paused, each tile has flags for its material (empty space, granite, magma etc etc) and it just builds its own much simpler model from that for displaying.  Theirs some grouping of tiles into larger 'Cells' as I call them and it toggles rendering of a whole cell on/off as you move around the map.  I'm fairly certain the cells match up with the large area blocks you select when your choosing your map with U/M/H/K (5x5 area is default) and if you use a map-revealing utility to look at the minerals/veins underground its quite obvious that their being generated in that same grid pattern.  I don't know if these Cell areas are actually an object when DF is running though, they could just artifacts of map generation.  If they do exist at run-time then their a perfect starting point for the map-zone-heuristic path finding system.