Games & Apps that Challenge Minds
Archive for November, 2010
Detecting Collisions with SAT
Nov 28th
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!
Using the classes we created last time, this is quite simple. First create a shape:
var shape1:Polygon = Polygon.rectangle(530, 30, new Vector2D(270, 360));
It’s a simple polygon created using the static function of the rectangle class. Now we need another shape to collide with:
var shape2:Polygon = Polygon.rectangle(20, 50, new Vector2D(260, 350));
And now we need to test for a collision:
var data:CollisionData = Collision.testShapes(shape1, shape2);
When you run this, you should More >
Using the Separation of Axis Theorem
Nov 22nd
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.
In the post on SAT, we created the code to detect collisions, however use of the code was not covered. (A download of all the classes used in the post is available at the bottom).
The Shape ClassesThe easiest way to use SAT uses Shape classes. There are two shape classes we will need, the Circle and the More >
Steering Behaviors and A* Source
Nov 15th
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 class with all the code for the behaviors. For more information on each behavior, you can go here. The Vehicle class found in com.rocketmandevelopment.steering contains all the steering behaviors. The vehicle requires an update to be called to move as well as a behavior(s) to be called.
A-star was discussed in-depth here. The A* classes are in com.rocketmandevelopment.grid. There is the Grid class, the Cell class and the AStar class. They all More >
A* and Pathfollowing Steering Behavior
Nov 10th
Vehicle Following the Path
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* PathfindingIn 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 More >
A* Heuristics
Nov 9th
In the first post on A*, we explored the theory behind A*. Then we took A-star and put it into code. Now we will look at different heuristics for A* and how they affect the path.
The Manhattan MethodThe Manhattan Heuristic produces this path.
This is the heuristic function we used in our implementation of A*. The Manhattan method will get you to the end cell in the least steps, but it doesn’t always guarantee the shortest path. It will usually give the shortest path, but it if doesn’t, the chosen path won’t be too much longer. The Manhattan heuristic overvalues the cost More >
Putting A* into Code
Nov 8th
In yesterday’s post on the basics of A star, we explored the theory behind A*. Today we will take that theory and put it into code.
Because A-star uses a grid made up of cells, we need some classes to store that data. First the cell class:
package com.rocketmandevelopment.grid.cells {
import flash.display.Graphics;
public class Cell {
public var f:Number = 0;
public var g:Number = 0;
public var h:Number = 0;
public var isClosed:Boolean = false;
public var isOpen:Boolean = false;
public var isWalkable:Boolean = true;
These public variables are the key variables that a cell needs to have. The F, G, More >
A* Pathfinding Basics
Nov 7th
A* (A-star) is an algorithm used for pathfinding. Pathfinding is where a computer computes the shortest (or best) path from a start point to an end point through a grid or nodes.
We will be using a grid to find a path. The green cell is the start point and the red cell is the end point. The computer must find the shortest route from start to finish without going through the walls.
We are using a grid because it is a simple way to represent the concept behind A-Star. You can use this same algorithm to find a path through connected More >
