Print

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

[Draco18s]

In order for these nodes to work, you need to have any "local" pathfinding capable of finding the other tiles in the same node without leaving the node.

The nodes being defined as a convex volume of space with no obstructions you don't need local pathfinding: it's a strait line.

[Mohican]

For someone who starts off by saying that he didn't read the thread, you're pretty quick to tell people not to post their thoughts on the subject because your ideas are the best.     What you've posted is basically a repeat of what others have said, except in a few cases that don't make much sense, like the funnel algorithm.

In case you didn't notice, I've been posting in this thread before, and was only talking about how the way in which this gets put into memory, because simply having fast pathfinding is NOT the only goal here - it also has to conserve memory and respond to dynamic changes extremely well.  What you quoted wasn't a new idea, it was the same idea we've been talking about where I was disucssing how it could best fit those constraints on dynamic map changes.

(And to anyone else, what good ideas are there on ways to make a map react better to something like flooding with water as tiles individually flood or empty of water?  For that matter, how do we handle things like digging or bridging in pathfinding cheaply?)

Anyway, just drawing cubes over the map is problematic as long as it is entirely possible for players to not have any vertical access between most areas of the map (such as the central stairwell method of fortress design).  In order for these nodes to work, you need to have any "local" pathfinding capable of finding the other tiles in the same node without leaving the node.  If you then have something like two or three minor hallways with rooms branched off of them, with no access through rooms to other hallways, you would need to make the one-tile tall functional square nodes smaller and skinnier, still, since you wouldn't be able to path from one hallway to another without first finding the major access hallways in other nodes.

I don't see any benefit to using funnel algorithm, which might make sense in a game with floating point location values, but seems like wasted cycles spent on "path smoothing" in a game that has no need for path smoothing.  DF just needs to move diagonally when it can and horizontally when it can't.  There are no other considerations that need to be taken into account.

The game already prefers diagonals, since they are functionally free (or rather, cost no more than a horizontal move), which means that point on preferring diagonals is pointless.

The changing of the node structure based upon locking doors or digging is exactly what I was talking about finding the best ways to accomidate in that last post.  (You did read it, right?)

You also have to be aware of how the node changes aren't something as simple as "it's water now" - each individual tile will have to become flooded, and the game will likely be checking for which portions of the map are being flooded without a good system for how this will actually be updated.

Ok I read the whole thread , and like I thought it was mainly the same idea as the current pathfinding with some tweaks.
For what I can read of your post you didn't get almost every part of my method.

No there is no problem with fortress without vertical access.
No there is no need of any internal pathfinding , a cube is convex , which mean that for any two points of the cube the straight line conecting this two point is also include in the cube. Just in case a cube can be a 1x1x1 tile, which means this method is in the WORST case localy as fast(slow?) as the current method.
I think you just don't understand the funnel algorithm, it's an algorithm which take a bunch of touching convex polygons (with our start point in the first one and the end point in the last one), and returns you a bunch of straight lines conecting the 2 points, these straight lines ARE the path.
The function that take care of the changing of the map only do local changes not global, so it is very cheap in calculation.
I think the fluid system is as simple as "it's water now" (with an index of 1 to 7), I think the fluid system just need to know what is the "fluid index" of every tiles to work, but I may be wrong on this one.
Ho and the navigation mesh is known to be the (actual) best pathfinding method.

Edit: http://www.ai-blog.net/archives/000152.html here is a nice site explaining and showing some nice example of nav mesh.

[NW_Kohaku]

Ok I read the whole thread , and like I thought it was mainly the same idea as the current pathfinding with some tweaks.
For what I can read of your post you didn't get almost every part of my method.

No there is no problem with fortress without vertical access.
No there is no need of any internal pathfinding , a cube is convex , which mean that for any two points of the cube the straight line conecting this two point is also include in the cube. Just in case a cube can be a 1x1x1 tile, which means this method is in the WORST case localy as fast(slow?) as the current method.
I think you just don't understand the funnel algorithm, it's an algorithm which take a bunch of touching convex polygons (with our start point in the first one and the end point in the last one), and returns you a bunch of straight lines conecting the 2 points, these straight lines ARE the path.
The function that take care of the changing of the map only do local changes not global, so it is very cheap in calculation.
I think the fluid system is as simple as "it's water now" (with an index of 1 to 7), I think the fluid system just need to know what is the "fluid index" of every tiles to work, but I may be wrong on this one.
Ho and the navigation mesh is known to be the (actual) best pathfinding method.

Edit: http://www.ai-blog.net/archives/000152.html here is a nice site explaining and showing some nice example of nav mesh.

And yet, I think the problem is you're still not understanding what we are talking about...

Whether you call it a nav mesh or not, this is still functionally the same thing we have already been talking about, except for the fact that we are dealing with non-floating-point cubic tiles.  You're coming into the thread, saying we should drop everything, and work on "your system", and then describe "your system" as being almost exactly what we were talking about (except that your is based upon floating-point distances), anyway, and then try telling us how much better your system is.

Also, no, it's not as simple as "it's water now".  The entire node doesn't instantly fill with water.  Only individual tiles fill with water, certain levels of water at a time, and do so sequentially - that means that at one point, there will be water in some of the tiles in one node, and not in other tiles in the node, and you are going to have to start splitting that node up and testing to see whether it fits in with other nearby nodes.  There is an interface point (3/7 water) where swimming creatures and walking creatures can both occupy a tile.  That means those tiles are probably going to be in their own individual nodes, and checking to be put in with other nearby nodes rather frequently, as water sloshes around randomly.  In a situation with 3/7 and 4/7 water in a basin, the 4/7 water is going to be cutting off land access every time that 4/7 water depth shifts around, and that means the nodes are going to be cut up and merged very rapidly with one another.  That's a potentially costly set of calculations to make, and something that can be optimized. 


EDIT:
Since I probably need to go into further detail as to why "Funnel" isn't helpful - first off, the mesh system and polygons and linear pathways you are talking about are for floating-point-distance pathing.  This is a grid-based game.  The funnel pathfinding where you calculate how many meshes you can path down in a straight line is unneccessary calculation, since as long as you can assume connectivity without explicit pathfinding, there is no reason to have to worry about pathing around corners, anyway.  There is no need to worry about making the "smooth line" or avoiding "zig-zagging" in the way that pathfinding is taking place already, so spending extra calculations to look ahead several nodes to make a straight line between the nodes is pointless. 

Further, there is a problem you are ignoring when talking about all this - the pathfinding you are linking to assumes large open areas with clusters of obstacles and relatively few moving units.  DF is a game where units cannot move through one another easily - collisions require both units to stop (or in pile-ups, everyone to stop), a unit to try to pathfind a sidestep, or failing that, everyone but one unit has to stop everything to let one unit advance one space. 

Try having dwarves pick up a pile of random objects like stones left over from tunneling when you only have a one-tile-wide hallway for them to access it, and you'll immediately see the problems with the traffic pileups. 

Consider a major pathway where the overall shape of the path units must take is a "U", starting or ending in the northwest and northeast with dwarves needing to go back and forth repeatedly, but needing to travel along a major hallway that connects portions of the fortress from east-to-west.  Every dwarf travelling to and from those points would automatically hug the northern wall of the major hallway - colliding with every single other dwarf who is coming from the direction of their destination.

This was why I was advocating a "Highway" system - it may be slightly less dwarf-walking-distance efficient, but it manages to be much more efficient overall for the problem at hand, because if you assume that dwarves prefer walking along the right-hand path of a hallway, only deviating from that path to "change lanes" by stepping to the left in the highway to pass a slower moving walker, you can assume that in any hallway wider than one tile, you can at least prevent most head-on-collisions until traffic density is such that dwarves are going to be repeatedly attempting "passing" maneuvers.   

This still assumes pathfinding automatically at everything but local "inside the node" start and end points, based purely upon the node's connectivity, but it manages to solve other problems the game needs to solve with pathfinding, as well.

[Symmetry]

I dunno, a discrete nav mesh approach is quite attractive.  It's just dividing the map into easy to path blocks and pathing between them, which has been suggested a million times.  The "funnel" algorithm would end up utterly trivial when implemented on discrete rectangles, and it nicely handles the odd case people usually struggle to explain when two large zones touch at more than a single tile.

Dodging other walkers becomes easy if we only allow dodging to another square in the same segment.  Yes this means there are times when dodging would help and we can't do it with the solution, but the pure simplicity of it will make it quick and under player control. five wide corridors will work still.

The water problem is large.  I think it is best to use a sticky approach, where water is walkable until it hits 5 deep, then it becomes impassable until it hits 3 deep.  The actual water itself would work as now, but for the purposes of long distance pathfinding we can simplify things a bit perhaps.  It's fairly pointless to plan a detailed path in advance if it goes through these volatile areas anyway.

However there are problems.  The way the zones are created and coalesced has a huge effect on pathfinding.
For example a corridor with cubby holes could be represented (at least) two ways.  Letters represent pathfinding zones:

Code: [Select]

A B C D
XXXXXXXX


Code: [Select]

B D F H
ABCDEFGH

The second case is a bit of a disaster I think?

I apologise if I'm tearing this thread even more off subject, I've not read the whole thing as although I think it's hugely important to the game I really don't think I can solve the problem.  And I get frustrated because I want the source code to generate traffic statistics and try optimisations on it myself

[Mohican]

Whether you call it a nav mesh or not, this is still functionally the same thing we have already been talking about, except for the fact that we are dealing with non-floating-point cubic tiles.  You're coming into the thread, saying we should drop everything, and work on "your system", and then describe "your system" as being almost exactly what we were talking about (except that your is based upon floating-point distances), anyway, and then try telling us how much better your system is.

there isn't any post (except the one of soralin in an other thread) relating to my method , but I don't care this is not MY method , this is just the most efficient method, I didn't invent it.
I don't know why you are talking about float, I never mention it. we use rectangular cube AxBxC where A,B,C are integers.

Also, no, it's not as simple as "it's water now".  The entire node doesn't instantly fill with water.  Only individual tiles fill with water, certain levels of water at a time, and do so sequentially - that means that at one point, there will be water in some of the tiles in one node, and not in other tiles in the node, and you are going to have to start splitting that node up and testing to see whether it fits in with other nearby nodes.  There is an interface point (3/7 water) where swimming creatures and walking creatures can both occupy a tile.  That means those tiles are probably going to be in their own individual nodes, and checking to be put in with other nearby nodes rather frequently, as water sloshes around randomly.  In a situation with 3/7 and 4/7 water in a basin, the 4/7 water is going to be cutting off land access every time that 4/7 water depth shifts around, and that means the nodes are going to be cut up and merged very rapidly with one another.  That's a potentially costly set of calculations to make, and something that can be optimized. 

You have a point here, even if you still don't understand a node represents a cube of tiles of the SAME type, that means there is only tiles with x/7 water in the same cube, so there is no problem for the walking thing, but it could be a lot of node rebuilding during a flood so maybe it could be improved. Though the complexities of the subroutines that add a node , merge 2 nodes , split one or change the type of a node are constant, so the complexity of the function will be linear to the amount of change (if there is 10 changes to do , it'll take as much time as doing 10 times 1 change), so I don't think it's a big deal.

Since I probably need to go into further detail as to why "Funnel" isn't helpful ...

I think I need an example.

Code: [Select]

##################
#+++++#+X++#+++++#
#+++++#++++#+++++#
#+++++###+##+++++#
#++++++++++++++++#
#######++++#######
#+++++#++++#+++++#
#+++++#++++#+++++#
#++++++++++++++++#
#######++++#######
#+++++#++++#++Y++#
#+++++#++++#+++++#
#++++++++++++++++#
##################
this will be represented by something like that:

Code: [Select]

##################
#22222#1X11#77777#
#22222#1111#77777#
#22222###a##77777#
#22222b6666c77777#
#######6666#######        1
#33333#6666#88888#        |
#33333#6666#88888#    2-b a c-7
#33333g6666d88888#       \|/
#######6666#######    3-g-6-d-8
#44444#6666#55Y55#       / \
#44444#6666#55555#    4-f   e-5
#44444f6666e55555#
##################
where 1,2,3,4,5,6,7,8,a,b,c,d,e,f,g are the nodes of the graph, X and Y the points we try to find a path for. X is in 1 , Y in 5.
the A* will tell us , the path go through 1->a->6->e->5, but this is NOT the path, you have all the necessary information to easily find it , but you don't have it yet , you need the funnel algorithm (which is a very simple algorithm with integers mesh) to find out the exact path:

Code: [Select]

##################
#+++++#+X++#+++++#
#+++++#++++#+++++#
#+++++###A##+++++#
#++++++++++++++++#
#######++++#######
#+++++#++++#+++++#
#+++++#++++#+++++#
#++++++++++++++++#
#######++++#######
#+++++#++++#++Y++#
#+++++#++++#+++++#
#+++++++++BC+++++#
##################
Wich means go in straight line from X to A , then go in straight line from A to B , then go in straight line from B to C , then go in straight line from C to Y. You cant skip this step, knowing by wich cube you have to go through is not enough. This algorithm is extremly fast , and the A* has been through only 4-5 nodes instead of about 50 with the current method. I hope I've been clear and my post is understandable.

EDIT:

However there are problems.  The way the zones are created and coalesced has a huge effect on pathfinding.
For example a corridor with cubby holes could be represented (at least) two ways.  Letters represent pathfinding zones:

Code: [Select]

A B C D
XXXXXXXX


Code: [Select]

B D F H
ABCDEFGH

The second case is a bit of a disaster I think?

yes you are right, there is multiple possibilities to represent the same zone, and some are more optimized than other, I can't see right now a way to find out how to represent it optimaly, maybe if someone have an idea. But even a non optimized representation is at least as fast as considering each tile as a node, so it's totally worth it.

[Draco18s]

As for water: it's easy.  Any tile with water in it is its own node.  You don't merge it with adjacent nodes until one of two conditions is reached:

1) Tile contains no water
2) Tile is marked as non-flowing

As for corridor division:
It's long been a problem of nav-mesh generation,* however, given the rules we've decided upon for nodes being added to a corridor, it wouldn't occur often.**
The only thing we need to do it insure that it NEVER happens under our current rules set is to say that when a tile is merged and there are two or more existing nodes it could be merged with, always choose the larger one.

*If you've ever messed with the Source engine (TF2, L4D, HL2 mapping) you'll know about Hint brushes.  They act as designer-defined boundaries of the visibility leaves (visibility in the Source engine is almost exactly the method we're discussing here: convex volumes).  They're created by carving out geometry from an initial cube, and the "carve" function isn't very smart.  However, since we're working with discrete tiles and doing a split/merge on a per-tile basis, we don't need "hint brushes."

**You'd have to intentionally try and break it, as if you dig the corridor first, then the niches, you'll get the first solution.  You'd have to dig 1 tile of corridor, then the nitch, then the neighboring tile and even then it'd depend on how the engine decided to do the merge.  With my above rule, provided that our corridor is 2 tiles deep (as far as node-size is concerned) before digging a nitch, the nitch will never create a node that breaks the hallway into multiple nodes.

[Symmetry]

yes you are right, there is multiple possibilities to represent the same zone, and some are more optimized than other, I can't see right now a way to find out how to represent it optimaly, maybe if someone have an idea. But even a non optimized representation is at least as fast as considering each tile as a node, so it's totally worth it.

I don't think it will be, at least not quite.  When you know the size of every node and you know where the neighbours are, and you know each node has the same number of neighbours, it's much easier to write a decent data structure.  Or just use the main map one which I believe is what DF does.  When nodes have properties like width and height and depth, and can have many more neighbours, the algorithm will be less efficient.  Maybe we still win, maybe not.  Depends on implementation and memory efficiency etc.

That said a hardcoded shortcut data structure / code path for dealing with doorways would probably make up the difference.

I see what you mean about the way the nodes grow draco18s.  I also think our coalesce algorithm will need to be capable of cascading coalesce operations, splitting neighbours in order to create large blocks.  Think of the permutations possible at a T junction.

But anyway, I guess you're both right.  The improvement (assuming a decent implementation) will be so big these become interesting questions rather than problems.

[NW_Kohaku]

I don't care this is not MY method , this is just the most efficient method, I didn't invent it.
I don't know why you are talking about float, I never mention it. we use rectangular cube AxBxC where A,B,C are integers.

It's the method you were arguing we should follow and stop making suggestions for other methods.  It's your argument, your method.

And I'm talking about floating point values of positions because all those references and suggestions you are making are designed upon floating point distance and positioning.  You seemingly aren't taking the time to recognize the differences this causes.

I think I need an example.

this will be represented by something like that:

Code: [Select]

##################
#22222#1X11#77777#
#22222#1111#77777#
#22222###a##77777#
#22222b6666c77777#
#######6666#######        1
#33333#6666#88888#        |
#33333#6666#88888#    2-b a c-7
#33333g6666d88888#       \|/
#######6666#######    3-g-6-d-8
#44444#6666#55Y55#       / \
#44444#6666#55555#    4-f   e-5
#44444f6666e55555#
##################
where 1,2,3,4,5,6,7,8,a,b,c,d,e,f,g are the nodes of the graph, X and Y the points we try to find a path for. X is in 1 , Y in 5.
the A* will tell us , the path go through 1->a->6->e->5, but this is NOT the path, you have all the necessary information to easily find it , but you don't have it yet , you need the funnel algorithm (which is a very simple algorithm with integers mesh) to find out the exact path:

Code: [Select]

##################
#+++++#+X++#+++++#
#+++++#++++#+++++#
#+++++###A##+++++#
#++++++++++++++++#
#######++++#######
#+++++#++++#+++++#
#+++++#++++#+++++#
#++++++++++++++++#
#######++++#######
#+++++#++++#++Y++#
#+++++#++++#+++++#
#+++++++++BC+++++#
##################
Wich means go in straight line from X to A , then go in straight line from A to B , then go in straight line from B to C , then go in straight line from C to Y. You cant skip this step, knowing by wich cube you have to go through is not enough. This algorithm is extremly fast , and the A* has been through only 4-5 nodes instead of about 50 with the current method. I hope I've been clear and my post is understandable.

Again, the problem I'm saying you seem to be having is that you're drawing distinctions between what I am talking about and what you are talking about that don't really exist.  The difference between the sort of hierarchical node system and a nav mesh is largely nominal.  It doesn't matter whether you call something a "node" or a "convex rectangular cuboid", so long as the code functions basically the same.

What I was talking about with a "highway" system would do exactly the same slicing of the map up into the same nodes, and follow basically the same path.  The only real difference would be that the dwarf would hug the wall when walking through 6 until it came time to start moving diagonally to hit the door.

As for water: it's easy.  Any tile with water in it is its own node.  You don't merge it with adjacent nodes until one of two conditions is reached:

1) Tile contains no water
2) Tile is marked as non-flowing

Hmm... I guess this works, although it would require an odd exception system.  As far as memory serves, water tends to basically never stop flowing, though.  If there is any unevenness in the water amounts, it will pretty much be "flowing" forever.

Dodging other walkers becomes easy if we only allow dodging to another square in the same segment.  Yes this means there are times when dodging would help and we can't do it with the solution, but the pure simplicity of it will make it quick and under player control. five wide corridors will work still.

Dodging is a problem we should try to avoid having to do in the first place, however.  People already want "one-way road" designations because of how often dodging has to take place, and how much it muddles general traffic.  A hug-the-right-wall approach solves most traffic jams innately. 

However there are problems.  The way the zones are created and coalesced has a huge effect on pathfinding.
For example a corridor with cubby holes could be represented (at least) two ways.  Letters represent pathfinding zones:

Code: [Select]

A B C D
XXXXXXXX


Code: [Select]

B D F H
ABCDEFGH

The second case is a bit of a disaster I think?

I apologise if I'm tearing this thread even more off subject, I've not read the whole thing as although I think it's hugely important to the game I really don't think I can solve the problem.  And I get frustrated because I want the source code to generate traffic statistics and try optimisations on it myself

This isn't a derail at all, it's exactly the sort of problem we need to be able to solve well.

A zone with a "ribbed" hallway like the one you were describing there should really be considered a single node, though.  Realistically, if you are pathing through it, you just want to follow the XXXX path unless you have a destination that is in one of those alcoves.  Nodes don't necessarily need to be rectanges every time - a "circular" node will make sense in the case of something like the image I can quickly just steal a link to from the Ironhand graphics set preview.

Spoiler (click to show/hide)

The only thing that is important is that the assumptions we are going to make of the nodes will still hold true - the ability to make direct paths through them from one end to another with a single given movement type.  This is why saving the data structure as a "highway" where you record both length and width of the structure abstractly can help - you can make the highway go around a corner if you do it right, although this would probably quickly break the line of direct pathing. 

[Starver]

**You'd have to intentionally try and break it, as if you dig the corridor first, then the niches, you'll get the first solution.  You'd have to dig 1 tile of corridor, then the nitch, then the neighboring tile and even then it'd depend on how the engine decided to do the merge.  With my above rule, provided that our corridor is 2 tiles deep (as far as node-size is concerned) before digging a nitch, the nitch will never create a node that breaks the hallway into multiple nodes.

The one way I could easily see the 'breaking' occur is as follows:

Code: [Select]


[Dug]    [Meshed]

Start with a zig-zag

#######  #######
#.#.#.#  #b#d#f#
.#.#.#.  a#c#e#g
#######  #######

Then straighten the zig-zag

#######  #######
#.#.#.#  #b#d#f#
.......  abcdefg
#######  #######

Of course, starting from the zig-zag, digging the first 'straight' connector, e.g. the lower 'b', would have a choice between merging the "a?c" into a single zone, leaving the alcove 'b' to one side or the worst-case result of making the new cell part of the 'b'-zone.

That's codeable for.  But what if it wasn't just alcoves, but a "comb".  e.g. this was a proto-bedroom corridor, featuring (future) 1x3 bedrooms.

Code: [Select]


You may want to save a little bit on digging by only half-cutting the corridor

#######  #######
#.#.#.#  #b#d#f#
#.#.#.#  #b#d#f#
#.#.#.#  #b#d#f#
.#.#.#.  a#c#e#g
#######  #######

Now the choice is between


#######     #######
#b#d#f#     #b#d#f#
#b#d#f# and #b#d#f#
#b#d#f#     #b#d#f#
abc#e#g     aaa#e#g
#######     #######


So, is 1x4 (b) plus two 1x1s (a,c) actually still less sensible than the two 1x3s that are 'a' (was "a?c") and the original 'b'?

Maybe, but what if 'b' is ten long?  Twenty?

Ultimately, once the 'd' and 'f' non-niche bits are cut, maybe the algorithm recognises the value of a continuous 1x7 'a' (was "a?c?e?g") with branches of whatever length of, rather than branch+1 lengths and the individual and isolated 1x1s.

And using rectilinear shapes also means inefficiencies in other quarters.  What is more efficient?

Code: [Select]

aa#####
aa#####
##b####
###c###
####d##
#####ee
#####ee

aa#####
aa#####
##b####
###b### 
####b##
#####ee
#####ee

bc#####
ab#####
##b#### 
###b###
####b##
#####be
#####db



Example one is based upon squares (or cubes, but of Z=1 size) and how it would turn out.

Example two has a 'b' is a perfectly valid convex shape, which would be more efficient, but is not rectilinear.

Example three looks bad, but it's possible that (depending on what the original 'a' and 'e' rooms expand out into) could be more efficient, e.g.

Code: [Select]


######
###a##
##aa##  Not possible (although all intra-'a' travel
#aaa##    is still straight-line possible, even with
####b#    that chunk taken out, so still convex)
#####?

######
###d##
##aa##  One of the easy-splitting ways
#caa##   (c.f. also the 1x1, 1x2 and 1x3 split)
####b#
#####?

######
###c##
##bc##  Arguably more efficient,
#aab##   although really depends on what use
####b#   is made of the space.
#####?



[Mohican]

Again, the problem I'm saying you seem to be having is that you're drawing distinctions between what I am talking about and what you are talking about that don't really exist.  The difference between the sort of hierarchical node system and a nav mesh is largely nominal.  It doesn't matter whether you call something a "node" or a "convex rectangular cuboid", so long as the code functions basically the same.

What I was talking about with a "highway" system would do exactly the same slicing of the map up into the same nodes, and follow basically the same path.  The only real difference would be that the dwarf would hug the wall when walking through 6 until it came time to start moving diagonally to hit the door.

well then sorry I may have misunderstood what your highway system is, and I'll reread your posts. (things like using limited 12x12x12 nodes, and "internal pathfinding" in your previous post may have induce me in error)

Nodes don't necessarily need to be rectanges every time - a "circular" node will make sense

Yeah, in theory any convex shape should do the job. (but may be difficult to represent)
I think a straight line should be defined as going diagonal then horizontal or vertical OR going first horizontal or vertical then going diagonal.
If we use only one of those definition we have a problem , the straight line [A:B] isnt the same as [B:A], which pose some problem with the convexity. with this definition the corridor problem is solved

Code: [Select]

A B C D
XXXXXXXX


Code: [Select]

B D F H
BBBBBBBB
Yes , the B shape IS convex with the definition of straight line I gave.
but a new problem come with this corridor...

Code: [Select]

A B C D
 A B C D
XXXXXXXX


[Draco18s]

Which basically leads us back to:

Finding the most optimal system space-filling convex solid is not an easy problem (is it NP-complete?) and you go with the fastest method that is "good enough."

Most people won't be digging zig-zag hallways, and even in the case that they do, the sub-optimal node-graph isn't significantly detrimental to A*.  The worst case scenario is still better than what we're using now.

[NW_Kohaku]

Let me see...

The other conditions we should try to satisfy are

• to be able to path vehicles (I.E. 3x3 tile wagons, but also eventually ships, which are going to be potentially any arbitrarily large number of tiles)
• to be able to path diggers and bridgers
• to be able to penalize pathways for invaders, so that they have a reason to avoid certain areas that are obvious killzones (probably requiring each invading force to have their own map with weights to reflect their knowledge of existing killzones)
• be able to minimize memory usage storing nodes
• and minimize the amount of processor time spent on checks to retest the connections or split/join nodes every time a local change is made in the terrain, in a tradeoff with the amount of time spent actually having dwarves pathfind if we accept suboptimal node formation

Pathing vehicles is probably going to require the ability to occupy multiple nodes at once, which is tricky to code, to start with, but could be made simpler if we put the complexity on how the nodes are formed - with a recognition of how wide the pathways they will allow through them are. 

Arbitrary size vehicles, especially, can cut out many of the shortcuts that Toady was probably using on wagons (like simply making another connectivity grid, and making each obstacle count as an obstacle for the tile adjacent to itself, as well, and pathing only the center tile of the wagon through the map).

Pathing for diggers is one of those nightmare situations I'm reluctant to even start wrapping my head around.  I remember Draco doing a nice graph once, though, with pits for bridgers to put up to two bridges out as an example.  Digging is even worse, though, since there are so many more situations where just knocking down a wall can create hundreds of new potential pathways you'd have to start evaluating and eliminating.  It also basically pulls the bottom out of nodal pathways, and almost makes it easier to just use A* with a modified heuristic based upon the nodal system if you can simply punch through all the obstacles with a minor delay.

[Niseg]

this will be represented by something like that:

Code: [Select]

##################
#22222#1X11#77777#
#22222#1111#77777#
#22222###a##77777#
#22222b6666c77777#
#######6666#######        1
#33333#6666#88888#        |
#33333#6666#88888#    2-b a c-7
#33333g6666d88888#       \|/
#######6666#######    3-g-6-d-8
#44444#6666#55Y55#       / \
#44444#6666#55555#    4-f   e-5
#44444f6666e55555#
##################
ng each tile as a node, so it's totally worth it.

The main problem  is how to come  up with that node graph .

You can see your simple maze in my silly program

The output of aimless bfs from top left corner looks like this:

The numbers are real distances and the colors signify number of children of a node in this complex  graph (100~nodes potential). (red 0 orange 1 yellow 2 green 3+) The computer can't really see it but we can tell that there are rooms all it sees are the numbers(distance from start) and colors(number of children) or other things that describe the graph.

You need to tell it how to convert numbers and "colors"(aka other numbers) into groups and form those groups into a reduced graph. As I mentioned before BFS might not be the right algorithm to generate those "numbers and colors".

Now after you make some rules you need to tell it how to decide between a minor and major change. If for example a tree grows in those rooms some most of them would not change the general structure of the room unless it blocks the path to it.  Also deforming the rooms by digging  does not really change the general structure of the reduced graph unless it creates a new path to a node.

Representing rooms may not be a big problem because  you can generally put corners of a polygon into the data type. We can also save entry points to in the edges  to make pathing easier .

[Mohican]

this will be represented by something like that:

Code: [Select]

##################
#22222#1X11#77777#
#22222#1111#77777#
#22222###a##77777#
#22222b6666c77777#
#######6666#######        1
#33333#6666#88888#        |
#33333#6666#88888#    2-b a c-7
#33333g6666d88888#       \|/
#######6666#######    3-g-6-d-8
#44444#6666#55Y55#       / \
#44444#6666#55555#    4-f   e-5
#44444f6666e55555#
##################


The main problem  is how to come  up with that node graph .

Once we have the map sliced in rectangles, obtain the graph is trivial, slicing the map in rectangle is also trivial BUT slicing it optimaly is a much more difficult problem.
The first question to ask is what is an optimal representation? I think it's a representation where the "depth" of the graph (the maximal distance (in nodes) between 2 nodes) is minimal

Code: [Select]

  B D F H          A-B-C-D-E-F-G-H   is the graph representing it , the depth is 8
 ABCDEFGH


Code: [Select]

A B C D                               
EEEEEEEEEEE                           
                                              C
                                              |
                                            A-E-B   is the graph , the depth is 3
                                              |
                                              D
So the 2nd representaion is better because the depth of the graph is smaller than the first one.
I think I may have an idea , let's take my previous example

Code: [Select]

##################
#+++++#+X++#+++++#
#+++++#++++#+++++#
#+++++###+##+++++#
#++++++++++++++++#
#######++++#######
#+++++#++++#+++++#
#+++++#++++#+++++#
#++++++++++++++++#
#######++++#######
#+++++#++++#++Y++#
#+++++#++++#+++++#
#++++++++++++++++#
##################
My idea consist to take all "maximal" rectangles, here are all of them

Code: [Select]

##################   ##################   ##################
#AAAAA#GGGG#CCCCC#   #+++++#++L+#+++++#   #+++++#++++#+++++#
#AAAAA#GGGG#CCCCC#   #+++++#++L+#+++++#   #+++++#++++#+++++#
#AAAAA###+##CCCCC#   #+++++###L##+++++#   #+++++###+##+++++#
#AAAAA+FFFF+CCCCC#   #++++++++L+++++++#   #IIIIIIIIIIIIIIII#
#######FFFF#######   #######++L+#######   #######++++#######
#BBBBB#FFFF#DDDDD#   #+++++#++L+#+++++#   #+++++#++++#+++++#
#BBBBB#FFFF#DDDDD#   #+++++#++L+#+++++#   #+++++#++++#+++++#
#BBBBB+FFFF+DDDDD#   #++++++++L+++++++#   #JJJJJJJJJJJJJJJJ#
#######FFFF#######   #######++L+#######   #######++++#######
#HHHHH#FFFF#EEEEE#   #+++++#++L+#+++++#   #+++++#++++#+++++#
#HHHHH#FFFF#EEEEE#   #+++++#++L+#+++++#   #+++++#++++#+++++#
#HHHHH+FFFF+EEEEE#   #++++++++L+++++++#   #KKKKKKKKKKKKKKKK#
##################   ##################   ##################


My idea is to make a graph using this rectangles (yes they are not disjoint), a node is still a rectangle , and 2 nodes are connected if the 2 rectangles are touching (or overlaping)
so we should have this graph :

then the A* should give us G->L->K->E. Using a classic Funnel algorithm, we should end up with a path, but not the shortest (we don't pass through F).
But I'm sure by doing just a little trick we should end up with the shortest path. What do you think of this?

Edit :
the algorithm finding the "maximal" rectangles is very simple:
0)- just take a random tile
1)- make the maximal rectangle starting with this tile
2)- save this rectangle
3)- look at all the tiles in this area that are touching a tile that is not in the area, take one of this tile
4)- make a new maximal rectangle starting from this tile
5)- repeat to 2) until the area cover the entire map.

[Starver]

the algorithm finding the "maximal" rectangles is very simple:
0)- just take a random tile
[...]
3)- look at all the tiles in this area that are touching a tile that is not in the area, take one of this tile
[...]

I'm not saying this is 'wrong', but I'm wary of aiming for optimality by starting off with a random tile, and continuing with random tiles.

Of all the possible starting/next tiles, there may be one that is the absolute worst-case (creating a very sub-optimal 'optimal' division and/ or leading down the route where the most work is put into the map compared with the savings it ends up giving).

Obviously, the alternative of trying each and every possible start tile, and each and every possible continuation tile for any given start tile and continuation tile, brings us back to the original issue of path-finding, more or less, which can be done in breadth-first, depth-first or some more clue-guided manner.

Of course, given the fact that the idea (at least at first) is that the node-structure is a "build-once, revamp the occassional segment as changes require" thing, it's perhaps not too much of a problem[1] when compared with the existing pathing system, but I'm not yet able to prove (or even strongly suggest) to my own satisfaction that there won't be a horrible car-crash of a situation where it could go horribly wrong.

Just my thoughts, not really an objection, as much as something to be aware of.

And, no, I don't have a (foolproof, and yet not resource intensive) method in mind that doesn't rely on randomness or some form of systemic bias in initiating and perpetuating the zone analysis process.  Brute forcing the entire map from every single starting point with every single possible neighbouring region would be 'ideal'[3].  But hardly easy on the processor.


(Indeed, I know what you're thinking: sometimes "perfection is the enemy of the good-enough".  But that's the way I tend to think.)


[1] Unless you're finding that certain circumstances[2] where the ad-hoc zone-merging leads onto something awkward.

[2] Off the top of my head, a generally 'l'-shaped room (i.e. square area with a significant corner untapped) that was first dug out with pillars left all across the floor, and depending on the order the pillars are removed, the zone-merging algorithm may end up giving you a different end-result zonings, some of which are going to better (for the immediate vicinity, or for connecting to neighbouring zones) than others.  However, even in this example it is right that a less-optimal solution of zones that cover many tiles still offer an advantage over search systems that are nothing more than tile-per-node types.

[3] Even then, I could foresee a situation where a more parallel-seeking solution could come up with a better overall map than any point-outwards one you might care to mention.  The best point (or group of points) to start to optimise one sub-region would mean sub-optimality on another region, and starting somewhere that would help with the latter makes the former 'wrong'.  Starting anywhere not within either region's "happy zone" means both are sub-optimal.  But, on the other hand, while starting multiple spots, like growing crystal grains, could allow such critical areas to be optimised and then simply connected, the converging zones would necessarily subject their rapidly narrowing no-man's land between them to the pinch of zone-acquisition leaving who-knows-what pathing detritus between them.