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

Subject: Re: [stella] Non-Recursive "Travelling Salesman" Solutions (Big Dig)
From: Christopher Tumber <christophertumber@xxxxxxxxxx>
Date: Sat, 05 Apr 2003 17:21:50 -0500
Thomas wrote:

>I have some kind of floodfill implemented in the maze generator of my
>Robot City demo that is used to avoid generating unreachable areas
>(CheckFill). It's small, dead simple and not very fast, but maybe you
>can use some ideas from it.

Speaking of which... Julian's mention of flood fill got me thinking about labyrinth solving algorithyms since it's all really a sheep of another colour. Labyrinth algorithyms tend to be focussed on finding an exit, rather than wandering the entire maze, but it's still quite similar.

I started fiddlying with a modified Right Hand Rule alorithym where instead of ALWAYS turning right at any corner, the direction to go is assigned a priority where right>foreward>left>backwards BUT an even higher priority is given to: non-visited space> space we've already visited before.

So in effect:

right+new>foreward+new>left+new>back+new>right+been there>foreward+been there>left+been there>back+been there

This seems to do a pretty efficient job a travelling all the way through the "maze" (and this may be a pretty good AI for maze games) however the problem is determining when it's finished and all spaces have been "touched". I'm thinking of keeping track of the total number of spaces flagged and also how many moves it's been since the last new space was found. Something like:    moves since last new space found>2*number of spaces     should give a good indication of when things are done but it does lead to some wasted effort at the end (particularly for large objects). [In the case of a maze game AI, this would reset all the "been there" flags.]

>Julian's algorithm however sounds very similar to some floodfill
>implementations I have seen and done so far. It should be very fast and
>efficient.

Yeh, I also worked out the "enhanced brute force" algorithym which does the sequential search, but modifies the search area as new matches are found so as to eliminate areas with no new spaces. I think I'll probably try and implement all three algorithyms (or a similar flood fill if not exactly Julian's, I'm still looking through source material) and compare "real world" performances. My game engine will allow up to 6 different coloured blocks (plus "blank" or "empty") however, levels will have anywhere from 3 to 6 different coloured blocks. Lesser numbers of colours will tend to mean larger clusters of like coloured blocks and more complex shapes. So it's quite possible that one algorithym will tend to be better suited than another depending upon the number of colours. So optimum algorithym could be selected on a level by level basis.

(Or maybe the first one I actually code will turn out to be "good enough" and I'll leave it at that...)


Chris...

----------------------------------------------------------------------------------------------
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/


Current Thread