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