Subject: Re: [stella] Non-Recursive "Travelling Salesman" Solutions (Big Dig) From: Julian Squires <tek@xxxxxxxxxxxxxxx> Date: Fri, 4 Apr 2003 19:04:04 -0500 |
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/
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
[stella] Big Dig rewrite WIP, Christopher Tumber | Thread | Re: [stella] Non-Recursive "Travell, Christopher Tumber |
[stella] Big Dig rewrite WIP, Christopher Tumber | Date | Re: [stella] Non-Recursive "Travell, Christopher Tumber |
Month |