The var/fold/random script that comes with Swath isn't 100% accurate as far as I can tell and is rather slow and inefficient to get any kind of accuracy (high random values, especially for 20k sector games). The load on busy servers with several people running it simultaneously must bring them to their knees.

I saw a thread a while back that had suggestions on building a better one but it still had manditory dead-end checking, and I'm not so sure that it was 100% accurate either (though I could be mistaken, as I don't recall the algorithm specifics).

I put some thought into this matter and came up with a 100% accurate algorithm which relies on structures in memory to store data temporarily for each sector and which removes the need for dead-end checks at the end. It also stores accumulated data ahead of time (by course plots) to save time down the road.

To avoid limiting the algorithm to any specific scripting method, I'll be as general as I can. (Swath's Java implementation looks to be rather ideal for this, though perhaps more CPU intensive than something written for TWX or REXX of which I've used neither.)

1) Initialization
- A list of sectors (1 to SECTOR_MAX) with no warp data
- Room for 6 warps
- Count variable to say how many warps already determined
- Various other variables to handle functionality
2) Implementation
- A couple functions, namely fnZTM() and fnMapPath(/* in */ FromSector)
2.1) fnZTM
- This function increments from sector 1 to SECTOR_MAX
- At each step, it must:
i) Store, then Clear all avoids
ii) call fnMapPath with current sector
iii) Increment to next sector
iV) Restore avoids
2.2) fnMapPath
- This function does the real work
- Initialization:
i) Store the number of warps already found for the current sector
ii) Loop while warp count < 6
- Get a random sector
- Plot course from current to random sector (stored to an array)
- If null, break out of loop
- Else, step through course array adding warp data to sector array
(ie: course array has {1,45,72,347},
assign paths as {1->45,45->72,72->347})
- Avoid first sector in course array
iii) Return from function

(Hope I haven't left anything out.. sorta wrote this on a whim by the seat of my pants for something to do.. heh)

As I see it, it will plot a course along each one-way warp at most one time (treating a two-way warp as two one-way warps), storing longer warp paths incidentally as it goes to save time down the road. The only inefficiency I see is the 'extra' plot in any sectors having less than 6 warps (resulting in a 'no path found' message), but I'm sure this is unavoidable. One way warp checking is unnecessary because every sector and it's warp data is mapped from the computer's course plotter, collected, and stored appropriately depending on your environment.

I started implementing this a while ago in Java for Swath, but never got around to finishing it; I had pretty much finished it at the time so perhaps I'll get back to it and release the code. If it really does turn out to be less server intensive and efficient enough to use it'll certainly take a load off of the busier servers for those sys/gameops who don't release warp data for new games (most of them, I'm sure).

What do you folk think?
DC.

It sounds like you are getting every sector and the sectors adjacent to that sector using the avoids. This is similar, I believe, to what SupG's script does to a degree.

I have written a ZTM that gets every sector adjacent and TWX stores the data. It uses a single pass to get a warp out of every sector and then starts its second pass setting avoids on adjacent sectors to "x" and when there are not more paths to sector "y", it increments "x" and subtracts 1 from "y" to start the process over.

It would seem that with a database that contains all sectors with their adjacent sectors, a 100% map would be obtained, but I have found that for some reason that is not the case. This is the point I am at with my script and adding dead-end plots is the next thing for me to do.

Now, someone will ask why recreate the wheel when scripts from SupG and the Reverand are out and do a very good job. My reason is to get data during the ZTM that I have to do later. My data gathering scripts were added to the ZTM and run when the ZTM is finished.

               / Promethius / Enigma / Wolfen /

"A man who has no skills can be taught, a man who has no honor has nothing."

Well, if there is someone who has spent more time researching ZTM than I have... I feel sorry for him

I agree that the correct approach to a more accurate ZTM is to void the first-hop out. Unfortunately, there are still a few scenarios when this will not obtain all of the warps. There is still the need to check for one-ways, and I'll catch you up on the situations I've identified.

The first scenario: Sector 12 and 13 are dead ends, both adjacent to sector 11. Warps after ZTM for each sector appear as follows:
11 12 13 1000
12 11
13 11

What you didn't find was that there was a two-way or one-way warp 12 <> 13. No avoid you could have set would have displayed it. You would have had to test that specific warp, both ways. Additionally, no plot from 11 to any sector other than 12 would reveal the warp 11 > 12. This is why the one-way test must be performed. This is simple to do with TWX, as well as maintaining warp data.

There is a second scenario when a warp will be missed. There is a 5 sector bubble, setup like this:
100 <> 200 <> 400 <> 500-SPACE
/\
\/
300
If there is a one-way warp from 300 > 100, or any sector farther back in the bubble, it will almost always be missed.

I've come up with some pretty creative and efficient methods of identifying and testing these possibilities when they present themselves, but nothing I've fully implemented yet. I banged a 20k with max size gold bubbles, ran my ZTM method, and determined which warps were missed. I then analyzed each missed warp and determined why it was missed. If you are serious about near-perfect or perfect maps, you need to do the same.

As it has been said over and over, accuracy comes at the expense of time. I think the best possible trade-off between time and accuracy has been accomplished with Rev's method. But there is always value in accuracy... and if the script is gonna run overnight anyways, then I'd just assume it take twice as long to be more accurate. Now implement your ideas, so we can improve upon them

+EP+

Thanks EP, those scenarios never occured to me; I didn't really take the time to lay out all the sector possibilities as I should have.

At least now the dead-end check makes sense. I think that, aside from the missed cases above, the algorithm should still be pretty efficient and will at least allow the identification of such scenarios by a dead-end checker.

As for the script running over night.. that's something I was hoping to avoid; it's gotta play hell on the busier servers and annoy those who are actually trying to play while they're being run by others. The idea is to minimize the number of course plots sent to the game server and put the logic on the player's cpu.

Anyhow, I'll put some more thought into this when I get a chance; been rather busy lately.

Thanks,
DC.

On a modern server, ZTM requests are a breeze. I would speculate that 100 users doing ZTM would present a very small load for a 1 GHz CPU... far less than if those players were PPTing. Time is certainly a consideration, but server load shouldn't be.

+EP+

There were delays built into course plots specifically to keep the server resources from being tied up by ztms. As EP said, the load you put on the TWGS isn't really a needed consideration.