Treasure Maps
Oct. 20th, 2005 06:11 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
rbandrewsThis is what's been bugging me the last couple of days, finished. It takes a five by five grid and divides it into five equal-size contiguous regions. I'm going to use it for a game; you'll findpieces of a treasure map as you play, then when the game is over you guess where on the main board the treasure is. I figured I'd post it since I bugged so many of you for tips on how to do it.
This is a random algorithm, and like most of them, the worst-case runtime is infinite. I've made the average case very short though.
I have a function where you give it a random empty square and it colors a region of five spaces including that, randomly. The algorithm starts by doing that with what's left of the map, and seeing if it's divided the empty regions into two groups. If it has, then it's possible that it's made some number of regions that are too small for pieces to fit in. So, wipe that piece out and try again. If you can't draw a piece that doesn't divide things, or a piece that is five squares large, in ten tries, then wipe the whole map out and start again. This prevents it from looping for very long periods to find the single solution.
It's actually possible to make a three-piece setup that hasn't divided the empty space and still can't complete. If this happens, then the failsafe just kicks in and it restarts.
This is a random algorithm, and like most of them, the worst-case runtime is infinite. I've made the average case very short though.
I have a function where you give it a random empty square and it colors a region of five spaces including that, randomly. The algorithm starts by doing that with what's left of the map, and seeing if it's divided the empty regions into two groups. If it has, then it's possible that it's made some number of regions that are too small for pieces to fit in. So, wipe that piece out and try again. If you can't draw a piece that doesn't divide things, or a piece that is five squares large, in ten tries, then wipe the whole map out and start again. This prevents it from looping for very long periods to find the single solution.
It's actually possible to make a three-piece setup that hasn't divided the empty space and still can't complete. If this happens, then the failsafe just kicks in and it restarts.
