5

我正在尝试使用 p5.js (Javascript) 创建棋盘游戏

要设置 6 x 6 网格的游戏板，我必须用 6 种颜色填充网格，使水平或垂直接触的单元格不具有相同的颜色。并且所有 6 种颜色都必须在 6 个单元格中使用。

但现在我正在努力创建一个随机放置颜色但保持规则的算法。

我尝试从左上角开始，填充随机颜色。然后我开始用不同的颜色填充左侧和底部的单元格。

问题是，当脚本想要填充最后几个单元格时，没有颜色可以使用（已经填充了 6 个单元格或者剩余的颜色是邻居）

示例：仍然需要两个单元格为红色，但只剩下一个位置为红色（在白色下）：

//fill placedColors Array with zeros
placedColors = [];
for(let i=0; i<6; i++) {
    placedColors[i] = 0;
}

//fill allIndexes Array with indizies to keep control of visited cells
let allIndexes = [];
for(let i=0; i<36; i++) {
    allIndexes.push(i);
}

//build board
//when I set the limit to 36 the script runs forever because no solution is found
for(let i=0; i<33; i++) {
    fillCells(i);
}

function fillCells(index) {
    //get top and left color
    let topColor = false;
    //index is in the second row
    if(index >= 6) {
        topColor = cells[index-6].color;
    }
    
    let leftColor = false;
    //index is not in the first column
    if(index % 6 > 0 && index > 0) {
        leftColor = cells[index-1].color;
    }
    
    if(allIndexes.indexOf(index) > -1) {
        cells.push(new Cell(index, pickColor(topColor, leftColor)));
    }
    
    //mark index as visited
    var allIndexesIndex = allIndexes.indexOf(index);
    if (allIndexesIndex !== -1) {
        allIndexes.splice(allIndexesIndex, 1);
    }
}

function pickColor(invalidColor1,invalidColor2) {
    let colorFound = false;
    do {
        randColor = floor(random(6));
        
        if(placedColors[randColor] < 6 && randColor!=invalidColor1 && randColor!=invalidColor2) {
            placedColors[randColor]++;
            colorFound = true;
        }
    } while(!colorFound);
    
    return randColor;
}
4

3 回答 3

4

一种看待这种情况的方法是在树中搜索一条路径，其中每个节点都有 6 个可能的子节点，用于接下来可能出现的六种颜色。最初忽略所有约束，您随机选择其中一个 36 次，并拥有您的展示位置顺序。

使用递归函数（稍后会有用），不受约束的搜索将如下所示：

function randomChoice(list) {
  return list[Math.floor(Math.random() * list.length)];
}

function placeNext(sequenceSoFar) {
    const availableColours = [0,1,2,3,4,5];
    let chosenColour = randomChoice(availableColours);
    sequenceSoFar = [...sequenceSoFar, colourToAdd];
    
    if ( sequenceSoFar.length == 36 ) {
        // Completed sequence!
        return sequenceSoFar;
    }
    else {
        // Recurse to make next choice
        return placeNext(sequenceSoFar);
    }
}
 
// Start with an empty array
let sequence = placeNext([]);
console.log(sequence);

接下来，我们需要消除会违反问题约束的选择：

  • 左边的单元格颜色不同，即chosenColour !== sequenceSoFar[nextIndex-1]
  • 上面的单元格颜色不同，即chosenColour !== sequenceSoFar[nextIndex-6]
  • 颜色在序列中还没有出现六次，即sequenceSoFar.filter((element) => element === chosenColour).length < 6

如果所选颜色不符合这些要求，我们会将其从候选列表中删除并重试：

function randomChoice(list) {
  return list[Math.floor(Math.random() * list.length)];
}

function newColourIsValid(sequenceSoFar, chosenColour) {
   // We haven't added the next colour yet, but know where it *will* be
   let nextIndex = sequenceSoFar.length;
   
   return (
       // The cell to the left isn't the same colour
       ( nextIndex < 1 || chosenColour !== sequenceSoFar[nextIndex-1] )
       &&
       // The cell above isn't the same colour
       ( nextIndex < 6 || chosenColour !== sequenceSoFar[nextIndex-6] )
       &&
       // The colour doesn't already occur six times in the sequence
       sequenceSoFar.filter((element) => element === chosenColour).length < 6
   );
}

function placeNext(sequenceSoFar) {
    let availableColours = [0,1,2,3,4,5];
    let chosenColour;
    
    do {
        // If we run out of possible colours, then ... panic?
        if ( availableColours.length === 0 ) {
            console.log(sequenceSoFar);
            throw 'No sequence possible from here!';
        }
    
        chosenColour = randomChoice(availableColours);
        
        // Eliminate the colour from the list of choices for next iteration
        availableColours = availableColours.filter((element) => element !== chosenColour);
    } while ( ! newColourIsValid(sequenceSoFar, chosenColour) );       

    sequenceSoFar = [...sequenceSoFar, colourToAdd];

    if ( sequenceSoFar.length == 36 ) {
        // Completed sequence!
        return sequenceSoFar;
    }
    else {
        // Recurse to make next choice
        return placeNext(sequenceSoFar);
    }
}
 
// Start with an empty array
let sequence = placeNext([]);
console.log(sequence);

到目前为止，这与您的原始代码存在相同的问题 - 如果它遇到死胡同，它不知道该怎么做。为了解决这个问题，我们可以使用回溯算法。这个想法是，如果我们用完 position 的候选人n，我们会拒绝 position 的选择n-1并尝试不同的选择。

而不是placeNext，我们需要我们的函数是，如果序列遇到死胡同tryPlaceNext，它可以返回：false

function randomChoice(list) {
  return list[Math.floor(Math.random() * list.length)];
}

function newColourIsValid(sequenceSoFar, chosenColour) {
   // We haven't added the next colour yet, but know where it *will* be
   let nextIndex = sequenceSoFar.length;
   
   return (
       // The cell to the left isn't the same colour
       ( nextIndex < 1 || chosenColour !== sequenceSoFar[nextIndex-1] )
       &&
       // The cell above isn't the same colour
       ( nextIndex < 6 || chosenColour !== sequenceSoFar[nextIndex-6] )
       &&
       // The colour doesn't already occur six times in the sequence
       sequenceSoFar.filter((element) => element === chosenColour).length < 6
   );
}

function tryPlaceNext(sequenceSoFar, colourToAdd) {
    let availableColours = [0,1,2,3,4,5];
    
    if ( ! newColourIsValid(sequenceSoFar, colourToAdd) ) {
        // Invalid choice, indicate to caller to try again
        return false;
    }
    
    // Valid choice, add to sequence, and find the next
    sequenceSoFar = [...sequenceSoFar, colourToAdd];
    
    if ( sequenceSoFar.length === 36 ) {
        // Completed sequence!
        return sequenceSoFar;
    }
    
    while ( availableColours.length > 0 ) {
        // Otherwise, pick one and see if we can continue the sequence with it
        let chosenColour = randomChoice(availableColours);
        
        // Recurse to make next choice
        let continuedSequence = tryPlaceNext(sequenceSoFar, chosenColour);
        
        if ( continuedSequence !== false ) {
            // Recursive call found a valid sequence, return it
            return continuedSequence;
        }
        
        // Eliminate the colour from the list of choices for next iteration
        availableColours = availableColours.filter((element) => element !== chosenColour);
    }

    // If we get here, we ran out of possible colours, so indicate a dead end to caller
    return false;
}
 
// Root function to start an array with any first element
function generateSequence() {
    let availableColours = [0,1,2,3,4,5];
    let chosenColour = randomChoice(availableColours);
    return tryPlaceNext([], chosenColour);
}

let sequence = generateSequence();
console.log(sequence);

于 2022-02-06T18:17:07.430 回答
0

一个简单的方法是从一个有效的颜色开始（例如，任何 6x6 拉丁方格都是有效的颜色），然后他们通过找到一对可以交换的东西来混合它，然后交换它们。

一项改进（提高混合速度，并防止算法卡住）是最多允许一个单元格无效（即：如果删除一个单元格，则剩余部分保留为有效颜色）。如果没有无效单元格，则交换两个随机单元格，如果其中至少一个在交换后有效。如果有一个无效单元格，则选择该单元格和另一个要交换的随机单元格，假设再次交换至少其中一个有效。再次重复很多时间，仅在着色有效时停止。

这个想法的实现（对不起，不是 Javascript）在这里：https ://go.dev/play/p/sxMvLxHfhmC

于 2022-02-09T11:39:27.220 回答
0

感谢您的建议！我试图找到与发布的解决方案平行的自己的解决方案。现在使用此代码，它可以正常工作：

function buildBoard() {
    cells = [];

    for(let i=0; i<gameSize; i++) {
        placedColors[i] = 0;
    }
    
    for(var i=0; i<gameSize*gameSize; i++) {
        cells.push(new Cell(i, pickColor()));
    }

    do {
        invalidFields = [];
        findInvalidFields();
        
        if(invalidFields.length > 0) {
            let cell1index = Math.floor(Math.random() * invalidFields.length);
            cell1 = invalidFields[cell1index];
            //check, if cell in different color available
            let otherColorAvailable = false;
            for(cell of invalidFields) {
                if(cell.color != cell1.color) {
                    otherColorAvailable = true;
                    break;
                }
            }
    
            if(otherColorAvailable) {
                //pick invalid cell
                do {
                    let cell2index = Math.floor(Math.random() * invalidFields.length);
                    cell2 = invalidFields[cell2index];
                } while (cell2.color == cell1.color)
            } else {
                //pick random cell
                do {
                    let cell2index = Math.floor(Math.random() * cells.length);
                    cell2 = cells[cell2index];
                } while (cell2.color == cell1.color)            
            }
            
            //switch colors of cells
            let tempColor = cell1.color;
            cell1.color = cell2.color;
            cell2.color = tempColor;
        }
    } while (!checkStartField());   
}

function findInvalidFields() {
    for(let index=0; index<cells.length; index++) {
        let thisColor = cells[index].color;

        //right
        if(index%gameSize < gameSize-1 && cells[index+1].color == thisColor) {
            if(invalidFields.indexOf(cells[index+1])) {
                invalidFields.push(cells[index+1]);
            }
        }
        
        //bottom
        if(index < gameSize*gameSize-gameSize && cells[index+gameSize].color == thisColor) {
            if(invalidFields.indexOf(cells[index+gameSize])) {
                invalidFields.push(cells[index+gameSize]);
            }
        }
    }
}

function checkStartField() {
    for(let index=0; index<cells.length; index++) {
        let thisColor = cells[index].color;
        
        //top
        if(index >= gameSize && cells[index-gameSize].color == thisColor) {
            //console.log(index+'top');
            return false;
        }
        
        //right
        if(index%gameSize < gameSize-1 && cells[index+1].color == thisColor) {
            //console.log(index+'right');
            return false;
        }
        
        //bottom
        if(index < gameSize*gameSize-gameSize && cells[index+gameSize].color == thisColor) {
            //console.log(index+'bottom');
            return false;
        }
        
        //left
        if(index%gameSize > 0 && cells[index-1].color == thisColor) {
            //console.log(index+'left');
            return false;
        }
    }
    
    return true;
}
于 2022-02-09T07:19:17.247 回答