crash@jc3b21.UUCP (Frank J. Edwards) (04/22/89)
I obtained some PD dungeon maps and am in the process of converting them
to plotter output for my Apple plotter (but the computer is an Amiga - Yea!)
The point I'm at now is optimizing the vector list to minimize pen movement.
Right now, this is more of a programming obsession than a "practical"
project (not that it was very "practical" to begin with :-).
I realize this is a somewhat open-ended request, but I'd like to poll the
net.readers out there for "tips and techniques" in this area.
My current strategy:
1) Sort the vectors in increasing (x,y) order of starting point
(the data is "struct { short sx, sy, ex, ey, flags }").
The "flags" member is for recording whether or not a particular
element has already been drawn.
2) Also generate and sort an array of pointers into the
start-point array, but sort these by end-point.
(This allows two methods of accessing the data; via start-point
or end-point order.)
3) Starting at the first element of the start-point array, move
thru the array looking for a start-point which is not duplicated
(this should be an "terminator" for a vector).
4) Draw the vector found from the previous step.
5) Find the same entry in the end-point array.
6) Look on either side of the located element in the end-point
array for the same coordinate. This is the continuation of
that vector.
7) Now draw the element found in step 6 (in reverse start/end order).
8) Return to the start-point array and locate the element just drawn.
(Found in step 6.)
9) Look on either side of that element for the continuation element.
10) Loop back to step 4, until no matching element is found (in steps
6 or 9).
11) The vector has been completed. Do the next one by looping back to
step 3, but start the search at the current element.
As I typed the above list, I saw another improvement (of course :-)
In steps 6 and 9, don't look for an exact match, but just the closest
match. This means the pen has to be picked up, moved, and put back
down, but it's better then the implication of starting over again with
a new vector. Of course, "closest match" means checking absolute
distance between points, and that may require scaling (since the
plotted maps are 640x200). For example, (0,0) is closer to (2,0)
than (2,1) is!? (Since the interval between y-axis points is three
times that of the x-axis.)
Typical maps may look like (they are larger than this, though :-):
+--+--------+--+--------+-----+
| | | | | |
| | +--+ | | +--+ | +--+
| | | | | | | | |
| | | | | | +-----+ | |
| | | |
+--------+-----+--------------+
Anyway, my fingers have been all typed out. Does anyone have anything
to say about this? I realize that this may/may_not belong in a couple
of the groups I picked (rec.games.programmer for instance).
Thanks all. If nothing else, at least I have a lead on a further
improvement on my current routines.
----
Frank "Crash" Edwards
...!uunet!pdn!jc3b21!crash
----
I don't have a cute .signaturecdl@mplvax.EDU (Carl Lowenstein) (04/24/89)
In article <633@jc3b21.UUCP> crash@jc3b21.UUCP (Frank J. Edwards) writes: >The point I'm at now is optimizing the vector list to minimize pen movement. >Right now, this is more of a programming obsession than a "practical" >project (not that it was very "practical" to begin with :-). Look through "Writing Efficient Programs", Jon Bentley, Prentice-Hall 1982. ISBN 0-13-970244-X He uses the problem of optimizing pen movement as the framework for most of the examples in the book. The only difficulty is that he uses the wrong 'cost' function. (At least for most of my pen-plotter experience). The cost of writing a vector should be proportional to max(abs(dx),abs(dy)) rather than sqrt(dx**2 + dy**2). But there are lots of good optimizations. -- carl lowenstein marine physical lab u.c. san diego {decvax|ucbvax} !ucsd!mplvax!cdl cdl@mplvax.ucsd.edu
dillon@POSTGRES.BERKELEY.EDU (Matt Dillon) (04/25/89)
Determining the most optimal plotter drawing sequence is almost the
traveling salesman problem! Still, for a picture that is mainly vertical and
horizontal segments the easiest thing to do is something like this:
* collect the horizontal and vertical segments into two different lists.
* sort horizontal (H) list by y and sub-sort by x. (i.e. a simple
numerical sort where 'y' is the msb and 'x' is the lsb).
* sort the vertical (V) list by x and sub-sort by y.
* starting at the top, draw the horizontal lines across reversing
direction each time. I.e. like a bi-directional printer.
* starting at the nearest corner, draw the vertical lines in the same
manner... up then down then up ...
* draw any diagonals (assumed to be only a few) that remain.
-Matt
:I realize this is a somewhat open-ended request, but I'd like to poll the
:net.readers out there for "tips and techniques" in this area.
:
:My current strategy:
:
:1) Sort the vectors in increasing (x,y) order of starting point
: (the data is "struct { short sx, sy, ex, ey, flags }").
: The "flags" member is for recording whether or not a particular
: element has already been drawn.
:
:2) Also generate and sort an array of pointers into the
: start-point array, but sort these by end-point.
: (This allows two methods of accessing the data; via start-point
: or end-point order.)
:...doug@xdos.UUCP (Doug Merritt) (04/26/89)
In article <8904242129.AA25480@postgres.Berkeley.EDU> dillon@POSTGRES.BERKELEY.EDU (Matt Dillon) writes: > > Determining the most optimal plotter drawing sequence is almost the >traveling salesman problem! Yes. In fact, "almost" understates it. As Bill Joy pointed out to me in '77 (in connection with optimal sequencing of intelligent terminal ops to redraw a screen [for the first version of vi], which maps one-to-one with this problem), the optimal method is NP-complete, just the same as the T.S. problem. (In case anyone is wondering, that means there [almost certainly] aren't any polynomial-time solutions, which means essentially that there is no way to fully optimally solve the general case in a reasonable amount of time... you have to settle for heuristic and sub-optimal and/or unreasonably slow solutions.) Actually Bill fed the problem to me and let me stew on it for a few days, and *then* explained NP-completeness to me when I'd discovered it was a much harder problem than it at first sounded. Made for a very intuitive introduction to the subject. Doug -- Doug Merritt Member, Crusaders for a Better Tomorrow {sun!pyramid,apple}!xdos!doug Professional Wildeyed Visionary "Of course, I'm no rocket scientist" -- Randell Jesup, Capt. Boinger Corps