Print

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

[Niseg]

Just to point out:
You've always been choosing a room division size in order to convenience yourself.  You're not allowed to chose the "best case scenario" for each example.

For example, what if the first step returned this?
[...]
What it the rooms were larger (rather than the quick and dirty 2x3 rooms I made)?

[...]

You know, it's pathetically easy to write code that can flood-fill and detect rectangular areas? Bigger size rooms will make any node or room-based search algorithm far more efficient than pure A*. It's the small rooms / close packed where you would see less % improvement.

You should check previous page . Shape is no longer an Issue(using a bit vector). you can floodfill any shape using  a depth limited Breadth First search the issue is where to start and not to miss any open space. my idea for room splitting is this:

-arbitrarily divide  map  into flat squares
- block off each square with walls and make sure every node in it  can reach any other node.
- split  unreachable areas into new rooms
- make a connection graph between rooms (you can do collision detection BFS)
- merge smaller rooms into larger rooms with some size limit. It might be smart to keep ones with up/down access as exceptions.

Then when you search for a path you look for a room to room path. instead of a point to point path.

This is a better system than waypoint based path caching but it takes more work to add . I'm going to add this method to my JS demo but it would take me some time to do.

[Sunken]

Have each room / hallway keep a list of 'portals' - i.e points or zones connecting to the next room/area. Straight-line pathing can route dwarves from entrance to exit through a zone. No need to declare a specific path - the dwarf uses straight-line pathing through each zone given the constraint that zones are contiguous recatangles this can be done in realtime very fast.

How will you define the cost of moving from one portal to another? How will you define the A* heuristic?

[Talonj]

If I'm reading this thread correctly, there are three major ideas, each of which seems misunderstood by people discussing the other ideas...

The first is NW_Kohaku's hierarchical structure, which I don't fully understand myself.
Second is Niseg's, which I'd like to elaborate on a bit:

On embark:
1. Split the map into arbitrary N x M x O rectangular prisms (perhaps set as an init option, I will refer to them as cubes for convenience)
Then, for each cube:
2. Run Niseg's BFS search idea on a random node to ensure all open space within the cube is reachable.
3. All tiles highlighted by this BFS search are assigned to a node.
4. if there are more open space tiles left, go to 2.

Now you have a significantly smaller map to search through to find a general path, though each individual tile will still need to be searched for the actual path.
Use cases for this idea:
A) Mining a tile
1. Update the adjacency map (current system, discussed earlier in the thread)
2. Check all tiles adjacent to the current tile AND within the mined nodes cube.
3. Add this tile to the first found adjacent node.
4. If there is another adjacent node within the cube, combine the two nodes.

B) Pathing from a mason's shop to a stone
1. Find the stone using the item finding heuristic
2. Look at what node the tile the stone is on is in.
3. Look at what node the tile the dwarf is currently standing on is in
4. Use A* on the node structure to find the ideal path to the object, if this fails there is no path
Then, on each individual node:
1. If the item being searched for is NOT in the current node: from the algorithm's current position (initialized at the current position of the dwarf), use the item finding heuristic (restricted to the set of "all tiles on the edge" for the node) to find the nearest tile marked as an entrance into the target node OTHERWISE path to the square (containing the item) already found in the last search and end the search
2. Take one step toward the next node in the sequence, putting you inside that next node, then return to 1 until search ended

Notes:
 I chose arbitrary blocks to swiftly streamline the creation of nodes. If nodes were allowed to grow to arbitrary size, then the process of breaking them up into blocks small enough to be meaningful while also large enough to be effective would become significantly more difficult. There are certainly ways to create more efficient nodes, however there is not a more efficient way (That I can think of) to create nodes in general.
The other reason for arbitrary block size is that it allows a uniform "cost" to be assigned to each node and still have a reasonable closeness to the true cost of pathing through the node. Yes, this will result in sub-optimal paths being used, and used frequently, but the speed at which the paths will be found will improve significantly. You COULD save the true cost between every pair of nodes, but that's using a lot of memory, because one node can connect to quite a few other nodes, even with the "block" limitation.
Also, if the cube size is set as an init option, you can go as low as 2x2x2 and still reduce the number of total searchable nodes (compared to the current system) by anywhere from a factor of 2 to 8. As the cubes grow smaller, the possibility for winding paths and such grows smaller, which makes each node having the same cost more likely.
edit: Also, this would unfortunately significantly hinder the benefits of current pathfinding designations. The only feasibly quick way to do it would be that either the lowest or the highest of all path designations would be applied to the whole node. Or it could be done by the count of such designated tiles within the node. Also, while I was realizing this, I hit upon an idea... Apply the same concept to individual objects. Have each node have the status that it "contains microcline blocks" or "contains steel bars" and then use the overall heuristic based on the nearest node to do this. Depending on how the nodes end up being laid out, it might end up being feasible to do a BFS from the dwarf's current node to the first node found containing the material he's looking for. dwarves that know the specific destination they're pathing to, such as the bedroom, would obviously use the A* heuristic method, but the manhattan distance item finding heuristic has bothered a lot of people.


To summarize:
This algorithm will require each node to keep track of each exit to another node from each individual tile.
This algorithm will significantly improve the WORST CASE in A* of searching down every path with the manhattan distance heuristic. It will instead search down every dead end node, and since there are a logarithmically smaller number of nodes than tiles, this is still MUCH faster.
This algorithm will NOT improve the best case, since you still need to A* through each individual node, once the general path is found.
The overhead from this algorithm is relatively small, but it does not replace the current system, only adds to it, which means it is GUARANTEED to add at least some overhead. (You can of course do it in different ways that may replace the current system, but I don't know if they'd be faster. Feel free to call me out on it if there is a faster way)

Note2: Yes, this says almost exactly what Niseg's last post says, except with cubes. I just wanted to add on use cases for creating a new tile / using the grid to make it more readable, and also point out that it does not improve the best case, unlike what follows.

The third is Mohicans, which bears many similarities to Niseg's, but is fundamentally different.

The primary difference is in the use of convex polyhedrons, allowing the elimination of A* on a tile-by-tile level. The problem is in the creation of these convex polyhedrons. The problem does not, as some seem to believe, lie in creating nodes from already dug out rooms -- The problem is to create nodes while digging out rooms. Niseg's idea makes it easy, because there is no prerequisite for a tile being included in a node, you just check for an adjacent node and add to it. However, with this idea, unless a highly efficient algorithm to create and merge nodes is used, the overhead may outweigh the benefit, and the benefit may be mitigated by highly suboptimal shapes.
However, with that said, I highly favor speculation on this idea, because it would vastly improve pathfinding overall, as the vast majority of A* searching would be eliminated entirely, since instead of searching through each node, you simply walk in a straight line to the "gate" to the next node, because the whole point is that the nodes are designed in a way so that there is no pathfinding needed to traverse them, just a straight line.

I can elaborate more on this for people who don't understand (as this is the best idea if an efficient method of creating effective nodes can be found). I just don't have the time right now to demonstrate exactly the faults with currently suggested methods of creating these nodes.

[NW_Kohaku]

The hierarchical structure I was talking about is just a method of using search trees as a data structure to organize the connectivity of nodes and speed up inter-node pathing.  It doesn't have anything to do with intra-node pathing or zoning.

Basically, I was thinking of a Binary Search Tree as inspiration for it, and how that helps speed up searches.

Instead of making a standard connectivity grid for nodes, and then using a pathfinding program to search for a path, you create a tree data structure where connectivity is recorded in the pointers from one branch in the tree to the next. 

Searching a tree data structure is much easier than trying to pathfind through them, so it can abstractly find a set of nodes to path through very, very quickly with the minimum possible number of memory fetching. 

The data structure itself would kind of get bloated with pointers, depending on how you want to set it up - you basically can trade memory for speed and making better pathing decisions.

However, as I said before, this is talking solely about how to figure out which nodes to transverse once you have already set up the map, and doesn't even handle the size or shape of the nodes or intra-node pathing or anything besides the highest-level abstract pathing between nodes.

[Reelyanoob]

Have each room / hallway keep a list of 'portals' - i.e points or zones connecting to the next room/area. Straight-line pathing can route dwarves from entrance to exit through a zone. No need to declare a specific path - the dwarf uses straight-line pathing through each zone given the constraint that zones are contiguous recatangles this can be done in realtime very fast.

How will you define the cost of moving from one portal to another? How will you define the A* heuristic?

I covered that detail in my post (there was quite a bit of text though) - the cost to navigate through a rectangular zone portal => portal would be the dist from portal->portal in the zone, since zones are defined as openly connect rectangles this is a good estimate of the path cost. That would be added to the "path so far" for the graph A* is searching.

The heuristic for remaining distance to the target would be calculated in the normal A* way (with the additional check of 'is the target INSIDE this zone? - actually the dest zone ID could be determined before the search, and the zoneID of each searched zone compared to this ID), this will affect choice of zones to explore first (putting opened zones into the open list/heap). A* will search an arbitrary graph just as easily as it's set to search a grid.

[Talonj]

Have each room / hallway keep a list of 'portals' - i.e points or zones connecting to the next room/area. Straight-line pathing can route dwarves from entrance to exit through a zone. No need to declare a specific path - the dwarf uses straight-line pathing through each zone given the constraint that zones are contiguous recatangles this can be done in realtime very fast.

How will you define the cost of moving from one portal to another? How will you define the A* heuristic?

I covered that detail in my post (there was quite a bit of text though) - the cost to navigate through a rectangular zone portal => portal would be the dist from portal->portal in the zone, since zones are defined as openly connect rectangles this is a good estimate of the path cost. That would be added to the "path so far" for the graph A* is searching.

The heuristic for remaining distance to the target would be calculated in the normal A* way (with the additional check of 'is the target INSIDE this zone? - actually the dest zone ID could be determined before the search, and the zoneID of each searched zone compared to this ID), this will affect choice of zones to explore first (putting opened zones into the open list/heap). A* will search an arbitrary graph just as easily as it's set to search a grid.

The problem is, as stated in my (probably TL;DR) post, in creating the zones in the first place. While it is relatively simple to flood fill random areas until there are no more rectangles to be had, fortresses aren't built all at once, they're dug out or constructed one tile at a time by dwarves who don't enjoy digging things out in a meaningful manner. Obviously, you need to attempt to merge the newly opened tile with nearby rectangles, or, conversely, remove the now-closed tile and split the rectangle up into smaller ones. However, I can't think of any suitably fast ways to do this, and no conclusive algorithms have really been put forth in this thread. (I spent most of my free time before posting consolidating ideas in my head to solidify Niseg's idea, since it is significantly easier to implement)

The hierarchical structure I was talking about is just a method of using search trees as a data structure to organize the connectivity of nodes and speed up inter-node pathing.  It doesn't have anything to do with intra-node pathing or zoning.

Basically, I was thinking of a Binary Search Tree as inspiration for it, and how that helps speed up searches.

Instead of making a standard connectivity grid for nodes, and then using a pathfinding program to search for a path, you create a tree data structure where connectivity is recorded in the pointers from one branch in the tree to the next. 

Searching a tree data structure is much easier than trying to pathfind through them, so it can abstractly find a set of nodes to path through very, very quickly with the minimum possible number of memory fetching. 

The data structure itself would kind of get bloated with pointers, depending on how you want to set it up - you basically can trade memory for speed and making better pathing decisions.

However, as I said before, this is talking solely about how to figure out which nodes to transverse once you have already set up the map, and doesn't even handle the size or shape of the nodes or intra-node pathing or anything besides the highest-level abstract pathing between nodes.

So you're saying that it's a method of searching through zones created by other means? I.e. we can use it on whichever grouping method other come up with? In that case, it's pretty cool, even though I don't really understand it.
In this vein, a short while after editing my wall of text for the second time, I realized that you can actually re-apply Niseg's algorithm on top of itself -- that is, group a cube of cubes of tiles into cubes of nodes, and search those, and create a massive tree structure that lends itself to recursive use of A* -- this would allow both the optimality of 2x2x2 cubes, and the abstraction and swiftness of 16x16x16 cubes, and also possibly make the idea of BFSing for the nearest (larger) node that contains a target material for item searching much more feasible, by then simply using nearest manhattan distance on a list of all items within that large node. There would be additional overhead for both, of course, but I believe it would be worth it, due to the sheer amount of pathfinding done in a mature fortress.

[Niseg]

I think the room splitting algorithm is well defined don't forget the bitvector that defines nodes in a room. the bit vector is one of the major advantage.

example map(folded):

Spoiler (click to show/hide)

_01234567
0#######
1##t+++#
2##++++#
3##+++++
4##+++b#
5#######
6#######

room is defined from point t( 2,1) to point b (4,6) with a bit vector :

Spoiler (click to show/hide)

1111
1111
1111
1111

to add 1,3 all we need to do is change t to 1,1 and then grow and regenerate the bit vector . It might be easier to create a new room and then merge it. the new room bit mask is:

Spoiler (click to show/hide)

01111
01111
11111
01111

When the other points are dag out it's just a matter of setting bits. when you wall off the room you can clear bits and at some point shrink the room (not really critical).  with a bitmask you can get an O(1) answer if a node is in a room .

It might be smart to create 3d  rooms and there is nothing stopping you from doing it with this model. It's also scalable to infinity so if your map becomes complicated you can split it farther by grouping its rooms into regions.

Anyways As I said the room splitting model a tad complicated (it's not that bad though most of it is already well defined). I think we should be aiming for path caching first( I have a working simulator) and we might be able to optimize it enough to make it adequate . Path caching is super easy and it can be user guided . If the user want to abuse it to confuse goblinite with silly waypoints he'll just get FPS drops.

There are two improvements I can think of to path caching:

1. directional waypoints.
2.  path smoothing. .

1.  since the simplest model user placed  the waypoints can be directional which would affect the heuristic function that helps selecting waypoints  closest to source and destination. As we all know the heuristic can lie and the shape can fix it. example(folded):

Spoiler (click to show/hide)

##########
#S+#w++++#
#++#++#++#
##+##+##+#
#++#++#+w#
#w+#++#++#
##+##+##+#
#+++++#++#
#++#+w#+D#
##########

As you see due to the distance from S to the  east waypoint being shorter than the distance to the south  waypoint it would pick the wrong waypoint . Same with the destination D this cause the waypoint path finding to be worst than A*. by changing the huristic to give a directional penalty (can be automatic if wp is by a wall) it would help it pick a better waypoint.

Waypoint picking need to be smarter than heuristic but it should also try not to be too complex.

2. Path smoothing is a very important part of any waypoint system so anyone navigating using a waypoint won't have to go through the waypoint and only use it as a guide. This can be done by some simple function that intelligently picks 2 points and use depth  limited A* to make the path smoother . example (folded)

Spoiler (click to show/hide)

###########
#S+++++++w#
#####+#####
#+++++++++#
#+#########
#+++++++#w#
#+#######+#
#++++#++++#
#++++#++D+#
#+++++++++#
###########

You see that here you got a zigzag from S to upper waypoint. S goes to the waypoint and then backtrack and then it goes to the next waypoint and backtracks to the destination.

This example isn't too good because it is bad waypoint placement but there are other examples where you got extremely long path you just need to smooth out the two ends.
 
Anyways I have decent progress with my simulator I do have a few minor bugs I gotta iron out and I also need to fix some structure ( like move the few instructions I added) . I'll probably start a new thread about it.

[Talonj]

I think the room splitting algorithm is well defined don't forget the bitvector that defines nodes in a room. the bit vector is one of the major advantage.

example map(folded):

Spoiler (click to show/hide)

_01234567
0#######
1##t+++#
2##++++#
3##+++++
4##+++b#
5#######
6#######

room is defined from point t( 2,1) to point b (4,6) with a bit vector :

Spoiler (click to show/hide)

1111
1111
1111
1111

to add 1,3 all we need to do is change t to 1,1 and then grow and regenerate the bit vector . It might be easier to create a new room and then merge it. the new room bit mask is:

Spoiler (click to show/hide)

01111
01111
11111
01111

When the other points are dag out it's just a matter of setting bits. when you wall off the room you can clear bits and at some point shrink the room (not really critical).  with a bitmask you can get an O(1) answer if a node is in a room .

It might be smart to create 3d  rooms and there is nothing stopping you from doing it with this model. It's also scalable to infinity so if your map becomes complicated you can split it farther by grouping its rooms into regions.

Anyways As I said the room splitting model a tad complicated (it's not that bad though most of it is already well defined). I think we should be aiming for path caching first( I have a working simulator) and we might be able to optimize it enough to make it adequate . Path caching is super easy and it can be user guided . If the user want to abuse it to confuse goblinite with silly waypoints he'll just get FPS drops.

There's a lot more to rooms than just squares. What about ramps? How about connections and shapes? If there isn't an arbitrary pre-set size cutoff, how will a room know when to split?
If you try to split based off of 1-2 tile wide passageways, what if a 1-2 tile wide passageway is dug out a series of times in a small room, creating many smaller, misshapen "rooms" within one larger room? This would end up with fewer tiles per room than an arbitrary size. Also, I don't see how just having a bit mask makes determining paths O(1)... Or the fact that the node structure is defined using a bit vector means anything at all. Okay, so the node area is stored as a map of boolean values... ... How ELSE would you do it?

Also, you say "to add 1,3 all we need to do is add 1,1 and grow and regenerate the bit vector" What exactly is this growing and regeneration? Just how big of an area are you going to rebuild with every newly created tile / newly walled off tile?

For that matter, path caching is most certainly not the way to go, for several reasons mentioned... Also, not mentioned is that combining these two methods is functionally impossible, since ideally all zones would be invisible to the player and automatically generated, thus setting waypoints would have no effect on the overall path algorithm used because it is not used on actual tiles, but groups of them -- unfortunately this also affects the useful traffic designations, but I think the FPS gain would be worth it. The other problem with path caching is that the overhead of caching paths, with the significantly reduced worst case scenario of the node grouping algorithms, may actually exceed the possible gains simply because the sheer number of paths needing to be cached.

Also, what you are doing there seems to be using the same zone theory and simply letting the player designate "zone" areas by using waypoints -- since the waypoints are in fact not even being used to cache paths anymore, if a dwarf is not standing exactly on top of the waypoint, he cannot use a cached path. Are you trying to cache paths starting from all points within a certain distance from the waypoint? Because that would quickly become exponentially more complicated...

The intent of my post was to create discussion on the potentially BETTER algorithm -- how to create the convex polyhedrons used within the navmesh algorithm, which is significantly more complex than just creating arbitrarily shaped rooms.

[Niseg]

There's a lot more to rooms than just squares. What about ramps? How about connections and shapes? If there isn't an arbitrary pre-set size cutoff, how will a room know when to split?

The ramp just means a path upwards the bitmask is just to say if the node is in a room or not.  There is no problem with overlapping rooms and they would never cover the same nodes. You can even define a room within a room. The spliting size should be big enough to be useful but small enough that you won't make path search too complex.

If you try to split based off of 1-2 tile wide passageways, what if a 1-2 tile wide passageway is dug out a series of times in a small room, creating many smaller, misshapen "rooms" within one larger room? This would end up with fewer tiles per room than an arbitrary size. Also, I don't see how just having a bit mask makes determining paths O(1)... Or the fact that the node structure is defined using a bit vector means anything at all.

I didn't talk about O(1)  path finding but it's possible in a room system. I was talking about O(1) validation: "is the point in the square and is it's bit set.". I'm not sure how you'll search your start and destination rooms but those are not that bad even if you use a linear search.

smaller rooms are not a problem the can be group into 1 bigger room that contains them. The bitmap allows any shape rooms which makes it very flexible in terms of adding nodes while still having a "square" shape which make it easy to tell if the point is within it or not.

 Okay, so the node area is stored as a map of boolean values... ... How ELSE would you do it?

Also, you say "to add 1,3 all we need to do is add 1,1 and grow and regenerate the bit vector" What exactly is this growing and regeneration? Just how big of an area are you going to rebuild with every newly created tile / newly walled off tile?

This is the kind of optimizations i'll leave for later. In general if room structure changes I'll regenerate it  - it's not as bad as you think in terms of runtime.

For that matter, path caching is most certainly not the way to go, for several reasons mentioned... Also, not mentioned is that combining these two methods is functionally impossible, since ideally all zones would be invisible to the player and automatically generated, thus setting waypoints would have no effect on the overall path algorithm used because it is not used on actual tiles, but groups of them -- unfortunately this also affects the useful traffic designations, but I think the FPS gain would be worth it. The other problem with path caching is that the overhead of caching paths, with the significantly reduced worst case scenario of the node grouping algorithms, may actually exceed the possible gains simply because the sheer number of paths needing to be cached.

Also, what you are doing there seems to be using the same zone theory and simply letting the player designate "zone" areas by using waypoints -- since the waypoints are in fact not even being used to cache paths anymore, if a dwarf is not standing exactly on top of the waypoint, he cannot use a cached path. Are you trying to cache paths starting from all points within a certain distance from the waypoint? Because that would quickly become exponentially more complicated...

I was also skeptical about the path caching method at first till I kept looking at it. I explained how it works in previous pages. if you want to get to S->D you can do it through 2 waypoints w1 and w2 which have a full path cache then the only thing you need to do is find the closest waypoints to S and D and find paths to them from S and D. You might think it's not worth it and it's memory consuming but with good waypoint placement you can reduce the number of nodes visited from 60% to 5%. keeping the paths to the waypoint  short can  improve  the pathfinding algorithm complexity by a factor of 10.

Adding waypoint based pathfinding navigation is very easy  to do and the gains from it would be major. I know that room spliting is a better system but it would take us some time to make it work.

The intent of my post was to create discussion on the potentially BETTER algorithm -- how to create the convex polyhedrons used within the navmesh algorithm, which is significantly more complex than just creating arbitrarily shaped rooms.

constructing  nav mesh seems complicated and It could have too much memory and overhead use in case of  many "teeth" .

[Draco18s]

The problem is, as stated in my (probably TL;DR) post, in creating the zones in the first place. While it is relatively simple to flood fill random areas until there are no more rectangles to be had, fortresses aren't built all at once, they're dug out or constructed one tile at a time by dwarves who don't enjoy digging things out in a meaningful manner. Obviously, you need to attempt to merge the newly opened tile with nearby rectangles, or, conversely, remove the now-closed tile and split the rectangle up into smaller ones. However, I can't think of any suitably fast ways to do this, and no conclusive algorithms have really been put forth in this thread. (I spent most of my free time before posting consolidating ideas in my head to solidify Niseg's idea, since it is significantly easier to implement)

Actually, I have covered that.

But people don't like to give my method any merit, despite the fact that it's the only way that even makes sense.  We go side tracked on this "bitmask" think which is pointless and useless.  All that's really doing is covering how the navigation mesh is stored in memory (which is irrelevant) and not how it's built or used.

[Talonj]

The problem is, as stated in my (probably TL;DR) post, in creating the zones in the first place. While it is relatively simple to flood fill random areas until there are no more rectangles to be had, fortresses aren't built all at once, they're dug out or constructed one tile at a time by dwarves who don't enjoy digging things out in a meaningful manner. Obviously, you need to attempt to merge the newly opened tile with nearby rectangles, or, conversely, remove the now-closed tile and split the rectangle up into smaller ones. However, I can't think of any suitably fast ways to do this, and no conclusive algorithms have really been put forth in this thread. (I spent most of my free time before posting consolidating ideas in my head to solidify Niseg's idea, since it is significantly easier to implement)

Actually, I have covered that.

But people don't like to give my method any merit, despite the fact that it's the only way that even makes sense.  We go side tracked on this "bitmask" think which is pointless and useless.  All that's really doing is covering how the navigation mesh is stored in memory (which is irrelevant) and not how it's built or used.

You have covered an incredibly general algorithm, however "cluster into nodes" is not language specific enough to write into code, unfortunately. That's the sort of specificity I'm looking for -- If we want to even think about getting Toady to implement any of these (And I know that's a dream hiding in all of our hearts) -- we need at least some basic pseudocode, that I attempted in my post, but I know I left out a few important steps even then. The idea of creating a separate map for each pathing type is a good one, yes, as is the idea of giving workshops their own nodes, though I don't know if that is actually necessary.

Like I said in my post, the nodes are just an invisible abstraction rather than waypoints to frequently used structures. They need to be small enough that an algorithm searching on the tile level does not need to search very many dead ends, but large enough to significantly cut down on the searches done. That's why I think the arbitrary cube slicing has merit -- they don't need to be sensibly shaped, they just need to be groups that are searched with one single comparison in A*.

Also, if you look to my just previous post, you'll see me expressing my own confusion on getting hung up over how the vector is stored in memory has anything to do with algorithms

snip

The ramp just means a path upwards the bitmask is just to say if the node is in a room or not.  There is no problem with overlapping rooms and they would never cover the same nodes. You can even define a room within a room. The spliting size should be big enough to be useful but small enough that you won't make path search too complex.

My point is that ramps upward represent a straight line in terms of games and should ideally be contained in a single room. This would significantly cut down on the number of nodes for those embarks that are nearly nothing but ramps. Also, my question is exactly when to split? Under what conditions? Tile count within a node = 30? Length = 5x width? The pink elephants have come to play? If you're even going to think about implementing this anywhere, there need to be details! So many more details, and most of what you have been posting recently have sadly been vague generalities.

If you try to split based off of 1-2 tile wide passageways, what if a 1-2 tile wide passageway is dug out a series of times in a small room, creating many smaller, misshapen "rooms" within one larger room? This would end up with fewer tiles per room than an arbitrary size. Also, I don't see how just having a bit mask makes determining paths O(1)... Or the fact that the node structure is defined using a bit vector means anything at all.

I didn't talk about O(1)  path finding but it's possible in a room system. I was talking about O(1) validation: "is the point in the square and is it's bit set.". I'm not sure how you'll search your start and destination rooms but those are not that bad even if you use a linear search.

I see I misread you there, but O(1) validation can be acquired as simply as adding a pointer to the Tile structure that points at its node. That simple. It shouldn't even ever have come to discussion, really.

smaller rooms are not a problem the can be group into 1 bigger room that contains them. The bitmap allows any shape rooms which makes it very flexible in terms of adding nodes while still having a "square" shape which make it easy to tell if the point is within it or not.

Under what conditions? When does a room join? Immediately until reaching the splitting size, I would assume, but even that is undefined. Keep in mind, as in my previous reply, that the idea isn't to create landmarks for the nodes, it's just to cut down the search space.

 Okay, so the node area is stored as a map of boolean values... ... How ELSE would you do it?

Also, you say "to add 1,3 all we need to do is add 1,1 and grow and regenerate the bit vector" What exactly is this growing and regeneration? Just how big of an area are you going to rebuild with every newly created tile / newly walled off tile?

This is the kind of optimizations i'll leave for later. In general if room structure changes I'll regenerate it  - it's not as bad as you think in terms of runtime.

That's not an optimization, it's the core of the algorithm. If building a node and referencing the resulting structures takes up too much longer than the current method, we are trading pathfinding optimization for landscape changing optimization. If we ever get moving fortress parts, and a few other updates, landscape changing is going to happen more and more frequently. It already happens at an incredible rate. Before even being considered viable, it needs to be as detailed as possible, to ensure it's even better than the current method.

For that matter, path caching is most certainly not the way to go, for several reasons mentioned... Also, not mentioned is that combining these two methods is functionally impossible, since ideally all zones would be invisible to the player and automatically generated, thus setting waypoints would have no effect on the overall path algorithm used because it is not used on actual tiles, but groups of them -- unfortunately this also affects the useful traffic designations, but I think the FPS gain would be worth it. The other problem with path caching is that the overhead of caching paths, with the significantly reduced worst case scenario of the node grouping algorithms, may actually exceed the possible gains simply because the sheer number of paths needing to be cached.

Also, what you are doing there seems to be using the same zone theory and simply letting the player designate "zone" areas by using waypoints -- since the waypoints are in fact not even being used to cache paths anymore, if a dwarf is not standing exactly on top of the waypoint, he cannot use a cached path. Are you trying to cache paths starting from all points within a certain distance from the waypoint? Because that would quickly become exponentially more complicated...

I was also skeptical about the path caching method at first till I kept looking at it. I explained how it works in previous pages. if you want to get to S->D you can do it through 2 waypoints w1 and w2 which have a full path cache then the only thing you need to do is find the closest waypoints to S and D and find paths to them from S and D. You might think it's not worth it and it's memory consuming but with good waypoint placement you can reduce the number of nodes visited from 60% to 5%. keeping the paths to the waypoint  short can  improve  the pathfinding algorithm complexity by a factor of 10.

Adding waypoint based pathfinding navigation is very easy  to do and the gains from it would be major. I know that room spliting is a better system but it would take us some time to make it work.

I'm not too sure how waypoint pathfinding would be easier to code than node grouping. Add in the algorithm to slice nodes, add the data structures and associated functions, change the initial pathfinding algorithm to work on nodes, then copy paste the pathfinding algorithm and loop it through each individual node. It is, of course, a little more complicated than that, but it's at least largely using an existing system. Creating path smoothing waypoints seems a little more complicated to me, but that may not be the case. I haven't seen the actual source code, after all. Regardless, my point was and still is, if you spend the time to implement waypoint path caching, you will have to scrap ALL OF THE CODE when switching over to room nodes, because they are INCOMPATIBLE.

The intent of my post was to create discussion on the potentially BETTER algorithm -- how to create the convex polyhedrons used within the navmesh algorithm, which is significantly more complex than just creating arbitrarily shaped rooms.

constructing  nav mesh seems complicated and It could have too much memory and overhead use in case of  many "teeth" .

As I outlined in my first post, the ONLY difference between navmesh and your idea is that navmesh has a restricted shape for the node size. I don't know what you mean by teeth. The memory use will be slightly higher, only because the number of nodes will probably be higher, but the point is is that it is an order of magnitude faster than the current method, so the overhead while pathfinding is meaningless. If we can find a method that deals with the frequently changing landscape in a sane manner that has as little overhead in that area as possible, it would without a doubt be THE ideal method.

[Niseg]

A nav mesh is a special case of node grouping where the rooms have a shape of some polygon.  polygons means some floating point stuff and complex operations like division and multiplication but it might not be that bad.

A Nav mesh uses "convex polygons" and triangles so I guess we can do something like that . I'm still not sure how we'll cover all the nodes with shapes. "teethed " regions would be majorly problematic.
little example:

Spoiler (click to show/hide)

################
#+++++###++++###
####++###++++###
#++++++##++++###
####++++#++++###
#+++++++#++++###
####++++##+++###
#++++++++#+++++#
####+++++#+++###
#++++++++#+++###
####+++++#+++###
#+++++++++#++###
####++++++#++###
#+++++++++#++###
#######+++######
########++######
################

I'm counting here over 12 nodes created for a mesh and that's a lot of data . Node grouping can do it in 1 or 2.  Other than that those meshes are usually used to convert open areas into a graph which is navigated with A*. Those polygons are usually also hand drawn.

I think that with a mesh you might have the problem that maintaining it would be complicated and as you dig through your port you get crazy shapes and the nav mesh generator would keep trying to fit those polygons in which would be counter productive. I can try to write a simulation for it but it would take some research. I haven't found any source code that relates to nav mesh generation and its dynamic maintenance . I might want to look at RTS or something.

I'm not a big expert in discrete math and graph algorithms . I just know the basic and how to put things together. If you give me code I can read it and understand how it works.I did find some stuff on the internet. As I said I'm going to perfect my waypoint navigator before switching an approach .

You are welcome to write some source code in any language or show me an existing project that does automatic navmesh generation. I don't think it's worth the trouble but I was  previously a big skeptic of the path caching approach and now became an advocate of it. It's not as memory intensive as you think and its gains in CPU time are huge.
 
As I said before A* can be fooled to go the wrong way. This is especially useful if you want to travel long distances. I made my program A* rather than using identical waypoint because it would be silly to do it and I observed some crazy stuff( I can probably fix it just figured it out  ).

Another approach you can take in pathing is to assume you can get anywhere in a straight line and then deal with obstetrical . This generally assumes that if you go toward your target you'll reach it especially if it's on the same level. If you can fly this is what you want to do .

example:

Spoiler (click to show/hide)

###########
#+++#+++++#
#+D+#+++++#
#d+5#+++#+#
#+q+#+++++#
#++p#3#+++#
##++#+2+++#
#++++n+#++#
#++#++m+S+#
#+++++#s++#
#++++++++##
###########

If you want to reach from S to D and want to use a streight line point 1 is blocked, 2 and 3 are passable 4 is blocked and 5 is passable .

A* complexity of this problem is 21. Using my program I can calculate how much complexity it would take to go around the obstacles.  S to 2 = 4, 3 to 5 = 18. This yields higher complexity so it's not always good especially for walker. What a walker can do instead of trying to go around obstacles is think other straight paths from nodes nearby to like the lower case one. The problem with walker is that it's still trying to shoot through a needle hole but in open areas you can get to your target fairly fast. The other issue with A* is the amount of overhead in the algorithm and visiting a node has a lot more involved than checking it's passable.

I'll have to respond to Talonj later I currently don't have the time .

[Draco18s]

I'm counting here over 12 nodes created for a mesh and that's a lot of data . Node grouping can do it in 1 or 2.  Other than that those meshes are usually used to convert open areas into a graph which is navigated with A*. Those polygons are usually also hand drawn.
If you want to reach from S to D and want to use a streight line point 1 is blocked, 2 and 3 are passable 4 is blocked and 5 is passable .

The problem with node grouping is that you still need to do local A* to travel inside a single node.  With a navigation mesh of convex polygons you do not.
You're trading RAM (cheap) for CPU (expensive).

Also, it's very easy to merge tiles into nodes as they are dug out.  It has been explained, although it's broken into several parts.
One
Two
Three
Four
Five

Essentially, take the tile to be added to the nodes, compare with neighboring nodes, find the largest it can merge with and still maintain a convex shape (restricting the algorithm to 45 degree angles, if necessary, to allow for non-square nodes), then attempt to merge that node with its neighbors (repeat as necessary).

Removing tiles works in reverse.  Simply carve* its volume out of the node it is a part of.

*There's a smarter way to carve than the way Hammer does it, although it doesn't save a whole lot.  Basically, determine your first new node, then make the second on the opposite side, rather than around the edge:

Spoiler (click to show/hide)

. = floor of original node
O = new wall
#########
#.......#
#.......#
#.......#
#...O...#
#.......#
#.......#
#.......#
#########

#########
#111....#
#111....#
#111....#
#111O...#
#111....#
#111....#
#111....#
#########

What Hammer does:
#########
#1112222#
#1112222#
#1112222#
#111O...#
#111....#
#111....#
#111....#
#########

Best
#########
#111.222#
#111.222#
#111.222#
#111O222#
#111.222#
#111.222#
#111.222#
#########

[NW_Kohaku]

Actually, I have covered that.

But people don't like to give my method any merit, despite the fact that it's the only way that even makes sense.  We go side tracked on this "bitmask" think which is pointless and useless.  All that's really doing is covering how the navigation mesh is stored in memory (which is irrelevant) and not how it's built or used.

That's not true, I assume something basically the same as what you are talking about (although I'm not sure of why the workshops need to be their own node) when I'm talking about any of these things.  If I don't say I support it, it's just because I was assuming that was true.

So you're saying that it's a method of searching through zones created by other means? I.e. we can use it on whichever grouping method other come up with? In that case, it's pretty cool, even though I don't really understand it.
In this vein, a short while after editing my wall of text for the second time, I realized that you can actually re-apply Niseg's algorithm on top of itself -- that is, group a cube of cubes of tiles into cubes of nodes, and search those, and create a massive tree structure that lends itself to recursive use of A* -- this would allow both the optimality of 2x2x2 cubes, and the abstraction and swiftness of 16x16x16 cubes, and also possibly make the idea of BFSing for the nearest (larger) node that contains a target material for item searching much more feasible, by then simply using nearest manhattan distance on a list of all items within that large node. There would be additional overhead for both, of course, but I believe it would be worth it, due to the sheer amount of pathfinding done in a mature fortress.

What you are talking about is multi-tiered pathfinding - something that can make sense, based upon certain assumptions of how complex a map will be.

What I'm talking about with a tree data structure, however, is a tree data structure, which means it's inherently hierarchical.  Trees contain branch nodes which are fully functional as smaller trees, themselves. 

It's not all that complicated if you consider it - Once you have a grand list of nodes that you have cut the map up into, you have to start organizing them.  You pick some arbitrary node near the middle of the map (you would need to be able to "balance" the tree later on, anyway, so starting from an arbitrary point is fine for now), and make that the root node.  Let me use an older diagram for this:

Spoiler (click to show/hide)

The root node here is the central stairwell that is in bright red. 

Pointers are stored in a vector (a sad necessity, as you can have arbitrary numbers of connections) to all nodes the root node can connect to. 

These are the doors that splay out from the central stairwell (darker red).

These connect to branch nodes, themselves (the red-orange square hallway around the central stairway), and then to other nodes (the orange hallways leading away from the central stairwell), then to others (yellow-orange doors and minor hallways), then to others (some of the yellow rooms or doors off of minor hallways), etc.

Now, you have a data structure where connectivity is implied through the presence of pointers to given nodes.  This isn't all that different from most other meshes or other means of pathfinding at this point, except that we don't really care about the relative locations of any given nodes (east, west, up, down, doesn't matter, just connection matters).

Now, we need to put in the two things we need that lets us actually do the basic pathfinding. 

Each node needs to store with its pointers the length of the path through it, the width of the path through it, and the type of movement it requires (I.E. walking, swimming, flying). 

Further, in order to make the search possible without advanced pathfinding, each branch node needs to store some form of list (maybe a hash to be faster?) that contains all of the leaves and branches that are "higher up" ("higher" means away from the roots, towards leaves) the tree from itself that it can connect to through only moving up the tree from where it is. 

This last point is where this method becomes faster, but also takes up more memory than other pathfinding methods, the hash list would involve lots of duplicate references to nodes.  This would have to be as compressed as possible (Just a reference to a specific node) to save on memory. 

Now, in order to search this tree, you start from the starting node, and search the hash list of branches and leaves connected to the starting node.  If the destination node is not in that list, you go down a node on the tree, and search the lower node that connects to the starting node, and see if you can reach the destination node by only going up from there.  If that doesn't work, you keep going down the tree all the way to the roots until you can find a path to the destination node.

Once you find a branch with a connection to the destination node, you just go up the tree, testing which branches will have connections to the destination node, until you finally strike the destination node, itself.

The list of nodes you had to go down and then up is a valid path to the destination. 

[Talonj]

Essentially, take the tile to be added to the nodes, compare with neighboring nodes, find the largest it can merge with and still maintain a convex shape (restricting the algorithm to 45 degree angles, if necessary, to allow for non-square nodes), then attempt to merge that node with its neighbors (repeat as necessary).

Most of those links before were reiterating problems with the idea, not exactly the best links to give. I understand that finding the optimal would be difficult, but if you settle for node groupings and merging algorithms that are SO suboptimal that they end up being the current system + overhead from checking every additional node, we'll have a new problem: Digging lag.

I can't think of a simple "merge with largest neighbor" algorithm that wouldn't take up a relatively large amount of time. With just using node grouping, without bothering with convex shapes (which, to reiterate, DOES improve the worst case, but does NOT improve the best case, like this does) you pick an arbitrary neighbor and then add yourself to it. Or, when adding a wall, just remove the tile from the node, simple as that.

You only dig out one tile at a time. That means that new tiles dug out can only be added to a node if that node is a 1 tile wide hallway in the given direction. Also, remember that dwarves dig in seemingly (to the player) random directions (though it's a simple direction preference hierarchy, I think), so breaking the algorithm to build suboptimal nodes wouldn't be as intentional as you believe. You could code the algorithm to these preferences, but since I don't know them off hand, speculation on that is out.

I'm saying that, if we want to make this a feasible idea, we need to put together a step by step exactly what parameters of each tile/node will be checked, in which order, to merge nodes. I can't think of such a step-by-step algorithm for the navmesh convex polyhedrons. I can for arbitrary rectangular prisms subdivided into accessible regions, which is what I outlined in my first post.

A nav mesh is a special case of node grouping where the rooms have a shape of some polygon.  polygons means some floating point stuff and complex operations like division and multiplication but it might not be that bad.

A Nav mesh uses "convex polygons" and triangles so I guess we can do something like that . I'm still not sure how we'll cover all the nodes with shapes. "teethed " regions would be majorly problematic.
little example:

Spoiler (click to show/hide)

################
#+++++###++++###
####++###++++###
#++++++##++++###
####++++#++++###
#+++++++#++++###
####++++##+++###
#++++++++#+++++#
####+++++#+++###
#++++++++#+++###
####+++++#+++###
#+++++++++#++###
####++++++#++###
#+++++++++#++###
#######+++######
########++######
################

I'm counting here over 12 nodes created for a mesh and that's a lot of data . Node grouping can do it in 1 or 2.  Other than that those meshes are usually used to convert open areas into a graph which is navigated with A*. Those polygons are usually also hand drawn.

I think that with a mesh you might have the problem that maintaining it would be complicated and as you dig through your port you get crazy shapes and the nav mesh generator would keep trying to fit those polygons in which would be counter productive. I can try to write a simulation for it but it would take some research. I haven't found any source code that relates to nav mesh generation and its dynamic maintenance . I might want to look at RTS or something.

I'm not a big expert in discrete math and graph algorithms . I just know the basic and how to put things together. If you give me code I can read it and understand how it works.I did find some stuff on the internet. As I said I'm going to perfect my waypoint navigator before switching an approach .

You are welcome to write some source code in any language or show me an existing project that does automatic navmesh generation. I don't think it's worth the trouble but I was  previously a big skeptic of the path caching approach and now became an advocate of it. It's not as memory intensive as you think and its gains in CPU time are huge.
 
As I said before A* can be fooled to go the wrong way. This is especially useful if you want to travel long distances. I made my program A* rather than using identical waypoint because it would be silly to do it and I observed some crazy stuff( I can probably fix it just figured it out  ).

Another approach you can take in pathing is to assume you can get anywhere in a straight line and then deal with obstetrical . This generally assumes that if you go toward your target you'll reach it especially if it's on the same level. If you can fly this is what you want to do .

example:

Spoiler (click to show/hide)

###########
#+++#+++++#
#+D+#+++++#
#d+5#+++#+#
#+q+#+++++#
#++p#3#+++#
##++#+2+++#
#++++n+#++#
#++#++m+S+#
#+++++#s++#
#++++++++##
###########

If you want to reach from S to D and want to use a streight line point 1 is blocked, 2 and 3 are passable 4 is blocked and 5 is passable .

A* complexity of this problem is 21. Using my program I can calculate how much complexity it would take to go around the obstacles.  S to 2 = 4, 3 to 5 = 18. This yields higher complexity so it's not always good especially for walker. What a walker can do instead of trying to go around obstacles is think other straight paths from nodes nearby to like the lower case one. The problem with walker is that it's still trying to shoot through a needle hole but in open areas you can get to your target fairly fast. The other issue with A* is the amount of overhead in the algorithm and visiting a node has a lot more involved than checking it's passable.

I'll have to respond to Talonj later I currently don't have the time .

First off, you're severely misunderstanding complexity. Complexity is measured in worst case, best case, average case based on some variable (in this case, generally, something to do with the total number of tiles). In A*, all you do is visit one node, then check all surrounding nodes for the node with the lowest of (estimated distance to target from node + cost to move to said node). In DF, all costs are equal, so only a swift coordinate subtraction is required to find the distance. What do you even mean with your second picture anyway? From what I'm reading, it seems like you're picking nodes progressively farther from start waypoint to target waypoint and just computing straight line and then checking to see if there is any straight line path between the nodes, going on until you find one. Explain your algorithm so I can make a slightly less ridiculous conclusion, please...

Also, you're significantly overcomplicating the Navmesh problem. In DF, since we are dealing with discrete tiles instead of open space, there are no floating point calculations to be had. How will you travel across .2376 of a tile anyway? The only thing the algorithm has to deal with is maintaining the polygons. And, for the third or fourth time, my post is asking people to start suggesting ideas for how to create a dynamic navmesh maintenance algorithm. The navmesh is better. There can never be an argument against that, it lowers best and worst case complexities by an order of magnitude. It will reduce the whole of pathfinding down another logarithm.

Also, I looked and there isn't really much easily findable literature on automatic, dynamic generation and maintenance of navmeshes using discrete tiles like we have here. However, it shouldn't be THAT complicated, quite a few have thrown in ideas and tossed around problems already. What we need to do now is compile together a list of individual conditions for the cases of adding and removing a tile that can be translated into code relatively easily.

For example:

Spoiler (click to show/hide)

Code: [Select]


#######
###B###
###BB##
AAA#B##
###C###
###C###
#######
into this:

Code: [Select]

#######
#BBBBB#
#BBBBB#
AAAAAAA
#CCCCC#
#CCCCC#
#######


I can't wrap my head around how to do it efficiently. I don't mean to yell at others to do what I can't, but I know that before we can tout the feasibility and improvements of the navmesh system, we have to outline exactly how it will work, why it is feasible, and, more importantly, if we are to have a chance in hell of convincing Toady to improve the pathfinding algorithm in this way, we need detailed pseudocode that can easily and directly be translated into programming statements.

(I closed my laptop and drove for a half-hour in the middle of this post, so I may have repeated myself a couple of times)