Print

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

[Starver]

To play a more accurate analogy, it would be as though time itself slowed down when too many people gathered in a city. Unlike the speed of light issue, which we can definitely measure in-universe, such an effect would be as unmeasurable to us as the pathfinding slowdown would be for our simulated dwarves.

Even before I read the second sentence, I was going "well, maybe it is like that..."

All jokes about life being more leisurely in the country, because they've got plenty of time while the city tries to get things done, if we're being simulated and certain conditions (large groupings of interacting consciousnesses, if that's relevant, but of course I think it'd be more like large groupings of interacting atoms, which make each and every star a computational nightmare on their own) take a lot of Oomph, but the simulation doesn't notice the world.  As you say.

The universe could be being 'simulated' by an exact 1:1 scale model of the universe being 'run' (which is a bit arbitrary when it comes to such an extreme) or via a single 'head' Turin machine.  Or indeed like this, which is essentially the same as the latter (and, ultimately, the former).

But if the universe is being strictly simulated in a linear fashion, things can't happen before their causes.  This is probably not the reason behind the speed limit of 'c' in such a scenario (which may be a feature of the modelling technique being used, only necessarily a 'bug' by your definition).  If the universe is being calculated in a way truly alien to us, perhaps there is some computational reason behind the old frames-of-reference problem (twins' paradox, etc), but it may be as hard to speculate about that as someone living on a Conway's Game Of Life grid would have in trying understanding a circular ripple.  So that way There Be Dragons.

I should be able to mod my dwarves to have [SPEED:-1], which would cause them to appear at their destination before they left.

Um, no.  DF works linearly, and while there's no technical reason why Toady could not allow instantaneous travel (one blink, at location A; next blink, at location B... or possibly same blink disappearing from A even while appearing at B) finding an agent at location B prior (even by one blink) even to the decision to leave location A is not possible, as is.

(If DF were actually to run a multi-pass look-ahead system of calculating movements, covering a 'blink range' sufficient to encompass a given amount of time travel prescience, then it may delay the 'T-zero' blink output until it has worked out T+1 decisions, found out that Dwarf42 wants to have already been somewhere else at T-zero, re-try T-zero with both pre-move and post-move Dwarf42, ensure that the presence of the latter Dwarf42 doesn't change the mind of the former, and then 'release' the T-zero blink in order to re-calcuate for new T-zero (was T+1) and T+1 (was until now the unknown future and still uncalculated).  Otherwise, if latter Dwarf42 manages to do something (e.g. pull a level, assuming that this effect were immediate on the accessibility of the faster-than-time path being used[1]) that would have prevented the former Dwarf42 from making that trip, there'd be a "Dwarf42 cancels time-jump: Disturbed by Paradox" or similar, and the T-0 release would occur without such a trip.  And you could have a blink range of T0..7 to allow for a series of backwards jumps, but Dwarf42 couldn't actually make more consecutive backwards jumps than the range allows, not without restarting the whole fort from a previous save-point and recalculating, which I'm not sure is what anybody wants.  Imagine in a mature fort, Dwarf42, Legendary in every art, craft, skill and martial art there is, making hundreds, thousands or millions of SPEED:-1 steps back in time to be around at the very start of the fort, potentially changing its whole history.  Imagine a Berserk Dwarf42, of the same military prowess, doing the same, and actively wiping it out as a site.  Killing himself, his parents or, indeed, his grandparents in the process.  Or if not that, at least making a site so different so that there'd be no Dwarf42 the Peasant immigrating shortly thereafter.  I don't call it a bug that this cannot happen (although I think it would be interesting if something of a limited nature of this kind could do so, it would have to split 'alternate branches in time', though, if it doesn't do a whole-history recalculation to wipe out paradoxes, or applies a handwavium fudge of some other kind).  As such, I don't call it a bug that one cannot call function that in (say) seven iterations of a simple loop cannot find the best (or even a reasonably best) path between absolutely any point and absolutely any other point.  The limitation is informatical, which is not to say that a LogN function might not be available where an N.LogN function is currently used (or whatever the order of overhead actually is).  But a bug would be something incorrect, not merely suboptimal.)

TL;DR; - I don't expect to see the Urist McPicard Manoeuvre happening anytime soon.

To be completely honest myself, I tend grow bored of a fort shortly after initial setup; right when I start plotting out the MOST EPIC FORTRESS EVER CONCEIVED™ and remember that building large (complex and therefore interesting) structures is still a PITA, and thus am rarely affected by this myself.

For the last few versions, I've rarely got beyond year 3 or 4, and approaching 100 dwarfs or so (nowhere near the habitually init-revised cap of 300, and 150 kids) before my slow progress (most of the delay is my micromanaging things, although the interminable wait for my the dozen or so Seasonal Saves (my own petard, by which I hoist myself)) gets overtaken by the next version needing trying out (from scratch), or the realisation that I didn't EPIC it enough and wanting to start again...  So I know what you mean.  Although as the pathing algorithm hasn't significantly changed for quite a long time (and I do tend to accumulate an awful lot of spare stones, which is part of the original complaint here, IIRC) so I hope you still don't mind me making my own representations on the subject.



[1] Player interaction in-between T0 and T+1 is another issue.  In the cached T+1 time-slot, Dwarf42 decides he's jumping back to T0 to craft something, but just as T0 becomes 'real', with Dwarf42 now in both places and T+1/+2 now about to be calculated as the new T0/+1, the player unsets Dwarf42's craftsdwarf assignments.  This cannot be applied to pre-jump Dwarf42[2]the only logical situation is that post-jump Dwarf42 finds him or herself having to find something else to do.  Regardless, a tachyonic dwarf could not keep moving backwards in time, and would have to actually bide a wee while awaiting reality to catch them up, at some point.  Which sort of puts the mockers down on a SPEED:-1 dwarf or indeed any negative number in there.

[2] Actually, it can in a one-jump scenario, he could just fade out and "has never jumped back, honest guv".  But imagine a multi-step jump scenario, which is then allowed to continue for part of that multi- before the correction is made that disperses the possibility of the jump having occurred.  You could again Marty McFly him, but it leaves echoes of effect from him having been there and altered others' behaviour.  Not that this isn't usable in some way, but it feels very unsatisfactory to me.

[Niseg]

I started messing around with "node grouping" . In generally I want to write a small program to dynamically generate rooms. I wrote a very simple JS program and put it  here (this free host has trackers but no ads)
http://niseg.0adz.com/test_maze.html

ps: clicking the floors  ('+')toggles them  to walls ('#') and back.

The current thing only count the neighbors and display them which isn't that useful.

My current idea is based on breadth first search. I'm thinking about a combination of "search depth" and number of neighbors in order to find choke points and use them as new starting points for my search. After i find those points I can group the other nodes into rooms. The rooms can be farther reduced by the same algorithm to a region map.

here is my idea
given this maze where + is floor and # is wall X is starting point

Code: [Select]

##################
#++++++++++++++++#
###########+######
#+++#+++#++++++++#
#+++++++#+++#++++#
#+++#+++++++#+++X#
##################

this is the same maze with numbers which signify the "depth" of a breadth first search

Code: [Select]


##################
#++++++987666789+#
###########5######
#+++#+++#76543222#
#++++++9#765#3211#
#+++#++98766#321X#
##################

You'll notice as I you get farther away from the X you get bands of numbers which show the distance between  X and that spot. After inspecting the search steps you can see choke points at 4 and 8 and one at 5 which is harder to find  . Those are generally  are good spots to start a new search and to setup a "room".

What I hope is the next iteration I'll generate this map automatically . Using the search I can probably find dead ends(I think i finished the search part) . I'm don't remember much about graph theory but I'm digging into the subject .

Any suggestions are welcome. Feel free to do whatever you want with the code ; it's rather simplistic and messy . I do need an optimization on search (marking visited nodes with 2,getting rid of silly search and then revert to 0s ).

I've now thought of a way to define rooms - by checking for connections between similar depth rooms like the 6s which are clearly disjoint which makes the 5 point between them a good spot to make a split like the 4 and 8. I also have a the general issue of where to start the search and how to limit the depth.

[NW_Kohaku]

You'll notice as I you get farther away from the X you get bands of numbers which show the distance between  X and that spot. After inspecting the search steps you can see choke points at 4 and 8 and one at 5 which is harder to find  . Those are generally 

You forgot to finish your thought, there...

Anyway, the problem with a breadth-first search like this is that every time something like water flows over the area, a door is locked, or someone channels a floor, you'd have to do another breadth-first search.  That's painful.

[Niseg]

You'll notice as I you get farther away from the X you get bands of numbers which show the distance between  X and that spot. After inspecting the search steps you can see choke points at 4 and 8 and one at 5 which is harder to find  . Those are generally 

oops kinda finished it
You forgot to finish your thought, there...

oops kinda finished it. They are good starting point and splitting points.

Anyway, the problem with a breadth-first search like this is that every time something like water flows over the area, a door is locked, or someone channels a floor, you'd have to do another breadth-first search.  That's painful.

The idea is not to replace pathing with BFS it would be silly. BFS was chosen  in order to join nodes into a region. the depth of the search is gonna be limited and it would only require changes when a path is blocked off or things like that then all you'll need to do is check if a path still exist from the region affected to its listed neighboring regions.

You'll still use A* or whatever you want to move from region to region but you won't have to do go through a very long N and you'll be heading toward the general direction of your target but you won't make mistake due to the fact you are using a region map.

finding a way to chop the map into regions is the complicated part.

Another optimization i can think of is improve heuristic function runtime. I once had a trick to find a decent rootfinding guess  ( I totally avoided rootfinding and used the guess ) my guess consists of counting leading zeros and them shifting the number in half. In general I would generally avoid the sqrt in general the multiplication is bad enough.

[NW_Kohaku]

The idea is not to replace pathing with BFS it would be silly. BFS was chosen  in order to join nodes into a region. the depth of the search is gonna be limited and it would only require changes when a path is blocked off or things like that then all you'll need to do is check if a path still exist from the region affected to its listed neighboring regions.

No, that's exactly what I meant - you're doing a flood search every time you need to update the connectivity map.

If you are only updating the nodes you are currently partitioning off, that does help, however.  It does mean that you need to be careful about making sure you take into account all ramifications, and you will probably need to mess with the neighbor nodes to make sure all the paths they expect to be open are still open, as well.

Another optimization i can think of is improve heuristic function runtime. I once had a trick to find a decent rootfinding guess  ( I totally avoided rootfinding and used the guess ) my guess consists of counting leading zeros and them shifting the number in half. In general I would generally avoid the sqrt in general the multiplication is bad enough.

They don't use sqrt right now - as far as I can tell, they just functionally use the largest of the three distances, x, y, or z.  Since diagonals are free, 3 spaces directly to the east and 3 spaces east and 3 spaces north are the same distance away, 3 spaces. 

[tps12]

They don't use sqrt right now - as far as I can tell, they just functionally use the largest of the three distances, x, y, or z.  Since diagonals are free, 3 spaces directly to the east and 3 spaces east and 3 spaces north are the same distance away, 3 spaces. 

I thought I remembered someone verifying that diagonal movements were weighted correctly and took sqrt(2) times as long as straight moves.

Edit: Diagonal movement is weighted correctly when it takes place, but the A* heuristic is Manhattan distance (sum of distance rather than max).

[Starver]

They don't use sqrt right now - as far as I can tell, they just functionally use the largest of the three distances, x, y, or z.  Since diagonals are free, 3 spaces directly to the east and 3 spaces east and 3 spaces north are the same distance away, 3 spaces. 

I thought I remembered someone verifying that diagonal movements were weighted correctly and took sqrt(2) times as long as straight moves.

My impression as well, from The Other Improved Pathfind Thread (TM).  Yeah, I could search for it.  No, I haven't been doing.

Not that this is the point, but while Manhattan distances mean a diamond shape of "equal distance", and diagonal=1 enhanced Manhattan means square-shaped "circles", diagonal=2^0.5 still won't give you a circular 'circle'.  It'll be correct (within a unit or so) at orthogonals and diagonals, but at all angles in-between you'd potentially be not getting as far as a 'true' radius for the same steps.  Which leads onto the whole issue of paths from corner-tile-to-corner-tile across a 4x5 tile area are all 4 steps[1] but there's four different routes that can be taken that are exactly equivalent:

Code: [Select]

01... 0.... 0.... 0....
..2.. .12.. .1... .1...
...3. ...3. ..23. ..2..
....4 ....4 ....4 ...34

...and the larger the area, the more routes.  Which is why I quite liked (in the previous thread) the idea of convex zones that can keep a track of a single measure from all access points[2] to all other access points.  These convex zones would be defined as having at least one barrier-immune path available to cross from all relevant edge-points to all other relevant edge-points without being impeded.  (A pillar in the middle of a 3x3 room would fully impede corner-to-corner diagonal travel (two unit steps with a root-2 step in-between), and impede centre-edge to centre-edge cardinal travel (two root-2 steps instead of two unit-steps), but wouldn't have bearing upon any other journey.

A very simple example says that a "corner-junction" 3x3 room with doors at (say) centre-West and centre-South would still allow the same journey (from one doorway, step onto SW corner, then to other doorway) regardless of any piller (central or side-connected) except for having one in the SW corner on only point of contact that this 3x3 would otherwise have to be involved in.  This is an absurdly simple example, of course, but shows us a convexity complication.

W-E travel from centre-west to centre-east doorways bounding the 3x3, having a central pillar, could be accomplished by entering from the doorway square either at a diagonal (NE,SE) or directly (E) then stepping to the side of the pillar (E and E for the "pre-diagonalled" step, NE or SE if they first stepped on the horizontal) for a choice of four different routes, and then a further pair of route-choices (diagonal and horizontal or vice-versa) to get into the opposite doorway.  Whichever of these eight routes is taken, the step-time = 2x(1+root(2)).  It could be treated as a modified convex zone.  Everyone has to go that distance across it, regardless of how they accomplish it.  And what if one had a string of such rooms?  (Including corner-connector type rooms as already discussed.)

This is a fairly common type of dig-out construction for me (at least until I open the area out), closely followed by that of 5x5 rooms.  (Later on, I may open out the doorways to make them more of corridors, which would change the dynamic, of course.)  The rooms may have workshops in them (essentially representing a certain 'pillar' configuration for each workshop type, ignoring those that would actually block certain door exits in the first place).  Each room would be an easy zone to map, and together they'd be a meta-zone where passing into the workshop-corridor at one end one should be able to know that, regardless of the exact pattern of side-steps[2], they've got a fixed distance.  And that they don't need to worry about the middle bit for now, just use that information in their initial route-finding algorithm and if this turns out to be the favoured way (indeed, a possible one!) then when they get to the room, meta-room or, perhaps meta-meta-room, work out which of the many otherwise identical routes they are now going to take.


I'd relate this to the "Pinch-points" thread, except there's a bit of an exception to that rule.

Code: [Select]

A####
 # #
1+ #
2+ +4
3+ +5
 # +6
 # #
####B

Depending on whereabouts in the room from the left you enter, and depending on the whereabouts in the room to your right you are going to depart, it's entirely possible that two different routes (door 2 to door 4, or door 3 to door 5) could be as easy to navigate.  Being forced to make  side-steps in an otherwise horizontal journey might encourage you along one particular of these.  Or a journey from entrance A to entrance B could have you diagonally moving 1..4 or 2..6, for the exact same journey.

So in one, there's a pinch-point (not seen, but dictacted to by the outside) and in the other there are pinch-points two-tiles wide (you can easily find ones even wider, or even discontinuously distributed, say where a pillar-and-gap repetition occurs).  Now.  How to abstract those?  If one could, it could be advantageous, but is the overhead in searching for that kind of feature too expensive?


[1] 5.24-and-a-bit. time-units under the root-2 schema, where a non-gridded distance would be 5.

[2] Important only, perhaps, in some future Additionall Improved Pathfinding technique which can say to itself, while working out the merits of different meta-paths with different on-route characteristics, "That area's busy, but there are plenty of opportunities to side-step and avoid crawling, unlike a single-tile tunnel".  In fact, forced side-steps at the advantage of avoiding differently-sidestepping oncoming traffic might be better than straight-through single-tile tunnels where oncoming traffic slows you down to a (literal) crawl.

[Niseg]

I did a small change to my program by enabling BFS from top left floor node. it did crash on me during development including an infinate loop hopefully I fixed the bugs . Use it at your own risk (at worst it will crash your browser or halt it). I disabled edge wall toggling so it should be more stable. I bet you can still find a way to kill it. 
http://niseg.0adz.com/test_maze.html

the old one was renamed to
http://niseg.0adz.com/test_maze1.html

[NW_Kohaku]

They don't use sqrt right now - as far as I can tell, they just functionally use the largest of the three distances, x, y, or z.  Since diagonals are free, 3 spaces directly to the east and 3 spaces east and 3 spaces north are the same distance away, 3 spaces. 

I thought I remembered someone verifying that diagonal movements were weighted correctly and took sqrt(2) times as long as straight moves.

Edit: Diagonal movement is weighted correctly when it takes place, but the A* heuristic is Manhattan distance (sum of distance rather than max).

Unfortuantely, I don't see anything in there talking about any proof that moving diagonally takes 1.4 times as long as moving horizontally, especially since DF movement diagonally does not have any evidence of moving slower than horizontal movement.  I'd have to ask G-Flex if he still believes that, and if he has evidence of that statement.

Distance in DF is calculated in terms of concentric cubes - just look at how constructions list the distances to the potential building materials, or the impact of noise.  Diagonals are considered an equal distance to horizontals. 

[tps12]

Unfortuantely, I don't see anything in there talking about any proof that moving diagonally takes 1.4 times as long as moving horizontally, especially since DF movement diagonally does not have any evidence of moving slower than horizontal movement.  I'd have to ask G-Flex if he still believes that, and if he has evidence of that statement.

After running around in the arena a bit with a stopwatch, I'm going to retract my earlier assertion and agree with you. I feel like the idea that diagonal movements cost more has been "around," so I don't think G-Flex just made it up out of nowhere (any more than I did when I just asserted it), but I'm convinced it's wrong.

[Reelyanoob]

What about player-created paths?  Not traffic designations, but set point A to point B paths that creatures can incorporate into their calculated paths.  Only the player actually understands his or her fort's layout well enough to optimize pathfinding within it.  Or optimize it for aesthetics so they'll actually use the nice paved roads, or if the player wants the manic little beard transports to be sure to wander past all the nice calming statuary.

I thought that was the point of traffic designations?  How would you go about doing that without traffic designations?

Traffic designations only alter the costs of nearby cells, favouring A* pathing in certain directions.

The idea of manually setting control points is to have a pre-stored section of a path. So, you find the nearest control point, and calculate the nearest control point to your destination. If they're the same, you use normal path finding, if they're not you path to the first control point, follow the stored path to control point 2, and then path to the destination. It'd be best if you could manually link the control points into a network, then dwarves could sample the path from node to node to find the way to any destination very quickly.

Actually it might be better to be able define the search nodes on the scale of whole rooms (similar to burrow designations). Because with the "control point" system as i mentioned it above sometimes a dwarf would backtrack for no reason (since sometimes the destination square would be close to a node on the other side). Pathing into a region should alleviate that possible problem

Another option to storing whole paths is to store a series of waypoints sampling the path, then pathing from one waypoint to the next as you go - this could be used in the control point system eg storing portal/doorway locations between adjacent nodes

[Draco18s]

What about player-created paths?  Not traffic designations, but set point A to point B paths that creatures can incorporate into their calculated paths.  Only the player actually understands his or her fort's layout well enough to optimize pathfinding within it.  Or optimize it for aesthetics so they'll actually use the nice paved roads, or if the player wants the manic little beard transports to be sure to wander past all the nice calming statuary.

I thought that was the point of traffic designations?  How would you go about doing that without traffic designations?

Traffic designations only alter the costs of nearby cells, favouring A* pathing in certain directions.

Partly incorrect.  Traffic designations don't make A* favor pathing certain directions but through certain areas.

And the advantage of node points is better than traffic designations, as the idea is to give A* more shortcuts.  Traffic areas reduce the number of processing cycles because A* checks fewer tiles.  Pathing node points cause A* to get from one area to another without having to check ANY of the tiles in between.

Effectively, using node-points would cause there to be a wormhole in the map (as far as A* is concerned) with a "traffic cost" of 1/2/5 (depending on traffic settings of the end point) so that A* can skip across the fort with few itterations.

[NW_Kohaku]

Starver:

I've been looking over some of the previous pathfinding threads recently, and I think this link to hierarchical annotated A* pathfinding is something you should probably check out. (credit: link provided by Footkerchief here.)

The article basically talks about how to cut up a map into a multi-tier pathfinding system, but then also strip out the superfluous data.  If a 3x3 clearance pathway exists, and several 1x1 clearance pathways exist, then you only need to record the 3x3 pathway as part of the map, for example. 

I still want to do a bit more research before I really try to put out a cohesive plan, but from what I have read Toady talking about on this, the real problems he has with most of these is making sure that the hierarchical systems would not take up too much memory overhead, and could react to dynamic changes in the map's features without taking up more time than updating the connectivity map does already.  I believe focusing debate upon matching those two criteria may lead to more potentially persuasive suggestions to Toady.

Traffic designations only alter the costs of nearby cells, favouring A* pathing in certain directions.

The idea of manually setting control points is to have a pre-stored section of a path. So, you find the nearest control point, and calculate the nearest control point to your destination. If they're the same, you use normal path finding, if they're not you path to the first control point, follow the stored path to control point 2, and then path to the destination. It'd be best if you could manually link the control points into a network, then dwarves could sample the path from node to node to find the way to any destination very quickly.

Actually it might be better to be able define the search nodes on the scale of whole rooms (similar to burrow designations). Because with the "control point" system as i mentioned it above sometimes a dwarf would backtrack for no reason (since sometimes the destination square would be close to a node on the other side). Pathing into a region should alleviate that possible problem

Another option to storing whole paths is to store a series of waypoints sampling the path, then pathing from one waypoint to the next as you go - this could be used in the control point system eg storing portal/doorway locations between adjacent nodes

I can see that, and I've been reading up more on A* and pathfinding in general, so I think I have a better understanding of the probem now than I did at that point, but the problem I have with manual control is that people don't really use traffic designations already.

Now, I could reluctantly agree with a "designate a room" system where you manually paint rooms, designate bedrooms or other "dead ends", while at the same time designating "hallways" that encourage pathing, and use a manual sort of tiered nodal pathing structure in that way.  The thing is, ideally, this should be automatic.  What if someone is a newb, and doesn't understand it, or if someone just forgets to paint rooms after a period of time, or other problems?  Yes, they would eventually be forced into painting pathfinding systems, and it would be more powerful and flexible than encouraging use/exploit of doors and z-level changes to control pathing, but I really see an automation of this sort of very dry, technical control of AI as being the sort of thing that should be automated.  Especially since something like a flooding of part of these rooms would necessarily have to cut some of these hallways into pieces when they could no longer maintain connectivity.

As I said in the upper half of this post, I'm trying to come up with a good way to dynamically update a multi-tiered connectivity map for less than the cost of a connectivity map upadate in the current system.


Ninja response quasi-edit:

Partly incorrect.  Traffic designations don't make A* favor pathing certain directions but through certain areas.

And the advantage of node points is better than traffic designations, as the idea is to give A* more shortcuts.  Traffic areas reduce the number of processing cycles because A* checks fewer tiles.  Pathing node points cause A* to get from one area to another without having to check ANY of the tiles in between.

Effectively, using node-points would cause there to be a wormhole in the map (as far as A* is concerned) with a "traffic cost" of 1/2/5 (depending on traffic settings of the end point) so that A* can skip across the fort with few itterations.

Not to disagree, with what you are saying, but to illustrate it, the hierarchical AA* has a good demonstration of this:

Spoiler (click to show/hide)

A map is cut into nodes, with black walls and blue water tiles, and the map is designed to allow for amphibious creatures.


Connections are drawn between the nodes, for each mode of transport.


The nodes are abstracted, and superfluous connections are discarded.


The resulting pathways are stored like shown.  If a unit wants to move from the top right C2 section to the bottom right C3 section, then the computer can simply look and see that it needs to do standard/"local" pathfinding to one of the "exits" to C2, add on the distances that are stored for walking through C4 or C1, and then do standard/"local" pathfinding to the exact tile in C3.

A walk through C4 takes 4 moves, while C1 takes 7 moves.  Any path made will follow that exact path (excpeting "dodging" a creature that is in the way, which does not seem to require a full re-pathing), so there is no reason to do a full A* check on those sections of the map unless you are performing a "local" pathfinding to particular tiles in those specific nodes.  Which exact node the unit will walk through will depend on local proximity to the exits.

[Draco18s]

I've seen that article before.

[Niseg]

The HAA* looks  pretty good and it's generally what I was thinking about.  I'm more thinking about an arbitrary split too instead of my complex BFS  aimless BFS idea. My Idea is not really about speeding up the algorithm but spreading  by splitting the large pathing problem to many smaller pathing problems.

I improved my little test program that I'm checking BFS for splinting of rooms . I added a path count on each possible paths left for each node onc reached . I then color coded the output to :
3+ paths = green
2  paths = yellow
1  path  = orange
0 path = red (not necessarily a dead end .
it looks like this now:

Spoiler (click to show/hide)

I'm thinking of making  a parallel bfs function  start from a few central spots so they compete on grabbing territory This would probably require me to mark owned rooms for each search . This way I can Easily find connections by collisions  of the BFS . This bfs method is still problematic since it doesn't make square rooms but that can be fixed  in a later stage by node exchange;)