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
ymchee@water.waterloo.edu (Yeow Meng Chee) (04/25/89)
In article <SARREL.89Apr24143841@dory.cis.ohio-state.edu>, sarrel@dory.cis.ohio-state.edu (Marc Sarrel) writes: > It occurs to me that the famous "travelling salesman" problem, which > we know to be NP-Complete, might reduce to the pen plotter > optimization problem. If the pen optimization problem is, therefore, > NP-Complete, it cannot be solved in non-deterministic polynomial time. > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ > (assuming that P != NP) ..... Of course the problem could be solve in non-deterministic polynomial time (independent of whether P=NP or not). That is what NP is all about. Please read Garey and Johnson to understand what the notion of NP means! ************************************************************* Yeow Meng Chee; Department of Computer Science; Faculty of Mathematics; University of Waterloo; Waterloo, Ontario, Canada N2L 3G1 {ymchee@water.bitnet; ymchee@water.uwaterloo.ca} Good Day eh!
sarrel@dory.cis.ohio-state.edu (Marc Sarrel) (04/25/89)
In article <2271@water.waterloo.edu> ymchee@water.waterloo.edu (Yeow Meng Chee) writes: In article <SARREL.89Apr24143841@dory.cis.ohio-state.edu>, sarrel@dory.cis.ohio-state.edu (Marc Sarrel) writes: > optimization problem. If the pen optimization problem is, therefore, > NP-Complete, it cannot be solved in non-deterministic polynomial time. > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Of course the problem could be solve in non-deterministic polynomial time (independent of whether P=NP or not). That is what NP is all about. Sorry, my fault. Honest, I do know what NP-Complete is. Attribute the above mistake to a typo. :-) :-) -=- "Master, why is the letter 'i' the symbol for current?" "Because there is no letter 'i' in the word 'current'." "Master, why do we use the letter 'j' as sqrt(-1)?" "Because we use the letter 'i' for current." Whereupon the Master struck the Disciple, and the Disciple became enlightened.
maddog@cbnews.ATT.COM (john.j.tupper) (04/25/89)
In article <SARREL.89Apr24143841@dory.cis.ohio-state.edu> sarrel@dory.cis.ohio-state.edu (Marc Sarrel) writes: >In article <863@mplvax.EDU> cdl@mplvax.EDU (Carl Lowenstein) writes: > >Discusses algorithm to minimize pen movement on a pen plotter, given a >series of lines to be drawn. > > 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 :-). I "solved" this problem a couple of years back. I found that buffering a large number of lines and then drawing whichever line had the nearest endpoint to the current pen position to work very well. Two things to look out for: 1) It is more important to avoid pen changes. If your plotter has N pens, draw your figure N times throwing away all comands that are not drawn in the current color. 2) When using transparency pens on either transparencies or hp glossy paper, you should draw lines in only one direction (i.e. from left to right and top to bottom, but not right to left or bottom to top). If you draw them both directions, half the lines will be ugly, ugly, ugly. >It occurs to me that the famous "travelling salesman" problem, which >we know to be NP-Complete, might reduce to the pen plotter >optimization problem. Yup, it does. Setup all the end points of all the lines as cities. Each of these cities is connected to every other city with a straight road of the proper length. Now add a city at the mid-point of each line. These mid-point cities are connected only to the cities at the end-point of their line. If you solve the plot optimization problem, you also solve the traveling salemen problem. ------------------------------------------------------------------------- sdlfk lsd sd My real signature is illegible too.