Okay. someone has got to say it.

Thanks to the Admins (or 'Admin'), this place has gotten Darn boring to Troll. I mean posts are either: "Hey here's a bug" ... or ... "yeah it's a bug".

I miss the great questions and convo's. Like: Why does it hurt when I pee? (Frank Zappa said this, not me.. no really). Does anyone else see the irony of a game being 'upgraded' while the intended audience is fading away??? I mean come on! for frig sakes

So. what does this have to do with the subject line? Absolutely nothing. I was bored, cause there was absolutely NOTHING worth reading here and I wrote a script. goofing around.. I'm not known for Notation/Comments in my scripts (I think the code speaks for itself), only thing I'm gonna say is that the attached script is meant to be used in conjunction with Rammers Twarp Gridder. Can anyone figure out how this script might be useful once in a while?

Oh and btw... to Admin. I dare you to delete this "ACTUAL" Topic

It's a DE nearfig report using a BFS-in search. Had one since Rev and I played in a game back in 2006. Try to figure out how to improve the search speed, there's several neat ways.

Yes it is. But it does something a little more than that. I draw your attention to the while loop: Lines 51 to 57.

It loops thru the path and marks them off for the next search? Isn't that an option that all figpath searches have?

Think you can find a way to do it all with a single BFS-in search? If EP is reading... yeh, you know what I mean.

I pulled the Breadth routine from Rammers Twarp Gridder script for a reason (it is EP's routine that Rammer had used). Making it better is a challenge that I might attempt, but I'm not sure what you mean byBFS-in search.

Doing a strict BFS search of all DE's with a closest fig >= 5hops away, might net you 2000+/- results. For example a bubble will contain multiple DE's that will meet that search criteria (DE with nearest Fig 5hops away). The routine I posted finds a candidate plots the course from the nearest Fig, marks the path as fig'd because Rammer Twarp gridder is going to use that same path. The end result is that any other DE's in that immediate area will be bypassed because the routine will think that there is a fig within 5hops. So you end up with an efficient 'Targeting' list for clearing out bubbles. The name of the script is Targeting_101.ts for a reason.. heh

BFS-in as opposed to a getNearestWarps search (which
is BFS out).

Doing a BFS of all unfigged DEs can be a daunting
challenge, as you said the queue can get pretty
massive. At the 8 hops range, you might be looking
at 1000 or more sectors.

It won't stop ram from hitting those sectors tho.
Ram's writes to it's own fig file, so you need to
work with that too if you want to interact with it.
Just because you write to the array doesn't mean
the array is persistent.

For the first run, fig distance is a good way to
clear out bubbles. But once you fill in the top 3
or 4, you will get many bubbles within the 5 hops
filter range.

For the single BFS, things get tricky. But it's
also a lot of fun. Graph theory and set transforms
are a really cool area of compsci, with a lot of
potential. It's one area that scripters haven't
really delved into much in TW, so it presents a new
area to explore.

It's rather easy, once you figure out how to use
a DFS, to use a single BFS and a single DFS to find
all single gate bubbles in the universe. Multi-gate
bubbles are trickier, tho. But it might be possible
to do the entire figpath search in a single BFS as
opposed to one for each unfigged sector. It may also
be possible to transform a single BFS to fit other
circumstances too. It's a fun challenge.

Sure, let me comment with a little personal history. You see, I've never been taught graph theory, search algorithms, or any other computer science subject. I struggled through trying to write a nearfig script, until Rev said "you need an array to track what you've already queued." I then wrote my first working Breadth First Search (or BFS, though I didn't know to call it that) in about 10 minutes. I proceeded to write and optimize BFS routines for everything I could conceive... including bubble searches.

I figured out several ways to use a BFS routine to locate bubbles, but they were all slow. While brainstorming ways to speed it up, I began to envision a way to find all bubbles with a single BFS. I often referred to it in these forums as my "universal theory". I banged my head on it off and on for a couple years. Then one day, again while chatting with Rev, I got caught up in it. At some earlier point I'd had a new idea, and I implemented it while we were chatting... breakthrough! - it seemed to work! Rev and I began testing it (he in ZOC, I in TWX) and as far as we could tell, it faithfully identified all single-door bubble sectors. And it did it in about 3 seconds for a 5K. The short summary of the breakthrough is that I allowed a sector to be queued in the BFS any number of times, but a sector could queue a given adjacent only once. At the end of the BFS, if a sector had only been queued once, then it was inside of a single-gate BFS.

This was probably a 2 or 3 year hobby pursuit, and it was a great deal of fun. I would often chew on this problem while driving around, picturing the TW universe, brainstorming ways to "flood it" to locate these air pockets (bubble). I don't know how many remaining players enjoy these logic pursuits, but this one was worthwhile for me. I'd love to hear about other people's own personal "universal theory" pursuits.

I worked on a similar method for about a year after
we talked about it last. I kept having trouble with
certain loop structures at the time, altho I've gotten
past that now. I started looking pretty heavily into
graph theory to answer some other questions I had
in trading (there's a lot of similarity), and they led me
to a new approach.

I ran into something called an articulation point. Turns
out if you DFS the entire universe, you can identify
bubbles or sub areas of the graph (universe) by counting
the number of branches on the DFS. These are formally
referred to as biconnected components of a graph.

http://en.wikipedia.org/wiki/Biconnected_component

http://www.cs.pitt.edu/~kirk/cs1501/notes/bicon.html

http://www.ibluemojo.com/school/articul_algorithm.html

All that said, I wonder whether a similar approach as
yours could be used to identify the nearfig paths for
every sector in the uni. Another possibility is to mod
the graph to make the search easier.