Vehicle

As I wrote the previous post, this week I'll be writing about AI agents. It is a cool subject and I am eager to see what the final results will be. Now, AI might be a strong word for the dumb behavior that this vehicle displays but all the underlying math is there and should provide a basis for development of a more sophisticated system. To make thing more interesting I have decided to implement everything in Silverlight so that can be available in a browser and to test drive the technology while I am at it. Lets see the final result, and than go through the process.



I have used the Vehicles as a title, generally because it's the title of a vary inspirational book by Valentino Braitenberg, that touches the subject of autonomus agents as a early as 1984 and I can recomend it to anyone even remotely interested in the subject. It's just 17$ on Amazon. While this book gives more than enough philosophical background, most of the engeenering is based on the Steering Behaviors by Craig W. Reynolds. Steering behaviors are just simple rules that give steering directions to the vehicles. By smart use and combination of these rules we can build complex behaviors that mimic the behavior a bird or sheep in a flock. Some pepole like Craig W. Reynolds have been working on steering behaviors since the 80's, making them more experinced on the subject than I am in waking, so I will not give a watered down explanation, rather just refer to their pages. What I will give is a some C# code. Now why C# and Silverlight? I have been a long time Flash user for small demos like this one. But having a real programing language like C# is just too good not to try and I am not a huge fan of scripting languages, like Action Script. Plus the tools are completely free. For this post I will implement only the most basic behavoirs seek and flee. Bacause I would like to use it in a Silverlight aplication I will create a Silverlight Library project in Visual Studio. This will be our AI library and should not be aware of any drawing code, so that it can be used in a difirent project, say an XNA game. Now, the first thing that stroke me was that the System.Windows.Vector was just not available on my computer and of course I have the latest SDK. Now instead of wasting couple of days I decided to write my own implementation of a 2D Vector. I think I have done one in every language I have come across. And then a Matrix class implementation to do some transformations over the vectors (I assume knowledge basic linear algebra). With all that in place we can make a simple vehicle class which simply takes the output from the steering behavior and apply is as a force. The update method of the vehicle class looks something like this:

virtual Update(float dt)
{
   Vector2 steeringForce = steering.Calculate();
   //Acceleration = Force/Mass
   Vector2 acceleration = steeringForce / mass;
   velocity += acceleration * dt;
   velocity.Truncate(maxSpeed);
   position += velocity * dt;
   if (velocity.LengthSq > 0.00000001)
   {
      heading = Vector2.Normalize(velocity);
      //
      side = heading.Perp;
   }
   position.WrapAround(400, 400);
}

The Seek and Flee methods are extremely simple as you can see:

Vector2 Seek(Vector2 targetPos)
{
   if ((targetPos - vehicle.Position).LengthSq > threshold)
   {
      Vector2 desiredVelocity = Vector2.Normalize(targetPos - vehicle.Position) * vehicle.MaxSpeed;
      return desiredVelocity - vehicle.Velocity;
   }
   return new Vector2(0.0f);
}

private Vector2 Flee(Vector2 targetPos)
{
   if ((vehicle.Position - targetPos).LengthSq < panicDistanceSq && (vehicle.Position - targetPos).LengthSq > 0.1f)
   {
       Vector2 desiredVelocity = Vector2.Normalize(vehicle.Position - targetPos) * vehicle.MaxSpeed;
      return desiredVelocity - vehicle.Velocity;
   }
   return newVector2(0.0f);
}

In the Calculate method we just average the force from both, like so:

Vector2 Calculate()
{
return (Seek(target1) + Flee(target2)) * 0.8f;
}

Now I want to use that in the Silverlight application, and one of the coolest features in Silverlight, the MatrixTransform class enabling us to apply some affine transformations fast. Anyone who has done some graphics programming will appreciate this. All we need to do is take the heading vector from the vehicle, its perpendicular vector and the position of the vehicle and we have our transformation matrix:

transformMatrix.M11 = vehicle.Heading.x;
transformMatrix.M12 = vehicle.Heading.y;
transformMatrix.M21 = vehicle.Heading.Perp.x;
transformMatrix.M22 = vehicle.Heading.Perp.y;
transformMatrix.OffsetX = vehicle.Position.x;
transformMatrix.OffsetY = vehicle.Position.y;
transform.Matrix = transformMatrix;                // Makes sense ha?
shape.RenderTransform = transform;

Just be careful with the origin of the transformation. Expression Blend uses the center by default, while the API will use top left. You can download the code here.

Next week pizza! Just kidding, I’ll be adding obstacles.