RE: Redesign of boards...

> On a side note, this sounds a lot like the traveling salesman puzzle
> where one
> tries to find the quickest route for a salesman that must visit a
> bunch of
> cities.
>
Yep. It's the shortest path problem. ;-)

> Last I heard there is no sort for this kind of thing (short of a brute
> force
> approach), in fact it's mostly believed that no algorithm will ever be
> found
> (See Robert Sedgwick's "Algorithms" book). According to the chapter
> on
> exhaustive searches even given a computer 1,000,000 times faster that
> today's
> fastest (copyright was 1992) you couldn't sort a 100 points, of the
> traveling
> salesman puzzle, in a year's time. Pretty hard to do a couple of
> hundred points
> forty times a second...
>
Aiiigh! Run! It's the revenge of CS325! I think the nature of the
hardware gives you some heuristics though that bound your sort
considerably. There's a couple things we'd like if we were WG vector
monitors.... ;-)

1) we like the beam to be by the center of the screen
2) we don't like to jump long distances at a time

Given those two you can tackle the vector list with a little more
smarts... Sort the points based on distance from the center, then
tackle each quadrant as a "section" to draw. Draw as much as you can
going from close to the center to out, then hop back to the center to
settle. You'd probably want to draw the quadrants in 1-3-2-4 order or
something to balance the deflection. For any "long" lines (where "long"
means aproaching half a screen axis), break them up into several smaller
segments. Since we're mostly likely a fast Digital Vector Generator
we'll assume we can get back exactly to where we leave off a line.
(Unlike the AVG.)

Feh. It's probably all academic though since all you need is a *little*
more ooomph out of the monitor to get all the Sega stuff. Zonn's idea
to stretch the draw time should help. Project number 234123-7 for me is
to add some wait-states in the Sega vector generator after a beam "jump"
to give the WG monitor time to settle inbetween beam moves. I think I
figured it's only a couple micro seconds that are needed...

For what it's worth, with the Vantis 64 macrocell parts so cheap now I
think I'm going to toss the DSP idea (which wasn't *quite* fast enough,
and just try a couple of hardware adders/controllers)...

-Clay

> But if you do work out this sort you could be very famous among the
> mathematical
> types, and with a properly applied patent, very rich!
>
> -Zonn
>
> <><><><><><><><><><><><><><><><><><><><><><><><><><><><
>
> ------ ___ Member of A.A.C.S.:
> |---- | ( ) Association for Artistically
> / / ( () ) Challenged Signatures
> / / //\\ // (__)
> / ---/ // \\ //\\ // zonn @ zonn . com
> -------| // \\/
>
Received on Fri Jun 5 12:34:47 1998