A* and Pathfollowing Steering Behavior

Posted by: rocketman on November 10, 2010

In the last three posts, we explored the how A* works, then we put A-star into code, then we looked at different heuristics for A*. Now we will combine A* pathfinding with the path following steering behavior.

We have already done most of the work to do this. But we'll do a quick review in case you missed those posts.

A* Pathfinding


In A* we take a grid of cells and find a path from start to finish. Each cell has an x,y for location, a parent for creating the path, and F, G, and H values for calculating the cost of the path. A* searches the grid, excluding cells that are blocked and finds the optimal path to the finish. When it is done, it creates an array containing the cells for the path. For more information on A*, you can learn the basics here, how to put it into code here, and different heuristics to calculate cost here.

Path Following Steering Behavior


The path following steering behavior takes an array of Vector2D's and seeks them in order. It calculates the distance between the vehicle and the next location. If it is within 10 pixels, it considers that "on" the goal and moves on to seeking the next one.

This creates one minor problem. A* returns an array of cells, but the path following steering behavior expects an array of Vector2Ds. To make them work together, we need to make one small change. After we get A-star's path, we need to run this function:

public function convertToVector2D(path:Array):Array {
  for(var i:int = 0; i < path.length; i++){
    path[i] = new Vector2D(path[i].x,path[i].y);
  }
  return path;
}

This will convert the path from cells to Vector2Ds. Now we can create a Vehicle and have it follow the path.

var vehicle:Vehicle = new Vehicle();
addChild(vehicle);
//in an update function (possibly enterFrame)
//where path is the converted array.
vehicle.followPath(path);
vehicle.update();

That's it Using the ideas we used in previous posts, we were able to get a vehicle to follow a path found by A*. Click here to see it in action. It's the same A* finder as before, but with a vehicle follow path button to create a vehicle that will follow the path.

Current rating: 5


Comments

  • Breakdance McFunkypants 3 years, 10 months ago

    I've been avidly following all your posts since the beginning of the steering behaviours and am blown away by this implementation: a fantastic mashup of a-star and your car movement code. Would love to see a full as3 source code .zip so we don't have to copy code from numerous posts to get it working. I would also love to see an a-star class that is NOT mixed with any drawing functionality so it could be used in games more easily.
    Keep up the amazing work - I really appreciate your coding skills and have learned a lot. Thank you!

    Link / Reply
  • rocketman 3 years, 10 months ago

    Sure, I'll get a .zip of the source ready for tomorrow as well as a pure A* source.

    Link / Reply
  • katopz 3 years, 10 months ago

    //slow\r\nfor(var i:int = 0; i &lt; path.length; i++)\r\n//faster\r\nvar path_length:int = path.length;\r\nfor(var i:int = 0; i &lt; path_length; i++)\r\n\r\n//slow\r\npath[i] = new Vector2D(path[i].x,path[i].y);\r\n//faster\r\npath[int(i)] = new Vector2D(path[int(i)].x,path[int(i)].y);\r\n\r\nand even faster if you use Vector. fix length\r\n\r\nfyi just in case you seeking for speed :)\r\nnice article btw, thx for sharing! :D\r\n\r\nbtw, put it in googlecode would be (alot) better for tracking change and let ppl patch each line :)

    Link / Reply
  • Trent Sterling 3 years, 10 months ago

    Wow, all these steering behavior and path-finding posts are great! I have a much better understanding of how these things work now!

    Link / Reply
  • Ewag 3 years, 1 month ago

    I know this is a long time after the fact, but I'm looking for help if you come upon this comment. I'm an Actionscript amateur but I've got an idea for a game and I was hoping to use this tutorial to understand pathfinding a little better. Unfortunately, through my fumbling around with the source, I've been unable to recreate the example shown at the end of this tutorial where a vehicle travels the route. How exactly does one set up their .fla in order to get that working? Currently, I've got a black screen and calling the createGrid function doesn't seem to do anything.

    Link / Reply

New Comment

required
required (not published)
optional
  • Back in July, we looked at how to use Ray Casting for collision detection. We also learned how to use the Separation of Axis Theorem. I recently had a request for a way to use the Shapes we created here with the Ray Casting method.¬†First, lets do a quick review of the shape classes. read more
    3 years, 7 months ago
  • Today we will finally be detecting a collision with SAT. We know how SAT works, we've built classes to work with SAT, now we can use all of this to detect a real, live collision! read more
    3 years, 10 months ago
  • A few months ago, I posted on the separation of axis theorem. You can learn all about SAT and how it works here. What that post failed to do was use the SAT. We will explore using SAT for collision detection in this post. read more
    3 years, 10 months ago
  • Some of you have asked for the entire steering behavior source as well as the A* source. Here is the zip with all the classes. In there is the vehicle... read more
    3 years, 10 months ago
  • In the last three posts, we explored the how A* works, then we put A-star into code, then we looked at different heuristics for A*. Now we will combine A*... read more
    3 years, 10 months ago
RSS / Atom