Print

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

[devek]

Well, its true you don't have to totally regenerate with any system. When someone digs out a room you just add to the nodes/mesh either way and optimizing it during spare cpu time.

What sucks (for any method)is when someone locks a door, currently you can feel DF hang for a second recalculating its pathfinding data.

Either way, your method will work and it is going in the right direction now. With a mesh or nodes, you're actually working with a proper graph now and this is where things actually improve. Feel free to burn as much cpu building/maintining your graph, in the end it is cheaper than traversing a suboptimal one.

[Niseg]

Well, its true you don't have to totally regenerate with any system. When someone digs out a room you just add to the nodes/mesh either way and optimizing it during spare cpu time.

What sucks (for any method)is when someone locks a door, currently you can feel DF hang for a second recalculating its pathfinding data.

I don't think it would hang for a second. With a non-caching method all you need to keep track of is weather a "room" is accessible or not. You should also consider the fact that the UI and user are significantly  slower than the back-end and CPU.  When you make a change you might want to go through  path validation but that's pretty quick on room paths(no guesswork either),  or let everyone hit the wall(like they do now.

 I think A* should be modified farther for this mode - it should consider the room shape and it's destination - it should consider nodes in other rooms to be blocked.  I can do that currently by quitting prematurely when it  start considering nodes that are significantly away from the target (it go to the closest ones first). It's too general and costly to do it this way.

Either way, your method will work and it is going in the right direction now. With a mesh or nodes, you're actually working with a proper graph now and this is where things actually improve. Feel free to burn as much cpu building/maintining your graph, in the end it is cheaper than traversing a suboptimal one.

It's not a matter of "proper" or not the current map is fine as a graph the problem is that it's really big and  too complicated. I've read in a book google scaned that they don't recommend using pure A* on "boards" larger than 60X60. What DF has in a 4X4 embark is a graph 192X192X100    or 3.7~ million nodes .  I'm not sure how Toady implemented his A* but if there is a dead end and you can  access to 1/10 of those nodes you are pushing 370000 nodes into a queue before you figure out it's a dead end.

The overlaying map model just leads A* to the right direction this way it doesn't get overly confused and kill your CPU. It also divide the A* of  a long path to many small A*s for short paths which spreads the load a little.

[Fieari]

Don't forget that we know that connectivity maps are ALREADY used.  Requiring a connectivity map for certain implications doesn't imply things will be slower than now, just that it won't necessarily be faster.  You can use bit flags to create a single number for combinations of different movement types, and it wouldn't be any slower.  I'm not sure how you can get around avoiding connectivity maps anyway, even with nodes.

[devek]

I don't think it would hang for a second. With a non-caching method all you need to keep track of is weather a "room" is accessible or not.

I meant, under the current system DF lags when you lock/unlock doors I'm not saying future systems will necessarily do it, but it is a case that will need to be described by your graph.

It's not a matter of "proper" or not the current map is fine as a graph the problem is that it's really big and  too complicated. I've read in a book google scaned that they don't recommend using pure A* on "boards" larger than 60X60. What DF has in a 4X4 embark is a graph 192X192X100    or 3.7~ million nodes.

Now we're starting to agree on stuff. Million of nodes isn't proper. Which is what goes back to my original argument, how you pathfind isn't a big deal. I can run a horrible algorithm, with no heuristic at all, over a proper graph faster than you can make the best algorithm ever scan over a non-proper graph.

Even putting the data in contiguous memory would have a bigger impact on performance than any other change you could possibly make in the pathfinding code itself. Right now to simply access a single tile, you have to dereference 5 pointers to get there. array->X->Y->Z->mapblock->data. Also, the 192x192x100 example you gave earlier has 14,400 mapblocks, with at least 2 vectors, a 512 alloc, 2=some 1024 allocs to go with each plus god knows what else that we haven't figured out and all of that is on the heap which probably puts around 100,000 items in the bucket allocator. Part of the main loop is that each of those 14,400 mapblocks has to be checked EVERY FRAME to see if the dirty bit is set. If the 16x16 mapblock is simply a #define statement and not based on actual code, changing them to 64x64 would make a bigger difference on performance than any pathfinding code change and only require changing 2 or 4 characters in the source. In many ways a 4x4 embark would become as fast as a 1x1 embark is now.. (not completely obviously)

The more you get into this, you will see why I hate people that are like, "derp, use this pathfinding function instead derp!" but you are clearly not one of those people now since you're analyzing the dataset so I like you now. <3

[Niseg]

I added a new search mode to a_star.js - searching in rooms (I may improve it to search for the next room instead of just a destination). This mode doesn't add nodes to the open list if they are not in the starting room or destination room . It only made it twice as fast in term of complexity. I also calculate complexity a little better by incrementing a counters on most loops (except the ones that adds neighbors) . It doesn't display it on any of the path caching algorithms but I'll add that later.

if you try my example. You'll get about 2.1 million for A* and 11502  for my newer no cache algorithm. A* is about 180 times more complex than my algorithm. When you consider the fact it makes a 13+1 subpathes the load spread out well with about 850~ iterations per search (my path smoother takes about 500 if you want to compare). The cache performance should also be much better than finding a huge path.

I'm thinking about optimizing the open set queue in A* so they insert stuff in order - it's about  log(n) insertion and O(1) (the best node is always in element 0). This should improve A* performance by a lot because it generally spends more time searching its queues than anything else . I might want to turn the closed set into another data structure like a hash table. Those improvement may help both algorithm run faster but it wouldn't affect the  potential memory thrashing of calculating many  extremely long paths.

[NW_Kohaku]

The more you get into this, you will see why I hate people that are like, "derp, use this pathfinding function instead derp!" but you are clearly not one of those people now since you're analyzing the dataset so I like you now. <3

You know, starting from the viewpoint that you hate everyone until they prove themselves to you is problematic in what is fundamentally a board for persuasive argument (and this is endemic to almost all of your arguments). 

Even putting the data in contiguous memory would have a bigger impact on performance than any other change you could possibly make in the pathfinding code itself. Right now to simply access a single tile, you have to dereference 5 pointers to get there. array->X->Y->Z->mapblock->data. Also, the 192x192x100 example you gave earlier has 14,400 mapblocks, with at least 2 vectors, a 512 alloc, 2=some 1024 allocs to go with each plus god knows what else that we haven't figured out and all of that is on the heap which probably puts around 100,000 items in the bucket allocator. Part of the main loop is that each of those 14,400 mapblocks has to be checked EVERY FRAME to see if the dirty bit is set. If the 16x16 mapblock is simply a #define statement and not based on actual code, changing them to 64x64 would make a bigger difference on performance than any pathfinding code change and only require changing 2 or 4 characters in the source. In many ways a 4x4 embark would become as fast as a 1x1 embark is now.. (not completely obviously)

Anyway, while building from the bottom up, as opposed to starting from the top down is all well and good, you have to keep in mind that these things still need to actually work. 

You cannot simply cut the map into a series of 16x16x1 grids completely without regard for what is actually contained within those grids and still have a connectivity map that makes sense, which was what Draco18s and I were talking about when this whole concept was first aired. 

Again, consider this scenario:

Code: [Select]

###+####+#######
###+####+#######
###+####+#######
++++####+#######
########+#######
########+###++++
########+###+###
########+###+###
########+###+###
########+###+###
########+###+###
########+###+###
########+###+###
########+###+###
########+###+###
########+###+###
This node connects to nodes north, east, south, and west of itself.  Let's say, for the sake of argument, that the node to the north connects both paths that lead to the north, but both paths that lead to the south do not connect without a massive amount of backtracking. 

Now, if all you do is have a graph that says "this connects to the east, and it connects to the west", then you have a problem if you assume that this means it actually connects east to west, and that dwarves can traverse it. 

Trying to limit the use of vectors is fine as an idea, but you can't actually cripple functionality to get there. 

[devek]

The more you get into this, you will see why I hate people that are like, "derp, use this pathfinding function instead derp!" but you are clearly not one of those people now since you're analyzing the dataset so I like you now. <3

You know, starting from the viewpoint that you hate everyone until they prove themselves to you is problematic in what is fundamentally a board for persuasive argument (and this is endemic to almost all of your arguments). 

It is a simple fact that pretty much everyone who starts a pathfinding/threading/64-bit thread does so without the knowledge of how DF actually works. Anyone who does know how DF works also knows there are bigger problems. When someone makes those suggestions it proves(to me at least) they don't know how DF works. I'll try not to be such a dick about it though hehe. The decision of what should or should not be worked on is up to Toady, and I don't have to tell him what needs to be done because he already knows. DF receives new features while getting faster almost every release.

Anyway, while building from the bottom up, as opposed to starting from the top down is all well and good, you have to keep in mind that these things still need to actually work.

Of course things need to work. In fact, when people face exponential slowdowns in their fort they are the victim of something that doesn't work. Saves before and after are asked for time and time again on the bug tracker, to no avail. There totally are cases where pathfinding or whatever might be broken, but without a save to demonstrate it it is pretty damn hard to do anything about it. I personally haven't experienced it in any of my forts in a very long time, and if I did I could narrow it down and fix the bug myself.

You cannot simply cut the map into a series of 16x16x1 grids completely without regard for what is actually contained within those grids

Lets make something very clear.. pathfinding doesn't know or care about what it is looking at it. It could be looking at a massive grid, waypoint nodes, vector meshes, or even the BGP table. All it sees are paths it needs to travel to get where it wants to go. The reason I suggested changing the mapblock from 16x16 to 64x64 has nothing to do with pathfinding, since the pathfinding function itself doesn't even know the size of a mapblock. The 64x64 thing is just an example of memory optimization that would beat the snot out of anything pathfinding related while potentially only requiring the changing of 4 characters in the source. At the end of the day, pathfinding would have to process the same amount of data regardless of how the map was broken up if broken up at all.

I'm very certain Toady knows there needs to be changes to the dataset, and I am certain he has good reasons for not working on it right now. He hates putting bandaids on things, and he can't really rework the entire dataset without knowing what it needs to accomplish. DF is far from done, and having to rework the entire system all over again in order to add a new feature would suck and not be fun. The current dataset is flexible enough to do just about anything, and there is no evidence it is responsible for the exponential slowdowns. At the end of the day there are still huge performance gains to be made that have nothing to do with anything we are talking about, and those gains are made in every DF release. I have no reason to complain.

[Draco18s]

Lets make something very clear.. pathfinding doesn't know or care about what it is looking at it. It could be looking at a massive grid, waypoint nodes, vector meshes, or even the BGP table. All it sees are paths it needs to travel to get where it wants to go. The reason I suggested changing the mapblock from 16x16 to 64x64 has nothing to do with pathfinding, since the pathfinding function itself doesn't even know the size of a mapblock. The 64x64 thing is just an example of memory optimization that would beat the snot out of anything pathfinding related while potentially only requiring the changing of 4 characters in the source. At the end of the day, pathfinding would have to process the same amount of data regardless of how the map was broken up if broken up at all.

Except that it matters.  In the case NW_Kohaku outlined, lets say a dwarf is traveling from the west to the east and passes through that block, and the one north of it (due to the two north-passages connecting there) and the one south of it (which leads east).  At least, that's the path that exists on the tile-level that we, as humans, can see.

The initial assumption about that block is West-side, this one, east side.

Except that no path actually exists there.

So it goes West-side, this, north, this, south (etc.).

"Wait a minute," the pathfinding algorithm says.  "We have a loop.  The path passes through this same node twice."  And it simplifies it: west-side, this, south (etc.).  Except that, once again, no actual path exists like that.

[devek]

I had to read that like 5 times to get what you guys were saying..

Are you saying that the mapblock itself is a node? If you are I can totally understand what you are saying. If you are not, disregard the rest of this post hehe

DF mapblocks are simple organizations of data inside of computer memory, they can't be nodes for the very reason you're saying. The pathfinding function doesn't look at mapblocks to find where it is going, it only looks at mapblocks to access the data inside of them. It would work the same regardless of if the mapblocks existed at all. If something I said sparked that confusion, I am really sorry.

You can either use each room as a node, or generate waypoints/vector meshes/rooms like Niseg/global and local connectivity maps/etc over the entire dataset and use those as nodes. The actual pathfinding works the exact same no matter what, and doesn't actually know or care what it is being given.

[Draco18s]

I had to read that like 5 times to get what you guys were saying..

Are you saying that the mapblock itself is a node? If you are I can totally understand what you are saying. If you are not, disregard the rest of this post hehe

It has been suggested to use the mapblock (or similar data structure as a mapblock) as a node that gets passed to A*

[devek]

Oh, well that is a bad suggestion. My brain is horrible at handling irrational thoughts, so if someone suggested it I probably didn't even see it.

I mean, how would that even handle fliers/magma walkers/swimmers? Hell, you could make the entire map off-limits to non magma walkers by putting a single piece of magma in each mapblock.

[NW_Kohaku]

Alright, sorry, I was thinking you were talking about merging mapblock data and pathfinding into the same set of data.

Designations are a separate 16x16 array per mapblock from the pathfinding data, they are for... designations like digging or channeling and such If it was up to me, that data would be replaced with a designation list but whatever hehe.

Right here I mean, it looks like traffic is stored as part of the designation data: https://github.com/peterix/dfhack/blob/master/library/include/dfhack/modules/Maps.h#L300

Or maybe I'm misreading.

No, you're not misreading *facepalm*. If that is true, then it means DF might be accessing more data than it needs to lol. The designation data for a mapblock is stored in a different memory allocation than the pathfinding data...

I had assumed it was packing all the data it needed for pathfinding into the pathfinding data :/ That still might be the case though, the traffic designations might be stored in both which wouldn't be a problem since its just 2 bits.

If you were just talking about storing mapblock data, however, 64x64x1 z-level mapblocks can run into problems... what if you have a 2x2 embark?  That's 96x96xz tiles, which means that you have to use 4 sets of 64x64, with 7168 tiles of "overlap" that contain no data per z-level. 

I'm not actually even sure how Adventure Mode works, either.  I know that pathfinding is much easier for the system in general in Pathfinding mode, since right now, almost nobody does any pathfinding, but if we are introducing cities where, potentially, we have random peasants deciding they need to pathfind to a point in the city outside the currently loaded section of the map, we need to have some sort of system that allows for both abstract and observed travel, where different blocks of the map come into "focus" and then back out into abstraction again.

If we are dealing with a map where the size of the "chunks" of map expand in 48-tile increments, the size of mapblocks should be a denominator of 48.  Otherwise, it just becomes problematic when you are adding or subtracting chunks of embark tiles from the "view" of the computer. 

The same goes when we are considering "moving fortresses".

Anyway, right now, the one true failure of the current A* system (which is to say, disregarding lag, and only focusing on the functions it seriously cannot perform) is that it doesn't actually support multitile creatures at all, and that it doesn't support swimming or flying creatures very well.

The problem with how much lag the HFS produces is that fliers seem to actually use BFS over the entire map every time they try to pathfind, even if all access into the fortress is blocked.  That means flood-filling the HFS (at least) every frame for every creature. 

At the very least, we do need a system capable of handling more flexible movement types and it would make sense to build the system in a manner that allows for abstract overland travel and "watched" travel to be swapped in and out as the player may or may not "follow" an AI that is set to travel overland in an abstracted path, forcing it to switch to "watched" travel.

[devek]

Alright, sorry, I was thinking you were talking about merging mapblock data and pathfinding into the same set of data.

Aha! I was, sort of.. let me explain.

The mapblock data includes pointers toward data like desginations and pathfinding data. I don't think anyone has quite figured out what all the bits in the pathfinding data represent, but it seems imply things like a "flyer can go here", "a building destroyer can go here", "a magma walker can go here", etc. The traffic designations are stored in the designations data. A memory optimization would be to put the traffic designations into the pathfinding data(its just 2 bits), if would save a pointer deference and a memory read for each traversed node. I wasn't trying to say that the mapblock itself should be a node, and I apologize for not being clear (I suck at English).

If you reread the part I wrote now, it should make more sense. I was wanting to consolidate data inside the mapblock or even the mapblocks themselves, not use them as a node hehe. The gains for doing so would be pretty big and require few changes in the code compared to reworking entire systems.

If you were just talking about storing mapblock data, however, 64x64x1 z-level mapblocks can run into problems... what if you have a 2x2 embark?  That's 96x96xz tiles, which means that you have to use 4 sets of 64x64, with 7168 tiles of "overlap" that contain no data per z-level.

I should have said one embark tile and not 64x64.. For some reason I was thinking 4 mapblocks per embark tile. My mistake. 

Anyway, right now, the one true failure of the current A* system (which is to say, disregarding lag, and only focusing on the functions it seriously cannot perform) is that it doesn't actually support multitile creatures at all, and that it doesn't support swimming or flying creatures very well.

Multitile creatures are solved by vector meshes, they can't travel through nodes that are too narrow or not tall enough. Also consider that many times pathfinding won't be necessary at all with vectors (if the target is in the same node, the dwarf can just walk a direct path to it). Swimming and flying creatures seem to suffer from bugs more than any flaw in the system. It is really hard for hackers to debug that type of interaction without the source :/ We can do it, it just takes more time than we like to spend :/

The problem with how much lag the HFS produces is that fliers seem to actually use BFS over the entire map every time they try to pathfind, even if all access into the fortress is blocked.  That means flood-filling the HFS (at least) every frame for every creature.

*** The rest of this post is addressing a worst case situation. Few forts breach HFS without the intent of fighting them off. ***

Possibly flood-filling the HFS for every dwarf in your fortress for every creature that is in HFS hehe. 200 dwarfs and other creatures in/above your fort, 20 HFS without access to your fort, and half a million tiles in your HFS? 2,000,000,000 possible node operations per frame lol.

I still defend my position that it isn't a flaw in the pathfinding code. It isn't the pathfinders fault if it is being called unnecessarily. HFS creatures shouldn't be so aggressive that they seek targets every frame, if they are that should be fixed regardless of how anything else works. A nice bandaid optimization would be the storing of z levels searched during pathfinding when looking for dwarf A, then checking if dwarf B was within those z levels before trying to path to it.

The proper fix is fixing the dataset, but maybe that isn't wise during this stage of game development idk. There are problems with the dataset that hurt more than pathfinding, and Toady is aware of that. DF didn't always have Z levels and so many features have been tacked onto a once basic system. In the average case it isn't a big deal and it is flexible enough to do anything. In the meantime there are many other pressing issues when it comes to performance(mainly bugs) but at some point, it will be looked at. I just hope vector meshes are considered when that day comes, because tons of game developers make the mistake of not using them (even huge well funded ones) :/

[Fieari]

Once an HFS finds a target, I don't believe they continue the BFS every frame, but I do believe they will seek a target until they find one-- and I don't necessarily see anything wrong with that.  It could be and should be improved with a proper set of connectivity maps that take fliers into account, of course, but the aggressiveness isn't the problem.

HFS can be walled off once breached, which causes severe slowdowns.  Furthermore, there are MASSIVE numbers of HFS, and they respawn (albeit slowly).  This causes a LOT of said BFS.

Regardless though, the key here is to make a pathfinding system that is efficient for ANY movement type-- walking, flying, swimming, magma... heck, add in digging, climbing, maybe even jumping... and while we're at it, might as well add in multitile movement as well.  It must be robust to handle these kinds of things.

[devek]

Once an HFS finds a target, I don't believe they continue the BFS every frame, but I do believe they will seek a target until they find one-- and I don't necessarily see anything wrong with that.

There is a lot wrong with that(if that is the way it works).

Think about your computer for a second, it is controlled by an operating system that runs processes. The processes can ether be event driven or they can can poll. Notepad for example is event driven, it never does anything until the operating system tells it there is something to do(user typed something on the keyboard notepad, do something about it). Windows update for example polls, it wakes up at certain intervals and sees if your system needs to be updated. If windows update was constantly checking to see if your computer needed to be updated, it would be using up 100% of your cpu all of your time slowing down the rest of your machine. How often a polling process checks to see if it has something to do is referred to "aggressiveness". If windows update was too aggressive, it wouldn't be the fault of the update code it would be the fault of how aggressive it was trying to update.

Game design works the same way. Enemies are logical processes inside of your game, if they are spending all of their time looking for something to do that will slow down your game. Just like windows update, you need to tell them to chill and only check for work as often as necessary.