Breadth First Searchs (Anticipation Scripts)
| Author |
Message |
|
ElderProphet
Commander
Joined: Tue Oct 07, 2003 2:00 am Posts: 1134 Location: Augusta, GA
|
 Re: Breadth First Searchs (Anticipation Scripts)
So you posted that to demonstrate how not to do it?
_________________ Claim to Fame: only guy to ever crack the TW haggle algorithm, and fig/shield/hold price formula, twice.
|
| Thu Oct 30, 2008 1:24 pm |
|
 |
|
Kaus
Gameop
Joined: Tue Nov 19, 2002 3:00 am Posts: 1050 Location: USA
|
 Re: Breadth First Searchs (Anticipation Scripts)
Forgive my ignorance, especially if its in the script manual or self evident. But how is finding the nearest de going to help with finging a adjacent or second adjacent with a torp script. More to the point sector parameters kinda of confuse me.
Once you set a sector parameter does it save the value you have given it indefintly for that database? What kind of information can you store on a parameter? How do you access it later from within the script?
_________________ Dark Dominion TWGS Telnet://twgs.darkworlds.org:23 ICQ#31380757, -=English 101 pwns me=- "This one claims to have been playing since 1993 and didn't know upgrading a port would raise his alignment."
|
| Thu Oct 30, 2008 2:00 pm |
|
 |
|
Vid Kid
Commander
Joined: Sun Feb 25, 2001 3:00 am Posts: 1838 Location: Guam USA
|
 Re: Breadth First Searchs (Anticipation Scripts)
Kaus , sector parameters are stored and updated to allow for faster retrieval by other scripts .. like the attack script. This makes everything faster .. the reason all this extra stuff is being done in the first place .. speed is the ... THE most important thing in the case of attack scripts.
Also this is why scriptwriters have to have a common set of parameters , so other scripts can share info. The parameters are stored in your twx database and must be updated to stay current.
_________________ TWGS V2 Vids World on Guam Port 2002 Telnet://vkworld.ddns.net:2002 Discord @ DiverDave#8374 Vid's World Discord
Founding Member -=[Team Kraaken]=- Ka Pla
 Winners of Gridwars 2010 MBN Fall Tournament 2011 winners Team Kraaken Undisputed Champions of 2019 HHT Just for showing up!
The Oldist , Longist Running , Orginal Registered Owner of a TWGS server : Vids World On Guam
|
| Thu Oct 30, 2008 2:36 pm |
|
 |
|
Singularity
Veteran Op
Joined: Thu Jun 02, 2005 2:00 am Posts: 5558 Location: USA
|
 Re: Breadth First Searchs (Anticipation Scripts)
Quote: Forgive my ignorance, especially if its in the script manual or self evident. But how is finding the nearest de going to help with finging a adjacent or second adjacent with a torp script. More to the point sector parameters kinda of confuse me. You're looking for an anticipation torper. The point of anticipation is to try and figure out where someone is going next. DEs are common targets. They kindof have to be. If you don't grid out DEs then ppl can hide there, so you're more or less forced to grid them. Hence they make a logical, and often times better than the standard method, anticipation torper. Sector parms are nothing but a way to store data and relate it to a particular sector. Quote: Once you set a sector parameter does it save the value you have given it indefintly for that database? What kind of information can you store on a parameter? How do you access it later from within the script? More or less. You can put almost anything in one. use getSectorParameter to pull it back up.
_________________ May the unholy fires of corbomite ignite deep within the depths of your soul...
1. TWGS server @ twgs.navhaz.com 2. The NavHaz Junction - Tradewars 2002 Scripts, Resources and Downloads 3. Open IRC chat @ irc.freenode.net:6667 #twchan 4. Parrothead wrote: Jesus wouldn't Subspace Crawl.
*** SG memorial donations via paypal to: dpocky68@booinc.com
|
| Thu Oct 30, 2008 3:33 pm |
|
 |
|
LoneStar
Commander
Joined: Fri Jun 09, 2006 2:00 am Posts: 1401 Location: Canada
|
 Re: Breadth First Searchs (Anticipation Scripts)
ElderProphet wrote: So you posted that to demonstrate how not to do it? Laff. Sorry. I tried and tried to not get sucked into this topic Weekend Warrior Signing off
_________________ ---------------------------- -= QUANTUM Computing 101: 15 = 3 x 5 ... 48% of the time.
|
| Thu Oct 30, 2008 4:44 pm |
|
 |
|
Kaus
Gameop
Joined: Tue Nov 19, 2002 3:00 am Posts: 1050 Location: USA
|
 Re: Breadth First Searchs (Anticipation Scripts)
LoneStar wrote: ElderProphet wrote: So you posted that to demonstrate how not to do it? Laff. Sorry. I tried and tried to not get sucked into this topic Weekend Warrior Signing off Why¿
_________________ Dark Dominion TWGS Telnet://twgs.darkworlds.org:23 ICQ#31380757, -=English 101 pwns me=- "This one claims to have been playing since 1993 and didn't know upgrading a port would raise his alignment."
|
| Thu Oct 30, 2008 5:07 pm |
|
 |
|
ElderProphet
Commander
Joined: Tue Oct 07, 2003 2:00 am Posts: 1134 Location: Augusta, GA
|
 Re: Breadth First Searchs (Anticipation Scripts)
Heh LS, it's good to see you can take a jab  Sector Parameters were added because so much of the data that the scripter wants to persist across TWX sessions is sector-specific, usually held in arrays that are sized the same as the universe in sectors. Consider the common $figged array, where you capture the results of the Deployed Fighter Scan: Code: :figRefresh setArray $figged SECTORS setVar $figCount 0 send "g" waitOn "Deployed Fighter Scan" setTextLineTrigger personal :getDeployed "Personal " setTextLineTrigger corp :getDeployed " Corp" waitOn "Command [TL" killTrigger personal killTrigger corp return
:getDeployed killTrigger personal killTrigger corp getWord CURRENTLINE $figSector 1 getWord CURRENTLINE $figged[$figSector] 2 add $figCount $figged[$figSector] setTextLineTrigger personal :getDeployed "Personal " setTextLineTrigger corp :getDeployed " Corp" pause If you wanted to save that data before there were sector params, you would have to create a text file, named uniquely for the game, and write out the fig results line by line, so that a 20K sector game wrote out 20K line files. And then you had to read those back in at the start of a script, which took an inordinate amount of time before the readToArray existed. Now consider how trivial it is to save it as a sector parameter, and not worry about it again at script load or exit, across TWX instances, since it's always ready to be queried or updated if the DB is loaded. Sector parameters are limited to a name of 10 characters, and a value of 40 characters.
_________________ Claim to Fame: only guy to ever crack the TW haggle algorithm, and fig/shield/hold price formula, twice.
|
| Thu Oct 30, 2008 8:42 pm |
|
 |
|
Kaus
Gameop
Joined: Tue Nov 19, 2002 3:00 am Posts: 1050 Location: USA
|
 Re: Breadth First Searchs (Anticipation Scripts)
Quote: Space-consuming quote removed for brevity. Please quote sparingly - EP Thanks EP, so when your making a parameter for later referance what happens if that value has changed? I.e. in your above example someone hit and removed a fighter from gridding or whatever. Or do you want to check the integrity of the parameter after the fact? Also doesnt the database get confused from having to many parameters named the same thing. Such as Nearest DE and having a value of 0 or the sector number? How does it tell the parameters different or is Nearest DE/ Figged just labels to the value and were actually searching for a labeled value against the real time game value.
_________________ Dark Dominion TWGS Telnet://twgs.darkworlds.org:23 ICQ#31380757, -=English 101 pwns me=- "This one claims to have been playing since 1993 and didn't know upgrading a port would raise his alignment."
|
| Thu Oct 30, 2008 9:28 pm |
|
 |
|
Singularity
Veteran Op
Joined: Thu Jun 02, 2005 2:00 am Posts: 5558 Location: USA
|
 Re: Breadth First Searchs (Anticipation Scripts)
Quote: Thanks EP, so when your making a parameter for later referance what happens if that value has changed? I.e. in your above example someone hit and removed a fighter from gridding or whatever. Or do you want to check the integrity of the parameter after the fact? Also doesnt the database get confused from having to many parameters named the same thing. Such as Nearest DE and having a value of 0 or the sector number? How does it tell the parameters different or is Nearest DE/ Figged just labels to the value and were actually searching for a labeled value against the real time game value. The values are stored relative (attached) to the sector number. So if the value of the parm changes for a particular sector, then it changes, and the next read will read the new value. Because they're related to a specific sector there's no confusion, altho you can't name 2 parms the same thing for a single sector (you'd just overwrite the old value). The parm NEARESTDE will only have 1 value per sector. Sector 1 will have a NEARESTDE, sector 2 will have a NEARESTDE... on to sector 20000 will have a NEARESTDE. It's a variable, so you can read from it, write to it, etc. It's not a constant, you can write to it more than once. They're just a name for the particular set of variables stored in the DB, that's all. Don't overthink it... =) There's no fixed association to a "real time game value" of any sort. It's all just a database. Each sector has a little variable named, say, NEARESTDE. You would getSectorParameter NEARESTDE for, say, sector 1000. That's a different value than sector 1001, or 2000, you've got 20000 effective variables (or however many sectors are in the universe) to work w/ for that one parm. They're just a bunch of variables. An entire stack of variables called "NEARESTDE" ... like a big stack of boxes. You've got a big bunch of boxes, the entire stack is called "NEARESTDE" and there's 20000 boxes to work with. You then address each box individually by number, sortof...
_________________ May the unholy fires of corbomite ignite deep within the depths of your soul...
1. TWGS server @ twgs.navhaz.com 2. The NavHaz Junction - Tradewars 2002 Scripts, Resources and Downloads 3. Open IRC chat @ irc.freenode.net:6667 #twchan 4. Parrothead wrote: Jesus wouldn't Subspace Crawl.
*** SG memorial donations via paypal to: dpocky68@booinc.com
|
| Thu Oct 30, 2008 10:06 pm |
|
 |
|
Kaus
Gameop
Joined: Tue Nov 19, 2002 3:00 am Posts: 1050 Location: USA
|
 Re: Breadth First Searchs (Anticipation Scripts)
ElderProphet wrote: 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. Code: getTime $start echo ANSI_15 "**Beginning NEARESTDE search at " $start setVar $nearestDE SECTORS setVar $distToDE SECTORS setArray $que SECTORS setArray $distance SECTORS # Begin with a falsely high distance setVar $i 1 while ($i <= SECTORS) setVar $distToDE[$i] 1000 add $i 1 end echo ANSI_15 "**Beginning NEARESTDE search." setVar $i 1 while ($i <= SECTORS) if (SECTOR.WARPCOUNT[$i] = 1) echo "*Assigning DE " $i setVar $nearestDE[$i] $i setVar $distToDE[$i] 0 gosub :bfs end add $i 1 end echo "*Setting Params..." setVar $i 1 while ($i <= SECTORS) getSectorParameter $i "NEARESTDE" $oldDE if ($oldDE <> $nearestDE[$i]) getDistance $dist1 $i $oldDE getDistance $dist2 $i $nearestDE[$i] echo "*Updating NEARESTDE for sector " $i " from " $oldDE " (" $dist1 ") to " $nearestDE[$i] " (" $dist2 ")" setSectorParameter $i "NEARESTDE" $nearestDE[$i] end add $i 1 end echo "*Complete.*Started: " $start ", Ended: " TIME "*" halt
:bfs setArray $checked SECTORS setVar $checked[$i] TRUE setVar $distance[$i] 0 setVar $que[1] $i setVar $top 1 setVar $bottom 1 while ($bottom <= $top) setVar $focus $que[$bottom] setVar $j 1 while ($j <= SECTOR.WARPINCOUNT[$focus]) setVar $adjacent SECTOR.WARPSIN[$focus][$j] if ($checked[$adjacent] = FALSE) setVar $checked[$adjacent] TRUE if (($distance[$focus] + 1) < $distToDE[$adjacent]) setVar $nearestDE[$adjacent] $i setVar $distance[$adjacent] ($distance[$focus] + 1) setVar $distToDE[$adjacent] $distance[$adjacent] add $top 1 setVar $que[$top] $adjacent end end add $j 1 end add $bottom 1 end echo " - Que depth was " $top return 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+ Heh that script is cool, really starts to get going about 500 or so into it. EP you had stated you would show me the 8 line Get Nearest DE using the new BFS routine. Can I request that now? I get the older way and see its very intensive, I'd like ot see the differance between the two. -Kaus
_________________ Dark Dominion TWGS Telnet://twgs.darkworlds.org:23 ICQ#31380757, -=English 101 pwns me=- "This one claims to have been playing since 1993 and didn't know upgrading a port would raise his alignment."
|
| Sun Feb 22, 2009 2:15 pm |
|
 |
|
ElderProphet
Commander
Joined: Tue Oct 07, 2003 2:00 am Posts: 1134 Location: Augusta, GA
|
 Re: Breadth First Searchs (Anticipation Scripts)
Dude, I don't even remember what that script does. Looks complicated though (and well written  ). The 8-line version was supposed to do something else I think. I'm willing to show it, but remind me what it is I'm supposed to be showing. +EP+
_________________ Claim to Fame: only guy to ever crack the TW haggle algorithm, and fig/shield/hold price formula, twice.
|
| Wed Feb 25, 2009 10:49 pm |
|
 |
|
Kaus
Gameop
Joined: Tue Nov 19, 2002 3:00 am Posts: 1050 Location: USA
|
 Re: Breadth First Searchs (Anticipation Scripts)
ElderProphet wrote: Dude, I don't even remember what that script does. Looks complicated though (and well written  ). The 8-line version was supposed to do something else I think. I'm willing to show it, but remind me what it is I'm supposed to be showing. +EP+ Yea hehe it's been awhile, I havnt given up on bfs's though and I def like the above example if alittle beyond my current comprehension. Anyways you had stated you could do Code: setVar $startingSector 1 // start at Terra for this search setVar $que[1] $startingSector setVar $top 1 setVar $bottom 1 while ($bottom <= $top) setVar $focus $que[$bottom] // focus on the next working item # Note: This is the clearest point to implement your search criteria # Let's say I'm looking for any sector with anyone's fig in it if (SECTOR.FIGS.QUANTITY[$focus] > 0) # Many scripts would jump out here, like "goto :figFound" echo "*Figs in sector " $focus end // That's it for the search portion # $focus is the working item, let's add its adjacents setVar $i 1 // $i is an iterator, a variable to track which warp of $focus we are currently working on while ($i <= SECTOR.WARPCOUNT[$focus]) setVar $adjacent SECTOR.WARPS[$focus][$i] // so when $i is 1, we're checking if the 1st warp has been seen before if ($previouslyQueued[$adjacent] = FALSE) # An unqueued adjacent has just been found, it goes on top, to be tested later add $top 1 // We have to increment $top so we know where to stick this unseen sector setVar $que[$top] $adjacent // now, in due course, this sector will be the focus setVar $previouslyQueued[$adjacent] = TRUE // haha, I bet you forgot this step, very important, grasshoppa end add $i 1 // now the next warp/adjacent of $focus will be tested end // all of that working sector's adjacents have been queued add $bottom 1 // now the next sector will be made the focus, so it's warps/adjacents will be tested end
In 8 lines and I'd really appreciate it if you would post it for contrast between the two. -Kaus
_________________ Dark Dominion TWGS Telnet://twgs.darkworlds.org:23 ICQ#31380757, -=English 101 pwns me=- "This one claims to have been playing since 1993 and didn't know upgrading a port would raise his alignment."
|
| Mon Mar 02, 2009 1:08 am |
|
 |
|
ElderProphet
Commander
Joined: Tue Oct 07, 2003 2:00 am Posts: 1134 Location: Augusta, GA
|
 Re: Breadth First Searchs (Anticipation Scripts)
Ah, now that routine can indeed be done in 8 lines. However, instead of the 8 line example, I'll give you this 9 line example which has the same output as my earlier 26-line version, but uses the getNearestWarps command to build the bfs array, then steps through it echoing sectors with figs. Code: getNearestWarps $nearArray 1 setVar $i 1 while ($i <= $nearArray) setVar $focus $nearArray[$i] if (SECTOR.FIGS.QUANTITY[$focus] > 0) echo "*Figs in sector " $focus end add $i 1 end The 8 line example eliminates the $focus variable, and you end up with a hard to read nested array element that looks like this: if (SECTOR.FIGS.QUANTITY[$nearArray[$i]] > 0) I try not to post code like that because it can be confusing to read. +EP+
_________________ Claim to Fame: only guy to ever crack the TW haggle algorithm, and fig/shield/hold price formula, twice.
|
| Thu Mar 05, 2009 8:59 pm |
|
 |
|
mob
Boo! inc.
Joined: Sat Oct 09, 2004 2:00 am Posts: 865 Location: USA
|
 Re: Breadth First Searchs (Anticipation Scripts)
ElderProphet wrote: Code: setVar $startingSector 1 // start at Terra for this search setVar $que[1] $startingSector setVar $top 1 setVar $bottom 1 while ($bottom <= $top) setVar $focus $que[$bottom] // focus on the next working item # Note: This is the clearest point to implement your search criteria # Let's say I'm looking for any sector with anyone's fig in it if (SECTOR.FIGS.QUANTITY[$focus] > 0) # Many scripts would jump out here, like "goto :figFound" echo "*Figs in sector " $focus end // That's it for the search portion # $focus is the working item, let's add its adjacents setVar $i 1 // $i is an iterator, a variable to track which warp of $focus we are currently working on while ($i <= SECTOR.WARPCOUNT[$focus]) setVar $adjacent SECTOR.WARPS[$focus][$i] // so when $i is 1, we're checking if the 1st warp has been seen before if ($previouslyQueued[$adjacent] = FALSE) # An unqueued adjacent has just been found, it goes on top, to be tested later add $top 1 // We have to increment $top so we know where to stick this unseen sector setVar $que[$top] $adjacent // now, in due course, this sector will be the focus setVar $previouslyQueued[$adjacent] = TRUE // haha, I bet you forgot this step, very important, grasshoppa end add $i 1 // now the next warp/adjacent of $focus will be tested end // all of that working sector's adjacents have been queued add $bottom 1 // now the next sector will be made the focus, so it's warps/adjacents will be tested end Ive been doing some research and I thought this was a real interesting thread to those who are bored on a Sat. night. Only issue I had this this snippet was it errored on: Quote: setVar $previouslyQueued[$adjacent] = TRUE // haha, I bet you forgot this step, very important, grasshoppa
Shouldn't it read: Quote: setVar $previouslyQueued[$adjacent] TRUE It turned out to be the perfect example of what I was looking for, I might be wrong don't throw anything at me if I am:) -mob
_________________ “The object of war is not to die for your corp but to make the other bastard die for his.”
Boo! inc.
|
| Sat Jun 27, 2009 8:32 pm |
|
 |
|
Promethius
Ambassador
Joined: Mon Feb 09, 2004 3:00 am Posts: 3141 Location: Kansas
|
 Re: Breadth First Searchs (Anticipation Scripts)
mob wrote: Ive been doing some research and I thought this was a real interesting thread to those who are bored on a Sat. night. Only issue I had this this snippet was it errored on: Quote: setVar $previouslyQueued[$adjacent] = TRUE // haha, I bet you forgot this step, very important, grasshoppa
Shouldn't it read: Quote: setVar $previouslyQueued[$adjacent] TRUE It turned out to be the perfect example of what I was looking for, I might be wrong don't throw anything at me if I am:) -mob End of line comments are not supported in 2.04. I am guessing that they might be in the next release, but I don't know for certain.
_________________
/ Promethius / Enigma / Wolfen /
"A man who has no skills can be taught, a man who has no honor has nothing."
|
| Sat Jun 27, 2009 8:46 pm |
|
 |
|
Who is online |
Users browsing this forum: No registered users and 31 guests |
|
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot post attachments in this forum
|
|