如何确定游戏区域中的可移动区域

Question

我正在构建基于2D正方形网格的基于回合的HTML游戏。每个网格平方可以穿越不同数量的移动点（IE：道路1 MP，草原1.5 MP，森林2 MP）等。当用户点击一个单位时，我想确定所有可能的可移动空间与所述单位的分配移动点，以便我可以突出显示它们并使其可点击。

有没有免费的图书馆可以做到这一点？我已经看到了一些路径算法，但没有关于确定可移动区域。其他游戏开发者如何处理这个问题？我对vanilla JS和JQuery解决方案都是开放的。

Answer 1

嗯，我决定尝试自己去攻击它。我从来没有在这些算法的伟大，所以我相信有一个更有效的方式来处理它比我所做的。但是，对我而言，它的运行速度足够快，非常简单易懂。

如果其他人希望这样做有帮助，我已经包含下面的代码。这是我的原始答案的更新版本，我修改后还存储了所采用的路径，以便您可以显示通过正确空间移动的单元。这个答案在下面的例子中使用JQuery，但只在少数几个地方使用;你可以很容易地用香草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> 

运行上面的代码后，您可以循环访问数组以查找所有可用的切片。这是我如何做的：

<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> 

希望这是帮助他人。