www.ClassicTW.com
http://classictw.com/

Sorting Routes
http://classictw.com/viewtopic.php?f=15&t=33176		 Page 1 of 1
Author:  SteveH_66 [ Tue Apr 17, 2012 1:41 pm ]
Post subject:  Sorting Routes
Hi, I was wondering if anyone could help me with a feature I want in a script I am writing. What I want to do is to sort the routes from one sector to a list of sectors most efficiently. I want to use the script for turn & resource efficient base management.

In this instance I am wanting to sort the routes in a bubble from the gate to the dead ends in the bubble, which I have in a list. I have already written the code to get the distance from each dead end to every other dead end, and it writes that to a file.

If that is not the best way to start out, I can use another method, such as Arrays in the script, comparing the arrays or whatever would be the most efficient way to do this.

But now I'm wondering what is the best way to sort the list. What I am trying to avoid is having to go back to the origin sector, the bubble gate in this case and go down each route. I would like to go from the gate to a dead end, jump to the next closest dead end that hasn't been visited and then go up the route back to the gate. Then repeat.

I guess I should first ask, is this strategy the most turn and fuel efficient? Or would it be most turn and fuel efficient to go to the dead end, jump back to the gate and then go down the next route?

I am trying to cover all the bases in all phases of the game, starting out when you are mostly going to be eWarping and tWarping, later in the game when you will probably be tWarping and tPad warping, and then later in the game when you will mostly probably be either tPad or pWarping.

I'm not asking anyone to write the script for me, just some insight into the best way to do it and some pointers. Want to try to write the script myself. Thanks for any help and pointers anyone can give on the best way to do this.
Author:  Promethius [ Tue Apr 17, 2012 5:40 pm ]
Post subject:  Re: Sorting Routes
Might search for "sorting algorithm" to see the different types of sorting routines. I think I used a type of bubble sort on the script I posted recently - promasscitbuilder". Is it accurate? Good question and one for the end user to determine. Is it quick - I don't think it is.
Author:  LoneStar [ Tue Apr 17, 2012 7:55 pm ]
Post subject:  Re: Sorting Routes
I think you're making this way too hard.

+Make a list/array of Deadends in the Bubble via ReadToArray;
+Start at first Deadend in List;
+Find nearest Deployed Fighter;
+Twarp/Bwarp to Nearest Fighter;
+Mow towards Deadend, setting "FIGSEC" as you Mow;
+Return to Fuelling/reFig'n point;
..and repeat.

in otherwords

Code:
ReadToArray "C:\DeadEnds.txt" $DEADENDS
SetVar $IDX 1
while ($IDX <= $DEADENDS)
   setvar $TARGET $DEADENDS[$IDX]
   GetNearestWarps $nearArray $TARGET
   SetVar $PTR 1
   while ($PTR <= $nearArray)
      GetSectorParameter $nearArray[$PTR] "FIGSEC" $FLAG
      if ($FLAG <> "0")
         SetVar $Jump_Point $nearArray[$PTR]
         goto :Found_Jump_Point
     end
     add $PTR 1
   end
   Echo "**Cannot Find A Jump Point.**"
   Halt
   :Found_Jump_Point
   #
   # Twarp to  $Jump_Point
   # Do Mow: $Jump_Point ---> $TARGET
   # SetSectorParameter "FIGSEC" TRUE as you Mow
   #
   # Twarp Back To Planet/Fueling-point and repeat...
   Add $IDX 1
End
Author:  Mongoose [ Tue Apr 17, 2012 9:28 pm ]
Post subject:  Re: Sorting Routes
It sounds like you are describing the Traveling Salesman Problem. Google it. It's a classic problem in graph theory, and finding an optimal solution is computationally very hard.

I did something similar in SWATH that would take me to the nearest "interesting" sector (i.e., probe hit or blocked port), check it out, and then go to the next nearest "interesting" sector. IIRC, TWX exposes the internals of its breadth-first searches (BFS) in the form of a list of sectors ordered by distance from the current sector. That list will make it fairly easy to find a rough solution to the Traveling Salesman Problem.

Start with a list of the sectors you want to visit (call it list A). Scan TWX's BFS list for the first sector that appears in list A. Travel to that sector and remove it from list A. Cause TWX to regenerate its BFS list (if it doesn't automatically when you move) and repeat until list A is empty.

Edit: as LoneStar noted, you could save turns by using TWarp to get around. Probably a good idea if it's a turns game. I dream of a BFS tree that follows virtual warps to your figs and thereby finds the shortest route to anywhere taking TWarp into consideration. (And if you don't have fuel in your holds, plots a virtual warp from the nearest source of fuel to your figs.)
Author:  Kaus [ Tue Apr 17, 2012 9:57 pm ]
Post subject:  Re: Sorting Routes
viewtopic.php?f=15&t=19151&hilit=sorting+routines
Author:  SteveH_66 [ Thu May 24, 2012 8:37 pm ]
Post subject:  Re: Sorting Routes
Promethius wrote:
Might search for "sorting algorithm" to see the different types of sorting routines. I think I used a type of bubble sort on the script I posted recently - promasscitbuilder". Is it accurate? Good question and one for the end user to determine. Is it quick - I don't think it is.

Thanks Pro, I've been doing some of that, learning a bit about sorting. One thing I noticed is that most of the popular languages have modules or libraries or whatever with sort routines in them, so the pages I am getting a lot of times they basically say "call this library to do a such and such sort on the data". On other ones they explain how to do a sort in C++ or JAVA or something, so I am having a bit of a problem figuring out how to adapt the syntax to TWX since they have additional logic operators such as AND, IF THEN, etc.

LoneStar wrote:
I think you're making this way too hard.

+Make a list/array of Deadends in the Bubble via ReadToArray;
+Start at first Deadend in List;
+Find nearest Deployed Fighter;
+Twarp/Bwarp to Nearest Fighter;
+Mow towards Deadend, setting "FIGSEC" as you Mow;
+Return to Fuelling/reFig'n point;
..and repeat.

Thanks Lone, if I was just wanting to mow the bubble that sounds like the way to go. And I noticed something interesting when I did a script to cover all the dead ends like that.

Later I was moving around the bubble doing some things, and I found sectors that were not visited in that script! It seems there are sectors in the bubble that are like side tracks, and routes through backdoors that aren't covered in a script just visiting dead ends. Not in the routes to the deads if you plot from gate to just the deads.

So I wrote a script getting courses to every sector in the bubble, and added in the courses to these sectors that aren't deads but which aren't visited in the default courses to the dead ends either.

Kaus wrote:
http://classictw.com/viewtopic.php?f=15&t=19151&hilit=sorting+routines

Thanks Kaus, interesting Thread, I found another interesting one here http://classictw.com/viewtopic.php?f=15&t=30674 where Sing and Parrothead are debating the best way to cover a route, in this case a list of ports in a bubble, interesting reading :D

Mongoose wrote:
I did something similar in SWATH that would take me to the nearest "interesting" sector (i.e., probe hit or blocked port), check it out, and then go to the next nearest "interesting" sector. IIRC, TWX exposes the internals of its breadth-first searches (BFS) in the form of a list of sectors ordered by distance from the current sector. That list will make it fairly easy to find a rough solution to the Traveling Salesman Problem.

Very interesting Mongoose. Could you explain more about what you mean "TWX exposes the internals of it's breadth-first searches"? What do you mean exposes the internals? How are they exposed? And how would one access these exposed internals? Are the getCourse, getNearestWarps and getAllWarps commands what you mean by exposes its BFS internals?

Thanks for those helpful replies everyone :D
Author:  Mongoose [ Thu May 24, 2012 8:58 pm ]
Post subject:  Re: Sorting Routes
By "exposes the internals", I mean it gives you access to the entire BFS tree, in the form of a list of sectors sorted by distance. SWATH only gives you the path from one sector to another that was computed using that BFS tree.

I think I was talking about the $SECTORS variable. About a year ago, I went through the TWX API looking for things TWX can do that SWATH can't. Providing you with a list of sectors sorted by distance was one of the few things on the list.
Author:  SteveH_66 [ Thu May 24, 2012 9:15 pm ]
Post subject:  Re: Sorting Routes
I don't think I illustrated what I'm actually talking about doing here clearly enough in the OP, please excuse me for not being clear.

See here is my theory, hopefully those with more scripting and game knowledge can correct any misconceptions I may have here. It is my contention that a script for finding bubbles doesn't completely sort the bubble in order. I don't know about bubbles from SWATH, they might, but experimentation with output from bubble finder TWX scripts tells me that this might be a good guess on my part. My conception is that a bubble is like a tree, with forks and branches.

If you look at it layed on it's side, in the horizontal, what dead end is at the top of the bubble and which is at the bottom? If you stand it up, looking at it in the vertical, which sector is on the far right and what sector is on the far left of the bubble?

So it is my theory, if you know the far left and far right of a bubble, or the top and the bottom if you want to orient it that way, then you can cover the bubble most efficiently. Start at the right and work your way to the far left, or start at the top and work your way down. Cover the route all the way to the end of the first branch (dead end) in the bubble. Then, jump to the terminator (usually a dead end) of the next branch of the bubble and work your way back only as far as you need to go to cover any unvisited sectors in the route. Repeat until the bubble is covered.

If you start from a known side or the top or bottom of the bubble, then I think that would be the most turn efficient way to cover the bubble. Probably as I understand Sing to be saying in the other thread i linked to in my above post, by using the getNearestWarps command.

Upon more reading in the forums and thinking on the problem, I realize that this is probably a case of me reading too much into the problem, but that was my original thinking when I made that first post. Once you have a twarp capable ship, and then citadels for tpad and then later pwarp capability it would probably not be all that important.

Although I still can't help but think that mapping out far sides or top and bottom of the bubble and then moving from top to bottom or side to side depending on how you look at the layout of the bubble would still be the most efficient way of covering the bubble.
Author:  SteveH_66 [ Thu May 24, 2012 9:23 pm ]
Post subject:  Re: Sorting Routes
Mongoose wrote:
By "exposes the internals", I mean it gives you access to the entire BFS tree, in the form of a list of sectors sorted by distance. SWATH only gives you the path from one sector to another that was computed using that BFS tree.

I think I was talking about the $SECTORS variable. About a year ago, I went through the TWX API looking for things TWX can do that SWATH can't. Providing you with a list of sectors sorted by distance was one of the few things on the list.

Very interesting Mongoose. So in your opinion, what would be the best way to access this list of sectors sorted by distance? Particularly in a case like I am talking about, where you want to find out the 'layout' of a bubble so that you know the top and bottom or the left and right of the bubble, so that you can work your way top down or from one side to the other through your bubble?

I guess I still don't understand enough about BFS, in general and particularly as to how it applies to TWX Proxy. I will have to search the forum for posts about BFS, so that I can learn more about it, particularly as it applies to TWX. Thanks for your posts, very interesting information and concepts. :D
Author:  Mongoose [ Thu May 24, 2012 10:09 pm ]
Post subject:  Re: Sorting Routes
If I am remembering correctly what $SECTORS is (a list of all sectors sorted by distance), you could do something like this:

1. Iterate over $SECTORS and find the first (i.e., nearest) sector that matches your search critieria.
2. Move to it (or adjacent to it, depending) and do whatever.
3. Regenerate $SECTORS (if TWX doesn't regen it automatically when you move)
4. Repeat as long as there are sectors that match your criteria.

From the sounds of it, your search criteria would be something like "the sector is inside the bubble I'm looking at, and I haven't visited it yet". But I have no idea how to express that in TWX code.
Author:  LoneStar [ Fri May 25, 2012 6:25 am ]
Post subject:  Re: Sorting Routes
SteveH_66 wrote:
I don't think I illustrated what I'm actually talking about doing here clearly enough in the OP, please excuse me for not being clear.

See here is my theory, hopefully those with more scripting and game knowledge can correct any misconceptions I may have here. It is my contention that a script for finding bubbles doesn't completely sort the bubble in order. I don't know about bubbles from SWATH, they might, but experimentation with output from bubble finder TWX scripts tells me that this might be a good guess on my part. My conception is that a bubble is like a tree, with forks and branches.


The bubble data that Swath generates does create a 'list' (horizontal), of sectors in proper order. That is to say, that the last sector in the horizontal line IS the furthest from the gate.

Forgive me for being blunt, but it seems that you're drawing 'conceptions' based upon ideals, and not actually looking at the Data available. Or am I missing something?

What I would suggest to you is this: Find a nice smallish sized bubble (say 10 to 20 sectors), draw it out on paper.. look at the data Swath/TWX-GetAllCourses gives you, and follow it along and see how it is presented. Start out with a Deployed fighter in the Gate and manually map it out. Figure out what you think is efficient or ideal.. There are only a few variables to consider.. but starting out with a small bubble will make a world of difference.

You don't have to take my word for it, but I am pretty certain I gave you the answer you're looking for in my initial post; you just didn't understand it.
Author:  ElderProphet [ Fri May 25, 2012 2:16 pm ]
Post subject:  Re: Sorting Routes
Steve, help us better understand how you are intending to move. If you are going to go from the gate, to a bubble sector, then another bubble sector, then another until they've all been visited, a simple and turn efficient way to accomplish this is to locate and move to the nearest unvisited bubble sector from wherever you are at. Then repeat until they've all been processed. Here is a general outline to accomplish this:
Code:
readToArray $targets $bubbleSectorFile
setArray $bubbleSector SECTORS // this will be used as a true/false test
# mark each bubble sector as TRUE in the $bubbleSector[] array
setVar $i 1
while ($i <= $targets)
   setVar $focus $targets[$i]
   setVar $bubbleSector[$focus] TRUE
   add $i 1
end

# the $checked[] array is used so we only process a given bubble sector once
setArray $checked SECTORS  // remember, array elements initialize to zero or FALSE

:processNearestBubbleSector
getNearestWarps $nearest CURRENTSECTOR
setVar $i 1
while ($i <= $nearest)
   setVar $focus $nearest[$i]
   if ($bubbleSector[$focus] = TRUE) and ($checked[$focus] = FALSE)
      setVar $moveTo $focus
      gosub :moveTo // routine to move to $moveTo
      gosub :processBubbleSector // routine to perform actions on CURRENTSECTOR
      setVar $checked[$focus] TRUE // now we won't process this sector again
      goto :processNearestBubbleSector
   end
   add $i 1
end
# all bubble sectors have been processed
halt
Now this is almost a fully functional script, but there are a couple things left to do, primarily the :moveTo and :processBubbleSector subroutines, but this should help you understand structurally how to script this. My advice is to go through and comment each section as you come to understand it. But if you really try and can't follow it, then ask and I'd be happy to clarify. But there is merit in you trying to digest it on your own first.

+EP+

Edit: Heh, in hindsight, this is pretty much verbatim what Mongoose said.
Page 1 of 1 All times are UTC - 5 hours
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/