Print

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

[NW_Kohaku]

I don't think anyone really gets your 'highway' concept (though I do think it would be useful). How exactly is the computer supposed to figure out where those traffic patterns go, anyway?

The game has to store a "path width" (which would be necessary for vehicles, anyway) for the nodes, and prefer to travel down the far right side.  If you have a three-tile-wide rectangular hallway, the dwarves would prefer to stay on the right hand side of that hallway, given their current direction of movement, hence making opposing traffic stay on either side of the hallway, the way that cars stay on the right (or left in certain countries) when driving down a road to prevent traffic collisions. 

Putting a traffic jam-solving method into the pathfinding would be a relatively minor burden on pathfinding time, provided it is set up correctly, and would give a performance boost in actual navigation when dwarves stop bumping into one another all the time, and having to pathfind around one another.

For comparison, worst-case for unaided A* is a wide, contiguous up/down stair column, so YMMV.

Isn't a giant field of up/down stairs the best case for A*?  You'd have a direct line of sight to wherever your destination is, meaning just picking the first tile that the heuristic will lead you to choose will always be the best choice, meaning you'd never have to do a double-back.

Technically, A*'s worst case is pathing to a completely blocked path or the like, where it functionally flood-fills, aborts, and tries again next frame, but the sort of thing that others were posting a couple posts ago is the next-worst, I.E. this:

Code: [Select]

##################
#s+++++++#d++++++#
#+##############+#
#++++++++#+#+#+#+#
#+########+#+#+#+#
#++++++++#+#+#+#+#
#+########+#+#+#+#
#++++++++#+#+#+#+#
#+########+#+#+#+#
#++++++++#+#+#+#+#
#+########+#+#+#+#
#++++++++++++++++#
#++++++++++++++++#
##################
This is the worst case because every time, the heuristic will trick the program into trying to go down each and every one of those dead-ends, thinking that it is a possible path to the exit.

Regarding those hell maps, they are still better than unaided A*. The worst case scenario for the convex polygon method is still half as intensive as unaided A* (it does gain that at the cost of greater memory overhead), and looks like this:

Code: [Select]

##################
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
##################



Also, I have a diagonal version of the notched corridor that I'm puzzling over. Ideal packing is one large node in the bottom corner, and successively smaller nodes adjacent to it, with 1x1 nodes only between larger nodes (think Sierpinski triangle). I don't know how to get that, though. On the other hand, I don't think ideal packing is ideal for pathing (at least via the funnel algorithm), so it may not matter.

Code: [Select]

##################
################.#
###############..#
##############...#
#############....#
############.....#
###########......#
##########.......#
#########........#
########.........#
#######..........#
######...........#
#####............#
####.............#
###..............#
##...............#
##################

And kaenneth, try to keep convex nodes, otherwise intra-node navigation needs A* to work.

Now, a giant triangle is the exact sort of convex node shape that works very well for this sort of thing.

The thing I'm asking is, is it really worth it to remove A* if we build node maps that are horribly complex because we're all using rectangles? 

Yes, A* uses up cycle time, but if we make a map that has 80,000 nodes in it because we have so many one-tile nodes, you're probably going to need to use A* or something to even navigate the node map in the first place, completely nullifying the point of the whole operation.

Rather, if we are going to have hierarchical node structures, we need to make the hierarchical nodes fast to search paths through, as well, and that means that it can be worth some inefficiencies in building the nodes in the first place to be able to make less 1-tile-nodes or fractured nodes like having the entire triangular room split into horizontal rectangles, where every step is pathing into the next node, anyway.

Now, for the statue hallway, ignore the fact that they are statues for a moment, in fact, ignore the alcoves, as well.

Let's just imagine a big square room with one tile of natural wall in the middle. 

Should we divide this room up into four separate nodes?  Or should it just be one big node where we give the dwarves the ability to path around the obstacle if they happen to go towards it?

Again, the problem with A* is not finding its way through mostly open areas, it's preventing A* from going down dead ends.  If you just find the dead ends and mark them off, A* works perfectly well.  That's all the hierarchical/nodal structure needs to do - zoom out to an abstract model, and find the zones that are the "leaf nodes" that are dead ends, the "branch nodes" that provide access to some local areas, and the "trunk nodes" that are the main throughfares that serve as the access points to all the other portions of the fortress. 

Now, the complexity of the system that divides up the rooms is a major sticking point - it needs to be fast enough that the computer doesn't spend more time dicking around looking for a "perfect" set of nodes than it does pathfinding in the first place, and it also needs to conserve on memory as much as it can, but these are all tradeoffs that should be balanced, rather than going for maximizing any one to the exclusion of all others. 

Or you could limit it to only 45 degree angle lines.  That would get you some non-grid convex shapes without having to go into complex math.

This is probably the simplest, fastest method of merging larger nodes.  Just make sure that there is a pathway to and from any given point in a grid using no more than a single "turn" of 45 or maybe 90 degrees.  Yeah, it means something like A* would have to be used, but as long as you have a very simple pathway from one end of a node to the other, that will never be much of a problem.

Of course, there's also a way to try and make the sort of stored pathways of a certain width, which may help with making that "highway" method of trafficking.  That means purposefully storing the width of specific nodes that you expect to get high traffic.

[Symmetry]

I don't think anyone really gets your 'highway' concept (though I do think it would be useful). How exactly is the computer supposed to figure out where those traffic patterns go, anyway?

The game has to store a "path width" (which would be necessary for vehicles, anyway) for the nodes, and prefer to travel down the far right side.  If you have a three-tile-wide rectangular hallway, the dwarves would prefer to stay on the right hand side of that hallway, given their current direction of movement, hence making opposing traffic stay on either side of the hallway, the way that cars stay on the right (or left in certain countries) when driving down a road to prevent traffic collisions. 

I'm not convinced.  How does it know the difference between a corridor and a dinning room?  If you want to move north s few squares in a room and you're on the wrong side do you run to the other side first?  It seems more like this is overcomplicating the path finding algorithm for a feature that should be handled at a higher level.

Also as a player this would drive me mad unless I have control over it.  With normal zones (whether rectangular, convex, or otherwise) we can allow the player to paint one way signs and attach the zone to the node graph with acyclic links.  I think this would be a better solution, if we do need one.

Also, using convex zones solves the path width problem quite nicely too.

Yes, A* uses up cycle time, but if we make a map that has 80,000 nodes in it because we have so many one-tile nodes, you're probably going to need to use A* or something to even navigate the node map in the first place, completely nullifying the point of the whole operation.

Yes we'll be using A* to path between nodes.  I think convex nodes will be a huge improvement and well worth it even though there will be quite a few of them, but this is the point where we need code to show what kind of difference it makes in practice.  Opinion and debate won't settle this.

Having said this, even if we allow arbitrary nodes then rectangular nodes can still exist as a special case (because they're so fast) so using them as a starting point seems fair.

Should we divide this room up into four separate nodes?  Or should it just be one big node where we give the dwarves the ability to path around the obstacle if they happen to go towards it?

Either is so much better than m*n nodes we have now that I'll take the one that's quickest to code.  And having intranode pathfinding be straight lines is a huge benefit.  Any long corridors, or open space, is pathed across instantly.  You don't even need to look.

Again, the problem with A* is not finding its way through mostly open areas, it's preventing A* from going down dead ends.  If you just find the dead ends and mark them off, A* works perfectly well.  That's all the hierarchical/nodal structure needs to do - zoom out to an abstract model, and find the zones that are the "leaf nodes" that are dead ends, the "branch nodes" that provide access to some local areas, and the "trunk nodes" that are the main throughfares that serve as the access points to all the other portions of the fortress. 

We can just add another level of heirarchy?  Using the simplest possible representation at the lowest level and having multiple self-similar levels of abstraction on top is usually a pretty good algorithm.

Now, the complexity of the system that divides up the rooms is a major sticking point - it needs to be fast enough that the computer doesn't spend more time dicking around looking for a "perfect" set of nodes than it does pathfinding in the first place, and it also needs to conserve on memory as much as it can, but these are all tradeoffs that should be balanced, rather than going for maximizing any one to the exclusion of all others. 

And simple enough to code it quickly with no bugs.

[Draco18s]

I don't think anyone really gets your 'highway' concept (though I do think it would be useful). How exactly is the computer supposed to figure out where those traffic patterns go, anyway?

The game has to store a "path width" (which would be necessary for vehicles, anyway) for the nodes, and prefer to travel down the far right side.  If you have a three-tile-wide rectangular hallway, the dwarves would prefer to stay on the right hand side of that hallway, given their current direction of movement, hence making opposing traffic stay on either side of the hallway, the way that cars stay on the right (or left in certain countries) when driving down a road to prevent traffic collisions. 

I'm not convinced.  How does it know the difference between a corridor and a dinning room?  If you want to move north s few squares in a room and you're on the wrong side do you run to the other side first?  It seems more like this is overcomplicating the path finding algorithm for a feature that should be handled at a higher level.

No, he doesn't run to the other side.  The direction of "flow" is dependant on connections to other nodes.  If a dwarf enters a node on the west and is headed towards a node on the east, he'll dodge south to avoid obstacles, etc.

[NW_Kohaku]

I'm not convinced.  How does it know the difference between a corridor and a dinning room?  If you want to move north s few squares in a room and you're on the wrong side do you run to the other side first?  It seems more like this is overcomplicating the path finding algorithm for a feature that should be handled at a higher level.

Also as a player this would drive me mad unless I have control over it.  With normal zones (whether rectangular, convex, or otherwise) we can allow the player to paint one way signs and attach the zone to the node graph with acyclic links.  I think this would be a better solution, if we do need one.

Also, using convex zones solves the path width problem quite nicely too.

Well, Draco already said the most relevant point, but...

Figuring out "what are the hallways" should be a major point of a heirarchical node structure in the first place.  If the nodal structure is going to be useful, it has to use something that takes the place of A* on the second-tier to find the most efficient path through the nodes.  After all, esepcially if we are going to have situations where a map has some absurdly high number of very small, almost one-tile nodes, then pathing through the second-tier abstract node map breadth-first could wind up costing more processor power than A* itself. 

How we go about doing this is up for debate, but the thing about A* is that you can always tell if you are moving "closer" or "further away" from your destination when you are moving, thanks to the heuristic.  In an abstract node map, it's much more difficult to make that sort of heuristic take the guesswork out of whether you are moving closer to the target or not without actually looking at all of the nodes - which again, is a major problem when you have potentially thousands of nodes.

Some sort of method of getting the pathfinding function to make a guess as to which nodes are more likely to lead to a destination, and which nodes are more likely not to is an important part of this, and the fastest, simplest way of doing that is to start by marking certain nodes as leaf nodes that have only one connection or are otherwise a "dead end" (maybe it has two connections, but is functionally a dead end, anyway, like the sides of the all-diagonal rooms Artanis00 posted, although this is part of the reason why we need a larger set of nodes to prevent those sorts of situations). 

From here, it's probably best to start thinking about this like IP routing.

The branch nodes then need to start ordering themselves until you can make certain high-traffic areas the "main hallway" or "hub" nodes (like a vertical staircase node in a central staircase style fortress), which can remember which branches spin off of them, and which leaves spin off of those. 

Potentially, we can have some sort of "memory" of successful paths through a given node - if a node is pathed through, and the pathfinder successfully finds a link to the destination, then it gets a point towards prioritizing searching down that node before other nearby nodes are searched, wheras nodes that are searched that don't provide useful paths lose prioritization points, making them the last nodes to be searched.  Nodes that get enough ponits become the candidates for becoming the "trunk" nodes.

Again, the problem with A* is not finding its way through mostly open areas, it's preventing A* from going down dead ends.  If you just find the dead ends and mark them off, A* works perfectly well.  That's all the hierarchical/nodal structure needs to do - zoom out to an abstract model, and find the zones that are the "leaf nodes" that are dead ends, the "branch nodes" that provide access to some local areas, and the "trunk nodes" that are the main throughfares that serve as the access points to all the other portions of the fortress. 

We can just add another level of heirarchy?  Using the simplest possible representation at the lowest level and having multiple self-similar levels of abstraction on top is usually a pretty good algorithm.

Adding another level of hierarchy just kicks the can down the road - now this level of hierarchy needs a way to organize itself, and now you're working on an abstractly shaped node chart, so you can't use many of those tricks that work with A* or the like.  How do you pathfind through the abstract nodes without having some sort of pathfinding code to make a guess as to which nodes to try to path through?  In an abstract path, it's even harder to get a good heuristic to even tell you if you are going the right way without checking everything. 

The only way to get a good level of hierarchy in that sense that I can think of immediately is to do the IP lookup sort of pathfinding, which requires a large table of every node that the trunk nodes can path to stored in the node itself to tell the pathfinding code how many layers of hierarchy it needs to go up the chain.  That can be potentially expensive, memory-wise, if there are enough nodes to search.

And simple enough to code it quickly with no bugs.

There is no such thing as code that you can make quickly without bugs.

The target should be something robust enough that it never needs to be heavily reworked again later, which will save much more work in the long run than constantly having to update it and tweak it.  Taking the time to do it right the first time is MUCH, MUCH easier than debugging it or having to revise it later.  (Although we are unfortunately already talking about revising the pathfinding code...)

[Draco18s]

There is no such thing as code that you can make quickly without bugs.

If you can do that, you can have MY job.
And I'm already called a genius by my coworkers.

[Starver]

[...]the thing about A* is that you can always tell if you are moving "closer" or "further away" from your destination when you are moving, thanks to the heuristic.  In an abstract node map, it's much more difficult to make that sort of heuristic take the guesswork out of whether you are moving closer to the target or not without actually looking at all of the nodes - which again, is a major problem when you have potentially thousands of nodes.

I know I'm not really addressing this issue head-on, and this method includes an overhead which makes the smallest-extending nodes far less efficient (but should be ok for the largest ones, at least), but if the centre-spot[1] coordinates are recorded for each node then it gives a basis towards a "that adjacent node looks closer than this other adjacent node, and this other one looks to be a back-tracking one (but we may still have to come back to it later)" analysis along the lines of the standard A* tile-by-tile heuristic.


(From a personal POV, I'm most concerned about the node-weightings situation.  A zone with five different entrances to it may be made into a node in a search-map net, but has to remember up to 10 different 'costs' in order to convey to the route-finding algorithm how much effort it takes to get so-many X, so-many Y and so-many Z[2] nearer the target.  And that's with single-width entrances.  I'm still hung-up on a series of multi-width connections between a string of zones, where twists and turns dictate that there are better and worse paths across a zone purely due to where the zones on either side have their entrances and exits to the zones once-more-removed, or even beyond.  Sorry, please ignore this complication in my own fiddling with my own code, which isn't exactly keeping pace or mirroring the heading of everything else being discussed here, so this whole issue is probably not worth talking about.)



[1] Need not involve integer values, for X, Y or Z...  and could be mid-way between the respective limits or a true average of all contained co-ordinates.

[2] Any or all of which may be zero or even negative values.

[NW_Kohaku]

I know I'm not really addressing this issue head-on, and this method includes an overhead which makes the smallest-extending nodes far less efficient (but should be ok for the largest ones, at least), but if the centre-spot[1] coordinates are recorded for each node then it gives a basis towards a "that adjacent node looks closer than this other adjacent node, and this other one looks to be a back-tracking one (but we may still have to come back to it later)" analysis along the lines of the standard A* tile-by-tile heuristic.

(From a personal POV, I'm most concerned about the node-weightings situation.  A zone with five different entrances to it may be made into a node in a search-map net, but has to remember up to 10 different 'costs' in order to convey to the route-finding algorithm how much effort it takes to get so-many X, so-many Y and so-many Z[2] nearer the target.  And that's with single-width entrances.  I'm still hung-up on a series of multi-width connections between a string of zones, where twists and turns dictate that there are better and worse paths across a zone purely due to where the zones on either side have their entrances and exits to the zones once-more-removed, or even beyond.  Sorry, please ignore this complication in my own fiddling with my own code, which isn't exactly keeping pace or mirroring the heading of everything else being discussed here, so this whole issue is probably not worth talking about.)



[1] Need not involve integer values, for X, Y or Z...  and could be mid-way between the respective limits or a true average of all contained co-ordinates.

[2] Any or all of which may be zero or even negative values.

You can do that, but the thing is, we generally want to try to at least keep in mind which nodes are the dead end nodes.  Otherwise, all we're accomplishing is making A* occasionally check multiple tiles at a time in the pathfinding, and potentially adding a lot of overhead in calculation the heuristic in with that. 

I'm not sure I understand your last two sentences in your second paragraph, though.

... The best way I can think of to make this sort of search would be to try to work it somewhat like a search tree - arrange all the nodes in a totally abstract search tree format, and have the individual branches and leaves record the path down the tree to get to where they are.  When a pathfind is called, you compare the number of nodes those have in common.

For example, if we have a tree that has 10 levels of complexity, and the starting point and the destination have 8 levels of complexity in common, then you know that you only have to go "up" 2 levels from the starting point, then can start searching "down" 2 levels to find the destination point.

[Starver]

You can do that, but the thing is, we generally want to try to at least keep in mind which nodes are the dead end nodes.[...]

I know, I was just addressing the "A* has an idea of what may be closer" idea.  Which wasn't quite what you were talking about, as I tried to acknowledge.

I'm not sure I understand your last two sentences in your second paragraph, though.

Well, the very last sentence was telling you to ignore the ramblings from the previous four sentences in that para.

If you're talking about the bit about having "hang-ups with a series of multi-width connections between a string of zones", then imagine something like the following:

Code: [Select]

#######     #######
#+++++#     #+++++#
#+++++#     #+++++#
#++A++#     #++B++#
#+++++#     #+++++#
#+++++#    2#+++++#
##+++#########+++##
#+++++#1+++2#+++++#
#+++++++++++++++++#
#++C+++++++++++D++#
#+++++++++++++++++#
#+++++#3+++4#+++++#
##+++#########+++##
#+++++#     #+++++#
#+++++#     #+++++#
#++E++#     #++F++#
#+++++#     #+++++#
#+++++#     #+++++#
#######     #######
Assuming that A..G represents zone names for shapes that inhabit something roughly equivalent to the whole 5x5 room they're ensconced in (and the 1x3 gaps joining them are either part of convex shapes A..G or their own individual but un-named connecting rectangles... or possibly shared-tiles belonging to both zones as part of the connectivity matrix), and that travel from X->Y means anywhere-in-X-zone to anwhere-in-Y-zone...  (By convention, letters from the top-end of the alphabet will be arbitrary designations.  There's already no particularly logical order of letters even in the bottom-end set, which will latter extend to encompass A..J anyway, but they at least relate to the features you can see or imagine being added on.)

A->E would go via C and would depend largely on where-in-A and where-in-E as to how it might have to cross C.  Ditto for B->F via D.  But C and D would have something like an "it takes five steps to cross" (by one measure of counting it, could also be six) as information associated with these nodes, when discussing A->E and B->F transits.

A->B and E->F travel would most naturally travel by 'hugging' the bends, i.e. the walls W&E of 1&2 or 3&4 respectively, as they travel through G (although a limited diagonal travel would be possible between those points for traffic purposes).  C and D would have a minimum of 1 tile stepped onto during this.  (More could be stepped on for an optimal path, depending on where the but to simplify things I'm going to assume that the the start/destination zones will absorb any extra lateral movement for this quick example.)  So C can report to a path-searching algorithm that it's willing to demand just one step, except when letting traffic transit from A->E in which case it needs to request that five steps be accounted for in any journey through it.

A->F and E->B travel would normally take a diagonal that nonetheless hugged the 1&4 walls or 3&2 walls in some way, although if starting from (say) the BL corner of zone A the movement could be diagonally through the gap and C until next to gap-wall @3, straight (or zig-zaggy!) across to hug 4 before moving diagonally into F (or even up to B if it was certain A->B attempts!).  But, again, C and D could be said to have 1 tile's-worth of stepping into in the calculations, the same as already described.

Even if you have some sort of rule (keep left/right rule, or "diagonals try to keep to the best antialiased valued tiles"), C->D travel will progress across G very variably, according to where in C and where in D are the start/destination points, but for all of these trips discussed so far (except the ones that don't pass through G at all) give G step-value of 5 (just like C,D did for those vertical-only zone transits).

But complicate things further by having a sub-critical amount of pillars in each zone (allowing them to stay "convex" for all meaningful journeys, but introducing any number of necessary side-steps at no nominal extra cost), changing the size and shape of the rooms (length-wise, changes the cost, width-wise not at all) and the offsets of the various gaps leading between the room-zones and the connected room-zones (forcing certain diagonals, perhaps, as long as this and the pillars don't change the zone's essentially convex nature, so no cost-change there), plus perhaps add in an alternate route (H,I,J) at the bottom end to tempt certain E->F end-point travel through I (by way of H and J) instead of G (by way of C and D), according to those various matters and if you've got your system of nodes that says "it takes N steps to cross X, if going from Y to Z" in the simple example, it now matters much more where in Y you start/Z you end up, or indeed if Y and Z end-points are technically just floating and V and W (the true route end-points) play a part in dictating where on the outer-edge of Y and Z a truncated version of the route through the system would pretend to start and end under other circumstances.

Erm, IYSWIM.  But I can see how that last one-sentence/multi-parenthesised paragraph is far more convoluted than my diagram.  Hopefully you get the sense.

Might be better to be doing the whole "ignore my ramblings" thing.  But was basically trying to say as how that was what was most concerning me in my own personal fiddling around with the whole routing algorithm under my own personal approach.

[NW_Kohaku]

OK, it's getting kind of late for me, so my mind is getting a bit fuzzy, and you kind of lose me near the end where you start talking about X and Y and Z but not really Y and Z, but V and W.  (Or where on the map H-I-J is.)

Anyway, from what I think you're saying, we're talking about how many different path distances there are to keep accurate information of path distances.

Basically, I'd just fudge this, and say that a diagonal crossing of passing through A through C to G in that graph is going to take 3 tiles (or 2 tiles if you don't count the "doorway"), measuring center-to-center.  Maybe you can path through it faster, only in one tile, even, but you just store 4 tiles distance from A to G and from E to G, and 6 (5) tiles distance from A to E as the pathing distances in C. 

Maybe it's right, maybe it's wrong, but we don't necessarily need to make the estimate for what nodes we want to path through a perfect one.  So long as its reasonably close, it shouldn't be terrible if in a few situations, the dwarves go in a slightly-less-than-optimal direction because they didn't use corner cutting in their heuristic to determine which nodes to pathfind through.

In fact, if we were doing the sort of "Highway" system I was talking about earlier, hugging the right wall going from A to B would mean that the dwarf would try to exit A on the far West side of the room, diagonally move southeast to point 3, to point 4, then diagonally northeast to the right-hand entrance of B.  (Trip takes 15 moves, starting from the edge of A.) 

The trip from B to A, hugging the right wall, it only takes 11 moves.

However, at the same time, a certain amount of inefficiency is worthwhile to stop even bigger inefficiencies, like traffic collisions.

[Starver]

OK, it's getting kind of late for me, so my mind is getting a bit fuzzy, and you kind of lose me near the end where you start talking about X and Y and Z but not really Y and Z, but V and W.  (Or where on the map H-I-J is.)

1) Don't worry about it, I was just trying to explain (badly, it seems) the issue I had made an off-hand comment about.
2) X, Y and Z are "any given start, middle, finish" (or possibly "...start, finish, middle", context was all anyway).
3) H,I,J were hypothetical extensions to the original grid, but in my mind they'd be laid out like:

Code: [Select]

A B
 CGD
 E F
 HIJ
The idea being that E->F travel might have been 'tempted' to go via HIJ instead of CGD, depending on where in E and F the end-points were.  (The labels were for zones only, not specific end-points within those rooms.)
...although by that time A-G were no longer strict 5x5s (give or take the transition-ways), may not have been completely open within-themselves and may have had various other unstated variances from the 'perfect' A..G model originally given.  something HIJ-ish (maybe not departing from three zones) could have represented a false-indication of shortcut, or a false-indication of being longer, depending on certain configurations the complex might have.

But don't worry about that.  Or the issue.  I shouldn't have mentioned my 'aperture' concerns at all, at least not in the context of the discussion at hand.

[Draco18s]

Just FYI:
You don't need to return the shortest path, best path, or anything other than a path.

[NW_Kohaku]

I got in the mood for maths.  (Does that count as a "strange mood"?)

I just did a quick calculation in a spreadsheet, thinking about the difference between the top-down and bottom-up memory storage and searching methods...

Basically, if we work this like an "I.P. Search", where we organize the data structure "Top-Down", with the central "root" node functionally storing a directory of all the nodes below it, and each node below that storing a the nodes below it, then we have leaf nodes that store little data, but a root node that carries the phonebook.

Conversly, I previously mentioned organizing a "search tree" style of abstract node organization, this means that the root node stores no map of any nodes other than the ones it directly touches, but each lower-level node stores a map back to the root node.  This is a "bottom-up" data structure, with each leaf node carrying the longest abstract maps.

I was worried that the bottom up's having a map (or rather, a list) in each leaf node may be prohibitively costly in memory terms, so I went and did some math.

Each map is made of 2047 nodes (I just started with a map where each node is connected to 2 other branches to start simple, and went down 10 layers).  Each one carries its abstract map inside the data structure of the nodes themselves, although top-down and bottom-up shift the burden of carrying that map.

2^ means that each node connects to 2 branch nodes below it, 5^ means each node connects to 5 branch nodes, and 10^ means each node connects to 10 branch nodes.  This isn't a choice we make at this point - the nodes will connect to every branch node they touch, I'm just trying to get a feel for how the "slope of the pyramid" affects memory consumption.

To be able to compare fairly, I stunted the growth of the trees with more than 2 branches per node to only having 2047 nodes total.

Code: [Select]

Number of nodes per level:

Level    2^      5^       10^
0 1 1 1
1 2 5 10
2 4 25 100
3 8 125 1000
4 16 625 936
5 32 1266
6 64
7 128
8 256
9 512
10 1024


Top-Down memory Allocation:

Level 2^ 5^ 10^
0 2046 2046 2046
1 2044 2041 2036
2 2040 2016 1936
3 2032 1891 936
4 2016 1266 0
5 1984 0
6 1920
7 1792
8 1536
9 1024
10 0


Bottom-Up Memory Allocation:

Level 2^ 5^ 10^
0 0 0 0
1 2 5 10
2 8 50 200
3 24 375 3000
4 64 2500 3744
5 160 6330
6 384
7 896
8 2048
9 4608
10 10240


Sums:
Bottom-up:
2^ 5^ 10^
18434 9260 6954

Top-Down:
2^ 5^ 10^
18434 9260 6954

So, basically, it's a draw.  Or more specifically, it's symmetrical.  Why didn't I think of that?  Ah, well...

Anyway, more immediately useful, the "slope of the pyramid" helps greatly in reducing the amoung of memory this sort of data structure takes up.  Of course, we can't really affect that directly - the number of branches or leaves a node will have depends entirely on the shape of the map, although we do have a choice in the shape that nodes will take by the code we use to cut the map up into nodes entirely.

Now, since what this is storing is basically just a pointer, we're only talking about one byte per node, but this has a sub-geometric complexity growth with the number of nodes we use.  (Basically the O*Log_b(O) as a growth rate, where b is the number of branches per node, which would not be uniform.)

This means that we save more memory generally by just trying to make larger convex nodes, even if they have obstacles inside of them, even if it means that we have to do local A* pathfinding inside the nodes to get from one side of the node to another.  The larger and more complex the nodes are, the longer it takes to pathfind from one end of a local node to another, but we are buying back memory with pathfinding time doing this.  So it's pretty much a judgement call.

Now, the advantage of this sort of IP-based/quasi-search-tree searching is that you can simply go up the number of branches in the tree as it takes to find the branching node that contains both the start and destination nodes, and you never have to search a single node beyond those.  (You would probably want to search for a "shorcut" between those nodes, but that would only involve checking for "touching" between the connecting branches and leaves that don't involve jumping up a level in the abstract path, but that's a trivial amount of calculation when we've already shut off so much of the rest of the map.)

We might have to still do A* for local nodes, and making larger nodes might make the node-construction and node-merging/splitting code more complex, but the amount of time you would save in long-distance pathfinding would be tremendous.  You wouldn't have to bother at all with heuristics or searching for more nodes than necessary in the abstract tier in this sort of search tree.

It should buy signfiicant speedups at the cost of a relatively manageable amount of memory consumption.

[Niseg]

I've been thinking about algorithms for node grouping but as usual I hit the wall with constraints :

- A room is a group of nodes that have a  impassable and passable nodes.
-  Every passable node in a room must be reachable from every other passable node in a room (this is where BFS can help)
- a room's shape must be a rectangle

here are the derived things we need to do in order to group nodes in to rooms
- arbitrary room division algorithm
- room validation - modified BFS with post-runtime scanning for unvisited nodes.
- room resizing ,merging and node trading (for both squaring and discarding impassible nodes)
- A room can overlap with other rooms. With rectangles it's unstoppable. it would take too much memory to do it in another way.

Because we are pathing we should also store have a way to describe edges. We should also consider data structures which are good for caching . It's not too critical because it would be faster than O(k^N) .

We need a function which can quickly convert x,y,z coords to node id .

I'll try to setup some demo using those rules.

[NW_Kohaku]

Nodes don't need to be rectangles.

They can be rectangles, but don't need to be...

You can have convex shapes, like the right triangle shape, and it breaks no assumptions.

You can also have non-rectangular shapes like a circular shape.  See:

Spoiler (click to show/hide)

Image borrowed from Ironhand's thread.

Now, you can make that entire circular room a node.  Depending on what sort of pathfinding you use, you can make the whole outer circle around that room be a big node, as well.  All the tiles in the node are accessable, you just need a small amount of A* pathfinding to find a route around the circular room's walls.  So long as A* is bounded into a "local node pathfinding" where the shapes are guaranteed to be simple, you can still use A* very efficiently.

After that, you don't need to have overlapping rooms.


Oh, and making a coordinate into a node id is fairly easy - just take the x-coordinate, make it the first eight bits (768 tiles are the maximum number of tiles horizontally), take the y-coordinate, make it the second 8 bits, and then make the z-coordinate the rest of the bits.

You could also do it hash-style, but this would probably be faster and cleaner.


I'm suddenly thinking of something else, as well, but that will take a diagram...

[NW_Kohaku]

OK, let's go with a diagram...

Spoiler (click to show/hide)

This map depicts a "Central Staircase" "Modular Fortress".  It's the sort of fortress I try to avoid, but it's also really fast to set up and demonstrate an idea, so I'm going with that.

"X" means stairway, and "+" means door.  "S" means starting point, and "F" means finishing point.

Now, the red central staircase is the root node in this demonstration - the doors are their own nodes so that they can be locked, and that node will simply be pulled out of the map.  Each color change radiating from that central staircase represents a successively lower-tiered node, going down 8 levels to the cyan colored room.

Also note, this isn't a very large map, but it already has 9 tiers in it.

Now watch me tear a hole in my previous idea...

The problem with working with a search-tree organized node map would be that, even though the red line I drew represents the direct path from start to finish that A* would probably find, the blue line is what the search tree style of pathfinding would likely find.

I actually put in the yellow (tier 6) door south of the Finish Room (a tier 8 room) a little after I started typing this, which is why the room itself is the wrong color - it should be a yellow-green (tier 7) because it is accessable by a tier 6 room.  The change from being a tier 8 to tier 7 after having that door punched in would be a fairly easy change (you just change some pointers), so that's not a big deal, but the problem comes from the sort of situation when you have two very different routes to the same place.

The red line is a faster line.

The way that the search tree pathing works, it tends to work better for either fractally-designed fortresses or for fortresses with fairly long hallways.  The sort of fortress where everything is a big grid with interchangable hallways can screw with the pathing.

Now, previously, I said you could do a search for a shortcut by trying to cut out going up too many branches in the tree.  You can see this in the blue line where the blue line goes through the red-orange ring room around the central staircase.  There are some small lines indicating a possible place for nodes to be split.  If this is a search tree, the red-orange nodes are on equal tiers with one another, and the finish room is down the north branch's path of leaf nodes.  The west red-orange area holds the starting room.  Hence, in pathing, the starting room has to go all the way up to the central staircase node to find a common node both the starting and ending rooms share.  Then, the game can check and see that the two red-orange rooms are contiguous with one antoher, and cut the central staircase out of the equation, and make a "shortcut" between the two red-orange rooms, rather than going back up all the way to the node they have in common.

From there, it follows the branching nodes down the different hallways to the door to the Finish room, using a search tree rather than standard pathfinding to find the room you were looking for. 

Now, here's the potential problem - if we want to optimize for distance travelled, the red line (A* pathfinding) is faster.  To have the search tree find that route without using a heuristic or pahtfinding through the tree, it would require the Finish Room be a part of both the west red-orange room's leaves and also the north red-orange room's leaves.  This would cause a potentially huge jump in the amount of memory these search trees would need to take up in order to handle overlapping data.  This may be unacceptable, even in an optimal organization of the data.

Alternately, we just take Draco's statement at full value, and just return A path, even if it's not the shortest path, so long as it is a path you can calculate very quickly.