Roy Triesscheijn’s Weblog

And another snippet for today. I wanted to test some more path finding code so I wanted to move a collidable object with the mouse. To do so you have to ‘unproject’ your mouse coordinates (x and y) to a position in 3D space (x,y,z). I first tried to use the unproject method directly. But after reading the msdn article I figured out that the z-values can be either 0 (near clip plane) or something else (far clip plane). So this didn’t give me good results if I just plugged in the z level I wanted.

After reading on about rays and intersect methods, user ConkerJo on #XNA pointed out that intersect returns a point of intersection instead of true or false. So with that knowledge, and a little help from him and msdn, I quickly produced the following code.

This code will convert your mouse position to a point laying on the ground plane.

Remember that the definition of your ground plane is a normal. So if you want the x-z space to be the floor (eg. y is up), assign it like this:

private Plane GroundPlane = new Plane(0, 1, 0, 0);  //creates a plane on the x-z axises.

And if you use another common approach, where z is up and the ground is on x-y use this:

private Plane GroundPlane = new Plane(0, 0, 1, 0); //creates a plane on the x-y axises.

And now here’s the actual snippet:

/// <summary>
        /// Calculates where the mouse would be if it would float around at the level of the ground plane.
        /// Based on http://msdn.microsoft.com/en-us/library/bb203905.aspx and user conkerjo who
        /// pointed out that Ray.Intereset returns a vector3 and not a boolean (true/false) *DOH*.
        /// </summary>
        /// <returns></returns>
        private Vector3 CalculateMouse3DPosition()
        {
            int mouseX = Mouse.GetState().X;
            int mouseY = Mouse.GetState().Y;

            Vector3 nearsource = new Vector3((float)mouseX, (float)mouseY, 0f);
            Vector3 farsource = new Vector3((float)mouseX, (float)mouseY, 1f);

            Matrix world = Matrix.CreateTranslation(0, 0, 0);

            Vector3 nearPoint = device.Viewport.Unproject(nearsource,
                camera.ProjectionMatrix, camera.ViewMatrix , Matrix.Identity);

            Vector3 farPoint = device.Viewport.Unproject(farsource,
                camera.ProjectionMatrix, camera.ViewMatrix, Matrix.Identity);

            Vector3 direction = farPoint - nearPoint;
            direction.Normalize();
            Ray pickRay = new Ray(nearPoint, direction);
            float? position = pickRay.Intersects(GroundPlane);

            if (position.HasValue)
            {
                return pickRay.Position + pickRay.Direction * position.Value;
            }
            else
            {
                return target.Position;
            }
        }

Today I converted my “Swarm Like collision avoidance, path finding and smooth following”- project (what a mouth full) to work with 3D coordinates, if you understood the code, you would know this wasn’t much of a problem. Anyway I did it for you today . (original article here).

public static void Attract(GameTime gameTime, Object3D ship, Object3D[] obstacles, Object3D target)
        {
            float pullDistance = Vector3.Distance(target.Position, ship.Position);

            //Only do something if we are not already there
            if (pullDistance > ((ship.Radius + target.Radius) * 1.5f))
            {
                Vector3 pull = (target.Position - ship.Position) * (1 / pullDistance); //the target tries to 'pull us in'
                Vector3 totalPush = Vector3.Zero;

                int contenders = 0;
                for (int i = 0; i < obstacles.Length; ++i)
                {

                    //draw a vector from the obstacle to the ship, that 'pushes the ship away'
                    Vector3 push = ship.Position - obstacles[i].Position;

                    //calculate how much we are pushed away from this obstacle, the closer, the more push
                    float distance = (Vector3.Distance(ship.Position, obstacles[i].Position) - obstacles[i].Radius) - ship.Radius;
                    //only use push force if this object is close enough such that an effect is needed
                    if (distance < ship.Radius * 3)
                    {
                        ++contenders; //count that this object is actively pushing

                        if (distance < 0.0001f) //prevent division by zero errors and extreme pushes
                        {
                            distance = 0.0001f;
                        }
                        float weight = 1 / distance;
                        totalPush += push * weight;
                    }
                }

                pull *= Math.Max(1, 4 * contenders); //4 * contenders gives the pull enough force to pull stuff trough (tweak this setting for your game!)
                pull += totalPush;

                //Normalize the vector so that we get a vector that points in a certain direction, which we van multiply by our desired speed
                pull.Normalize();
                //Set the ships new position;
                ship.Position += (pull * ship.Speed) * (float)gameTime.ElapsedGameTime.TotalSeconds;
            }
        }

Intro

There are many different algorithms for finding paths, for avoiding collision and for smoothly following a path.  A normal approach in game would be the following:

• Use a path finding algorithm like A* to construct a path.
  • (see my tutorial here: http://roy-t.nl/index.php/2009/07/07/new-version-a-pathfinding-in-3d/ )

• Construct an algorithm that follows the path exact enough not to collide with the predetermined ‘not empty tiles’ but loose enough so that it looks natural.
  • (In XNA you could use the curve class to help: http://msdn.microsoft.com/en-us/library/microsoft.xna.framework.curve.aspx )

• Construct an algorithm that detects objects that are on our path and calculates new routes around them.
  • (Maybe some ‘look ahead’ and A* again, question: do you calculate from the
    obstruction to the finish, or to the next free tile, or both?)

Although this looks like a lot of work, most of these algorithms are freely available, how to implement them is well know, and most of these algorithms are reasonably fast.  So for a little bit of work we get a solid, well known, always working, pretty fast algorithm that in a pretty constant world finds nice paths.

Problem

For my current project I’m trying to emulate a galaxy (no small taskJ) ships move from planet to planet, but these planets are not static, they are moving in ellipses around a sun. Calculating the paths ships have to take would be troublesome, because paths close the planets would constantly change, and even more important, once we get to the finish line the planet already moved a bit further. We could update our path every x-amount of time, but this would give our pour CPU too much to do, and would give us a strange and jerky path.

Solution

After a bit of whining on #XNA (see the links section) someone (I wish I remembered who, so I could give credit where it’s due) suggested taking a look at swarming algorithms. (Here computer models try to simulate how swarms of birds or fish interact with each other so that they don’t collide and keep following their leaders). Although I didn’t directly see a connection, I was interested in how these models kept birds from colliding with each other. Apparently when a bird ‘senses’ that another bird comes too close it tries to move in a direction so that the minimum space between them is restored, however it also tries to keep follow his targets, the result is a new direction vector  where the evasion and the following are calculated and weighted in. When a collision is imminent the weight of the evasion grows and when there is no danger at all the weight of evasion drops.

Another way to look at it is like a set of magnets. The bird is a little iron ball, the obstacles are negatively charged and try to push the ball away, while the finish is positively charged and tries to reel the ball in. Can you see it in your head now?

After I realized this it was pretty simple to create some code that produced the following video:

And now with moving obstacles:

As you can see the path is fairly smooth, nothing is hit, and we reach our end goal. All I had to do was write these 50 lines of code (including comments and white space)

 //Simple class that represents 2D objects
public class Object2D
{
    public Vector2 Position;
    public float Radius;
    public Color Color;
    public float MetersPerSecond;
}

        //All we need is this static method, here generically called update.
        public static void Update(GameTime gameTime, Object2D ship, Object2D[] obstacles, Object2D target)
        {
            float pullDistance = Vector2.Distance(target.Position, ship.Position);

            //Only do something if we are not already there
            if (pullDistance > 1)
            {
                Vector2 pull = (target.Position - ship.Position) * (1 /  pullDistance); //the target tries to 'pull us in'
                Vector2 totalPush = Vector2.Zero;

                int contenders = 0;
                for (int i = 0; i < obstacles.Length; ++i)
                {

                    //draw a vector from the obstacle to the ship, that 'pushes the ship away'
                    Vector2 push = ship.Position - obstacles[i].Position;

                    //calculate how much we are pushed away from this obstacle, the closer, the more push
                    float distance = (Vector2.Distance(ship.Position, obstacles[i].Position) - obstacles[i].Radius) - ship.Radius ;
                    //only use push force if this object is close enough such that an effect is needed
                    if (distance < ship.Radius * 3)
                    {
                        ++contenders; //note that this object is actively pushing

                        if (distance < 0.0001f) //prevent division by zero errors and extreme pushes
                        {
                            distance = 0.0001f;
                        }
                        float weight = 1 / distance;

                        totalPush += push * weight;
                    }
                }

                pull *= Math.Max(1, 4 * contenders); //4 * contenders gives the pull enough force to pull stuff trough (tweak this setting for your game!)
                pull += totalPush;

                //Normalize the vector so that we get a vector that points in a certain direction, which we van multiply by our desired speed
                pull.Normalize();
                //Set the ships new position;
                ship.Position += (pull * ship.MetersPerSecond) * (float)gameTime.ElapsedGameTime.TotalSeconds;
            }
        }

As you can see that is very little and simple code for path finding, collision avoidance and smooth following. However there are some drawbacks.

Take a note

Of course there is a good reason why not everyone is using this. The path finding is not optimal (with many objects the path is not always the shortest), there is a chance to get stuck if the finish is hard to reach and this code would fail horribly in mazes. However in space there are not many objects to avoid, it’s hard to get stuck and the paths might not be optimal, but after dodging a planet or two we can go to our target in a pretty much straight line. Other scenarios where it might be interesting to try this out is in racing game AI’s (where the target is for example a dot moving across the ideal line, a meter ahead of the car) where I think this would make a very interesting algorithm. (Of course you need a braking algorithm as well, maybe adjust throttle/braking on the change in direction compared to the current speed?)  Another genre might be surfing games, strategy games with little obstacles, or other ‘stupid’ AIs, like a pet AI for cute pets like in world of warcraft.

Conclusion

We made a simple and fun algorithm with much potential, when used wisely this algorithm can make your games code a lot easier. Take note of the drawbacks though, A* is not perfect in all situations (else we would’ve used A*) and this algorithm should only be used when it is appropriate. (If you have trouble deciding this please post a comment, I’ll try to help out, however sometimes it’s just a matter of experimenting).

Oh btw, after some browsing I found some fun alikeness  with steering behavior, although that does work a bit differently the same concept lays at the basics. You can find out more about steering behavior here: http://www.red3d.com/cwr/steer/

Today I came acros a great article on Game State Management on FocusedGames.com, you can find it here.

It explains a topic I always seem to have troubles with, and it tells you how to get rid of those nasty Enumarations (or worse: ints) that tell you in which state you are.

I beleive a whole series of articles on ATS (advanced state systems) is comming up, so be sure to keep an eye on FocusedGames.com