Map building - Tower Defense

Question

Before diving too deep into my question, let it be known that I am learning as far as java script goes and figured a simple Tower Defense game would be an excellent way to learn things.

So I have found a simple background image with a path drawn on it and my question is how would I go about building a path so that I can animate my objects. Would I have to take the image and overlay a grid system, or can I store the path in some sort of array and have my objects move across it?

Here is the background image:

Answer 1

There's a few options you have, since your question is fairly high level, I'll provide these high level suggestions:

1. Create a grid in code, and overlay the image on it
2. Using the color of your path, assign the grid spaces that match "path color" as walkable.
3. Use A* to find a path from start to finish.

There's some tweaking you can do with this one, altering the grid size to make for finer details, and using some kind of marker on the map to ensure the grid is aligned properly.

Another option:

1. Convert the map into tiles
2. Create a tiled map using the tiles you created above
3. Ensure the tiles used for making the path are "walkable"

This method will one of the most time intensive, but has the result of providing you with the most consistent verifiable results. You can also use the tiles you've created to automatically produce variations of the same map, altering your path to take different directions.

Answer 2

I think the most flexible way is to handle an array of segments that describes the path, and to move onto each segment depending on time elapsed and item speed.
The accuracy is ok as long as you take short segments.

Since it's not that hard to handle, we'll just go for an array of 2n points where index 2*p is the x of the pth point and 2*p+1 is its y.
Then, on each update of the game, a given time elapsed : this time multiplied by the speed will give you the distance you need to travel within the segments ( d = v * t ).
You go forward (or backward) a given distance by 'eating' each segment one after another. If you cannot eat up all of a segment, just eat a part of it (a ratio).

I made i fiddle for this, it works quite well : http://jsfiddle.net/xTf9P/1/

// PathFollower : Class describing an object that will
//   follow a path depending on its speed. 
//   It will 'bounce' if it encounters a path border.
//   use draw() to draw and move(dt) to make it move. (dt in ms)
//       path is an array [x0,y0, x1,y1, x2,y2, ...]
//       pathLength[i] = length of the ith segment.
function PathFollower(speed, path, pathLength, color) {
    this.x = 0;
    this.y = 0;
    this.speed = speed ;
    this.path  = path  ;
    this.pathLength = pathLength;
    this.color = color ;
    this.pathIndex = 0 ; 
    this.ratio     = 0 ;  // ratio of position within current segment.
  }

PathFollower.prototype = {
   draw : function() {
       var width = 14 + 2*Math.sin(Date.now()/200);
       ctx.strokeStyle = this.color;
       ctx.strokeRect(this.x - width, this.y-width, 
                                      2*width, 2* width);
   },
   move : function(dt) {
    // distance to travel
    var distance = Math.abs( dt * this.speed );    
    // speed sign
    var sign     = (this.speed > 0) ? 2 : -2 ;
    var segLength=0, remainingSegLength=0;
    while (distance >0) {
            // current segment length
            segLength = this.pathLength[this.pathIndex >> 1];
            // remaining segment length : depends on speed sign
            if (sign >0) {
                       if (this.ratio == 0)  remainingSegLength=segLength;
                       else remainingSegLength = (1-this.ratio) * segLength;
            } else {
                       if (this.ratio == 1) remainingSegLength=segLength;
                       else remainingSegLength = this.ratio * segLength;
            }

            if (remainingSegLength < distance) {
                 // if this segment cannot eat up the distance, skip to next.
                 distance -= remainingSegLength; // eat
                 this.ratio = (sign >0) ? 0 : 1; // new ratio within segment
                 // loop if encounter the end of the path
                 if ( (sign<0 && this.pathIndex == 0) ||
                      (sign>0 && this.pathIndex == this.path.length-4))  {
                        this.speed = -this.speed; 
                        this.ratio= (this.speed >0) ? 0 : 1;
                       break;
                    }
                  // iterate
                  this.pathIndex +=sign;       
                } else {
                   // let us eat as much of this segment as we can.
                   var ratio = distance / segLength ;
                   this.ratio += (sign>0) ? ratio : -ratio;
                   break;
                }    
          }
  // compute new (x, y)
  this.x = this.path[this.pathIndex] + 
       this.ratio *(this.path[this.pathIndex+2] - this.path[this.pathIndex]) ;
  this.y = this.path[this.pathIndex+1] + 
       this.ratio *(this.path[this.pathIndex+3] - this.path[this.pathIndex+1]);

  }
}

Obviously, you'll want your monster not to follow the exact same path : handle a constant offset or a distance to the curve for each of them to show separately.

(the fiddle for the very code above is here : http://jsfiddle.net/JYYmA/3/)

Answer 3

Since the other answers are more grid based, I thought I'd offer a path solution.

Disclaimer: I usually implement grids in my own games, and it'd be useful for when you have the user place tiles.

Anyways, what I'd do is first draw the path you want on the canvas. This can be done using something like the below code (taken from here)

context.beginPath();          // Begin your path
context.moveTo(100, 150);     // Move the starting cursor to 100, 150
context.lineTo(450, 0);       // Maps out 450 in the x dir
context.lineTo(0, 50);        // Maps out 50 in the y dir
// Repeat the above two lines to add more connected segments)
// Negative numbers go down or to the left
context.stroke();             // Actually draws the line

Once you figure out the right path, you can figure out a step by step traversal of it. So for example if you want to animate the path, we can take the 450 in the right direction and break it down over time, so depending on what speed you want your object to move, you can move it 5px every 20ms or something.

So far this solution has been completely hardcoded, making it pretty bad. It does help to get an understanding though and acts sort of like psuedocode for figuring out how to do it automatically.

Since we'd want out code to work on multiple levels, what you could do is create a level file, which you can place the commands for walking the route. The first line of the file could be the background that corresponds to the path. Then it's easy enough to parse the file taking in the background and then the path your object can go!

EDIT: I sort of forgot to answer the question. The way I'd store the path, would be however you find it most convenient.

One way would be to parse the level file, taking each command and storing it into a position/movement object that has an x and a y that you place into an array.

Example:

Move x 250
Move y 50
Move x 50
Move y -50
Move x 100

Would turn into

[(250,0), (0,50), (50, 0), (0,-50), (100,0)]

Then when you read your array, you can take the x and the y of the first index and put them into xMov and yMov (since you just use perpendicular paths you only have something stored in x or y at a time).

After every movement you subtract however far you went in that update from either xMove or yMov. Once you reach 0 in both, you read the next index of the array and store it in xMov and yMov again. Repeat until it finishes and your object is off the screen. Note you will need an xMov, yMov, and index variable for each object, so if you have more than one make sure you're using the correct one.

Essentially this looks overly complicated and maybe like nonsense, but it's really not too hard to implement. You could do the same exact thing as a grid since essentially we're using the pixels as a grid here.