Search Tips Advanced Search |
| Delphi Graphics and Game Programming Exposed with DirectX 7.0 by John Ayres Wordware Publishing, Inc. ISBN: 1556226373 Pub Date: 12/01/99
Search this book:
Previous | Table of Contents | Next
We’ll continue this process until we encounter an obstacle. Even though the next eastward node would be closest to the destination, it is an impassible obstacle and cannot be selected. Therefore, we need to select one of the other two nodes that are closest to the destination and are not blocked. In this example, either of these nodes will work just fine, so we’ll pick one at random. Figure 12–7: Moving past an obstacle Notice that we have now changed directions from east to northeast, which affects which nodes we’ll examine on the next pass. Specifically, the next nodes we will examine will now be north, northeast, and east of the current node. Figure 12–8: Examining nodes in a new direction Once again, we’ll see that the eastward node is the closest to the goal. This entire process continues until the goal is finally reached. Figure 12–9: A path from start to finish #### Back Stepping This basic algorithm will get us there in simple game worlds, but what about situations where we run into larger obstacles, such as the one below. Figure 12–10: A large wall As we can see here, all three examined nodes are blocked, and thus the path cannot proceed any further. This is where the array that tracks which nodes have been visited comes in. We need to delete the current node we are on from our list of path nodes, and back up to the previous node. When we reexamine the next closest nodes, we’ll treat the node we just visited as an impassible obstacle. This keeps us from choosing a node that we know will not work.
| Note: When we back up to a previous node, we also need to reset our direction to the direction we were facing in this previous node.
Figure 12–11: Backing up and reexamining nodes Continuing with this process, we see that our algorithm finds a relatively direct path to the destination. Figure 12–12: Pathing around a large wall Backing up and reexamining nodes in the previous direction really boosts this algorithm’s intelligence. Indeed, while our implementation of this algorithm isn’t totally infallible, it is pretty smart, and can get us around some fairly complex obstacles as illustrated below. Figure 12–13: Navigating a complex game world #### Case Study Unlike most examples throughout this book, the path finding example is implemented using standard Delphi controls for the visual feedback. This was done to highlight the path finding algorithm and to make it easier to examine the algorithm at run time. You can’t really set breakpoints and step through code once DirectDraw has exclusive access and has set the video mode to full screen. Implementing an A* path finding algorithm using standard Delphi controls allows you to step through it line by line to examine what’s happening as it runs. This will also make it easier to improve the algorithm’s performance and accuracy if you wish to play with it. In the output from this test application, the blue square is the origin, the red square is the destination, black squares indicate impassible obstacles, and purple squares indicate the final path. Green squares indicate nodes that were visited but did not belong on the final path. The following listing demonstrates a simple, straightforward implementation of the A* algorithm. Listing 12–6: The A* test bed
    interface

       .

       .

       .

      {defines the directions}

      TCompassDirection = (cdNorth, cdNorthEast, cdEast, cdSouthEast, cdSouth,

                           cdSouthWest, cdWest, cdNorthWest);

      {this defines node offsets relative to the current node for

       a particular direction}

      TDirectionOffset = array[TCompassDirection] of TPoint;

      {our node record, recording its coordinates and compass direction}

      TNode = record

        Direction: TCompassDirection;

        GridPt: TPoint;

      end;

      PNode = ^TNode;

      procedure ClearPathQueue;

    var

      frmPathFinder: TfrmPathFinder;

      {tracks the origin and destination}

      StartPt, EndPt: TPoint;

      SetStart: Boolean;

      {tracks the list of nodes on the final path}

      PathQueue: TList;

      {defines the game world. nodes defined as 0 are clear,

       1 are obstacles}

      MapGrid: array[0..14, 0..14] of Byte;

      {tracks which nodes we’ve already visited}

      VisitedNodes: array[0..14, 0..14] of Boolean;

    const

      {this defines the actual node offsets at a specific direction

       relative to the current node}

      DirectionOffset: TDirectionOffset = ((X: 0; Y: –1),

                                           (X: 1; Y: –1),

                                           (X: 1; Y: 0),

                                           (X: 1; Y: 1),

                                           (X: 0; Y: 1),

                                           (X: –1; Y: 1),

                                           (X: –1; Y: 0),

                                           (X: –1; Y: –1) );

      {define each of our node types}

      NODECLEAR     = ‘’;

      NODEOBSTACLE  = ‘1’;

      NODESTART     = ‘2’;

      NODEEND       = ‘3’;

      NODEPATH      = ‘4’;

      NODEVISITED   = ‘5’;

    implementation

    procedure TfrmPathFinder.FormCreate(Sender: TObject);

    begin

      {initialize the starting and ending node}

      StartPt := Point(–1, –1);

      EndPt := Point(–1, –1);

      {indicate that the left mouse button sets the start node by default}

      SetStart := TRUE;

      {create our list of path nodes}

      PathQueue := TList.Create;

    end;

    procedure TfrmPathFinder.FormDestroy(Sender: TObject);

    begin

      {free all existing nodes, and then free the path list}

      ClearPathQueue;

      PathQueue.Free;

    end;

    procedure ClearPathQueue;

    var

      iCount: Integer;

    begin

      {free each node in the list}

      for iCount := 0 to PathQueue.Count–1 do

        FreeMem(PathQueue[iCount], SizeOf(TNode));

      {empty the list}

      PathQueue.Clear;

    end;

    procedure TfrmPathFinder.grdPathMouseDown(Sender: TObject; Button: TMouseButton;

      Shift: TShiftState; X, Y: Integer);

    var

      GrdRow, GrdCol: Integer;

    begin

      {map the mouse cursor coordinates to grid cell coordinates}

      grdPath.MouseToCell(X, Y, GrdCol, GrdRow);

      {if the right mouse button was pressed...}

      if Button = mbRight then

      begin

        {...set or clear an obstacle node}

        if grdPath.Cells[GrdCol, GrdRow] = NODEOBSTACLE then

          grdPath.Cells[GrdCol, GrdRow] := NODECLEAR

        else

          grdPath.Cells[GrdCol, GrdRow] := NODEOBSTACLE;

      end

      else

      {...otherwise, we’re setting a starting or ending node}

      if SetStart then

      begin

        {if a start node has already been placed, clear the previous node}

        if StartPt.X <> –1 then

          grdPath.Cells[StartPt.X, StartPt.Y] := NODECLEAR;

        {set the new start node}

        grdPath.Cells[GrdCol, GrdRow] := NODESTART;

        StartPt := Point(GrdCol, GrdRow);

      end

      else

      begin

        {if an end node has already been placed, clear the previous node}

        if EndPt.X <> –1 then

          grdPath.Cells[EndPt.X, EndPt.Y] := NODECLEAR;

        {set the new end node}

        grdPath.Cells[GrdCol, GrdRow] := NODEEND;

        EndPt := Point(GrdCol, GrdRow);

      end;

    end;

    procedure TfrmPathFinder.grdPathDrawCell(Sender: TObject; ACol, ARow: Integer;

      Rect: TRect; State: TGridDrawState);

    begin

      {most squares should be colored white}

      grdPath.Canvas.Brush.Color := clWhite;

      {determine the color of the square based on its type}

      if grdPath.Cells[ACol, ARow] = NODEOBSTACLE then

        grdPath.Canvas.Brush.Color := clBlack;

      if grdPath.Cells[ACol, ARow] = NODESTART then

        grdPath.Canvas.Brush.Color := clBlue;

      if grdPath.Cells[ACol, ARow] = NODEEND then

        grdPath.Canvas.Brush.Color := clRed;

      if grdPath.Cells[ACol, ARow] = NODEPATH then

        grdPath.Canvas.Brush.Color := clPurple;

      if grdPath.Cells[ACol, ARow] = NODEVISITED then

        grdPath.Canvas.Brush.Color := clGreen;

      {fill this square with the appropriate color}

      grdPath.Canvas.FillRect(Rect);

    end;

    procedure TfrmPathFinder.shpStartPointMouseDown(Sender: TObject;

           Button: TMouseButton;

      Shift: TShiftState; X, Y: Integer);

    begin

      {indicate we are setting a start node}

      SetStart := TRUE;

    end;

    procedure TfrmPathFinder.shpDestPointMouseDown(Sender: TObject;

    	       Button: TMouseButton;

      Shift: TShiftState; X, Y: Integer);

    begin

      {indicate we are setting an end node}

      SetStart := FALSE;

    end;

    procedure TfrmPathFinder.btnClearMapClick(Sender: TObject);

    var

      iCount, iCount2: Integer;

    begin

      {clear out the map}

      for iCount := 0 to 14 do

        for iCount2 := 0 to 14 do

          grdPath.Cells[iCount, iCount2] := ‘’;

    end;

    procedure TfrmPathFinder.btnFindPathClick(Sender: TObject);

    var

      iCount, iCount2: Integer;

      CurPt, EvalPt, NewPt: TPoint;

      TempNode: PNode;

      Dist, EvalDist: Longword;

      Dir, NewDir: TCompassDirection;

      SearchDirs: array[0..2] of TCompassDirection;

    begin

      {don’t do anything until a starting and ending point have been set}

      if (StartPt.X = –1) or (EndPt.X = –1) then

        Exit;

      {clear out the visited nodes array}

      FillChar(VisitedNodes, SizeOf(VisitedNodes), 0);

      {populate the map grid with the specified impassible tiles}

      for iCount := 0 to 14 do

        for iCount2 := 0 to 14 do

          if grdPath.Cells[iCount, iCount2] = NODEOBSTACLE then

            MapGrid[iCount, iCount2] := 1

          else

            MapGrid[iCount, iCount2] := 0;

      {delete the current path}

      ClearPathQueue;

      {initialize the tracking variables}

      CurPt := StartPt;

      VisitedNodes[CurPt.X, CurPt.Y] := TRUE;

      {determine the initial direction}

      {destination left of origin}

      if EndPt.X < StartPt.X then

      begin

        if EndPt.Y > StartPt.Y then

          Dir := cdSouthWest

        else

        if EndPt.Y < StartPt.Y then

          Dir := cdNorthWest

        else

          Dir := cdWest;

      end

      else

      {destination right of origin}

      if EndPt.X > StartPt.X then

      begin

        if EndPt.Y > StartPt.Y then

          Dir := cdSouthEast

        else

        if EndPt.Y < StartPt.Y then

          Dir := cdNorthEast

        else

          Dir := cdEast;

      end

      else

      {destination directly above or below origin}

      if EndPt.Y > StartPt.Y then

        Dir := cdSouth

      else

        Dir := cdNorth;

      {create a node object}

      GetMem(TempNode, SizeOf(TNode));

      {initialize the node object with our current (starting) node information}

      TempNode^.Direction := Dir;

      TempNode^.GridPt.X := CurPt.X;

      TempNode^.GridPt.Y := CurPt.Y;

      {add this starting node to the path list}

      PathQueue.Add(TempNode);

      {begin searching the path until we reach the destination node}

      while (CurPt.X <> EndPt.X) or (CurPt.Y <> EndPt.Y) do

      begin

        {reset the new coordinates to indicate nothing has been found}

        NewPt := Point(–1, –1);

        {reset our distance to the largest value available (new nodes should

         be well under this distance to the destination)}

        Dist := $FFFFFFFF;

        {determine the 3 search directions}

        SearchDirs[0] := Pred(Dir);

        if Ord(SearchDirs[0]) < Ord(cdNorth) then

          SearchDirs[0] := cdNorthWest;

        SearchDirs[1] := Dir;

        SearchDirs[2] := Succ(Dir);

        if Ord(SearchDirs[2]) > Ord(cdNorthWest) then

          SearchDirs[2] := cdNorth;

        {evaluate grid locations in 3 directions}

        for iCount := 0 to 2 do

        begin

          {get the coordinates of the next node to examine relative to the

           current node, based on the direction we are facing }

          EvalPt.X := CurPt.X + DirectionOffset[SearchDirs[iCount]].X;

          EvalPt.Y := CurPt.Y + DirectionOffset[SearchDirs[iCount]].Y;

          {make sure this node is on the map}

          if (EvalPt.X > –1) and (EvalPt.X < 15) and

             (EvalPt.Y > –1) and (EvalPt.Y < 15) then

            {make sure we’ve never visited this node}

            if not VisitedNodes[EvalPt.X, EvalPt.Y] then

              {make sure this isn’t an impassible node}

              if MapGrid[EvalPt.X, EvalPt.Y] = 0 then

              begin

                {this is a clear node that we could move to. calculate

                 the distance from this node to the destination.

                 NOTE: since we’re interested in just relative distances as

                 opposed to exact distances, we don’t need to perform a square

                 root. this will dramatically speed up this calculation}

                EvalDist := ((EndPt.X – EvalPt.X)*(EndPt.X – EvalPt.X)) +

                            ((EndPt.Y – EvalPt.Y)*(EndPt.Y – EvalPt.Y));

                {if we have found a node closer to the destination, make this

                 the current node}

                if EvalDist < Dist then

                begin

                  {record the new distance and node}

                  Dist := EvalDist;

                  NewPt := EvalPt;

                  {record the direction of this new node}

                  NewDir := SearchDirs[iCount];

                end

              end;

        end;

        {at this point, if NewPt is still (–1, –1), we’ve run into a wall and

         cannot move any further. thus, we have to back up one and try again.

         otherwise, we can add this new node to our list of nodes}

        {we’ve got a valid node}

        if NewPt.X <> –1 then

        begin

          {make this new node our current node}

          CurPt := NewPt;

          {point us in the direction of this new node}

          Dir := NewDir;

          {mark this node as visited}

          VisitedNodes[CurPt.X, CurPt.Y] := TRUE;

          {create a node object}

          GetMem(TempNode, SizeOf(TNode));

          {initialize this node object with the new node information}

          TempNode^.Direction := Dir;

          TempNode^.GridPt.X := CurPt.X;

          TempNode^.GridPt.Y := CurPt.Y;

          {put this new node in the path list}

          PathQueue.Add(TempNode);

          {if we’ve recorded 50 nodes, break out of this loop}

          if PathQueue.Count > 50 then

            Break;

        end

        else

        begin

          {we’ve backed up to the point where we can no longer back up. thus, a

           path could not be found. we could improve this algorithm by

           recalculating the starting direction and trying again until we’ve

           searched in all possible directions}

          if PathQueue.Count = 1 then

            Break;

          {point us in the direction of the previous node}

          Dir := TNode(PathQueue[PathQueue.Count–2]^).Direction;

          {retrieve the coordinates of the previous node and make that

           our current node}

          CurPt := Point(TNode(PathQueue[PathQueue.Count–2]^).GridPt.X,

                         TNode(PathQueue[PathQueue.Count–2]^).GridPt.Y);

          {free the last node in the list and delete it}

          FreeMem(PathQueue[PathQueue.Count–1], SizeOf(TNode));

          PathQueue.Delete(PathQueue.Count–1);

        end;

      end;

      {at this point, we’ve found a path from the starting node to the destination

       node, so we should populate the grid and allow it to display the final path}

      {specify visited nodes}

      for iCount := 0 to 14 do

        for iCount2 := 0 to 14 do

          if VisitedNodes[iCount, iCount2] then

            grdPath.Cells[iCount, iCount2] := NODEVISITED;

      {specify nodes on the path}

      for iCount := 0 to PathQueue.Count–1 do

      begin

        grdPath.Cells[TNode(PathQueue[iCount]^).GridPt.X,

                      TNode(PathQueue[iCount]^).GridPt.Y] := NODEPATH;

      end;

      {specify the starting and ending nodes}

      grdPath.Cells[StartPt.X, StartPt.Y] := NODESTART;

      grdPath.Cells[EndPt.X, EndPt.Y] := NODEEND;

    end;
Figure 12–14: The A* algorithm in action
Previous | Table of Contents | Next

Products | Contact Us | About Us | Privacy | Ad Info | Home Use of this site is subject to certain Terms & Conditions, Copyright © 1996-2000 EarthWeb Inc. All rights reserved. Reproduction whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Read EarthWeb's privacy statement.