Print

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

[Jeoshua]

It doesn't need to make square rooms, it needs to make logical paths.

[NW_Kohaku]

It doesn't need to make square rooms, it needs to make logical paths.

Yes, pretty much.  It needs to be able to store a map of "highways" that represent the best places to funnel traffic down.  Whenever a dwarf needs to go a long distance, it needs to get to the nearest entrance to the "highway", follow the highway along to the local area that their destination is in, and get off and switch back to local movement to get to the specific destination they want to go to.

Cutting the map up into "square rooms" is just an intermediate step in making this sort of map, since the game needs to have some sort of way of breaking the vast amounts of map data down into managable chunks.

Basically, what we really need, however, is a system that only needs to do this sort of breaking the map up once, right at the start, and then allows the game to dynamically respond to the changes in the map, tile by tile, by checking only for local changes to the "highway" system that the game builds, and making changes only as necessary to maintain the integrity of the highway system.

[dwarf_sadist]

What there needs to be is a table or something for the AI to remember common routes. So when one dwarf finds the quickest way from dinning room to booze stockpile, the computer remembers it for the next time when 50 other dwarfs all start searching for booze at the same time. That way the computer does not have to calculate how best to walk the 37 steps x 50 for each dwarf. Instead, it checks (Stored path + extra distance) * 50 dwarfs.

[zilpin]

I'm pretty sure Toady already does this.

[Draco18s]

I'm pretty sure Toady already does this.

I'm pretty sure he doesn't.

[Starver]

Indeed.  People (some of them, anyway) aren't very upset about any necessary time take to make any particular path-finding search, except for the fact that it needs to be done every time.  Some very common paths could easily be cached, except:

• While it might be easy to throw-out and re-do a stock-pile to workshop path when the path ends up blocked, when does one realise the need for a re-cache of a quicker path when a short-cut is opened?
• Also, very few paths (except maybe between a 1x1 quantum stockpile and a workshop about to use now unforbidden items, and possibly the migrant edge-arrival point directly to the designated meeting area) have exactly the same end-points time after time after time.  Do you store one path for each point in a 10x10 stockpile?  Between every possibly food stockpile point and every single table?  Or sacrifice some of that final accuracy to "common point-to-common point" routing.[1]  This is one reason why a semi-cached "ultimately you always go through this zone at travel cost <foo>" look-up table is popular, the precise dtails of the travel through it to be worked out (at vastly less expense than while the trip would be still speculative) once there's general algorithmical agreement that it's necessary to sort out.  (Or, indeed, pull a zone-entrance to zone-exit cached path out from the known lists.
• Finally, multi-tile wide corridors get built for a reason, i.e. smoother traffic without having to crawl through oncoming traffic.  While I wouldn't generally say that any particular individual player layout styles should actually dictate the mechanics behind the pathfinding algorithm, to the extent of "it is currently considered good practice to use stairwell blocks, so optimise for stairwell blocks", it has to be appreciated that the player will have a small 'library' of common fortress 'tropes', and to restrict oneself to a pure-cached route that cannot deal with something as common as wide corridors without some kind of fudge[2] to handle this.

I suppose in some parts it depends on whether you want to accept a possibly sub-optimal path (especially as that would add an extra possibility or two to the "Dwarfs are Stupid" list) for fast game-playing, or whether you'd rather have a perfect path, every time.

You can add to either (or both?) of these two other requirements:

Firstly the possibility of needing to learn paths, which can either be done by Artificial Stupidity.  The computer knows the perfect path, but the agent knows that it shouldn't know the path so will work with what it does and then work to improve its knowledge, possibly by haranguing another nearby agent for the "information", a.k.a permission to realise that heading along one particular tunnel will take them to where the stone to be dumped is.

Secondly, dynamic response, architecture interaction and patience.  Not just "new path has opened, recalculate!", but "well, the bridge is up now, and it takes a long time to walk around the alternate route, but there's a pressure plate I can stamp on to lower the bridge for a moment, and if I'm quick (...although you can imagine the self-inflicted bridge-launchings and atom-smashings this might also cause[3]) I can get across and save myself a lot of walking".  Or the knowledge that magma-falls start and stop.  Or plain and simple sequential lever-operation to make an airlock-like route open.


Whatever, if there's limited/learned knowledge of routing for friendly agents, hostile ones are going to have the same possibilities to bustle their way through, a bit like certain friendly trader-nations can negate traps they know about after they've been pushed into becoming hostile.   Which is not to say that a "kill me!" dummy lever couldn't be added to kill off the more experimental of enemies, alongside the regular one for actually gaining entry.

[1] There are arguments for getting a selection of suitably known "to get there, starting from not-quite-here paths, run the "from here" path search until you encounter a point upon one or other of the paths then using the remainder of the cached route.

[2] "Hug the left" or "Hug the right" rules (possibly cultural as to which one gets adopted!) would help, here, and I think the current "which complex diagonal route to take" agent-pathing routine does give a taste of that.  Apart from dwarfs with different travel speed capabilities, it would mean you'd get an orderly progression of westward-bound dwarfs on one side of a corridor and eastward bound ones on the other side, for example.

[3] Sort-of-Mechanics suggestion: Klaxon.  In the above circumstances, link a lever (or other input) to both a bridge and a klaxon.  Klaxon has a quicker response than the bridge and blares out, and the dwarfs find out/learn/already know what this means and immediately vacate any danger area.  Other uses: general alarms (could even be tied directly into with military alerts, e.g. "enemies at south entrance!  Military get read, straight from pressure-plate activation", civvies get to safety!"), disturbing noise-makers (when you really want to annoy nobles), alarm-clocks for sleeping dwarfs ("come on, trader, get out of bed and get to the depot, before they leave!"), creature scarers ([CAN LEARN] or [INTELLIGENT] creatures get to ignore them, eventually, but at least at first they can be used to either repulse wildlife/etc or if set off behind them drawn them further into a zone you want them to be in.)

[NW_Kohaku]

There's basically no way you're going to be able to do something like having a dwarf learn that he's going to step on a pressure plate, and then will have only 100 frames to get across the bridge before it is raised.  That requires an abstract understanding of cause and effect that is way beyond the game's current level of AI sophistication.

Having dwarves "hug right" is a good idea, something I was thinking about regarding "highways", where you don't need one-way tiles, just three or four or five-tile wide "highway" hallways, where dwarves naturally hug right, and then step to the left to "pass" slower-moving dwarves the way that a car on the highway will pass slower traffic in the real world.  (Assuming we aren't dealing with island drive-on-the-left cultures.)

Doing this sort of thing isn't standard A*, however, you basically need to have the game recognize that you are dealing with a several-tile-wide "hallway" when you create something like that.

[ullrich]

What would be much, much simpler, and provide an optimal solution, as well as running very fast, would just be wavefront pathing.

An explanation of wavefront in there:

Spoiler (click to show/hide)

Making the Map:
1) find goal tile, cost = 0
2) Take all adjacent nodes of cost higher than current cost
2) Assign cost = current cost +1
3) Repeat step 2 from the new tiles.
4) stop when start is reached (or complete the entire map)[or when no more nodes can be added]

Pathing the Map:
1) Move to lowest adjacent cost square

Basically you can generate a "pathing" map of the entire map, that only needs to be altered when something physical changes the walkable tiles (i.e. bridge, locked door, etc).

Then the dwarf simply finds out is goal tile, and uses the associated map for that tile to find the cheapest adjacent tile.

It would be a massive improvement in speed at the cost of memory space, although may cause a "chug" when paths have to be recalculated (in general wont happen often, unless you have a repeater).

[Draco18s]

Except that it only works for any given goal.  It's also really CPU intensive as it ignores no tiles and every creature with a unique goal would need to build a weight-map.

[Niseg]

That wave front thing sounds like Breadth first search from the destination. My current program is similar to that - it find the first open upper left corner and  iterate through the whole maze aimlessly( I didn't tell it to find something yet) .  The problem with this kind of algorithm is that it's extremely inefficient especially if you don't limit your depth . This isn't going to work on a multi layer complicated maze like DF , we are talking about 192~X192~ per level for 4X4 embark .

The only reason I'm using breadth first search is to group nearby nodes so map segmentation would be logical rather than arbitrary. I recently made the BFS function have the ability to be iterative and soon I'll do a multiwave from multiple blocks (might share the visit array then I can scan for "mountains") .

I just need to add easy maze load save like ?maze= with a hexadecimal or b64 value . Then after it's somewhat more functional I can start experimenting all sort of pathing methods  .

So far I only added wall toggling on edges . I'm keeping it as simple as possible while being somewhat functional .

I'm might have mentioned it before but without a clear working algorithm like a computer program I doubt anything would come out of this thread.

[Artanis00]

I just need to add easy maze load save like ?maze= with a hexadecimal or b64 value . Then after it's somewhat more functional I can start experimenting all sort of pathing methods  .

You should do that. I'll add a mode that outputs to that format to this little script I made yesterday that generates random maps.

I'm might have mentioned it before but without a clear working algorithm like a computer program I doubt anything would come out of this thread.

True. I really need to study this stuff more.

[Niseg]

I just need to add easy maze load save like ?maze= with a hexadecimal or b64 value . Then after it's somewhat more functional I can start experimenting all sort of pathing methods  .

You should do that.

I just did    but the output is really long with hex but if you are well versed in binary you could almost see the maze  .
example:
http://niseg.0adz.com/test_maze.html?maze=0080008000800000FFF7008000000080EFFF008000010080FFF7008000000080

I can change that to B64 -the conversion is the same just 6bits at a time instead of 4 (did it on a damage calculator for infantry online). B64 would be 43 chars instead of 64. I might add some run length encoding into it but I think it's too much trouble for this narrow purpose (We aren't trying to rewrite DF in JS ). 

I'll add a mode that outputs to that format to this little script I made yesterday that generates random maps.

Python stuff ewww . I can probably convert that to JS - I can read pretty much any computer language . As I mentioned I like JS because it's easy to code in (for C coders) and runs on any web browser. I did notice that on mobile browser my page isn't working too well (not critical from my point of view but I might be able to fix it). I also added a code section generator to convert the maze into forum post-able (there is probably something like this in existence already that does the same thing).

I'm might have mentioned it before but without a clear working algorithm like a computer program I doubt anything would come out of this thread.

True. I really need to study this stuff more.

People at work saw my Algorithm book out and had memories . Learning is important part of my job. I usually remember what I learn but I only think we covered half that book .

[PartyBear]

Except that it only works for any given goal.  It's also really CPU intensive as it ignores no tiles and every creature with a unique goal would need to build a weight-map.

I think the idea might be for every tile to store a map of the distance to every other tile from the beginning.  If the maps never had to change, it would work well, but of course we can dig and build to drastically change the landscape, and to work perfectly, every single tile would have to recalculate its map every time you did something like lock a door or dig a tile, which would take a very long time.

But maybe it wouldn't have to work perfectly.  It should be possible to prioritize which tiles get their maps recalculated.  Priorities could be based on whether the tiles are associated with active jobs, how critical those jobs are, whether the tiles have items on them, whether the tiles are part of a stockpile, building, room, or burrow, and of course when a dwarf following an outdated map hits a dead end (on a side note, I like the realism that particular wrinkle could add).  Recalculating low priority maps could be done at low CPU priority, as well, or when the simulation is paused.  That kind of thing sounds like asking for multithreading again, though.  This pathing method would probably benefit even more from multithreading than the existing method, actually.

Also, only parts of the maps should actually change.  For example, if you cause a new tile to be walkable, you only have to look at the lowest cost tile adjacent to the new tile for the new tile's cost, and then calculate starting from there.

I can't say that all that would actually be enough to save your FPS, and it probably wouldn't be.  I'm just throwing it out there.

[NW_Kohaku]

But the major problems with nodal/hierarchical pathfinding, as far as Toady has expressed them, are the need to recalculate connectivity with every map change and not having to take up too much additional memory.  If you're going to try to come up with a better pathfinding system, you have to start off with the argument of why whatever it is you are talking about is better capable of reacting to unexpected changes to the shape of your map than standard A* with a connectivity map is.

[Draco18s]

I think the idea might be for every tile to store a map of the distance to every other tile from the beginning.

No, bad puppy, no cookie.  That's an O(n^2) function with regards to memory.

There are approximately 230,400 tiles for a 1x1 embark, and you want each of them to hold a copy of the entire map
(assuming 1 byte of storage to track tile location and distance, a 1x1 embark at the listed size would require 53,084,160,000 bytes of information, or 50,625 MB of information, and you want that information in RAM)

((A 2x2 embark would be 810,000 MB, and a standard 4x4 would be 12,960,000 MB, and the maximum 16x16 falls in at 3,317,760,000 MB (3164 TB)))