Snake fills 2d area
BlitzMax Forums/BlitzMax Programming/Snake fills 2d area
| ||
| My latest project has caused me lots of head scratching. I need an algorithm for a 2d grid (which I'm making as square as possible depending on the area - e.g. Area=259; x=16, y=17 with 14 squares greyed out, or Area=189; x=14, y=14 with 7 squares greyed out - get it?) With a starting point anywhere in the grid, is there a method of traversing every grid square - snake-style (U,D,L,R) touching every square only once? This is such an old school problem I'm sure someone has a workable algorithm for it - no point me trying to re-invent the wheel. In fact it probably has a name, so any pointers to a name for Google searching would be appreciated too. |
| ||
| You need a more precise statement of the problem before there can be an answer. How are the grayed out squares placed? If they divide the rectangle into two "islands" then there can be no solution. So let's take what seems the most favorable case, together in a corner. If they fit in a single row or column that's even better. Next, how snaky does the path have to be? There would be an obvious solution "by rows" or columns. But that's not snaky at all. What about the other extreme, a turn at every step? What I mean is never two consecutive steps in the same direction. In that case there will not always be solution. Consider an extremely simple case, a 3x3 grid with one corner grayed out. A little scribbling will soon demonstrate that an always turning path is impossible. |
| ||
| Thanks Floyd. I have spent some time working on very small grids working up in size, the number of valid routes increases exponentially with grid size. I did consider using known valid 4x4 routes and breaking down larger grids fractal style - so a 16x16 would become a 4x4 of 4x4's. The down side to this method is it makes the maze puzzle a bit easier once you know the fractal method is in use. Your example of a 3x3 with one square greyed out - the one doesn't have to be on a corner, any one greyed out causes a real problem for a snaky route. I'm sure I read something on this many years ago, wish I could remember who wrote it... |
| ||
| I think "the starting point anywhere in the grid" makes it that it must fail in many cases. For example, cell[1,0] is grayed out, starting point = cell[0,1] -> instant failure... |
| ||
| Your example of a 3x3 with one square greyed out - the one doesn't have to be on a corner I was starting with what seemed intuitively to be a favorable layout and noting that it still failed. There are mathematical oddities called Space Filling Curves which have been adapted for this sort of thing. A notable example is the Hilbert curve which operates in your "breaking down larger grids" style. It starts with a 2x2 grid, trivially filled with a U shape. A 4x4 grid is considered to be a 2x2 grid with each cell being a 2x2 square. These are filled in Hilbert style and the appropriately oriented U's are connected to make a path. But I've never seen these applied to situations where not all cells in the rectangular grid are available. |
| ||
| Can you draw a visual of what you're wanting, TP ? Usually that helps explain things. |
| ||
| dw, it's basically a 2d maze, with absolutely only one correct path. The planned app is to take a famous quote or piece of literature, scrunch it up onto a square-ish grid, tell the player the starting point and let them steer their way through the letters building up the original words. Obviously the 'walls' of the 'maze' would not be shown. Try this one: A R A I I W N E P M L L I O E S S H E T S K A H T Q U E E O R S A H T B O N I T B E # T O T T O # Starts with the bottom left T. The #'s are greyed out. Clue: Literary quote and author. Answer tomorrow Only took me a matter of seconds to create on paper and transcribe to this post a minute or two more. Frustratingly difficult to get a computer to create this though. |
| ||
| So you want the program to BUILD the puzzle based on textual input, not solve it, correct? Does that also mean the program has control over the grayed out area's? |
| ||
| Errm ... As odd a game as this sounds, I can easily see how to write this in BlitzMAX using my own maze-making method, where the correct words match the tiles in the corridors, TP. Do you think there will be a heavy demand for a game that uses letters in place of corridor tiles ? |
| ||
| Yes Cocopino, I would like the computer to build it on the fly. Or if that's too complicated, have a cache of valid routes for a good number of grid sizes - the excess (greyed out) squares could be trimmed off either end as required. btw, did anyone get the quote from yesterday? TO BE OR NOT TO BE THAT IS THE QUESTION WILLIAM SHAKESPEAR Just one of several ideas for a mobile/tablet game that has simple rules, and can be updated with new content daily - think of the puzzle page/section in your daily newspaper. The hook/niche with this one is that you can present a bang-up-to-date quote from a public figure to appeal to the tabloid mass media readers. This could be the next Candy Crush |
| ||
| I find it difficult to come up with an algorithm that does not deliver the same outcome everytime. But if you only need one puzzle a day you could brute force it, that's a very easy way of course. Maybe this page will help a bit? http://codegolf.stackexchange.com/questions/34962/draw-an-image-with-a-snake |
| ||
| Thanks C, I had a look at that link. I have tried random snakes thinking randomness at huge speed will glean a result eventually (the infinite monkey cage idea), but after over a million attempts it could not even traverse a 10x10 successfully (never mind write some Shakespeare!) I think I'll ignore the on-the-fly building idea, and simply use my brain to create a route, then it gets sent along with the text content for the puzzle. This way everyone's puzzle is identical, which may promote sharing of solutions and prompting over social networks which in turn can only increase. Back to doing simple graphics and i/o for this. Thanks to all who assisted with my un-solveable query. |
   |