Delphi Graphics and Game Programming Exposed! with DirectX For versions 5.0-7.0:Artificial Intelligence Techniques                       Search Tips   Advanced Search        Title Author Publisher ISBN    Please Select ----------- Artificial Intel Business & Mgmt Components Content Mgmt Certification Databases Enterprise Mgmt Fun/Games Groupware Hardware IBM Redbooks Intranet Dev Middleware Multimedia Networks OS Productivity Apps Programming Langs Security Soft Engineering UI Web Services Webmaster Y2K ----------- New Arrivals









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.