A little assistance if you please.

[ghorricks]

Flash MX 2004 Pro.

I'm in the middle of a game that needs a certain mechanic while playing.

A grid of 5x5 squares:

X,X,X,X,X
X,X,X,X,X
X,X,X,X,X
X,X,X,X,X
X,X,X,X,X

Each square can have a value of 1 to max_prize.
I'm looking for a function that will select a random grid number and give it a random value between 1 & max_prize. Easy until you realise that there must never be a line of 3 like values in the grid (horizontally, vertically or diagonally).

It would also be handy if I could trigger a line of 3 like values at some point within this function.

Any ideas?

I know that it would probably be best using an array for the grid and perform checks to see what values are already around the grid number.

Many thanks in advance.

Gav

[CMU]

There are two ways to do this (assume you're writing a function that picks a prize value for a grid location):

1. The dubious way:
Pick a random prize. Test if it may be inserted into the relevant grid slot. If not, keep picking more random prize numbers until you've got one that fits. This is dubious for a few reasons. You don't know how long it'll be searching. You aren't stopping it trying the same number over and over. Also you don't know if a solution actually exists (in which case you'll go into an infinite loop). Suppose max_prize is low - it's pretty easy to make it so you can't add any number after a few iterations.

2. The better way:
Create an empty prize array. Iterate from 1 to max_prize, and test the current loop iteration against your constraints. If the number is allowed, push it into the array. When you hit max_prize, you now have an array of values that will slot legally into the chosen square. Pick one at random and there's your value. If the array turns out empty, there is no number that will legally fit and you can detect it easily.

Remember for either method that a new value could complete a line by being in the middle, left or right end of the line. Ie, suppose you're picking a value for position X. You have to test horizontally three times - one to detect the 66X line, one for 6X1 line, and one for X11 line. Likewise for both diagonals and the vertical direction.

 | | | | 
 |7|2| | 
6|6|X|1|1
 | | |7| 
 | |2| |

Edges become easy to handle now - if the check runs off the edge of the grid, it doesn't count as a constraint.

[ghorricks]

Ay, I realised the better way would be the way to go. The problem I have been having is creating a neat function that does all the checking. There are so many variants of what checks need to be performed and I am struggling to get something neat and tidy instead of the long mess I have at the moment, which has a set of check for each grid position.

function check_pos(n){
if (n eq 0){
.....
.....
.....
}
if (n eq 1){
.....
.....
.....
}

And so on......
}

[CMU]

Ok, I reckon this is a prime case of divide and conquer, and clear thinking. It's essential to get what you're trying to do clear in your head before tackling it.

I can see at least two separate tasks here - one is to organise all the directions to check, and the other is to actually perform the checks. That sounds like two functions to me.

First function - organise the checks. This needs to run a check in each of the directions we can check in. If we're checking the X position below (or any X position for that matter), we need to perform a number of 3-square checks.

// Checking position X

 .|.|.|.|.
 .|.|.|.|.
 .|.|X|.|.
 .|.|.|.|.
 .|.|.|.|.

// Must check end conditions

 .|.|C|.|.
 .|.|C|.|.
 .|.|C|.|.
 .|.|.|.|.
 .|.|.|.|.

 .|.|.|.|C
 .|.|.|C|.
 .|.|C|.|.
 .|.|.|.|.
 .|.|.|.|.

 .|.|.|.|.
 .|.|.|.|.
 .|.|C|C|C
 .|.|.|.|.
 .|.|.|.|.

 .|.|.|.|.
 .|.|.|.|.
 .|.|C|.|.
 .|.|.|C|.
 .|.|.|.|C

 .|.|.|.|.
 .|.|.|.|.
 .|.|C|.|.
 .|.|C|.|.
 .|.|C|.|.

 .|.|.|.|.
 .|.|.|.|.
 .|.|C|.|.
 .|C|.|.|.
 C|.|.|.|.

 .|.|.|.|.
 .|.|.|.|.
 C|C|C|.|.
 .|.|.|.|.
 .|.|.|.|.

 C|.|.|.|.
 .|C|.|.|.
 .|.|C|.|.
 .|.|.|.|.
 .|.|.|.|.

// Also must check for middle spots

 .|.|.|.|.
 .|.|C|.|.
 .|.|C|.|.
 .|.|C|.|.
 .|.|.|.|.

 .|.|.|.|.
 .|.|.|C|.
 .|.|C|.|.
 .|C|.|.|.
 .|.|.|.|.

 .|.|.|.|.
 .|.|.|.|.
 .|C|C|C|.
 .|.|.|.|.
 .|.|.|.|.

 .|.|.|.|.
 .|C|.|.|.
 .|.|C|.|.
 .|.|.|C|.
 .|.|.|.|.

So that's 12 distinct cases. By drawing those out, I've noticed that there's a bit of a pattern to them. We can take advantage of that. Our check routine will start at a point we give it, and walk three spaces in a direction of our choosing. Then we just have to call it over and over for the 12 cases.

function checkValueAllowed(x, y, value)
{
    // Ensure the x/y position's value is undefined
    // we'll be overwriting it later when we find the answer
    prizeGrid[x][y] = undefined;
    
    // Check end cases
    checkValueAllowedInDirection(x, y,  0, -1, value);
    checkValueAllowedInDirection(x, y,  1, -1, value);
    checkValueAllowedInDirection(x, y,  1,  0, value);
    checkValueAllowedInDirection(x, y,  1,  1, value);
    checkValueAllowedInDirection(x, y,  0,  1, value);
    checkValueAllowedInDirection(x, y, -1,  1, value);
    checkValueAllowedInDirection(x, y, -1,  0, value);
    checkValueAllowedInDirection(x, y, -1, -1, value);

    // Check middle cases
    checkValueAllowedInDirection(x,   y-1,  0, 1, value);
    checkValueAllowedInDirection(x+1, y-1, -1, 1, value);
    checkValueAllowedInDirection(x-1, y,    1, 0, value);
    checkValueAllowedInDirection(x-1, y-1,  1, 1, value);
}

Ok, that just leaves the direction walking function to write. It has to handle the edges, including starting off the edge remember.

function checkValueAllowedInDirection(x, y, dx, dy, value)
{
    // Start at point x, y, walk three grid spaces
    matchedCount = 0;
    for (j=0; j<3; j++)
    {
        // If the current x/y coords put us out of the grid, this can't be a line of three matching numbers
        if ((x < 0) || (x > 4) || (y < 0) || (y > 4)) return false;
        
        // If the current grid position matches the value we're checking, count it
        if (prizeGrid[x][y] == value) matchedCount++;
    }
    
    // If we matched more than once, this value isn't allowed
    return (matchedCount >= 2) ? true : false;
}

Now, all of that is untested and I've made up all the variable names. You should be able to adapt it from there though. There's a final part of the puzzle - the bit that creates the array of allowable numbers and picks one. That should be pretty simple now.

Be warned that this probably isn't the most efficient way of doing this. It's not terrible though, so it should be good if you're setting up the grid of prizes before the game starts. I wouldn't want to run things like this each frame whilst running other stuff though.

[CMU]

Forgot to ask, what's all that for anyway? Sounds like an interesting game...

[ghorricks]

Basically it's a hybrid game for a company I work for.
It takes a classic space (shoot em up) game, and for every invader shot it adds a random coloured block to the 5x5 grid.

The important thing here is control. The code needs to be examined and be seen as tight.

Due to non disclosure, it's difficult to say exactly what, but I appreciate the thinking time that you have put into this. You are using 2 dimension arrays, which I have not yet done with flash, so it might be interesting to go down this route.

I'll look at your example and see if I can figure it out. Many thanks for now.

[CMU]

So I'm doing your job for you, for free? And you're getting paid for it. Hmmm. Where abouts is your company? I'm looking for Flash work at the moment (no, seriously).

My code above will work and is clean, in terms of its algorithm clarity. It won't be spectacularly fast though, so I really wouldn't use it each time an invader dies.

I'm surprised you don't know how to do 2D arrays already. I mean, what other practical way is there of working through a problem involving a grid?!

[ghorricks]

Hmm... I thought I replied to this on Thursday!

Ahh well - No jobs at my place at the moment, but will certainly look your way should we be taking any more people on.

I eventually solved the prroblem using a 2D array. I have used them before, but I can't remembeer what I was doing yesterday - let alone 18 months ago!

In a nutshell I did the 12 searches (using my own code I might add), and then if there are any pairs around I take these away from the array of possibles and then put in any random one left.

Of course it was possible to not be able to fit in any value - in that case I simply go and do another grid position!

Thanks for the heads up.

[CMU]

Cool - sounds like you've got your code sorted nicely

Hopefully, you can now see how you can turn a complex problem into a series of smaller, simpler problems. Then you crack each one in turn by understanding it and comming up with a clean, tidy solution.

Nice one!