Re: [stella] Non-Recursive "Travelling Salesman" Solutions (Big Dig)

Subject: Re: [stella] Non-Recursive "Travelling Salesman" Solutions (Big Dig)
From: Julian Squires <tek@xxxxxxxxxxxxxxx>
Date: Fri, 4 Apr 2003 19:04:04 -0500

(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 *)
	curscan = upscan
	upscan = null
    while(upscan != null)

    (* downward pass *)
	curscan = downscan
	downscan = null
    while(downscan != null)


    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

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.


Julian Squires
Archives (includes files) at
Unsub & more at

Current Thread