www.ClassicTW.com
https://mail.black-squirrel.com/

Sing or Prom..Please read and respond
https://mail.black-squirrel.com/viewtopic.php?f=15&t=18481		 Page 1 of 1
Author:  Parrothead [ Tue Jan 23, 2007 6:28 pm ]
Post subject: 
Sing wrote - "TWXproxy 2.04 final has a built in BFS w/ avoids. As an example I will be writing code that takes only the gate and finds the bubble and all sectors inside of it."
I'm having trouble using the aviods function to its full advantage.If you have a snippet illustrating the point I'd appricate it.TY
Author:  Singularity [ Tue Jan 23, 2007 6:36 pm ]
Post subject: 
Hmm... I haven't used it much yet myself. Let me do that and get back w/ you.

What I plan to do is getNearestSectors to terra and loop down the stack. For every sector that's not a DE, set it as an avoid, then bubble test each of the adjs. The bubble test is just a getNearestSectors and count the stack size. If it's under a maxBubbleSize number, say 30, then it's a bubble and the avoided sector is the gate.
Author:  Singularity [ Tue Jan 23, 2007 7:03 pm ]
Post subject: 
Ok... uhm, got it done. It's SLOOOOOOOOOOOW.

There's probably a way to speed it up. Not sure if in script, or if there's something to hope for in 2.05... hehe. But here it is.

Code:
setVar $file GAMENAME & "_bubble_gates.txt"
delete $file
getNearestWarps $terra_stack 1
setArray $checked SECTORS
setArray $bfsdone SECTORS
setVar $gate_idx 1
while ($gate_idx <= $terra_stack)
     setVar $gate_test $terra_stack[$gate_idx]
     if (SECTOR.WARPCOUNT[$gate_test] > 1) AND ($checked[$gate_test] = FALSE)
           setAvoid $gate_test
           setVar $bubble_loop_idx 1
           while ($bubble_loop_idx <= SECTOR.WARPCOUNT[$gate_test])
                setVar $bubble_test SECTOR.WARPS[$gate_test][$bubble_loop_idx]
                if (SECTOR.WARPCOUNT[$bubble_test] > 1) AND ($bfsdone[$bubble_test] = FALSE)
                      setVar $bfsdone[$bubble_test] TRUE
                     getNearestWarps $bubble_stack $bubble_test
                     if ($bubble_stack <= 300)
                            setVar $mark_idx 1
                            while ($mark_idx <= $bubble_stack)
                                 setVar $checked[$bubble_stack[$mark_idx]] TRUE
                                 setVar $bfsdone[$bubble_stack[$mark_idx]] TRUE
                                 add $mark_idx 1
                            end
                            write $file $gate_test
                       end
                end
                add $bubble_loop_idx 1
           end
           clearAvoid $gate_test
     end
     add $gate_idx 1
end
Author:  Parrothead [ Tue Jan 23, 2007 7:20 pm ]
Post subject: 
I was trying to come up with a way to limit the size of the array using voids by presetting them before hand.
For example an array from my currentsector but eliminate all sectors within 3 warps from stardock (for example) and/or 3 warps from terra without having to do a getdistance check on the data.Or perhaps just the an array of sectors with 10 hops of currentsector.to many loops in what i came up with.Thought perhaps you had so ideas using getallcourses in conjunction with getnearestwwarps
Author:  Parrothead [ Tue Jan 23, 2007 7:23 pm ]
Post subject: 
as for the gate test would voiding the gate then checking course to terra from the adjacent sectors be faster? If all adj sector going out of bubble are voided wont the getnearestwarps array be limited to bubblesectors only?
Author:  Singularity [ Tue Jan 23, 2007 7:59 pm ]
Post subject: 
Laff. I was musing on exactly that the other day... trying to see if I could reliably limit the size of the array w/ avoids. I couldn't do it in any way that would save time. Maybe we can get a "max stack size" option variable here? Not sure if that'd really save time tho, it might be the variable inits that take the most time.

Anyway...

I thought of the course to terra thing and I don't think so. Why? Because as the number of avoids grows, the path to terra will increase and more sectors will need to be checked for the course to be found. Still there's only 1 way to know for sure, and that's to test both variations. I don't know how efficient getCourse is w/ all of this under such conditions. The above variation is the one that EP proposed a while back.

I was hoping that 2.04 would have the ability to get the bubbles from twx into an array. That would greatly simplify this and speed it up. But oh well... laff. Can't have everything. Put that on my 2.05 wishlist tho! =)

If you have a gate already then yea, avoiding the first hop out in all paths to terra until there is none out, followed by a BFS, would pull up all of the sectors in the bubble. This could then, for instance, give you a grid list. Now that getCourse is fast, it would probably be the optimal way of doing that.

As for all hops within 2 distinct sectors, you can do it a lot of ways. For simplicity I'd do a getAllCourses from each target sector (like dock, terra, etc) and just test against that. But really only if I'm planning to test a lot of sectors. On my tests it takes like 500ms to do a getAllCourses... and a getCourses only takes about 1ms. So there's no doubt that if you're only doing 10 sectors, that'd not be very effective compared to just getCourses.

One of the nice things about the way the stack is set up is that once you've gone over the max hop distance, you're past the max hop range for all sectors. That can cut out a lot of work.

On the fly...

Code:
getAllCourses $distances 1
getNearestWarps $stack 1
setVar $pointer 1
while ($pointer <= $stack)
     if ($distances[$stack[$pointer]] > 10)
               subtract  $pointer 1
               goto :turtle
     end
     add $pointer 1
end
:turtle


Now you've got a $pointer, from 1 to $pointer you've got a list of sectors within 10 hops. Don't even need to rewrite the list.

There is another way. That's what's called a "binary chop" search. I'll type up some code on that later but what it does is pick a midpoint in a list, test it, and adjust the midpoint. This way you can find a target in log time. I'm pretty sure I could find a target hop distance in under 500 searches that way, which means I could probably shave off quite a bit of time if I'm just looking to cull a getNearestWarps list down the "all hops within X."

Oh, you'll notice in my parms list that some stuff, dist to/from terra and stock and the like, I tend to store as parms. I'm getting concerned about the size of my DB tho and might go back to storing that as a file (similar to CK's figfile approach) if it'll trim it down. You could cache a bunch of key sectors as a file that way, just do the search once, and then call it up as needed.
Author:  Parrothead [ Tue Jan 23, 2007 8:21 pm ]
Post subject: 
Thanks for the input i will try it a couple ways and see what i get for speed.
the only other thing i was thinking of was to get size of the bfs array (sectors with full ztm) then test a halfway piont for distance then adjust up or down till i found the first sector that was (x +1) then rewrite array up to that entry but if i have to write a file then readtoarray will solve the issue nicely on the second load of the script and that will prob do for the "zone defence idea that lonestar came up with" that would limit resource wasting attacks early game to an grid area deemed important.The other idea was to find a theorical "path of least resistance" to a potential opponent base location by using the internal avoids and available database info.
The FIGSEC parameter use is taking over for all figfiles now as it allows realtime tracking of figs i lose to gridding or aliens etc via a background script therefor limiting the need for constant fig updates for certain attack and trading scripts scripts so im glad that bug is gone.
Author:  Parrothead [ Tue Jan 23, 2007 9:05 pm ]
Post subject: 
This is as far as i got but it appears to work fairly quickly.This is your binary search idea i think.
 
getNearestWarps $warparray currentsector
setvar $maxwarp 10
setprecision 1
setvar $pointer ($warparray / 2)
:again
round $pointer 0
getdistance $dist currentsector $warparray[$pointer]
if ($dist < $maxwarp)
setprecision 1
setvar $pointer ($pointer * 1.5)
round $pointer 0
goto :again
elseif ($dist > $maxwarp)
setprecision 1
setvar $pointer ($pointer / 2)
round $pointer 0
setprecision 0
goto :again
elseif ($dist = $maxwarp)
setvar $limit ($maxwarp - 1)
while ($dist <> $limit)
subtract $pointer 1
setprecision 0
getdistance $dist currentsector $warparray[$pointer]
end
end
add $pointer 1
getdistance $dist currentsector $warparray[$pointer]
echo "Limit is " & $pointer & " dist is " & $dist & " sector is " & $warparray[$pointer] & "*"
 
 
Author:  Singularity [ Tue Jan 23, 2007 9:54 pm ]
Post subject: 
The binary thing... actually it's a bit different. Pseudcode is on wikipedia I think. Here:
http://en.wikipedia.org/wiki/Binary_search

Just been a bit lazy on the write up.

Anyway, in general on the grid defense thing... I think you'll run into 2 kinds of people. Those that defend their grid, those that don't. The latter won't offer any resistance, the former will fight for every sector they have like it's their last.

And yea, I love FIGSEC. It changed the way I do figs. While I don't do realtime parms in all instances (a big DB + frequent parms = slow response to fighits), it's definately sped up a lot of stuff.
Author:  Singularity [ Tue Jan 23, 2007 10:21 pm ]
Post subject: 
Ok. Finally wrote it. I really don't know if this is any faster or not. I'll let ya'll test it and see. I suspect getAllCourses is still faster tho.

Code:
# Get the list
setVar $target_dist 10
setVar $start_sect  1
getNearestWarps $stack $start_sect

# Chop it down
:binary_search
setVar $low  0
setVar $high SECTORS
setVar $pos  0
while ($low <= $high)
     setVar $mid ($low+$high)/2
     getDistance $this_dist $start_sect $stack[$mid]
     if ($target_dist > $this_dist)
           setVar $low ($mid + 1)
     elseif ($target_dist < $this_dist)
           setVar $high ($mid - 1)
     else
           setVar $pos $mid
           goto :found_dist
     end
end
:found_dist
if ($pos = 0)
     echo ANSI_12 & "*Couldn't find any matching sectors*"
     halt
end

# Find the last instance of the target distance
setVar $list_top 0
while ($pos <= $stack)
     getDistance $dist $start_sect $stack[$pos]
     if ($dist > $target_dist)
           setVar $list_top ($pos - 1)
           goto :got_top
     end
     add $pos 1
end
:got_top

# Write the output
setVar $file GAMENAME & "_binary_chop.txt"
delete $file
setVar $idx 1
while ($idx <= $list_top)
     write $file $stack[$idx]
     add $idx 1
end
Author:  Parrothead [ Tue Jan 23, 2007 11:29 pm ]
Post subject: 
not doing realtime to attack script but the background script is updating this allows reloading at the pause state to keep as accurate an array as possible without doing a fig refresh.
 
getNearestWarps $warparray currentsector
setvar $maxdist 10
getdistance $dist0 currentsector $warparray[1]
setvar $low $dist0
getdistance $dist1 currentsector $warparray[$warparray]
setvar $high $dist1
setvar $mid ($warparray / 2)
round $mid 0
while ($low <= $high)
getdistance $dist2 currentsector $warparray[$mid]
if ($dist2 < $maxdist)
add $mid 1
elseif ($dist2 > $maxdist)
subtract $mid 1
else
setvar $limit ($maxdist - 1)
while ($dist <> $limit)
subtract $mid 1
getdistance $dist currentsector $warparray[$mid]
end
goto :endloop
end
end
:endloop
setvar $mid ($mid + 1)
getdistance $dist currentsector $warparray[$mid]
echo "Limit is " & $mid & " dist is " & $dist & " sector is " & $warparray[$mid] & "*"
 
This is what i came up with on that but its slow
Author:  Parrothead [ Tue Jan 23, 2007 11:36 pm ]
Post subject: 
First one is ugly and algebraic in function not logarithmic but seems magnitudes faster
Author:  Singularity [ Tue Jan 23, 2007 11:47 pm ]
Post subject: 
That's because you're subtracting/adding 1 from the mid but not changing the high and low. If you look at mine you'll notice it's log2(n), as it bisects the stack every pass. It's designed to be more of an in-place kindof function, the high and low are adjusted every pass. It takes less than 2 seconds on my end to run the entire thing.

Couple other issues as well, for instance if someone requests a distance that doesn't exist in the universe... what would happen in your's versus mine? You need a stack exit for an "all within" kindof search.

And yea, I do something similar in my keepalive. It records fighits and saves data appropriately.
Author:  Parrothead [ Wed Jan 24, 2007 12:48 am ]
Post subject: 
ok added error checking and cleaned it up.
getTimer $startTicks
getNearestWarps $warparray currentsector
setvar $maxwarp 10
setprecision 0
setvar $pointer ($warparray / 2)
round $pointer 0
:again
getdistance $dist currentsector $warparray[$pointer]
if (($dist = "-1") or ($dist = 0))
goto :nodata
elseif ($dist < $maxwarp)
setvar $pointer ($pointer * 3)
setvar $pointer ($pointer / 2)
round $pointer 0
goto :again
elseif ($dist > $maxwarp)
setvar $pointer ($pointer / 2)
round $pointer 0
goto :again
elseif ($dist = $maxwarp)
setvar $limit ($maxwarp - 1)
while ($dist <> $limit)
subtract $pointer 1
getdistance $dist currentsector $warparray[$pointer]
if (($dist = "-1") or ($dist = 0))
goto :nodata
end
end
add $pointer 1
getdistance $dist currentsector $warparray[$pointer]
if (($dist = "-1") or ($dist = 0))
goto :nodata
end
end
echo "Limit is " & $pointer & " dist is " & $dist & " sector is " & $warparray[$pointer] & "*"
goto :timer
:nodata
Echo "*No Matching Sector*"
halt
:timer
getTimer $stopTicks
setVar $durationTicks ($stopTicks - $startTicks)
setPrecision 10
setVar $seconds ($durationTicks / 750000000)
setPrecision 0
echo "*Time lapse in Seconds: " $seconds "*"
Page 1 of 1 All times are UTC - 5 hours
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/