Print

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

[strainer]

Except for flying units, pathing is mostly across 2D spaces and mazes, so if the target position is on another level the pathfinders subtarget of first interest could the be the stair/ramps which tend best straight to target level.

some thoughts to scan and usurp with new...

Code: [Select]

  full_route_finding,
  stage_route_finding:
    beeline_till_bump...
    maze_crawling
      2d/3d 'step spilling' or algo* solutions
    hunch_following / waypoint reading and hopping
       waypoints/wayplaces are either
          deway :
            a 2d blob shape undefined, with a 'center'
          zeway :
            a cluster of stairwells/ramps with a center pos on self level
              and
            a vector of destination zeways
            that can be sorted by the count of times this zeway
            was taken to get to other zeways (on its zchain or beyond).
           
          zchain is a record of a chain of zeways which records
            the topmost and deepest zeway, to assist the search querys)
           
            so each zeways list of popularly connected zeways is created by
            fuzzy tallying (on good queries), the of number of times zeway was used
            to get to another zway
            and periodically sorting by popularity and pruned           
            to remove infrequently followed zeways (or waypoints...)

         nuway :
            unit can start near/in the scope of a deway
            or begin in a 'nullway' so make a new deway.
            (which is a wayplace) for its position.
            to get from a (observed&recorded) wayplace to a precise destination,
            unit can go straight at dest and check if it bumps
            or search seen wayplaces for adjoining, on its level
            or search seen zeways to stage to, to change level
            or panic and flail

notions:
dont impose uneccessary structure / limitations on waypoint connections
dont try to make them complete, or prune them too much

A list of (list of waypoints) per level,
contains an inexplicit abstract graph of
sparsely recorded observed routing data which
is useful for long range routing and
can be followed and updated during queries
from within its list-of-list-of-list structure:
  per level, per place, per dest level+place 
The inexplicit graph is optimised by occasional sorting and pruning
each waypoints note-list of observed destinations taken.
its possible to flag if wayplaces require 'maze walking' to traverse. 
Maze walking can be tried (and then followed or resigned)
Maze walks can generate sub wayplaces when successfuly traversed

nb of wayplaces per fort level : 30 to 300?
nb of way-destination-pointers-and-counts per wayplace avg : 5
 300*5 = 1500 destination hints per fort level
 @ 64 bytes per destination hint.
 so about 100kB per fort level required (maxish)
 @ 20 heavy levels conservatively 2 or 3 megabytes of this data for a big game,
common route queries would be guided through a small fraction of it
by those pruned and sorted links.

-=-=-=-=-=-=-=-=-=-=-=-=-
So I do apologise if that is all goblindegook.
I dont mean to start implementing the jazz,
Toadies solutions are likely tough to improve on.

[bloop_bleep]

I'm sorry, I don't quite understand what you mean by the "indices" that are stored? To be perfectly honest I only know how to implement the most basic versions of A* and Dijkstra; all the optimizations are completely unknown to me.

Also, I did the test you asked me to. This is the script I used:

Code: [Select]

local _ENV = mkmodule("pathfind_disable")

function disable()
    for i, u in ipairs(df.global.world.units.active) do
        if u.pos.x ~= -30000 then
            u.path.dest.x = u.pos.x
            u.path.dest.y = u.pos.y
            u.path.dest.z = u.pos.z
            u.path.path.x = {}
            u.path.path.y = {}
            u.path.path.z = {}
        end
    end
end

return _ENV

(It's worth mentioning that this world is modded, and heavily so (purely raws, no other DFHack scripts running.) It was pretty much the only one of decent enough population available to me when I started doing this. I could redo the experiment with another fort downloaded from the Community Games section, if you want me to.)

When I first loaded the game and unpaused, there was a 2-second freeze before everything started moving. The FPS fell from 100 to about 20 and stabilized there. I then loaded the script. I ran disable() once, causing all units to stop moving. Those that were mining kept mining tiles that were several tiles away from their position, and those that were doing workshop jobs cancelled them with the message "inappropriate building" and got reassigned jobs, which they completed normally. I did not notice any FPS change. I then imported repeat-util and ran the command:

Code: [Select]

ru.scheduleEvery("disable", 1, "ticks", pd.disable)
(where pd is the variable in which my module is stored.) This caused the FPS to plummet to ~10 FPS, though occasionally I would notice it would perk up to 37 or nearby briefly -- though this could just be because of the cancellation spam. Next I might try resetting their paths to something random, to see if that is the case.

[jeancallisti]

I'll comment on the performance tests later.

But I want to say this now:

Guys, don't get carried away with implementation. The core of the issue here is DF's implementation and read/write access to the world data, both CPU-wise and RAM-wise. So just completely forget about actual pathfinding algorithm for now.

Some people said that our attempts are probably useless because there's a bottleneck in memory read/write in native DF code.

I'm very skeptical about that, and here is why: DF's design makes it read world data a lot at every run of A*. our approach reads world data much much more at first, but then stores it in a separate memory area, and accessed the original world data very little afterwards. I think that modern OSs are able to optimize memory access from two different cores to two different memory areas. Not to mention that e completely shut down native pathfinder (hence not only the computations, but also memory read/write. Finally, our algorithm would index the shit out of world data. Very costly at first, but greatly reduces memory read afterwards. Therefore I think our approach reduces both CPU usage and memory usage in the native DF thread, and moves both to a separate thread. Then again the whole concept relies on the belief that the OS manages its memory access bus properly if two cores access different memory areas.

[PatrikLundell]

- Memory is a shared resource, with a single memory bus, so you can only have a single primary memory access going at a time (I haven't kept up to date with development, so it might be possible that the design has improved to keep multiple accesses in progress at the same time but in different stages. If so, it doesn't change the basic principle: it's not "nobody else is accessing this bank bank of memory, so I can do it in parallel", because there isn't a separate memory bus for each bank to each core. You can speed up some things by spreading data out over multiple banks because the banks themselves are slower than the memory bus, so data ordered to be read can flow at the same time as you order data to be read from the next bank). However, modern computers have multiple levels of cashes, where at least the outermost one is shared between cores and at least the innermost one is "private" to a core. Caches are much smaller than the primary memory, in particular the inner ones, so you can't expect to have much of the data cached.
- The only thing the OS can do is to determine which pieces of information to keep in which caches (and prioritize which processes get to access memory first, to some extent). You'd probably need optical computers to have multiple pieces of data using the same bus concurrently (by using different wavelengths, which is done today in optical fibers. It might be possible to use different polarization as well, but I'm not sure about that).
- Moving path finding to a different core will not reduce the CPU consumption of the DF core, but assuming it works, it would allow the DF 100% CPU thread to produce a higher FPS (only very early fortresses are capped by the FPS cap: thereafter the DF can't keep it running at full speed, so any savings would immediately be translated into a higher speed). That would still be quite useful, however.

Even if the investigation doesn't succeed in improving things it might still produce interesting results and insights, and so isn't necessarily useless.

[strainer]

I ran [paths_clear] once, causing all units to stop moving. Those that were mining kept mining tiles that were several tiles away from their position, and those that were doing workshop jobs cancelled them with the message "inappropriate building" and got reassigned jobs, which they completed normally. I did not notice any FPS change.

Since the all_path_clearing causes an increase in full path calculations over the next few steps FPS should get hit until the burst of 'repathing' is complete. The on screen FPS counter may be too smoothed to see that bump happening but not being able to notice a consequent slowdown suggests the long pathfinding is relatively inexpensive.
The pathing related processing budget may be more eaten up with deciding units response to its local environment and next movement.

[thompson]

Just a thought. You could probably save on memory traffic between RAM and CPU if you abstract the pathfinding to a limited number of nodes and ONLY direct the dwarf to the nearest node to the desired destination. Once the dwarf arrives there allow the native A* algorithm to take over the shorter final distance. I'd wager you could reduce memory usage to tens of kilobytes through that approach. Updating nodes would be more costly as you'd need to read the entire map, but that could be as infrequent as you like.

[Putnam]

pretty sure the game already does something like that

[bloop_bleep]

Just a thought. You could probably save on memory traffic between RAM and CPU if you abstract the pathfinding to a limited number of nodes and ONLY direct the dwarf to the nearest node to the desired destination. Once the dwarf arrives there allow the native A* algorithm to take over the shorter final distance. I'd wager you could reduce memory usage to tens of kilobytes through that approach. Updating nodes would be more costly as you'd need to read the entire map, but that could be as infrequent as you like.

Yeah, isn't that how A* works in the first place? Look in the direction towards the destination first, then do detours later?

[thompson]

Well, yes it does. But you could define nodes and pathing between them in a manner different to the native implementation. How really depends on what the OP wants to achieve, but I suppose you could do things like asymmetric routes between nodes so that dwarves travelling from A to B don't collide with dwarves going from B to A, or you could have a counter keeping track of traffic between different nodes and re-route dwarves to less crowded paths, or place penalties on nodes located in dangerous areas, or whatever else the custom algorithm is trying to achieve.

My suggestion was really to use the native A* implementation as a crutch to take the dwarf from their initial position to the closest node, then again from the final node to their destination. That would buy you a few 10s of ticks to run a CPU heavy memory-light pathfinding algorithm through your nodes on a separate CPU core. I don't know enough about DF Hack modding to know if that is feasible, or if it would work with whatever the OP wants to achieve, but it could be designed to minimise additional calls to RAM, which is (usually) the bottleneck.

[strainer]

I think the previous tests indicate that routine pathing doesnt take too long, except when changing bridges and cavern access causes the area connection tables to update.

A big complexity in this kind of simulation is discerning the collisions/encounters/interactions between things. The chance of encounters increases quadratically for the number of things in given space, hence 100 poults trapped in a room together can be a serious demand if not simplified.