• Concave Polygon Working

    Separation of Axis Theorem (SAT) for Collision Detection

    The Separation of Axis Theorem(SAT) is a technique to test whether two convex polygons are colliding. The SAT theorem: "given two convex shapes, there exists a line onto which their projections will be separate if and only if they are not intersecting." The line where the shapes have disjoint projections is called the separating axis. A separating line is the line that can be drawn between the two shapes,...

  • Using the Separation of Axis Theorem

    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...
  • The Diagonal Shortcut produces this path.

    A* Heuristics

    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 Method 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...
  • AStarFinal

    Putting A* into Code

    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: [as3] package com.rocketmandevelopment.grid.cells { import flash.display.Graphics; public class Cell { public var f:Number = 0; public var g:Number = 0; public var...
  • AStar

    A* Pathfinding Basics

    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...
  • Alignment

    Steering Behaviors: Flocking

    The next post steering behaviors series is unaligned collision avoidance. We will be using the Vector2D.as and Vehicle.as classes for this. You will need these classes for the this post. This post is based on Craig Reynold’s article Steering Behaviors For Autonomous Characters. Flocking is created by combining several steering behaviors: Separation, Cohesion and Alignment. ...

  • Detecting Collisions with SAT

    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...

Posts tagged 2D

Steering Behaviors: Seeking

Jun 11th

Posted by rocketman in AI

1 comment

This entry is part of 9 in the series Steering Behaviors

Steering behaviors are used to create intelligent movements on a computer. These posts will be an AS3 version of the principles illustrated in Craig Reynolds’ article located at http://www.red3d.com/cwr/steer/gdc99/.

Before we can start using steering behaviors, we need a few classes. First we will be using, yet again, the Vector2D.as class. Steering behaviors rely on vector math, so you should be familiar with it.

If you need more information on vector mathematics, you can look here:

https://users.cs.jmu.edu/bernstdh/web/common/lectures/slides_vector-math-2d.php

http://en.wikipedia.org/wiki/Vector_%28mathematics%29

Next we will need a vehicle class to hold all the vehicle’s properties. The properties each vehicle will More >

, , , , ,

SAT in Action

May 22nd

Posted by rocketman in AS3

2 comments

In a previous post, I explained the Separation of Axis Theorem. Now it’s time to see SAT in action.

Click on a shape to move it. It both will turn red when they are touching. The shapes will turn black again when they are not colliding. Use the drop down lists to change the shapes.

Click here to see SAT in action!

, , , , , , ,
Concave Polygon Working

Separation of Axis Theorem (SAT) for Collision Detection

May 19th

Posted by rocketman in AS3

21 comments

The separating line and axis form a 90 degree angle.

The Separation of Axis Theorem(SAT) is a technique to test whether two convex polygons are colliding. The SAT theorem: “given two convex shapes, there exists a line onto which their projections will be separate if and only if they are not intersecting.” The line where the shapes have disjoint projections is called the separating axis.

A separating line is the line that can be drawn between the two shapes, without touching either shape. Because flash is 2D, I will only be showing this method for 2D, but it can be done in 3D(in 3D, More >

, , , , , ,
«123