A* mouse movement javascript top-down game

Question

Im trying to implement a* path finding for my character movement in my game.

The game is written in javaScript along with jQuery in a canvas.

I have read up on A* so i believe i understand what it is and how it works.

My questions:

1) do you know of any a* tutorials specific to JavaScript and canvas? Just to get a bit more of an understanding so its concrete.

2) Once the a* is implemented, how would i get my player to move along that path to the destination? Obviously id use the player X,Y for the start pos and the mouse click for the end pos, but when the algorithm has completed the path, how would i proceed to make the player follow that path?

Thanks for any help and advice!

Answer 1

1) No I don't. Since canvas is relatively new I'm not sure you'll find one. This one is pretty good but you might have seen it already: http://www.policyalmanac.org/games/aStarTutorial.htm

2) Once the algorithm has worked out the path, you should have some kind of sorted array/list of tiles which take the player from their current position to the target tile.

Since you are probably working with a grid of squares equal size, you can easily work out the center x and y positions of each tile in the path. So, you make the player head towards each tile in the array in turn. When the distance between the player and the center of the target tile is small enough, move onto the next tile (next tile in path array).

Moving towards the center of the tiles is probably simplest, but depending on the game you might prefer finding the closest edge of each tile to get a "direct" route through. You need to read up on vectors if you haven't used them before.

Rough pseudo code-ish example:

i = 0;
while(i < path.length) {
  target = path[i]; // path is array of grid tiles created by algorithm
  targetx = target.col*tileWidth + (tileWidth / 2); // col = column of tile in grid (x)
  targety = target.row*tileHeight + (tileHeight / 2); // row = row of tile in grid (y)

  // TODO:
  // calculate distance from player to target
  // set heading vector

  if(distance < 2) // if near center of target tile, head to next tile in path
    i++;
}

Answer 2

I recently implemented a* in a game I'm working on in JavaScript, so I thought I'd try my best to answer your question. The path finding is functional in the Ludum Dare build and you can search for "findPath =" in the JavaScript file if you want to see my implementation, but it is custom for my game.

The basic idea of a* is that you have several possible positions that something can be in, each being connected to those near it, forming a web. In a lot of cases, this is a grid of some sort. a* is then able to find the shortest path from a starting position to a destination, if there is one, and try to do so quickly by guessing roughly how far a step will be from the destination using a heuristic before actually testing it. More possible positions will use up more memory and need more processing time. I could explain a* in more detail, but you're just as well off doing a search to learn more.

From how you have phrased your question, it sounds like you want to create a path using images that have been drawn to a Canvas (you can correct me if I'm wrong). Unless you are only drawing collision-useful images to the Canvas, this isn't a practical approach. You will likely want to be keeping track of player positions and collision information somewhere else. Path finding is not related to the way that you are displaying an image to a user, it's more about how you're storing collision and position data. A Canvas doesn't know anything about what you put on it aside from what everything looks like when it's done drawing.

Most a* implementations will give you a list containing steps. In the case of my game's implementation, it returns an array of grid indexes (y*width+x), in reverse order of when they should be traveled to. It's a fairly small tile-based game, so there aren't a lot of positions to check, and it skips checking empty or impassable tiles on the grid.

You can use this path to move your player character. Change its position to the next location in the path (if the distance between the points is long, you can always smooth it out a bit), wait a bit, then move it to the second location, and repeat. You should be redrawing the Canvas (or at least the parts that changed) whenever the player moves. Waiting can be done using a timeout or an interval, but rendering is generally best done using requestAnimationFrame because it waits until the user's monitor is ready to display the image.