Finding furthermost point in game world

Posted by user13414 on Game Development See other posts from Game Development or by user13414
Published on 2012-03-28T15:38:54Z Indexed on 2012/03/28 17:46 UTC
Read the original article Hit count: 245

Filed under:
|
|
|

I am attempting to find the furthermost point in my game world given the player's current location and a normalized direction vector in screen space. My current algorithm is:

  1. convert player world location to screen space
  2. multiply the direction vector by a large number (2000) and add it to the player's screen location to get the distant screen location
  3. convert the distant screen location to world space
  4. create a line running from the player's world location to the distant world location
  5. loop over the bounding "walls" (of which there are always 4) of my game world
    1. check whether the wall and the line intersect
      1. if so, where they intersect is the furthermost point of my game world in the direction of the vector

Here it is, more or less, in code:

public Vector2 GetFurthermostWorldPoint(Vector2 directionVector)
{
    var screenLocation = entity.WorldPointToScreen(entity.Location);
    var distantScreenLocation = screenLocation + (directionVector * 2000);
    var distantWorldLocation = entity.ScreenPointToWorld(distantScreenLocation);
    var line = new Line(entity.Center, distantWorldLocation);
    float intersectionDistance;
    Vector2 intersectionPoint;

    foreach (var boundingWall in entity.Level.BoundingWalls)
    {
        if (boundingWall.Intersects(line, out intersectionDistance, out intersectionPoint))
        {
            return intersectionPoint;            
        }
    }

    Debug.Assert(false, "No intersection found!");
    return Vector2.Zero;
}

Now this works, for some definition of "works". I've found that the further out my distant screen location is, the less chance it has of working. When digging into the reasons why, I noticed that calls to Viewport.Unproject could result in wildly varying return values for points that are "far away". I wrote this stupid little "test" to try and understand what was going on:

[Fact]
public void wtf()
{
    var screenPositions = new Vector2[]
        {
            new Vector2(400, 240),
            new Vector2(400, -2000),
        };

    var viewport = new Viewport(0, 0, 800, 480);
    var projectionMatrix = Matrix.CreatePerspectiveFieldOfView(MathHelper.PiOver4, viewport.Width / viewport.Height, 1, 200000);
    var viewMatrix = Matrix.CreateLookAt(new Vector3(400, 630, 600), new Vector3(400, 345, 0), new Vector3(0, 0, 1));
    var worldMatrix = Matrix.Identity;

    foreach (var screenPosition in screenPositions)
    {
        var nearPoint = viewport.Unproject(new Vector3(screenPosition, 0), projectionMatrix, viewMatrix, worldMatrix);
        var farPoint = viewport.Unproject(new Vector3(screenPosition, 1), projectionMatrix, viewMatrix, worldMatrix);

        Console.WriteLine("For screen position {0}:", screenPosition);
        Console.WriteLine("   Projected Near Point = {0}", nearPoint.TruncateZ());
        Console.WriteLine("   Projected Far Point = {0}", farPoint.TruncateZ());
        Console.WriteLine();
    }
}

The output I get on the console is:

  For screen position {X:400 Y:240}:
     Projected Near Point = {X:400 Y:629.571 Z:599.0967}
     Projected Far Point = {X:392.9302 Y:-83074.98 Z:-175627.9}

  For screen position {X:400 Y:-2000}:
     Projected Near Point = {X:400 Y:626.079 Z:600.7554}
     Projected Far Point = {X:390.2068 Y:-767438.6 Z:148564.2}

My question is really twofold:

  1. what am I doing wrong with the unprojection such that it varies so wildly and, thus, does not allow me to determine the corresponding world point for my distant screen point?
  2. is there a better way altogether to determine the furthermost point in world space given a current world space location, and a directional vector in screen space?

© Game Development or respective owner

Related posts about XNA

Related posts about c#