check if a random move has already been made, and to ignore previous move in the randomisation process?

Question

Im positioning sprites in a sliding puzzle game, but I have trouble to randomise the tile position

How can I check if a random move (arc4random) has already been made, and to ignore previous move in the randomisation process?

the tiles do randomise/reshuffle, but sometimes the repeat the random move made eg tile 23 slides to tile 24 position and back several times, counting as a random move (which means the board doesn't shuffle properly)

int count = 0;
int moveArray[5];
int GameTile;
int EmptySq;

//loop through the board and find the empty square
for (GameTile = 0; GameTile <25; ++GameTile) {
    if (boardOcc[GameTile]== kEMPTY) {
        EmptySq = GameTile;
        break;
    }
}

int RowEmpty = RowNumber[GameTile];
int colEmpty = ColHeight[GameTile];

if (RowEmpty <4) moveArray[count++] = (GameTile +5);//works out the current possible move
if (RowEmpty >0) moveArray[count++] = (GameTile -5);//to avoid unsolvable puzzles
if (colEmpty <4) moveArray[count++] = (GameTile +1);
if (colEmpty >0) moveArray[count++] = (GameTile -1);

int RandomIndex = arc4random()%count;
int RandomFrom = moveArray[RandomIndex];

boardOcc[EmptySq] = boardOcc[RandomFrom];
boardOcc[RandomFrom] = kEMPTY;

Answer 1

There are few - if not many possibilities.

One possibility would be to create a stack-like buffer array, which would contain, let's say 10 steps. (Stack - goes in from one end, goes out from other end)

For example:

NSMutableArray *_buffer = [NSMutableArray new];

So - game starts, buffer array is empty. You generate first random move, and also insert it into the buffer array:

[_buffer insertObject:[NSNumber numberWithInt:RandomIndex] atIndex:0];

Then run a check if our array contains more that 10 elements and remove last one if so:

if([_buffer count] > 10)
{
    [_buffer removeObjectAtIndex:10];
}

We need to remove only one item, as we only add one object each time.

And then we add the checking, so that next 'RandomIndex' would be something else than previous 10 indexes. We set 'RandomIndex' to some neutral value (-1) and then launch a while loop (to set 'RandomIndex' to some random value, and second time check if '_buffer' contains such value. If it contains, it will regenerate 'RandomIndex' and check again.. it could do so indefinitely, but if the 'count' is a much bigger number, then it will take 2-3 while loops, tops. No worries.

int RandomIndex = -1;

while(RandomIndex == -1 || [_buffer containsObject:[NSNumber numberWithInt:RandomIndex]])
{
    RandomIndex = arc4random()%count;
}

But You could add some safety, to allow it to break out of the loop if after, say, 5 cycles: (But then it will keep the repeating value..)

int RandomIndex = -1;

int safetyCounter = 0;

while(RandomIndex == -1 || [_buffer containsObject:[NSNumber numberWithInt:RandomIndex]])
{
    RandomIndex = arc4random()%count;

    if(safetyCounter == 5)
    { 
        break;
    }

    safetyCounter++;
}

You could also decrease the buffer size to - 3 or five, then it will work perfectly in 99.9999999% cases or even 100%. Just to disable that case, when randomly it picks the same number each second time as You described. Anyways - no worries.

But still. Let's discuss another - a bit more advanced and safer way.

Other possibility would be to create two separate buffers. One - as in previous example - would be used to store last 10 values, and second would have all the other possible unique moves.

So:

NSMutableArray *_buffer = [NSMutableArray new];
NSMutableArray *_allValues = [NSMutableArray new];

At the beginning '_buffer' is empty, but for '_allValues', we add all possible moves:

for(int i = 0; i < count; i++)
{
    [_allValues addObject:[NSNumber numberWithInt:i]];
}

and again - when we calculate a random value - we add it to the '_buffer' AND remove from '_allValues'

[_buffer insertObject:[NSNumber numberWithInt:RandomIndex] atIndex:0];
[_allValues removeObject:[NSNumber numberWithInt:RandomIndex]];

after that - we again check if _buffer is not larger than 10. If Yes, we remove last object, and add back to _allValues:

if([_buffer count] > 10)
{
    [_allValues addObject:[_buffer objectAtIndex:10]];

    [_buffer removeObjectAtIndex:10];
}

And most importantly - we calculate 'RandomIndex from the count of _allValues and take corresponding object's intValue:

RandomIndex = [[_allValues objectAtIndex:(arc4random()%[_allValues count])] intValue];

Thus - we don't need any safety checking, because in this way, each time calculated value will be unique for the last 10 moves.

Hope it helps.. happy coding!