| www.ClassicTW.com https://mail.black-squirrel.com/ |
|
| Bubble finder algorithms https://mail.black-squirrel.com/viewtopic.php?f=15&t=33412 |
Page 1 of 1 |
| Author: | Mongoose [ Tue Aug 14, 2012 8:17 pm ] |
| Post subject: | Bubble finder algorithms |
Have bubble finder algorithms been discussed anywhere? Is SWATH's bubble finder still considered to be the best out there? |
|
| Author: | Promethius [ Tue Aug 14, 2012 8:27 pm ] |
| Post subject: | Re: Bubble finder algorithms |
Mongoose wrote: Have bubble finder algorithms been discussed anywhere? Is SWATH's bubble finder still considered to be the best out there? I personally prefer this one: viewtopic.php?f=15&t=21335&p=183152&hilit=probubble#p183152 ...but I might be a bit biased. 
|
|
| Author: | Mongoose [ Tue Aug 14, 2012 9:09 pm ] |
| Post subject: | Re: Bubble finder algorithms |
I'm not sure I'm reading that correctly. Does it only find bubbles with one gate? Don't Gold bubbles usually have 3-4 gates? |
|
| Author: | Promethius [ Tue Aug 14, 2012 9:14 pm ] |
| Post subject: | Re: Bubble finder algorithms |
A bubble should only have one way in. It might have more than one way out though. |
|
| Author: | Mongoose [ Tue Aug 14, 2012 9:44 pm ] |
| Post subject: | Re: Bubble finder algorithms |
I'm interested in things like cutting the whole universe into large pieces... or finding a minimal cut that encloses all the MSLs. |
|
| Author: | Promethius [ Tue Aug 14, 2012 10:47 pm ] |
| Post subject: | Re: Bubble finder algorithms |
Mongoose wrote: I'm interested in things like cutting the whole universe into large pieces... or finding a minimal cut that encloses all the MSLs. The best person to contact on that would be EP. I know he has worked with bubble algorithms a lot. Might be able to modify the bubble script to allow more than 1 warp in to come up with larger "cuts". Defending it would be harder than the single warp-in, but a corp could do it possibly. |
|
| Author: | ElderProphet [ Sun Aug 19, 2012 10:38 pm ] |
| Post subject: | Re: Bubble finder algorithms |
I've done a lot of work with bubble searches over the years. I didn't study others' algorithms, but rather I came up with my own methods. I do believe I came up with a unique algorithm (after years of trying) that is able to find all single-door bubbles in the entire universe by running a single breadth-first search. Do you know where I might publish my work, and finally be recognized for my brilliance?  The obvious problem with bubble searches is that they can take forever to run. A simple single-door bubble search could be done by avoiding a sector, performing a BFS from Terra, and seeing how many sectors were queued. It would be Sectors-1 unless the voided sector is the door for a single-door bubble. An un-optimized TWX script can run this on a 5K universe in about 6 seconds, but the time that it takes increases exponentially with size. So a 30K universe (6x bigger) would take about 36 times as long, or 3.6 minutes. Natively, it would be much faster though. I think of this as an outside-looking-in approach, where you are looking for the "shadow" left when a sector is avoided. Assuming complete warp data, this method is comprehensive, but slows (without optimization) beyond a single-door, or in larger universes. For the TWXers, that script is as follows: Code: clearAllAvoids setVar $door 2 while ($door <= SECTORS) setAvoid $door getNearestWarps $warps 1 setVar $bubbleSize ((SECTORS - 1) - $warps) if ($bubbleSize > 0) echo "*Door: " $door ", Size: " $bubbleSize end clearAvoid $door add $door 1 end Still, there are a number of ways to optimize either approach, which we could brainstorm here or via chat sometime. IM me if you want to schedule something. |
|
| Page 1 of 1 | All times are UTC - 5 hours |
| Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |
|