javascript - 如何让车子朝怪物方向行驶

Question

我是游戏开发新手，我已经构建了一款汽车游戏，当它撞到怪物时，它会自动移动。现在我想让汽车朝怪物移动。所以我现在研究了路径查找算法我想在我的游戏中实现A-Star寻路算法。所以寻路函数如下:

function findPath(world, pathStart, pathEnd)
{
    // shortcuts for speed
    var abs = Math.abs;
    var max = Math.max;
    var pow = Math.pow;
    var sqrt = Math.sqrt;

    // the world data are integers:
    // anything higher than this number is considered blocked
    // this is handy is you use numbered sprites, more than one
    // of which is walkable road, grass, mud, etc
    var maxWalkableTileNum = 0;

    // keep track of the world dimensions
    // Note that this A-star implementation expects the world array to be square: 
    // it must have equal height and width. If your game world is rectangular, 
    // just fill the array with dummy values to pad the empty space.
    var worldWidth = world[0].length;
    var worldHeight = world.length;
    var worldSize = worldWidth * worldHeight;

    // which heuristic should we use?
    // default: no diagonals (Manhattan)
    var distanceFunction = ManhattanDistance;
    var findNeighbours = function(){}; // empty

    /*

    // alternate heuristics, depending on your game:

    // diagonals allowed but no sqeezing through cracks:
    var distanceFunction = DiagonalDistance;
    var findNeighbours = DiagonalNeighbours;

    // diagonals and squeezing through cracks allowed:
    var distanceFunction = DiagonalDistance;
    var findNeighbours = DiagonalNeighboursFree;

    // euclidean but no squeezing through cracks:
    var distanceFunction = EuclideanDistance;
    var findNeighbours = DiagonalNeighbours;

    // euclidean and squeezing through cracks allowed:
    var distanceFunction = EuclideanDistance;
    var findNeighbours = DiagonalNeighboursFree;

    */

    // distanceFunction functions
    // these return how far away a point is to another

    function ManhattanDistance(Point, Goal)
    {   // linear movement - no diagonals - just cardinal directions (NSEW)
        return abs(Point.x - Goal.x) + abs(Point.y - Goal.y);
    }

    function DiagonalDistance(Point, Goal)
    {   // diagonal movement - assumes diag dist is 1, same as cardinals
        return max(abs(Point.x - Goal.x), abs(Point.y - Goal.y));
    }

    function EuclideanDistance(Point, Goal)
    {   // diagonals are considered a little farther than cardinal directions
        // diagonal movement using Euclide (AC = sqrt(AB^2 + BC^2))
        // where AB = x2 - x1 and BC = y2 - y1 and AC will be [x3, y3]
        return sqrt(pow(Point.x - Goal.x, 2) + pow(Point.y - Goal.y, 2));
    }

    // Neighbours functions, used by findNeighbours function
    // to locate adjacent available cells that aren't blocked

    // Returns every available North, South, East or West
    // cell that is empty. No diagonals,
    // unless distanceFunction function is not Manhattan
    function Neighbours(x, y)
    {
        var N = y - 1,
        S = y + 1,
        E = x + 1,
        W = x - 1,
        myN = N > -1 && canWalkHere(x, N),
        myS = S < worldHeight && canWalkHere(x, S),
        myE = E < worldWidth && canWalkHere(E, y),
        myW = W > -1 && canWalkHere(W, y),
        result = [];
        if(myN)
        result.push({x:x, y:N});
        if(myE)
        result.push({x:E, y:y});
        if(myS)
        result.push({x:x, y:S});
        if(myW)
        result.push({x:W, y:y});
        findNeighbours(myN, myS, myE, myW, N, S, E, W, result);
        return result;
    }

    // returns every available North East, South East,
    // South West or North West cell - no squeezing through
    // "cracks" between two diagonals
    function DiagonalNeighbours(myN, myS, myE, myW, N, S, E, W, result)
    {
        if(myN)
        {
            if(myE && canWalkHere(E, N))
            result.push({x:E, y:N});
            if(myW && canWalkHere(W, N))
            result.push({x:W, y:N});
        }
        if(myS)
        {
            if(myE && canWalkHere(E, S))
            result.push({x:E, y:S});
            if(myW && canWalkHere(W, S))
            result.push({x:W, y:S});
        }
    }

    // returns every available North East, South East,
    // South West or North West cell including the times that
    // you would be squeezing through a "crack"
    function DiagonalNeighboursFree(myN, myS, myE, myW, N, S, E, W, result)
    {
        myN = N > -1;
        myS = S < worldHeight;
        myE = E < worldWidth;
        myW = W > -1;
        if(myE)
        {
            if(myN && canWalkHere(E, N))
            result.push({x:E, y:N});
            if(myS && canWalkHere(E, S))
            result.push({x:E, y:S});
        }
        if(myW)
        {
            if(myN && canWalkHere(W, N))
            result.push({x:W, y:N});
            if(myS && canWalkHere(W, S))
            result.push({x:W, y:S});
        }
    }

    // returns boolean value (world cell is available and open)
    function canWalkHere(x, y)
    {
        return ((world[x] != null) &&
            (world[x][y] != null) &&
            (world[x][y] <= maxWalkableTileNum));
    };

    // Node function, returns a new object with Node properties
    // Used in the calculatePath function to store route costs, etc.
    function Node(Parent, Point)
    {
        var newNode = {
            // pointer to another Node object
            Parent:Parent,
            // array index of this Node in the world linear array
            value:Point.x + (Point.y * worldWidth),
            // the location coordinates of this Node
            x:Point.x,
            y:Point.y,
            // the heuristic estimated cost
            // of an entire path using this node
            f:0,
            // the distanceFunction cost to get
            // from the starting point to this node
            g:0
        };

        return newNode;
    }

    // Path function, executes AStar algorithm operations
    function calculatePath()
    {
        // create Nodes from the Start and End x,y coordinates
        var mypathStart = Node(null, {x:pathStart[0], y:pathStart[1]});
        var mypathEnd = Node(null, {x:pathEnd[0], y:pathEnd[1]});
        // create an array that will contain all world cells
        var AStar = new Array(worldSize);
        // list of currently open Nodes
        var Open = [mypathStart];
        // list of closed Nodes
        var Closed = [];
        // list of the final output array
        var result = [];
        // reference to a Node (that is nearby)
        var myNeighbours;
        // reference to a Node (that we are considering now)
        var myNode;
        // reference to a Node (that starts a path in question)
        var myPath;
        // temp integer variables used in the calculations
        var length, max, min, i, j;
        // iterate through the open list until none are left
        while(length = Open.length)
        {
            max = worldSize;
            min = -1;
            for(i = 0; i < length; i++)
            {
                if(Open[i].f < max)
                {
                    max = Open[i].f;
                    min = i;
                }
            }
            // grab the next node and remove it from Open array
            myNode = Open.splice(min, 1)[0];
            // is it the destination node?
            if(myNode.value === mypathEnd.value)
            {
                myPath = Closed[Closed.push(myNode) - 1];
                do
                {
                    result.push([myPath.x, myPath.y]);
                }
                while (myPath = myPath.Parent);
                // clear the working arrays
                AStar = Closed = Open = [];
                // we want to return start to finish
                result.reverse();
            }
            else // not the destination
            {
                // find which nearby nodes are walkable
                myNeighbours = Neighbours(myNode.x, myNode.y);
                // test each one that hasn't been tried already
                for(i = 0, j = myNeighbours.length; i < j; i++)
                {
                    myPath = Node(myNode, myNeighbours[i]);
                    if (!AStar[myPath.value])
                    {
                        // estimated cost of this particular route so far
                        myPath.g = myNode.g + distanceFunction(myNeighbours[i], myNode);
                        // estimated cost of entire guessed route to the destination
                        myPath.f = myPath.g + distanceFunction(myNeighbours[i], mypathEnd);
                        // remember this new path for testing above
                        Open.push(myPath);
                        // mark this node in the world graph as visited
                        AStar[myPath.value] = true;
                    }
                }
                // remember this route as having no more untested options
                Closed.push(myNode);
            }
        } // keep iterating until the Open list is empty
        return result;
    }

    // actually calculate the a-star path!
    // this returns an array of coordinates
    // that is empty if no path is possible
    return calculatePath();

} // end of findPath() function

然后通过

调用该函数

currentPath = findPath(world,pathStart,pathEnd);

但不工作。我的工作 pen

感谢任何帮助。

Answer 1

这是一个简单的路径查找脚本，可以从这里开始。

一旦计算出路径，沿着它移动汽车应该是微不足道的。

该脚本有两个阶段:

1. 世界一代

扫描 map 中障碍物和怪物的位置

路径生成

发现怪物并计算路径的地方。

//HTML elements
var canvas = document.body.appendChild(document.createElement("canvas"));
canvas.height = 500;
canvas.width = canvas.height;
var ctx = canvas.getContext("2d");
//Logic elements
var tileSize = 16;
var monster = {
  x: Math.floor(Math.random() * Math.ceil(canvas.width / tileSize) / 2) * 2,
  y: Math.floor(Math.random() * Math.ceil(canvas.height / tileSize) / 2) * 2
};
var player = {
  x: 9,
  y: 9
};
var aStar = {
  path: [],
  opened: [],
  closed: [],
  done: false
};
//Simple distance formular
function distance(a, b) {
  return Math.sqrt(Math.pow(a.x - b.x, 2) + Math.pow(a.y - b.y, 2));
}

function draw() {
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  //Tested Tiles
  ctx.fillStyle = "cyan";
  for (var pi = 0; pi < aStar.closed.length; pi++) {
    var p = aStar.closed[pi];
    ctx.fillRect(p.x * tileSize, p.y * tileSize, tileSize, tileSize);
  }
  //Path
  ctx.fillStyle = "blue";
  for (var pi = 0; pi < aStar.path.length; pi++) {
    var p = aStar.path[pi];
    ctx.fillRect(p.x * tileSize, p.y * tileSize, tileSize, tileSize);
  }
  //Monster
  ctx.fillStyle = "red";
  ctx.fillRect(monster.x * tileSize, monster.y * tileSize, tileSize, tileSize);
  //Player
  ctx.fillStyle = "green";
  ctx.fillRect(player.x * tileSize, player.y * tileSize, tileSize, tileSize);
  //Tiles
  for (var x = 0; x < Math.ceil(canvas.width / tileSize); x++) {
    for (var y = 0; y < Math.ceil(canvas.height / tileSize); y++) {
      ctx.strokeRect(x * tileSize, y * tileSize, tileSize, tileSize);
    }
  }
}

function main() {
  //If no steps, open "player"
  if (aStar.opened.length == 0) {
    aStar.opened.push({
      x: player.x,
      y: player.y,
      step: 0
    });
  }
  //Check for monster
  if ((aStar.opened.some(function(c) {
      return c.x === monster.x && c.y === monster.y;
    })) == true) {
    //if monster found
    if (aStar.path.length < 1) {
      //If no steps in path, add monster as first
      aStar.path.push(aStar.opened.find(function(c) {
        return c.x === monster.x && c.y === monster.y;
      }));
    } else if ((aStar.path.length > 0 ? aStar.path[aStar.path.length - 1].step == 0 : false) === false) {
      //If last step of path isn't player, compute a step to path
      var lastTile = aStar.path[aStar.path.length - 1];
      var bestTile = {
        x: lastTile.x,
        y: lastTile.y,
        step: lastTile.step
      };
      //Loop through tiles adjacent to the last path tile and pick the "best"
      for (var x = lastTile.x - 1; x < lastTile.x + 2; x++) {
        for (var y = lastTile.y - 1; y < lastTile.y + 2; y++) {
          var suspect = aStar.closed.find(function(c) {
            return c.x === x && c.y === y;
          });
          if (suspect !== void 0) {
            if (suspect.step + distance(suspect, player) < bestTile.step + distance(bestTile, player)) {
              bestTile = suspect;
            }
          }
        }
      }
      //Add best tile to path
      aStar.path.push(bestTile);
    }
  } else {
    //If monster isn't found, continue world mapping
    //"newOpen" will hold the next "opened" list
    var newOpen = [];
    //For each opened, check neighbours
    for (var oi = 0; oi < aStar.opened.length; oi++) {
      var o = aStar.opened[oi];
      for (var x = o.x - 1; x < o.x + 2; x++) {
        for (var y = o.y - 1; y < o.y + 2; y++) {
          if (x === o.x && y === o.y ||
            aStar.closed.some(function(c) {
              return c.x === x && c.y === y;
            }) ||
            aStar.opened.some(function(c) {
              return c.x === x && c.y === y;
            }) ||
            newOpen.some(function(c) {
              return c.x === x && c.y === y;
            })) {
            continue;
          }
          //If neighbours isn't in any list, add it to the newOpen list
          newOpen.push({
            x: x,
            y: y,
            step: o.step + 1
          });
        }
      }
    }
    //Close the previously opened list
    aStar.closed = aStar.closed.concat(aStar.opened);
    //Add new opened list
    aStar.opened = newOpen;
  }
  //Draw progress
  draw();
  requestAnimationFrame(main);
}
//Start process
requestAnimationFrame(main);

编辑1 - 没有寻路

我什至不确定您是否需要为此进行寻路。

在下面的示例中，汽车只是根据其与目标的 Angular 被推向目标:

var __extends = (this && this.__extends) || (function() {
  var extendStatics = Object.setPrototypeOf ||
    ({
        __proto__: []
      }
      instanceof Array && function(d, b) {
        d.__proto__ = b;
      }) ||
    function(d, b) {
      for (var p in b)
        if (b.hasOwnProperty(p)) d[p] = b[p];
    };
  return function(d, b) {
    extendStatics(d, b);

    function __() {
      this.constructor = d;
    }
    d.prototype = b === null ? Object.create(b) : (__.prototype = b.prototype, new __());
  };
})();
var Game;
(function(Game) {
  var GameImage = (function() {
    function GameImage(name, src) {
      this.name = name;
      this.src = src;
      this.node = document.createElement("img");
      GameImage._pending++;
      this.node.onload = GameImage._loading;
      this.node.src = this.src;
      GameImage.all.push(this);
    }
    GameImage.loaded = function() {
      return this._loaded === this._pending;
    };
    GameImage._loading = function() {
      this._loaded++;
    };
    GameImage.getImage = function(id) {
      return this.all.find(function(img) {
        return img.name === id;
      });
    };
    return GameImage;
  }());
  GameImage.all = [];
  GameImage._loaded = 0;
  GameImage._pending = 0;
  new GameImage("background", "http://res.cloudinary.com/dfhppjli0/image/upload/c_scale,w_2048/v1492045665/road_dwsmux.png");
  new GameImage("hero", "http://res.cloudinary.com/dfhppjli0/image/upload/c_scale,w_32/v1491958999/car_p1k2hw.png");
  new GameImage("monster", "http://res.cloudinary.com/dfhppjli0/image/upload/v1491958478/monster_rsm0po.png");
  new GameImage("hero_other", "http://res.cloudinary.com/dfhppjli0/image/upload/v1492579967/car_03_ilt08o.png");

  function distance(a, b) {
    return Math.sqrt(Math.pow(a.x - b.x, 2) + Math.pow(a.y - b.y, 2));
  }

  function degreeToRadian(degrees) {
    return degrees * (Math.PI / 180);
  }

  function radianToDegree(radians) {
    return radians * (180 / Math.PI);
  }

  function angleBetweenTwoPoints(p1, p2) {
    return Math.atan2(p2.y - p1.y, p2.x - p1.x) * 180 / Math.PI;
  }
  var Actor = (function() {
    function Actor() {
      this.angle = 0;
    }
    Actor.prototype.main = function() {};
    Actor.prototype.render = function(ctx) {
      if (this.angle != 0) {
        var rads = degreeToRadian(this.angle - 90);
        ctx.translate(this.position.x + 0.5 * this.image.node.naturalWidth, this.position.y + 0.5 * this.image.node.naturalHeight);
        ctx.rotate(rads);
        ctx.drawImage(this.image.node, 0, 0);
        ctx.rotate(-rads);
        ctx.translate(-(this.position.x + 0.5 * this.image.node.naturalWidth), -(this.position.y + 0.5 * this.image.node.naturalHeight));
      } else {
        ctx.drawImage(this.image.node, this.position.x, this.position.y);
      }
    };
    return Actor;
  }());
  var Monster = (function(_super) {
    __extends(Monster, _super);

    function Monster(position) {
      var _this = _super.call(this) || this;
      _this.position = position;
      _this.image = GameImage.getImage("monster");
      Monster.all.push(_this);
      return _this;
    }
    return Monster;
  }(Actor));
  Monster.all = [];
  var Car = (function(_super) {
    __extends(Car, _super);

    function Car(position, target) {
      if (target === void 0) {
        target = null;
      }
      var _this = _super.call(this) || this;
      _this.position = position;
      _this.target = target;
      _this.hitCount = 0;
      _this.image = GameImage.getImage("hero");
      _this.speed = 10;
      Car.all.push(_this);
      return _this;
    }
    Car.prototype.main = function() {
      var angle = angleBetweenTwoPoints(this.target.position, this.position);
      var cos = Math.cos(degreeToRadian(angle)) * -1;
      var sin = Math.sin(degreeToRadian(angle));
      this.angle = angle;
      this.position.x += cos * this.speed;
      this.position.y -= sin * this.speed;
      if (distance(this.position, this.target.position) < 10) {
        this.target.position.x = Math.random() * mainCanvas.width;
        this.target.position.y = Math.random() * mainCanvas.height;
        this.hitCount++;
        console.log("Hit!");
      }
    };
    return Car;
  }(Actor));
  Car.all = [];
  var background = GameImage.getImage("background");
  var mainCanvas = document.body.appendChild(document.createElement("canvas"));
  mainCanvas.width = background.node.naturalWidth;
  mainCanvas.height = background.node.naturalHeight;
  var ctx = mainCanvas.getContext("2d");
  var monster1 = new Monster({
    x: Math.random() * mainCanvas.width,
    y: Math.random() * mainCanvas.height
  });
  var monster2 = new Monster({
    x: Math.random() * mainCanvas.width,
    y: Math.random() * mainCanvas.height
  });
  new Car({
    x: Math.random() * mainCanvas.width,
    y: Math.random() * mainCanvas.height
  }, monster1);
  new Car({
    x: Math.random() * mainCanvas.width,
    y: Math.random() * mainCanvas.height
  }, monster2);

  function main() {
    ctx.drawImage(background.node, 0, 0);
    for (var ci = 0; ci < Car.all.length; ci++) {
      var c = Car.all[ci];
      c.main();
      c.render(ctx);
    }
    for (var mi = 0; mi < Monster.all.length; mi++) {
      var m = Monster.all[mi];
      m.main();
      m.render(ctx);
    }
    requestAnimationFrame(main);
  }
  requestAnimationFrame(main);
})(Game || (Game = {}));

只要没有障碍物，就可以正常工作。