Thanks Rev, I'm not really hooked anymore which is a HUGE bonus. I think i'm pretty much done with the whole wow thing *hopefully*

For no reason other than it uses parameters I will continue my incessant questions in a attempt to learn based off his example.
Sing as I understand it from talking to you, your example uses parameters. I have been playing around with it (Your example) in twx and it generally just hangs. Does it take a long initial load or am i missing something? Could you impliment a echo (to return results) in your example so I can play around somemore with it in game change some things and maybe finally write a script that uses arrays and bfs's instead of my normal textlines.

My understanding of your script you posted is as follows (line by line)
I'm posting this here hoping others who have the same questions can reference it for later
------------------------------------------------
#Set initial index to 1
#while 1 is less than sectors
#set sector parameter of index to 0 (Data check reasons)
#add 1 to index
#
#set check to 1
#while 1 is less than sectors
#If the warpcount is 1
#Set parameter nearsetde that we set to 0 earlier to the sector
#goto our :next_sector label and add 1 since the while isnt finished yet it
#-continues
#
# else if it is a larger warpcount than the 1 warpcount were looking for
# get the nearest warps (breadth first search time)
# -were getting the nearest warps of our sector were checking and assigning
# - it to stack
# set a variable of searchy to 1
# while the variable searchy which is set to 1 is less than our
# - stack size
# Set a variable named focus to the setor number were working on
# If the warpcount of focus is 1 warpcount set it to the nearestde parameter
# goto our next_sector label and add 1 since the while statement isnt done
# if it didnt meet the requirement of 1 add a number to searchy
----------------------------------------------------------------

What this script does as I understand it:
a) creates a array of parameters for data verification in the case where a bad ztm/lack of creates a bad warpout etc
b) creates a second array of sectors to check against the first array
c) uses BFS (stacks of boxes/sectors) to check for the closest warpcount of 1 which in turn is the nearest DE, uses the first array to compare agaisnt the second array for data integrity. If it is good data then we found our closest Deadend.
d) echo deadend?

It will take a long time to crunch. It could take an hour, I've never timed this specific example.



You're going to find that echo has some issues in loops like this. But it's worth trying for the effect. Just add an echo for the sector number somewhere. Normally in large data programs I use a counter...



So that every 1000 rounds it touches the server to keep alive.



The 2nd array is the first array, stored as parms. I init the data so that if the data is never populated later on (like in the case of a bad ztm or broken universe) it's easier to detect. It also helps to speed up parms a bit if you pre-init them, which is another benefit.



Pretty much.

It then loops thru a counter, 1 for each sector in the universe, and runs a BFS for each. Once the BFS is run it runs thru the BFS stack to find the nearest DE, sticks it onto parms, and moves onto the next sector.

If you really wanted to try speeding that script up, you might try writing a script that performed a BFS (manually constructed) using WarpsIn, that ran from the DeadEnds only. It would start slow but speed up as it progressed, but still might not be faster. I could give the pseudocode if anyone is interested. It would be an advanced-level script... maybe expert-level.

How would you take in account conflicting deadends? Lets say I start at a DE, and 3 hops out there's a sector w/ a deadend that's only 2 hops from it. If I got to it from the far DE first, how would I compensate for that? Only way I could think to do it would be to incrementally increase the size of the BFS over multiple iterations (which would reset the stack each time, wouldn't it?), but that would definitely not be faster.

My data miner uses the warps out approach, but I don't use the getNearestWarps command for it. If I don't re-init the arrays all the time it's usually faster since I'm rarely going more than 5 hops. It would be nice to have a limit like that for getNearestWarps, since I could do incrementally larger passes (5 hops, 10 hops, no limit) and probably speed things up.

Using the WarpsIn BFS, I would track each sectors nearest DE in an array (vs. writing it as a sector parameter) as well as the distance to that DE, and write the sector param at the end. So let's say I'm testing DE's incrementally from sector 1 to SECTORS. If sector 8 was the first DE, then on the first iteration, all sectors would have sector 8 as their nearest DE, and the distance to sector 8 would be in another array. Then if sector 16 were the next sequential DE, it would become nearest DE for all sectors where it's distance was less than 8's. And so on for each DE.

But in the queue, you would only add sectors to the top if the DE you are testing wins for that sector, so the queue depth gets shorter as more DEs are tested.

Gotcha, so you'd also keep the distance to each DE in a separate array and only update sectors if they were closer than the previous stored value. Prolly would be faster, but that depends on how slow a manual BFS is versus the getNearestWarps command. 4k versus 20k sectors...

So how long until we have a GetNearestWarpsIn function?

Well, I went ahead and coded it. It takes 10 seconds in my 5K sector test game (vs. 21 seconds for the getNearestWarps version) because the queue depth gets very small very quickly. It finds many nearest deadends that don't match up with the getNearestWarps version, though the distance is the same. That would be difficult to align.

I apologize in advance if this code is hard to understand. This is a conventional BFS without the beauty that is getNearestWarps. And as for getNearestWarpsIn... hopefully in the next TWX.


What's cool is that you can literally watch this script speed up as it progresses through the DEs.

Oh, and by the way, you could play with limiting a getNearestWarps search by creating a "ring" of avoids. If you wanted to limit it to a distance of 5, you could setAvoid for all sectors that were 6 hops. Whether the time saved exceeded the time spent would depend on the specifics of the script.

+EP+

How's it perform in a 20k?



Nod. It'll all go to how the nearest warp calculation is done in the gridding script, really. If it does a BFS in, a WarpsIn version would be more efficient. On the other hand if you're using an unfigged gridder that's plotting courses out, you'd want the other approach.



But I'd have to know what sectors are 6 hops. Wouldn't that require doing the very work I want it to avoid?

The getNearestWarps routine takes me about 6.5 minutes in a 20K. The manual version posted takes me 2.5 minutes. I can think of a few ways to improve it, but I imagine ~2 minutes is probably the limit. Still, it's a nice speed up.

Scripts assumes people already have a sectorparameter "NEARESTDE" set.. something like this is needed at the beginning



Using avoids to set a proximity is unecessary when you can just limit the size of the QUE. For example:


Also. Code needed some basic bounds checking in the even that "NEARESTDE" was never set before:

My version inits it at the top, sets it all to 0. Nothing else is needed at that point.



On a manual BFS you can limit the size of the queue, but you cannot do that w/ getNearestWarps... which is what I was asking for.



Just set it to 0, then check for 0 in the torper. If you try to save the old variable you're going to have problems if you later add more to your map. GetDistance is really slow in a loop like that, so you're just better off redoing the entire set.

bfs + torper would seem pretty slow to me if bfs doesn't exit it till its crawled the system. Or does adding a while statement allow you to dump out early from the bfs? Does setting a bfs to a variable allow for referance later on or d you have to run a bfs everytime you want to access its data?

You can not run a BFS on response to a fighit. No way that's going to be fast enough.

The reason I use parms is so that you don't have to do this.

You pre-store the information, so when someone hits a fig all you have to do is pull up the nearest DE and react accordingly. You don't even have to do a getCourse, altho you can if you want (will slow things down a little, but you could pre-cache that too). All you'd really have to do is find the nearest DE, grab it's adjacent warp in and pdrop there. If you're running a torper then timing gets a little more complex... but not much.

!BRUTE FORCE!
Firstly. This is hideously slow (scans 25 sectors, change $LIMITER from 25, to SECTORS)... but only needs to be ran once. I like the results because I have *all* the nearest DE's to a TA, and I can filter out which is fig'd or not, on the fly.


[EDITED] Modified Code for improvment