javascript - 如何确定游戏方 block 中的可移动区域

Question

我正在构建一个基于 2D 方形网格的回合制 HTML 游戏。每个网格方 block 可以需要不同数量的移动点来穿​​越(即:道路 1 MP，草原 1.5 MP，森林 2 MP 等)。当用户单击一个单元时，我想通过该单元分配的移动点来确定所有可能的可移动空间，以便我可以突出显示它们并使它们可点击。

有免费的库可以做到这一点吗？我见过一些路径算法，但没有见过关于确定可移动区域的内容。其他游戏开发商如何处理这个问题？我对普通 JS 和 JQuery 解决方案持开放态度。

Answer 1

好吧，我决定自己尝试解决这个问题。我从来不擅长这类算法，所以我确信有一种比我所做的更有效的方法来处理它。然而，就我的目的而言，它运行得足够快，而且非常简单易懂。

如果它对其他想要做同样事情的人有帮助，我已经包含了下面的代码。这是我原始答案的更新版本，我对其进行了修改，以存储所采取的路径，以便您可以显示单位在正确的空间中移动。这个答案在下面的例子中使用了JQuery，但只在少数地方；你可以很容易地用 vanilla JS 替换它们。第一个代码块包含实际的路径/区域查找功能，是纯 JS。

<script>
    var possibleMovementAreaArray   = new Array();  // This array will hold our allowable movement tiles.  Your other functions can access this after running possibleMovementArea().

    function possibleMovementArea(unitIndex) {
        // I'm storing each unit in my game in an array.  So I pass in the index of the unit I want to determine the movement area for.
        var x   = unitList[unitIndex][10];  // x coordinate on the playgrid
        var y   = unitList[unitIndex][11];  // y coordinate on the playgrid
        var mp  = unitList[unitIndex][15];  // number of movement points
        possibleMovementAreaArray.length = 0;  // Clear our array so previous runs don't interfere.

        findPossibleMovement(x, y, mp);
    }

    function findPossibleMovement(x, y, mp, prevStepX, prevStepY) {
        // This is a recursive function; something I'm not normally too good at.

        for (var d=1; d<=4; d++) {
            // We run through each of the four cardinal directions.  Bump this to 8 and add 4 more cases to include corners.
            if (d == 1) {
                // Check Up
                var newX = x;
                var newY = y - 1;
            } else if (d == 2) {
                // Check Down
                var newX = x;
                var newY = y + 1;
            } else if (d == 3) {
                // Check Left
                var newX = x - 1;
                var newY = y;
            } else if (d == 4) {
                // Check Right
                var newX = x + 1;
                var newY = y;
            }

            // Check to see if this square is occupied by another unit.  Two units cannot occupy the same space.
            spaceOccupied = false;
            for (var j=1; j<=numUnits; j++) {
                if (unitList[j][10] == newX && unitList[j][11] == newY)
                    spaceOccupied = true;
            }

            if (!spaceOccupied) {
                // Modify this for loop as needed for your usage.  I have a 2D array called mainMap that holds the ID of a type of terrain for each tile.
                // I then have an array called terList that holds all the details for each type of terrain, such as movement points needed to get past.
                // This for loop is just looking up the ID of the terrain for use later.  Sort of like a "SELECT * FROM terrainInfo WHERE ID=terrainOfCurrentTile".
                for (var j=1; j<=numTerrains; j++) {
                    if (newX > 0 && newX <= mapWidth && newY > 0 && newY <= mapHeight && terList[j][1] == mainMap[newX][newY])
                        break;  // After finding the index of terList break out of the loop so j represents the correct index.
                }
                if (j <= numTerrains) {  // Run if an actual terrain is found.  No terrain is found if the search runs off the sides of the map.
                    var newMp   = mp - terList[j][7];  // Decrement the movement points for this particular path.
                    if (newMp >= 0) {  // Only continue if there were enough movement points to move to this square.
                        // Check to see if this square is already logged.  For both efficiency and simplicity we only want each square logged once.
                        var newIndex                            = possibleMovementAreaArray.length
                        var alreadyLogged = false
                        if (possibleMovementAreaArray.length > 0) {
                            for (var j=0; j<possibleMovementAreaArray.length; j++) {
                                if (possibleMovementAreaArray[j][1] == newX && possibleMovementAreaArray[j][2] == newY) {
                                    alreadyLogged           = true;
                                    var alreadyLoggedIndex  = j;
                                }
                            }
                        }
                        if (!alreadyLogged) {
                            // This adds a row to the array and records the x and y coordinates of this tile as movable
                            possibleMovementAreaArray[newIndex]     = new Array(6);
                            possibleMovementAreaArray[newIndex][1]  = newX;
                            possibleMovementAreaArray[newIndex][2]  = newY;
                            possibleMovementAreaArray[newIndex][3]  = prevStepX;  // This tracks the x coords of the steps taken so far to get here.
                            possibleMovementAreaArray[newIndex][4]  = prevStepY;  // This tracks the y coords of the steps taken so far to get here.
                            possibleMovementAreaArray[newIndex][5]  = newMp;  // Records remaining MP after the previous steps have been taken.
                        }
                        if (alreadyLogged && newMp > possibleMovementAreaArray[alreadyLoggedIndex][5]) {
                            // If this tile was already logged, but there was less MP remaining on that attempt, then this one is more efficient.  Update the old path with this one.
                            possibleMovementAreaArray[alreadyLoggedIndex][3]    = prevStepX;
                            possibleMovementAreaArray[alreadyLoggedIndex][4]    = prevStepY;
                            possibleMovementAreaArray[alreadyLoggedIndex][5]    = newMp;
                        }
                        if (newMp > 0) {
                            // Now update the list of previous steps to include this tile.  This list will be passed along to the next call of this function, thus building a path.
                            if (prevStepX == '') {
                                var newPrevStepX = [newX];
                                var newPrevStepY = [newY];
                            } else {
                                // This code is required to make a full copy of the array holding the existing list of steps.  If you use a simple equals then you just create a reference and
                                // subsequent calls are all updating the same array which creates a chaotic mess.  This way we store a separate array for each possible path.
                                var newPrevStepX = prevStepX.slice();
                                newPrevStepX.push(newX);
                                var newPrevStepY = prevStepY.slice();
                                newPrevStepY.push(newY);
                            }

                            // If there are still movement points remaining, check and see where we could move next.
                            findPossibleMovement(newX, newY, newMp, newPrevStepX, newPrevStepY);
                        }
                    }
                }
            }
        }
    }
</script>

运行上述代码后，您可以循环遍历数组以查找所有可用的图 block 。我是这样做的:

<script>
    // Shows the movement area based on the currently selected unit.
    function showMovement() {
        var newHTML = "";
        curAction   = "move";
        possibleMovementArea(curUnit);  // See above code
        for (x=0; x<possibleMovementAreaArray.length; x++) {
            // Loop over the array and do something with each tile.  In this case I'm creating an overlay that I'll fade in and out.
            var tileLeft    = (possibleMovementAreaArray[x][1] - 1) * mapTileSize;  // Figure out where to absolutely position this tile.
            var tileTop     = (possibleMovementAreaArray[x][2] - 1) * mapTileSize;  // Figure out where to absolutely position this tile.
            newHTML = newHTML + "<img id='path_" + possibleMovementAreaArray[x][1] + "_" + possibleMovementAreaArray[x][2] + "' onClick='mapClk(" + possibleMovementAreaArray[x][1] + ", " + possibleMovementAreaArray[x][2] + ", 0);' src='imgs/path.png' class='mapTile' style='left:" + tileLeft + "px; top:" + tileTop + "px;'>";
        }
        $("#movementDiv").html(newHTML);  // Add all those images into a preexisting div.
        $("#movementDiv").css("opacity", "0.5");  // Fade the div to 50%
        $("#movementDiv").show();  // Make the div visible.
        startFading();  // Run a routine to fade the div in and out.
    }
</script>

既然我们确定了路径，我们就可以通过循环存储的信息轻松显示运动:

<script>
    for (j=0; j<possibleMovementAreaArray[areaIndex][3].length; j++) {
        // This loop moves the unit img to each tile on its way to its destination.  The final destination tile is not included.
        var animSpeed   = 150;  // Time in ms that it takes to move each square.
        var animEase    = "linear"; // We want movement to remain a constant speed through each square in this case.
        var targetLeft  = (possibleMovementAreaArray[areaIndex][3][j]-1) * mapTileSize; // This looks at each step in the path array and multiplies it by tile size to determine the new horizonal position.
        var targetTop   = (possibleMovementAreaArray[areaIndex][4][j]-1) * mapTileSize; // This looks at each step in the path array and multiplies it by tile size to determine the new vertical position.
        $("#char_"+curUnit).animate({"left":targetLeft, "top":targetTop}, animSpeed, animEase);  // Do the animation.  Subsequent animations get queued.                
    }

    // Now we need to move to that last tile.
    newLeft = (x-1) * mapTileSize;
    newTop  = (y-1) * mapTileSize;
    $("#char_"+curUnit).animate({"left":newLeft, "top":newTop}, 400, "easeOutCubic");  // Slow unit at the end of journey for aesthetic purposes.

    $("#char_"+curUnit).addClass("unitMoved", 250); // Turns the image grayscale so it can easily be seen that it has already moved.
</script>

希望这对其他人有帮助。