Wondering if anyone out there can help with this routine. Inspired by Elder Prophets breadth-first routine, I decided to try and write a GetDistance routine that would be faster than the built-in TWX GetDistance. After a few attempts with different concepts (don't try: SetArray SECTORS SECTORS, lol), this is the best I could come up with. for short distances it appears accurate and fast (haven't compared timing with the native TWX command), but for long plots there's usually a difference of one-hop. This is interesting to me, because I've often wondered at how TWX derives it's Course-plots, etc. ...thinking that my routine might be a tad more accurate.. hehe.

I'm playing around with this because of another script I'd like to rewrite that makes intensive GetDistance calculations, and really bogs down the CPU with large data-sets.



Feel free to ask any questions about the code.. including criticisms.

Thanks

[EDIT] Not intended for sectors > 20k (would require a larger $QUE.
[EDIT] Cleaned up the code a tad.

You know I don't write scripts but I can make out a little bit.

Why hard code in Max Length? Shouldn't you be pulling that value from the * menu since it's sysop configurable?

If I'm not mistaken, the value you're alluding too is used with respect to Course Plots.

The value of '45' is arbitrary; I don't believe I've ever come across a course length greater. In practice the value could be anything but should not be infinite. The routine could be used, for example, to give you all sectors within/further-than x-hops, or give you all sectors x number of hops out. There are probably a few more possibilities but for now I'm curious about making it faster than the native GetDistance.

GetDistance execution time does vary with course length, so it would seem unlikely that any scripted version could improve on it. The breadth-first search clearly outperforms GetNearestWarps for finding nearby targets however, since it stops when a target is found rather than doing entire universe.

Since you use array $Checked to skip sectors already processed, it looks like SECTORS is the maximum possible number of elements in $QUE. The routine should terminate when all reachable sectors have been checked, whether $MAX_LENGTH is imposed or not.

$Distance seems to get out of synch with actual depth level somewhere; I am still looking it over. Have you tried implementing the routine with a stack instead of a queue?

$que is really a Stack (named QUE as a tip of the hat at EP). And it does need to be at least equal to the number of Warps in the game because of how it is used to reference previous results from the previous iterations. If you change the destination sector to one that is adjacent sector 10 for example (ie 3hops out), reduce the $que size to about 50, pause execution and look at the variables, you'll get an idea of how I'm using the QUE as a stack. Note that $absolute_ptr moves up through the Stack and the Que_Bottom and Que_top are relative.

Also, $Checked prevents an infinite Loop as sector 2 is adj sector 1; when scanning sector 2's adjacents we don't want to consider sector 1 again, otherwise the loop will run forever scanning and rescanning sector 1 and 2's adjacents.
I can post a screen cap if convenient.

…wanted to mention that this routine might I fact be ideal for the same reason you've pointed out; I can break out of the GetDistance if a Target is too far. Something I hadn't considered.

In that case it should be possible to keep $distance updated by incrementing it each time you "push" onto the stack and decrementing for each "pull".

If no sector ever gets stored in $Que more than once (because of $Checked), how is the universe warp count relevant?

Yeah. I see what you mean now. Makes sense. Thanks for the input, I really appreciate the outside perspective.

After much debugging and testing I figured out why $Distance returned was incorrect --some of the time. Let's just say that Stack-Pointers, Base-Pointers, and relative 'addressing' can be your friend or your nemesis


Example caller routine for testing purposes

Actual GetDistance routine, with minimal bounds checking.

I've written such routines many many times, and would be willing to share mine, if you'd like. There's no beating the native calls for getDistance and getCourse, but there are always cases where having your own is advantageous. I once wrote a getCourse search that worked both sides simultaneously (sorta) which was significantly faster than the typical approach (and might beat getCourse in speed), but was very hard to make it match the exact same path as the conventional method. That isn't necessarily important though. Fun times.

I implemented the getNearestWarps to serve the majority of breadth-first search needs (nearfig, nearest Sxx port, etc.), and it sure saves me a lot of time and lines of code. But rolling your own and creating your own exit criteria will sometimes be preferable for adept scripters - so kudos for pursuing it.

+EP+

Yes I would like to see how this could be faster. I learned a lot from studying your routines. I find that there's a certain level of intrinsic Awesome-azing qualities when stepping away from Brute force methods.

The following :getDistance subroutine isn't necessarily faster, but rather as simple as possible. It can be made a bit shorter, but that results in horrible looking nested variables which are hard to understand.

Let me point out that the $que array (which you'll see in much of my code) is not a stack, but is a queue. Let me explain for posterity. With a queue, you add new items that you want to investigate to the top of the queue, but you pull the next item to investigate from the bottom. So the earliest or oldest item is processed for each iteration. This is how breadth-first searches are normally performed, meaning that all sectors that are 1-hop away will be processed before all sectors that are 2-hops, and so on. This is a natural product of using a queue.

Conversely, with a stack, you add new items to the top as before, but you also pull the next item to process from the top. Or in common stack terms, you push items onto the stack (onto the top), and pop them off the stack (again, from the top). Stacks are commonly used in depth-first searches, where a course is pursued linearly to it's end, and then back-tracked to the last branch. Think of this approach as akin to entering a maze and always taking the left-most unexplored corridor (and leaving a mark so you'll know you've taken it already.) Eventually you'll reach a dead end, and backtrack to the last unexplored branch. This backtracking is hard to do in TWX scripting, so you don't see depth-first searches often. I could probably be persuaded to write and share one, though it's been years...

In the :getDistance code below, we create the $que array, the $checked array to ensure we don't re-process a sector, and an array to track distance. I use "pointers" to track where I'm at in processing the items in the queue. Specifically, I track the next sector that will be processed with $bottom, and I track where new items will be added with $top. I add the starting sector to the $que array, in position 1. Then I iterate from $bottom to $top, and the result is a breadth-first search. Pay special attention to the 2 returns -- one when the object of our search is found, and one when the search is exhausted (and failed.)

Let me know if there are any aspects that I can help clarify,
+EP+

P.S. Turning this into a getCourse routine only requires a few additional lines of code.

Thanks for sharing. I think I 'get' everything in the Code. I haven't worked with Stacks for a very long time, but I seem to remeber two different types of Stack: FIFO & LIFO, the QUE being the latter. However the native POP nemonic would be strictly be FIFO; and direct manipulating of Pointers would give LIFO. Anyway. I'm looking forward to testing the performance differences --my nested while-loops versus (your) single nested while-loop.

Great, I'd be interested to hear your results.

Regarding push and pop, I've only seen that turn-of-phrase applied to stacks, specifically LIFO stacks.

So I did some testing for a 5K sector map...

My un-optimized split-getDistance routine (that works from both directions simultaneously) is over 3.5 times faster on average than the normal getDistance routine I posted earlier. Theoritically, it could be about 4x faster, but remember that the course will not be the same that getCourse returns - same distance though.

However, the built-in TWX getDistance routine is 180 times faster than my split routine, and 640 times faster than the normal routine I posted. I expect these variances would increase as sector count increases.

This doesn't mean that there aren't times when you want to roll your own BFS though, but custom getDistance and getCourse routines will always be abysmal compared to the built-in versions.

+EP+