Ensure neighbor nodes do not share same value

Question

I'm creating a game- a grid of colors that the player can navigate either up, down, left, or right. If the direction says "go to red square", the player must do this. The path the player must follow is determined by a random path generation algorithm which follows these rules:

Game rules:

• This is maze a game to help people practice a foreign language
• The player is given grid of colors, which they traverse a randomly generated left-to-right path following the next given color (if next color on randomly generated path is red, they will be prompted to go to the red square) - obviously later the prompts will be in the foreign language
• For example, "Rojo" comes up, they must go to a red square
• It will be timing based... if you stay on the same tile for too long, you take damage
• If you step on the wrong color, you take damage
• Since the maze is generated left to right (see algorithm info below), they have options to move to the north, east, or south node

Logic rules:

• left to right, meaning a random row is selection at column 0
• the path must connect from col 0 to last column
• the path is windy, but it cannot traverse back, meaning it can loop up, down, and right
• nodes neighboring each other cannot share the same color
• nodes to the north, east, south of current node (for example the grey node) cannot share same color
• The color prompts (next cell to travel to) are pre-generated as the random path is generated... each color is assigned to a cell at grid creation... and the randomly generated path stores the order/path which those colors are on... so I can pass the next color to the player for them to step on.

Path generation algorithm information: Random path generation algorithm

I am generating a grid of randomized colors. Of course, this means it can't be totally random because I need to ensure the player can't have more than one of the same colors as a neighbor to choose from.

This image describes it: The grey cell is the player start location... the north, east, and south neighbors all share same color... this is bad.

In game

The grid is a grid of color tile images. Therefore the tile "colors" shouldn't be changed after I generate the grid. During grid creation, each new cell, I create a random index, and set the cell color equal to colorsObject[randomIndex] to ensure a random color is assigned

To try and solve this, I attempt to store the last used color... and on the next iteration of cell creation, I remove that stored last used color from the colors object (need an object for my own reasons, otherwise would use array), set the random to choose from shortened list of colors, and use that color. Then add that lastUsedColor back to the object:

    var lastUsedColor = "";
    for (var row = 0; row <= bridgeSegment.settings.rows-1; row++) {
        this.grid[row] = []; 
        for (var col = 0; col <= bridgeSegment.settings.cols-1; col++) {                
            if (lastUsedColor != "") delete this.colors[lastUsedColor];

            var colorIndex = Math.floor(Math.random() * (Object.keys(this.colors).length - 0) + 0);

            var keyName = Object.keys(this.colors)[colorIndex]; 

            image = (this.maze == 1) ? image : keyName;

            if (lastUsedColor != "") this.colors[lastUsedColor] = lastUsedColor;
            lastUsedColor = keyName;

            var myCell = me.pool.pull("mazetile", x, y, {
                name : "mazetile",
                type : "mazetile",
                image : image,
                row : row,
                col : col,
                width: 64,
                height : 64,
                spritewidth : 64
            });
            me.game.world.addChild(myCell);
            this.grids[row][col] = myCell;  
        }

This works on a row-by-row basis (meaning 2 neighboring columns won't share the same color), but on the next row, there can be neighboring nodes with same colors.

My next thought was to first generate all tile images with colors... then iterate again to check for neighboring colors... if there are, swap out for a new image. But I wanted to get this done on generate of set of tiles without having to do another nested for loop.

---

I've tried the method roko suggested, and the "maze" now works fine, but when the player moves to the next part of the bridge (where I've generated the second set of tiles in a grid, see this image for what I mean: http://i.imgur.com/Hlerxm3.png), there doesn't seem to be colors near him:

You can see it says "Yellow", but there are no yellow options around him.

Code: (Omitting the code to actually loop through and generate the grid, as that's not the issue)

run : function (maze) {
    this.maze= maze;
    this.list = [];
    this.containerOfGrids = [];
    this.myDirectionsText = new game.HUD.ScreenText(630, 10, 10, 10, {font: "32x32_font", text: "1"})

    game.data.gameHUD.addChild(this.myDirectionsText);          
    for (var i = 0; i <= game.data.bridgeSegments.length-1; i++) {
        this.containerOfGrids[i] = [];
        this.createGrid(game.data.bridgeSegments[i], i);                
    }

    //call to set initial color cell
    this.firstCell();

},  

Called initially to pick first cell.. If it's the top bridge segment (bridge shape 1), I need to start from a random row in the first column... if it's other grids as the path winds down, I need a random column selected...

firstCell : function () {
    //choose intitial random starting cell 
    if (game.data.bridgeSegments[this.bridgeIndex].settings.realname == "bridge_shape_1") {
        var row = Math.floor(Math.random() * (this.containerOfGrids[this.bridgeIndex].length - 0) + 0);
        var col = 0;    
        this.gridLen = this.containerOfGrids[this.bridgeIndex][row].length;
    }
    else {
        var row = 0;
        var col = Math.floor(Math.random() * (this.containerOfGrids[this.bridgeIndex][row].length - 0) + 0);
        this.gridLen = this.containerOfGrids[this.bridgeIndex].length;
    }
    this.containerOfGrids[this.bridgeIndex][row][col].firstCell = true;

    this.currColor = this.containerOfGrids[this.bridgeIndex][row][col].color;
    this.containerOfGrids[this.bridgeIndex][row][col].renderable.alpha = 1;
    this.myDirectionsText.settings.text = this.containerOfGrids[this.bridgeIndex][row][col].color;

},

//passing in collided cell, cell row and col from the Tile Class
nextCell : function (cell, row, col) {
    if (cell.col < this.gridLen) {  
        this.checkValidCells(row, col);
        this.checkValidMove(cell, this.currColor);

        var randomNumber = Math.floor(Math.random() * (this.list.length));          
        this.currColor = (this.list.length > 0) ? this.list[randomNumber].color : "RED";
        this.myDirectionsText.settings.text = this.currColor; 
    }

},

checkValidMove : function (cell, color) {
    if (cell.color == color) {
        cell.renderable.image = (game.data.bridgeSegments[this.bridgeIndex].settings.view == "topdown") ? me.loader.getImage("MyFlatTile3") :  me.loader.getImage("Tile128Green");          
    }
    else {
        game.data.health -=10;
        cell.renderable.image = (game.data.bridgeSegments[this.bridgeIndex].settings.view == "topdown") ? me.loader.getImage("MyFlatTile3") :  me.loader.getImage("Tile128Red");
    }
    cell.renderable.alpha = 1;  
},

checkValidCells : function (row, col) {
    this.list = [];


    if (row - 1 >= 0) {
        if (!this.containerOfGrids[this.bridgeIndex][row-1][col].explored) {
            this.list.push(this.containerOfGrids[this.bridgeIndex][row-1][col]);
        }
    }

    if (col - 1 >= 0) {
        if (!this.containerOfGrids[this.bridgeIndex][row][col-1].explored) {
            this.list.push(this.containerOfGrids[this.bridgeIndex][row][col-1]);
        }
    }       

    if (col + 1 < this.containerOfGrids[this.bridgeIndex][row].length && this.containerOfGrids[this.bridgeIndex][row][col + 1] != "undefined")  {
        if (!this.containerOfGrids[this.bridgeIndex][row][col+1].explored) {
            this.list.push(this.containerOfGrids[this.bridgeIndex][row][col+1]);
        }

    }
    if (row + 1 < this.containerOfGrids[this.bridgeIndex].length && this.containerOfGrids[this.bridgeIndex][row+1][col] != "undefined") {
        if (!this.containerOfGrids[this.bridgeIndex][row+1][col].explored) {
            this.list.push(this.containerOfGrids[this.bridgeIndex][row+1][col]);
        }
    }

}

In my tile class, I start the next cell on collision with current cell:

        if (!this.explored) {
            nextCell(this, this.row, this.col);
            this.explored=true;
        }

Answer 1

If I understand you right, you are not only concerned with not placing same color next to itself, but with everything 2 steps in all directions.

Instead of removing the color from the object, you can make a rule when you color a tile (a,b). Where that color is not allowed again if a-2 < x > a+2 AND y-2 < y < b+2. (within 2 squares above-below, and 2 squares left-right).

You will then have to check the rules for each color as you want to place it (there can be multiple active rules at the same time for each color, fx if 0,0 and 3,0 are both red, you need the first rule still for when you move to next row).

Without knowing how you have implemented the colors and grid it is hard to go more in detail.

EDIT Read it again and noticed I had written y-2 < y < b-2, the second - should be a +, as corrected above.

Answer 2

Does this work? I'm not sure if I understand the question completely, but I think this is right. I'm creating an array called grid and filling it with random colors, checking each time that it isn't the same as a nearby color.

Edit: No, this doesn't work yet. I'll try to fix it. Okay, I think I fixed it.

    grid = [];
for(var i=0;i<=totalRows;row++)
{
    grid[i]=[]
    for(var j=0;j<=totalCols;j++)
    {
        do
        {
            var colorIndex = Math.floor(Math.random() * (Object.keys(this.colors).length - 0) + 0);
            var keyName = Object.keys(this.colors)[colorIndex]; 
            grid[i][j]=keyName;
            var nearSameColor=false;
            for(var k=i-2;k<=i+2;k++)
            {
                if(k<0||k>totalRows)
                    continue;
                for(var l=j-2;l<=l+2;l++)
                {
                    if(l<0||l>totalCols||(k==i&&l==j))
                        continue;
                    nearSameColor=nearSameColor||grid[i+k][j+l]==grid[i][i];
                }
            }
        }while(nearSameColor)
    }
}
for (var row = 0; row <= totalRows; row++) {
    this.containerOfGrids[i][row] = [];
    for (var col = 0; col <= totalCols; col++) {
        image = grid[row][col];

        //other code