Movement and pathfinding I
Movement on the map
Our sprite
Before we consider issues of movement, first let's consider our object. Our sprite object has quite a lot of fields and methods, as it has to perform many functions, but for our purpose, we're interested in the following :
obj.orientation;
obj.x;
obj.y;
obj.cellx;
obj.celly;
obj.dest;
obj.walk = null;
obj.orientation describes the orientation of the sprite, whether it faces up, down, left or right. This is just decided by an enum of the form var DIR = {down: 0, left: 1, right: 2, up: 3};.
Straight movements
If there is no obstacle, the simplest way to implement movement is to move the sprite in a straight line to the destination. The separation between the original position $(x_1, y_1)$ and the destination $(x_2, y_2)$ is just
\begin{equation} \vec{\Delta} = (x_2 - x_1, y_2 - y_1) \end{equation} If we have a speed of $n$ pixels per frame, the movement will then be \begin{equation} \vec{d} = \frac{\vec{\Delta}}{|\vec{\Delta}|} n \end{equation}which is just the unit vector of the direction times the speed per frame. Up to rounding, this is pretty much what we'll use for an algorithm :
function moveStraight(sprite, end)
{
if(obj.dest.x != obj.x || obj.dest.y != obj.y)
{
var delta = {x: obj.dest.x - obj.x, y: obj.dest.y - obj.y};
var norm = Math.sqrt(delta.x * delta.x + delta.y * delta.y);
if(norm > speed)
{
delta.x *= speed/norm;
delta.y *= speed/norm;
obj.x += delta.x;
obj.y += delta.y;
obj.setAnimation("walk", obj.orientWalk(obj.delta));
}
else
{
obj.setAnimation("idle", obj.orientWalk(obj.delta));
}
}
}
If our sprite is not currently at its destination, we will first get our vector $\vec{\Delta}$ and get its norm $\| \vec{\Delta} \|$. If this distance is greater than the distance that it can travel in the current tick, it will simply change its position according to its speed and the direction. Otherwise, as to not overshoot it, it will simply set its position as the destination.
If the topology is different than the plane, the formulas vary somewhat. The main other topology used in game being the torus, where the edges of the map are identified, so that trying to go below the lower edge will bring the sprite to the upper edge, and likewise for the left and right edge. To do this, we'll need to simply check both directions to see which is shortest.
Those methods are not really pathfinding, except in the trivial case where the topology is this trivial and there are absolutely no obstacles, but this is nevertheless useful for such things as projectiles or particularly dim enemies.
Not quite the pathfinding yet, but as an intermediate step, it can also be useful to do the same type of movement as before, except this time sticking to the grid we have defined. To do this, we'll simply have the sprite move in the direction closest to the vector $\Delta$. Things will differ slightly for 4 and 8 possible directions in our case.
First, we need to define some functions related to the grid, as so far it has moved freely without much concern for the grid.
function moveStraight(sprite, end)
{
}
Pathfinding
If the map isn't free of obstacles, or otherwise has a somewhat complicated topologically (as far as the abstract graph structure of the map is concerned, this is equivalent), there will be no general formula to determine the shortest path (or even any path) between any two points, or the formula might be prohibitively large to hold in memory. In this case, almost every method commonly used rests on the same principle of graph traversal.
If our sprite can only move on discrete cells on the map, as opposed to continuous points, then each cell can be represented as the node of a graph, and the way from going from one cell to another is represented by an edge. We're also usually dealing with weighted edges, since we need something to represent the notion of the distance or time spent travelling between two nodes. Depending on what the map represents, the graph can have oriented edges or not : a door can make movement possible only in one direction, a conveyor belt can make the speed different depending on the direction. But for now, let's consider a very simple case : our map is a simple grid, $[0 \ldots N] \times [0 \ldots M]$, and every obstacle on the map is represented by its node being deleted, along with every edge connected to that node.
The map
We need to define some more specific structures for the map now. The simplest and most flexible way is to just consider the map as some matrix of cells, so that we can define whatever properties we want for each cells. For now we'll just consider a modifier to our speed. That is, if our sprite is on a cell with a modifier $\alpha$, its speed will be $v = v_0 \times \alpha$. This can double as a way to define obstacles if we consider that a cell with $\alpha = 0$ is an obstacle. Our map is then just a matrix of cells that, alongside the information necessary .
The path
Before seeing specific algorithms, first we need to implement how they will be dealt with. Instead of computing the path at every movement, we'll need to get a queue of adjoining cells. This is basically the same method we saw previously, except the next cell we select is determined by the queue from the pathfinding and not by the general direction.
The Dijkstra algorithm
Assuming none of the edges have a negative cost, the Dijkstra algorithm is guaranteed to find the shortest path, simply by trying out every path in order of length. The downside here is fairly obvious, as this is quite possibly the most expensive algorithm in terms of complexity, being of the order of $\mathcal{O}(|V|^2)$, for $V$ the set of nodes. On top of that, taking the precise shortest path may not look the most natural sort of movement, depending on what we are aiming for.
The basic idea of the algorithm is fairly simple. First, consider some set of nodes $A$, originally containing our original node $s$. Look at every edge connected to it (those are the edges starting from $s$, if the edges are oriented), and out of these, select the one with the smallest weight (the shortest distance or travel time). If this node is the destination we're looking for, everything is fine and we've arrived, and this is indeed the shortest path, as the weights are all positive. Otherwise, we put this node in $A$ and start again, considering every edge going from node in $A$ to nodes not in $A$, selecting the
The Greedy-First algorithm
On the other end of the scale, the greedy-first algorithm will simply traverse the graph by considering what seems locally like the best way. The simplest way to do this is to select preferentially the cells closest to the destination, using the raw distance between the two points. This is obviously much more efficient if there are no (or very simple) obstacles, reducing in many cases to only visiting the cells that will actually be used.
The A* algorithm
Last updated : 2019-12-04 10:50:41