Hi.
(warning, I've only been following the list casually so I'm not familiar
with your game concept... so I hope this is useful ;-))
On Fri, Apr 04, 2003 at 04:15:14PM -0500, Christopher Tumber wrote:
> This is, essentially a travelling salesman type problem however
> recursion is really not an option as there's no way I have enough RAM
> for the potential stack overhead.
Looks less like TSP and more like flood fill to me. Thankfully you can
improve on the traditional recursive flood fill algorithm and avoid
probably save a lot of the space requirements...
-8<-snipped algorithms->8-
> So I'm looking for any thoughts on improving this - Of which I may
> have just had one. Suppose the search area in Algo 2 is handled
> smarter. Instead of just constantly widening, what if the search area
> was instead set to where new blocks were last flagged? That is, if an
> area didn't show any new blocks the last time through, there's no need
> to search there any more. So the search are can be made smaller in one
> direction while growing in another.
Paul Heckbert gives a fairly time-efficient algorithm in Graphics Gems,
page 275, but I'm assuming you're looking for something that's more
space efficient. (Heckbert's algorithm uses a stacks-of-segments
approach which is actually probably not too space inefficient either if
implemented carefully)
How about this: (warning: not really tested, and as I might be getting
the nature of your needs wrong anyway, I won't elaborate too much... if
you want a more detailed pseudocode or implementation, just ask)
Algorithm 3:
(x,y,seed) <- first block (* seed is the region color *)
curscan <- (x -> x,y)
upscan <- null
downscan <- null
fill(up and down) [first line]
(* upward pass *)
do
curscan = upscan
upscan = null
fill(up)
while(upscan != null)
(* downward pass *)
do
curscan = downscan
downscan = null
fill(down)
while(downscan != null)
with:
fill(direction)
save the current position
while we're on the current scan,
if direction includes up, and block at (x,y-1) is seed color,
expand(upscan, x, y-1)
if direction includes down, and block at (x,y+1) is seed color,
expand(downscan, x, y+1)
if the block at (x,y) is seed color,
set the block at (x,y) to the new/flagged/marked color
if the block at (x-1,y) is seed color,
expand(curscan, x-1, y)
reset position to saved position.
repeat the above while loop, but with the last ``if'' changed to:
if the block at (x+1,y) is seed color,
expand(curscan, x+1, y)
The scans are basically horizontal ranges on a single line (so they are
comprised of three elements: x1, x2, y). expand(scan, x, y) would
basically add the point (x,y) to the scan, initializing it if it were
null.
The basic idea is the same as the other stacks-of-segments approaches,
but we skimp on the stack because we don't mind checking (hopefully only
a few!) extra pixels. I think the worst case is a grid structure, where
it performs worse than Algorithm 1. For convex objects it should be
very fast.
Like I said, hope this helps, and if you'd like further clarifications
or implementation suggestions, I'm sure I could come up with them.
Hopefully if there are any bugs in the above pseudocode, at least the
idea is clear.
Cheers.
--
Julian Squires
----------------------------------------------------------------------------------------------
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/
