So after finally quitting wow I need something to do other than my C++ project. I can safly say I remember a good 70% of the scripting commands and proper syntax. I'd like to pick up where I left off and that means getting back to my TW project I was working on.

Anyways to my question:

BFS (Breadth First Searchs) I have allways been kinda 50/50 on. I understand most of it but just have never been able to impliment it correctly. So I am imploring you uber scripters to help put it in plain english.

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

I have the concept but when it comes to the newer 2.04 command provided by EP I just can't seem to connect with it.

This is my understanding of it


Im interested in trying to find tunnels/deadends for fig hits.

Thank you for your time.
-Kaus

Elder Prophet has a great example on Grimy's

Thank you, I do have that .ts but I still have a hard time with it.

Guess I'm just slow

-I'll rebrowse it and read the M()Mbot.ts maybe ill get it if I play around somemore.

I used EP's routine in my Unexplored Sector Scout script as above (although I removed a cuple lines for ease of reading --they pertained to how far away my script would look before giving up).

There's Two Array's: CHECKED and QUE.
QUE is initailized to the 'current_sector' or start point. Now what helps me to undersatnd how this routine works is to imagine a STACK, the kind used in programming.

Think of the QUE array as 'the stack of sectors to be looked at' The FIGBOTTOM variable points to the place in the STACK that will become the FOCUS (FIG_Focus).

Now all the adjacents of the QUE[FIGBOTTOM], the FOCUS, are added to the QUE Araay and the FIG_TOP variable pointer moves up in essence increasing the size of the STACK

...so QUE at start equal our currentsector, lets say sector 1:
setVar QUE[1] 1

now we add all the adjacents to the QUE:
setVar QUE[1] 1 <---FIG BOTTOM AND FIG TOP
setVar QUE[2] 2
setVar QUE[3] 3
setVar QUE[4] 4
setVar QUE[5] 5
setVar QUE[6] 6
setVar QUE[7] 7 <---FIG TOP

...once this is done then the FIGBOTTOM variable is incremented and now points at QUE[2], which is now sector 2, and now the QUE might looks like:

setVar QUE[1] 1
setVar QUE[2] 2 <---FIG BOTTOM
setVar QUE[3] 3
setVar QUE[4] 4
setVar QUE[5] 5
setVar QUE[6] 6
setVar QUE[7] 1
setVar QUE[8] 3
setVar QUE[9] 7
setVar QUE[10] 8
setVar QUE[11] 9 <---FIG TOP

Now the QUE (STACK) contains adjacents of sector 1 and sector 2. This is howthe QUE is populated.. however you'll notice QUE[8] and QUE[3] both point to Sector 3. This is where the CHECKED array comes into the picture. EP's routine references the CHECKED array and would see that Sector 3 has alrady been CHECKED.

As FIGBOTTOM moves 'up' the array towards the 'TOP', it is checked against a Deployed FIghter Array to determine if a Fighter is present. As soon as one is found the routine RETURNS to the calling routine where $FIG_Focus points the the Sector we're looking for.

Hope this helps

Okay, let's boil this down.

Anticipation scripts just try to figure out a probable sector you'll hit next in a grid. It's used whenever you have lag to deal w/, either because your ping blows goats or because you're using tpad/twarp to photon or drop. Mostly all they do is find an adj sector and use that.

Classic anticipation does nothing more than wait for you to hit a 2-way and torp the other side, it can be expanded to hit 3-ways w/o a lot of additional problems, but that's why ram's gridder has a flex grid mode... to avoid those kind of classic anticipation shots.

Why? Because more complex stuff isn't all that neccessary, and the more work you try to do after the fighit the slower your response will be. You can't really use a BFS on-the-fly after a fighit, it's just not fast enough. But you can pre-calculate courses and do a number of things that are saved as parms. That's why I have NearestTun and NearestDE sector parms, my data miner finds the nearest of both for each sector and attaches them as parms.

If that's basically what you're trying to do you'll need to pre-cache all of it, what you're trying to do won't work directly for grid defense.

Ok, makes sense

----------------------------------------------------------------------------------------------
setVar $i 1
#set i to 1 (does the 1 actually equal a numeric value or in this case does it represent true?)

if ($figGrid[$focus] > 0)
#Lost here

add $i 1
#add 1 to i

---------------------------------------------------------------------------------------------

Does "i" actually equal a numeric number in the above example or is it a perverbial true or false statement. For your near tun/de your pre caching all the data you use correct? Doesnt that slow you down? I guess I'm confused why the BFS isnt the best approach? I have to assume the BFS is slower due to the size of the array but I can't think of another way to load the data so you can find said deadends.

Ok, makes sense

----------------------------------------------------------------------------------------------
setVar $i 1
#set i to 1 (does the 1 actually equal a numeric value or in this case does it represent true?)

if ($figGrid[$focus] > 0)
#Lost here

add $i 1
#add 1 to i

---------------------------------------------------------------------------------------------

Does "i" actually equal a numeric number in the above example or is it a perverbial true or false statement. For your near tun/de your pre caching all the data you use correct? Doesnt that slow you down? I guess I'm confused why the BFS isnt the best approach? I have to assume the BFS is slower due to the size of the array but I can't think of another way to load the data so you can find said deadends.

Consider the size of the arrays and the amount of work that has to be done in order to run a BFS for each fighit versus the amount of data that has to be stored just to remember the nearest DE and nearest tunnel, and the amount of time it takes to just load that. That's why BFS is too slow for on-the-fly grid defense, it takes 200+ ms to do the task, which more than doubles your reaction time. It turns an otherwise effective torper/dropper into a complete miss-fest.

Anyway...

So it's all just a stack. Think of it as a bunch of boxes stacked up. That's all an array is, and in this case there's 20000 boxes, each w/ a sector number.

So let's use the new BFS routines to do this beast. GetNearestWarps, beautiful thing, altho I wish there was a termination criteria.



Anyway... I think that'd work. I just wrote it, so I haven't tested it, but you get the concept. You crunch all the data ahead of time and store it a parm.

Kaus,
I think it helps to imagine warps in a cone, like this:

1                           <- Starting sector
2 3 4 5 6 7                 <- Sectors adjacent to former level (distance of 1)
8 9 10 19 24 28 55 74 100   <- Sectors adjacent to that level (distance of 2)
etc...

The queue is built exactly like this. Once a sector has been added to the queue, it is not to be added again. To build the queue, you take your starting sector, add all of it's adjacent sectors to the queue. Then you work through each of those new adjacents, and add their adjacents, always observing the rule where a sector can't be added a second time. Then you work through those new adjacents, and so on.

When you have a queue, you have to keep track of 2 places: which item you are working on, and where did you last add an item. I represent the current working item with $bottom, and the last add as $top, because you step through a queue from bottom to top. When you create your queue, the only thing in your queue is the starting sector, and your current and last add are both 1. As code...
setVar $que[1] $startingSector
setVar $top 1
setVar $bottom 1

What you do next is the loop, where you grab the next item to work on ($bottom) and add its adjacents to the top of the queue ($top), always observing the rule of only adding a sector once. The complete code, with comments, is as follows:


I've used TRUE and FALSE respectively, so you can know that 1 is numeric. Oh, and in the next TWX, in-line comments like that are supported.

The getNearestWarps version that does the same thing is 8 lines, but I'll wait to post that until you understand this, which is as simple and clear as I can write it. Questions?

+EP+

thanks ep! cool read.

Very Helpful EP, thank you for posting that. Do you think a BFS is the best approach for a world ptrade script in effort to find the closest xxx ports to buydown or sell?

Yes, if you use it for each port you'd get something called a "A* search" which is considered one of the best searches for this type of data (non-weighted linked lists). It's an NP-difficult problem, similar to the "traveling salesman" problem. Getting a more accurate (in terms of distance) solution takes exponentially more computing power, and while there are some people that need that level of accuracy for other applications... Tradewars isn't one of them.

This line of solutions isn't 100% perfect, since a quantum computer could theoretically solve it in a lot less time, but we're still 100 years out from that. Altho it would be entertaining to play TW w/ quantum computers... I'd love to see what we could do.

welcome back from WOW. now if we can just resist the expansion this november...

I've been following this thread for a while. Very interesting and informative. Thanx to all involved.

[OT]
No one think this forum should be split into two separate forums? Scripting Forum and TW Helpers Forum? There is a goldmine of scripting info here. It would be a lot easier to search too.

i'd love to see a scripting 101 and/or a projects sub forum/thread.
Also love to see some of the older scripters come and give there 2 pence/cents worth. Ram, Alex, Supg etc... Guess i might be hopin for 2 much there. Who knows.

Thank you EP it helped me get the concept of the BFS