Ok, well was hoping the Grimy Traders forum's was working before I reached this stage. But I finally got some kinks out of my current (and way to long) DataMining script. I beleive I have nailed down Identifying, Sorting and Reporting tunnels of different criteria. So I thought I would begin working on bubbles. Currently I'm in a paper development stage, trying to work through bubble location in my mind before I acutally start typing and was wondering if anyone would like to share how they have accomplished this already?
I'm assuming that plotting warp courses is the most definite manner in which to identify a bubble. Anyone want to comment? Maybe some background on bubbles and gold bubbles might be useful as well. Thanks a bunch in advance.
P.S. I will be updated my script at Grimy's for anyone who acutally finds it useful. Many, many revisions.

Zoso

Talk to EP, if you can pry him away from his upcoming release of TWX. I know he's done a lot of research on bubbles and bubble mapping techniques. I've talked to him about it a time or two, but most of it was over my head, heh.

I agree with psion,hit up ep or maybe RammaR.I learned some from them though they probably didnt know I was really listening [:)]

Right on guys. (I'll pay you for the props as we agreed [;)])

I need to lay a bit of a foundation, so bear with me Zoso.

To find bubbles, you need to start with a search routine, the simplest of which is a breadth-first search. This type of search routine revolves around a queue, where new items to parse are added to the top, and the next item to parse is pulled from the bottom. Think of a nearfig routine. You start with a given sector, check each adjacent for a fig, marking them as tested and adding them to the top of the queue as you go. Then you pull the sector at the bottom of the queue and check its adjacents, marking and adding them to the top. And so on until you find a fig.

The key to using a breadth-first search for finding bubbles is watching the size of the queue. Let's start with sector 11, mark it and its first warp (so you know not to add them to the que again), and put that first warp out of 11 in the queue. Then you repeatedly pull the bottom of the queue, and add all unmarked ajacents to the top of the queue. If the queue runs dry before reaching a size of 200, you've found a bubble. Here is what the code looks like, at least for the breadth-first part.

while ($bottom <= $top)
setVar $focus $queue[$bottom]
setVar $a 1
while ($a <= SECTOR.WARPCOUNT[$focus])
setVar $adjacent SECTOR.WARPS[$focus][$a]
if ($marked[$adjacent] = 0)
add $top 1
if ($top > 200)
echo "*Queue too big, no gate found."
return
end
setVar $queue[$top] $adjacent
setVar $marked[$adjacent] 1
end
add $a 1
end
add $bottom 1
end
# The Queue emptied, and was < 200, so we found a bubble!
echo "*Gate Found, first warp = " $queue[1] "."
returnYou perform that test for every sector in the game. You might want to create some limits, like min size and max size. And the other thing you'll want to do to be especially accurate is to only add two-way warps to the queue.

Feel free to point out any glaring errors I may have made. That is totally off the top of my head and untested code, but looks right. Shout back with additional questions, or if you'd like me to clarify something.

+EP+

Thanks for the quick and detailed post EP. I'm hitting the sack so I will look into it in more detail tommorow, but the first thing that jumped out at me was....
quote:And the other thing you'll want to do to be especially accurate is to only add two-way warps to the queue.
Correct me if I am wrong, but i thought a bubble was defined as "X amount of sectors connected to the rest of the universe buy one particular sector" So other than the "Gate" sector, could any other sector not be >2 warps?

Zoso

I'm not referring to the number of warps a sector has, I'm referring to whether a given warp is one-way or two-way.

If you are testing sector 33 and adding its warps to the queue, you may find that a warp leads to sector 90, but 90 has no warp leading back to 33. So while the warp to 90 is an exit from your potential bubble, it isn't an entrance, so don't mark it or add it to the queue.

Keep 'em coming

+EP+

You're the man EP.My big problem came when the 1 way/2 ways came in.And 1 thing to remember,learn from my mistake.Clear avoids lol.

quote:I'm not referring to the number of warps a sector has, I'm referring to whether a given warp is one-way or two-way.

Gotcha, Did a little tinkering, but the queue never empty's. On the right path though I think.

Edit: Scratch that last statement, I figured out my problem. Had a leak from the bubble. Metal note, read the entire thread throughly before posting.... hehehe

Zoso

You can still find plenty of bubbles without the one-way test, but you'll miss some good ones too.

Later, when you are trying to improve search times, you'll want to adjust that max size of 200, as it's pretty time consuming. The reason I set it for 200 is because that is the max size for Gold bubbles, so a setting of 200 will find every one-gate bubble. If you aren't playing in a game with Gold bubbles, you're probably safe setting the max to 20.

+EP+

It's actually possible to have a bubble larger than 200 sectors, either via manual editing of warps or random chance at big bang. Say you have 10 bubbles in a game, it's possible one of them will have their one link into another of the bubbles. I have seen live games with bubbles over 300 sectors.

Cool, I see how that could be possible. Big Bang will not intentionally create bubbles larger than 200 sectors, but that doesn't mean that they won't exist.

So how did you find a >300 sector bubble?

+EP+

I didn't, I think it was Dr. Bad who found them. He was the data god.

Boo!

tw pretty occasionally creates bigger bubbles than the settings when e.g. two 150 sector bubbles happen to have the same gate, or adjacent gates connected only to the same 3 warp sector.

EP, it probably won't surprise you that finding a 300 sector bubble you do the same way as a 10 or 20 sector bubble. The example you gave above isn't terrible. (there's a couple of either bugs or things you didn't bother specifying in detail with one-ways, but there's simple fixes for those). If its going too slowly for larger bubbles, then to be honest, most of making it fast enough is just about not writing it in a particularly slow interpretted language. e.g. C++ or Pascal are a good 10-100 times faster than Zoc. Not sure where twx fits in there these days, if its still interpretted I'd assume you're far better off dumping the CIM/ZTM data and doing the processing externally. There are plenty of algorithmic speedups possible, but they're not really that necessary unless you want to generalise this to finding clusters of space with a small number of entrances (e.g. 100-150 sector gold bubbles with say 2 entrances)

Cheers,

Dr. Bad

In a 20K sector game I once found a bubble with over 1.8K sectors (don't ask how)...heh! Wildstar...is easier to learn from other people's mistakes than your own...life is too short to learn all of the mistakes by yourself! Muhahahaha..... Now Doctor Bad...when you going to poke your head out of retirement and come back and play with us a bit? Got a big draft game coming up where you could teach a lot of us some of your devious tactics!

I believe when setting up the game before hitting big bang you can set how many bubbles you'd like in the game and how big the biggest would be. I've consistently had bubbles of 180 sectors and some over 300. Never saw one 1800 though, talk about building an empire.