Pathfinding

Pathfinding is of course a very popular mechanism used in many games. Developers very often use it in controlling enemies or opponents. Gorilla3D provides an easy to use component based on AStar algorithm. The TGorillaPathfindingAStar component helps you manage those automated movements. It abstracts your 3D world and obstacles into a 2D-Plane to compute a path from a starting point to a destination.

You can update obstacles at runtime and recompute the map to simulate a dynamic environment.

Each pathfinder is working on a single so called agent, which is the object to be moved on computed path.

uses
  Gorilla.Utils.Pathfinding, Gorilla.Utils.Pathfinding.AStar;
 
FPathFinder := TGorillaPathfindingAStar.Create(nil);
 
// apply the agent used as source (any TControl3D)
FPathFinder.Agent := FAgent;

Obstacles are restricted areas on the pathfinding map, where an agent can't walk onto, so the algorithm will find a way around this obstacle. You can add static or dynamic obstacles to the system. Obstacles can be all TControl3D instances. The pathfinder will use the bounding box to compute restricted areas. So there may be differences to the visual feedback of the object.

// add a dynamic obstacle - needs update
FPathFinder.AddObstacle(FObstacle1, false); 
 
// add a static obstacle
FPathFinder.AddObstacle(FObstacle2);

When adding an obstacle to the pathfinder you can define a margin. Those margins are useful if space between to obstacles is very tight. To prevent the agent to run into a narrow area, where it looks like he won't fit.

FPathFinder.ObstacleMargin := TPoint3D.Create(1, 1, 1);

const
  PATHFINDING_GRID_X   = 128;
  PATHFINDING_GRID_Z   = 128;
  PATHFINDING_3DSIZE_X = 20;
  PATHFINDING_3DSIZE_Z = 20;
 
var LGridSize : TPoint;
    LSize3D : TPointF;
 
[...]
 
// set dimensions of grid and used 3D space
LGridSize := TPoint.Create(PATHFINDING_GRID_X, PATHFINDING_GRID_Z);
FPathFinder.GridDimensions := LGridSize;
 
LSize3D := TPointF.Create(PATHFINDING_3DSIZE_X, PATHFINDING_3DSIZE_Z);
FPathFinder.Size3D := LSize3D;

The TGorillaPathfindingAStar component is just a logical instance. No movement will be performed by default.

FPath : TGorillaPath3D;
 
[...]
 
// compute a path around all obstacles in given area
FPathFinder.FindPath(Point3D(-10, 0, 10));
 
FPath := FPathFinder.ToNewPath3D(FGorilla);
FPath.Parent := FGorilla;

To move the agent we need a TGorillaPath3DAnimation component and connect both instances.

FPathAnim := TGorillaPath3DAnimation.Create(FAgent);
 
// the path animation need to manipulate position of the agent
FPathAnim.Parent := FAgent;
 
// it should take 5 seconds and move straight on the computed path
FPathAnim.Duration := 5;
FPathAnim.SplineType := TGorillaSpline3DType.Linear;
 
// here we need to apply the computed path data
FPathAnim.Path := FPath.Path;
 
// make sure the agent is at same position as the pathfinder computed from
FAgent.Position.Point := FPathFinder.StartPosition;
 
// start movemten on path
FPathAnim.Enabled := true;
FPathAnim.Start();

In case you want to update the map and path at runtime, you can use the following code snippet.

// new computation of path
FPathFinder.FindPath(Point3D(5, 0, 15));
 
// refresh map in our image
FPathFinder.Draw(FVerifyBmp);
Image1.Bitmap.Assign(FVerifyBmp);
 
// stop the current animation
FPathAnim.Stop();
FPathAnim.Enabled := false;
 
// apply computed path data to our existing TGorillaPath3D instance, instead for recreating each time
FPathFinder.ApplyToPath3D(FPath);
 
// reset the used path data in our path animation
FPathAnim.Path := FPath.Path;

LGridSize : TPoint;
FVerifyBmp : TBitmap;
 
[...]
 
// create a bitmap - to show map and path in a tiny image
// we use the adjusted grid size which includes agent width
LGridSize := FPathFinder.AdjustedGridSize;
FVerifyBmp := TBitmap.Create(LGridSize.X, LGridSize.Y);
 
// an image component, we've placed inside of our TGorillaViewport
Image1.Width  := LGridSize.X * 4;
Image1.Position.X := Form1.Width - Image1.Width - 32;
Image1.Height := LGridSize.Y * 4;
 
// draw pathfinder map
FPathFinder.Draw(FVerifyBmp);
// apply computed image to our visual feedback image in the viewport
Image1.Bitmap.Assign(FVerifyBmp);

Many developers may struggle with the question how to combine the setup above with user interaction.

Speaking for a classic Point & Click Adventure, a recommend way is to add a simple plane (TPlane, TGorillaPlane) for click detection.

All other 3D elements should be set to HitTest = false, to not disturb mouse interaction with the helper plane.

We then register a MouseUp event on the viewport, where we put all of our mouse handling.

var 
  FDestPoint : TPoint3D;
 
procedure TForm1.GorillaViewport1MouseUp(Sender: TObject; Button: TMouseButton;
  Shift: TShiftState; X, Y: Single);
var LRayPos,
    LRayDir : TPoint3D;
    LHitPos,
    LNormal,
    LScreenPos : TPoint3D;
begin
  // 1) Get 3D position of click, by converting screen coordinates into 3D coordinates
  LScreenPos := GorillaViewport1.ScreenToWorld(PointF(X, Y));
 
  // 2) Cast a ray from camera to the clicking position, to retrieve the real
  //    3D destination coordinate
  LRayPos := GorillaCamera1.AbsolutePosition;
  LRayDir := (LScreenPos - LRayPos).Normalize();
  if GorillaPlane1.RayCastIntersect(LRayPos, LRayDir, LHitPos, LNormal) then
  begin
    // If raycasting was successfully - we can start store the point hit by the ray
    FDestPoint := LHitPos;
    FDestPoint.Y := 0;
 
    // Aftwards we start pathfinding
    UpdatePathfinding();
  end;
end;
 
procedure TForm1.UpdatePathfinding();
var LAgentPos : TPoint3D;
begin
  // Get the agent position (pathfinding moving object)
  LAgentPos := GorillaModel1.AbsolutePosition;
 
  // Compute the path from 3D position - this will generate our new walking path
  FPathFinder.FindPath(LAgentPos, FDestPoint);
 
  // Stop the current animation
  FPathAnim.Stop();
  FPathAnim.Enabled := false;
 
  // Apply computed path data to our existing TGorillaPath3D instance, instead for recreating each time
  FPathFinder.ApplyToPath3D(FPath);
 
  // Reset the used path data in our path animation
  FPathAnim.Duration := FPath.Path.GetLength;
  FPathAnim.Path := FPath.Path;
 
  // For correct rotation of our character, we need the polygon to detect the
  // next node to adjust to - 
  // NOTICE: READ THE SECTION BELOW
  FPath.Path.FlattenToPolygon(FPolygon);
 
  // Restart movement on path
  FPathAnim.Enabled := true;
  FPathAnim.Start();
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
[...]
 
  // Register callback events
  FPathAnim.OnProcess  := DoOnPathAnimProcess;
  FPathAnim.OnFinish   := DoOnPathAnimFinished;
 
  // For correct rotation of our character, we need the polygon to detect the
  // next node to adjust to
  // NOTICE: If the path changes, this has to be called again!
  FPath.Path.FlattenToPolygon(FPolygon);
end;
 
procedure TForm1.DoOnPathAnimProcess(ASender : TObject);
 
  function GetKeyValues(APolygon : TGorillaPolygon3D; const T : Single;
  out P1, P2 : TPoint3D) : Single;
  var LDeltaPos : Single;
      LSglEnt : Integer;
  begin
    if System.Length(APolygon) <= 0 then
    begin
      P1 := TPoint3D.Zero;
      P2 := TPoint3D.Zero;
      Exit;
    end;
 
    // get current key position
    LDeltaPos := T * High(APolygon);
    // key value
    LSglEnt := Floor(LDeltaPos);
    // key offset
    Result := LDeltaPos - LSglEnt;
 
    // key coordinate
    if (LSglEnt <= High(APolygon)) then
      P1 := APolygon[LSglEnt]
    else
      P1 := APolygon[High(APolygon)];
 
    inc(LSglEnt);
    if (LSglEnt <= High(APolygon)) then
      P2 := APolygon[LSglEnt]
    else
      P2 := APolygon[High(APolygon)];
  end;
 
var dx, dz  : Single;
    LAngleY : Single;
    P1, P2  : TPoint3D;
begin
  // Get the currently relevant point to compute rotation
  GetKeyValues(FPolygon, FPathAnim.NormalizedTime, P1, P2);
 
  dx := P2.X - P1.X;
  dz := P1.Z - P2.Z;
  LAngleY := arctan2(dx, dz);
 
  GorillaModel1.RotationAngle.Y := RadToDeg(LAngleY);
  GorillaModel1.AnimationManager.PlayAnimation('run-forward.dae');
end;
 
procedure TForm1.DoOnPathAnimFinished(ASender : TObject);
begin
  GorillaModel1.AnimationManager.PlayAnimation('idle.dae');
end;

Next: Render Pass