In the following grid, all "b"s are 4-connected to the one "a":
-, b, - b, a, b -, b, - So for the sample grid -1,-1,-1 -1,-1,04 -1,-1,04 the cells which are 4-connected to the initialized cells are here marked with xx: -1,-1,xx -1,xx,04 -1,xx,04 In other words, the cells to randomly choose the new tile placement from are the ones at the boundary of the already-initialized region. In the initial description of the problem it sounded like valid paths did not include diagonals, which is why I say 4-connected. If diagonals are OK, use 8-connected. Dave On Wed, Mar 11, 2009 at 1:49 PM, Anthony Pace <[email protected]>wrote: > I just wanted to mention that I don't think it should be entirely random. > Perhaps you may want to add restrictions as I mentioned before, yet, make > sure it has a maximum that steps higher and higher based on availability, > and alternate between diagonal and side to side. > > So if there is no way 2 can be side by side or diagonal anymore, than max > distance plus 1, check for a max distance of 1 square/slot between from > available slots in the array, and so on. > > This would allow it to build out and use all available squares. > > > Paul Steven wrote: > >> Thanks David for your suggested solution - it looks very promising. I am >> not >> sure what 4-connected means? But I think I understand the general idea >> >> I am just wondering if your solution would guarantee that there will >> always >> be a matching tile within a clear path? >> >> For example if the random sequence is >> >> 4,4,27,27,1,1,36,36, <BLANK> >> >> -1,-1,-1 >> -1,-1,-1 >> -1,-1,-1 >> >> then >> >> -1,-1,-1 >> -1,-1,04 >> -1,-1,-1 >> >> then >> >> -1,-1,-1 >> -1,-1,04 >> -1,-1,04 >> >> then >> >> -1,-1,27 >> -1,-1,04 >> -1,-1,04 >> >> then >> >> -1,-1,27 >> -1,-1,04 >> -1,27,04 >> >> then >> >> -1,-1,27 >> -1,01,04 >> -1,27,04 >> >> then >> >> -1,-1,27 >> -1,01,04 >> 01,27,04 >> >> then >> >> -1,36,27 >> -1,01,04 >> 01,27,04 >> >> then >> >> -1,36,27 >> 36,01,04 >> 01,27,04 >> >> then >> >> 00,36,27 >> 36,01,04 >> 01,27,04 >> >> -----Original Message----- >> From: [email protected] >> [mailto:[email protected]] On Behalf Of David >> Hershberger >> Sent: 11 March 2009 17:40 >> To: Flash Coders List >> Subject: Re: [Flashcoders] Advice on creating random grid of pairs for a >> game >> >> My first thought for your algorithm is to essentially follow the solution >> path that your user might end up taking. Your user will be clearing areas >> out, opening them up. Your algorithm could start with an empty grid and >> fill in around a starting seed, growing the tile array outward. >> >> 1) empty grid >> 2) generate random sequence of pairs with the blank embedded in it, such >> as >> 4,4,27,27,1,1,36,<blank>,36, etc >> 3) choose random location for first tile, and place it there, and take it >> off the pair queue. >> 4) choose an unfilled location which is 4-connected to any filled >> location, >> and put the next tile from the queue in it. >> 5) repeat 4) until the queue is empty. >> >> In this system, putting the "blank" in a location counts as filling that >> location, so the value for "blank" needs to be different than the initial >> values in the grid. >> >> So for example, if -1 means uninitialized and 0 means blank: >> >> -1,-1,-1 >> -1,-1,-1 >> -1,-1,-1 >> then >> -1,-1,-1 >> -1,-1,04 >> -1,-1,-1 >> then >> -1,-1,04 >> -1,-1,04 >> -1,-1,-1 >> then >> -1,-1,04 >> -1,27,04 >> -1,-1,-1 >> then >> -1,-1,04 >> -1,27,04 >> -1,27,-1 >> then >> -1,-1,04 >> 01,27,04 >> -1,27,-1 >> then >> -1,-1,04 >> 01,27,04 >> -1,27,01 >> then >> 36,-1,04 >> 01,27,04 >> -1,27,01 >> then >> 36,00,04 >> 01,27,04 >> -1,27,01 >> then >> 36,00,04 >> 01,27,04 >> 36,27,01 >> >> This guarantees that a solution exists, because the algorithm essentially >> traces out the solution as it generates the level. >> >> This presumes that players are not allowed to move tiles around yet leave >> them on the board while solving the puzzle - it assumes that tiles just >> disappear from the grid when the user selects a pair which has a clear >> path >> between it, and that's the only interaction allowed. If they can slide >> them >> around, my algorithm will still produce solve-able puzzles, but they won't >> be as difficult as they could be, I think. :) >> >> Interesting problem! >> >> /mailman/listinfo/flashcoders >> >> _______________________________________________ >> Flashcoders mailing list >> [email protected] >> http://chattyfig.figleaf.com/mailman/listinfo/flashcoders >> >> >> > _______________________________________________ > Flashcoders mailing list > [email protected] > http://chattyfig.figleaf.com/mailman/listinfo/flashcoders > _______________________________________________ Flashcoders mailing list [email protected] http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
