PDA

View Full Version : Nearly A* Search Tutorial



cairnswm
21-02-2003, 09:25 AM
Nearly A* Search

For my game Fairy Fantasy I've required a path finding algorithm. I've spent quite a lot of time on www.gameai.com reading up on the A* algorithm. I finally got round to implementing the algorithm and found a whole lot of little things that either I didn't understand or I just couldn't do. So I scrapped everything I had done and started again from scratch. This tutorial will hopefully assist anyone else that needs pathfinding in their games to implement it more easily.

For this Tutorial I've decided to create a new application that shows what is happening rather than just code snippets that would possibly not be understood out of context. To show everything I've explained the application.

1. Create a new application
2. Add a Listbox (left aligned)
Sorted := True;
3. Add a StringGrid (Client Aligned)
ColCount := 50;
RowCount := 50;
DefaultColWidth := 24;
DefaultRowHeight := 24;
FixedCols := 0;
FixedRows := 0;
4. Add a PopupMenu (Linked from StringGrid)
5. Add the following menu options:
Start Point
End Point
Block
6. Define StartPointFunction


private
FStartPoint: TPoint;
procedure SetStartPoint(const Value: TPoint);
private
Property StartPoint : TPoint read FStartPoint write SetStartPoint;

procedure TForm1.SetStartPoint(const Value: TPoint);
begin
StringGrid1.Cells[FStartPoint.X, FStartPoint.Y] := '';
FStartPoint := Value;
// The Cell with A in it is the starting Point of the Search
StringGrid1.Cells[FStartPoint.X, FStartPoint.Y] := 'A';
end;

procedure TForm1.StartPoint1Click(Sender: TObject);
begin
StartPoint := Point(StringGrid1.Selection.Left,StringGrid1.Selec tion.Top);
end;


7. Define EndPoint Function


private
FEndPoint: TPoint;
procedure SetEndPoint(const Value: TPoint);
private
Property EndPoint : TPoint read FEndPoint write SetEndPoint;

procedure TForm1.SetEndPoint(const Value: TPoint);
begin
StringGrid1.Cells[FEndPoint.X, FEndPoint.Y] := '';
FEndPoint := Value;
// The Cell with Z in it is the goal Point of the Search
StringGrid1.Cells[FEndPoint.X, FEndPoint.Y] := 'Z';
end;

procedure TForm1.EndPoint1Click(Sender: TObject);
begin
EndPoint := Point(StringGrid1.Selection.Left,StringGrid1.Selec tion.Top);
end;


Quick note on properties: Properties for something like this are great! While they seem to add a lot of work they often actually decrease the amount of work - in the example above I've created properties to represent the start and end points of the search. When the value of one of these points is changed the grid is automatically updated to show the change - so wether the point is changed through a menu item or through the Form.OnCreate event the grid will always be up to date

8. Define the initial start and end points


procedure TForm1.FormCreate(Sender: TObject);
begin
StartPoint := Point(5,5);
EndPoint := Point(12,15);
end;


9. Define the block menu option


procedure TForm1.Block1Click(Sender: TObject);
Var
I, J : Integer;
begin
// X indicates unpassable
// Ensure Start and End Points are not overwritten
For I := StringGrid1.Selection.Left to StringGrid1.Selection.Right do
For J := StringGrid1.Selection.Top to StringGrid1.Selection.Bottom do
If Not ((I = StartPoint.X) and (J = StartPoint.Y)) and
Not ((I = EndPoint.X) and (J = EndPoint.Y)) then
StringGrid1.Cells[I,J] := 'X';
end;


At this point we have an application that creates simple maps. To this we just need to add the path finding. The A* path finding algorithm basically looks for the path of least resistance from Point A to Point Z. Blocks created in the path define the level of resistance each possible path will take.

The StringGrid effectivly displays a map in which the pathfinding happens. The Listbox is the priority list of which squares to search first.

For the path finding I'll first define how one parse of the path finding works.

10. Add a main menu to the application with a menu option '1 Step'
11. Now create procedure OneStep, This procedure takes a location on the map and calculates the cost of stepping one cell in each direction (Remember that A* finds path of least resistance)
To calculate the cost of moving to each surrounding square it is easiest to create a constant array that defines the possible movements from the block and how much each move adds to the cost.


Const
Offsets : Array [0..7] of
Record
DX, DY : Integer;
Cost : Integer;
End =
((DX:-1;DY:-1;Cost:14),(DX: 0;DY:-1;Cost:10),(DX:+1;DY:-1;Cost:14),
(DX:-1;DY: 0;Cost:10), (DX:+1;DY: 0;Cost:10),
(DX:-1;DY:+1;Cost:14),(DX: 0;DY:+1;Cost:10),(DX:+1;DY:+1;Cost:14));

Moving in staright lines has a movement cost of 10 while moving diagonally has a cost of 14. These figures were decided on as 1.4 is the square root of 2 and integers are faster to calculate with that reals.

Whenever a new block is added to the search it must be stored in the search list so that we remember to search it later again.



procedure TForm1.N1Step1Click(Sender: TObject);
begin
// Do one Step in the search pattern
OneStep(StartPoint.X, StartPoint.Y);
end;

Function TForm1.SearchItem(AX,AY,AW : Integer) : String;
Var
S : String;
Begin
// Format of the Items in the search list is
// ZerosPriority:X,Y
S := IntToStr(AW);
S := Copy('000000000',1,8-Length(S))+S+':';
S := S + IntToStr(AX)+',';
S := S + IntToStr(AY);
Result := S;
End;

Procedure TForm1.OneStep(X,Y : Integer);
Var
I : Integer;
W : Integer;
AX, AY, AW : Integer;
Begin
// Calculate the initial weighting of this cell
If StringGrid1.Cells[X,Y] = 'A' then
W := 0
else
W := StrToInt(StringGrid1.Cells[X,Y]);
// Check each surrounding cell - if empty then
// calculate and add weighting
For I := 0 to 7 do
Begin
AX := X + Offsets[I].DX;
AY := Y + Offsets[I].DY;
If (AX >= 0) and
(AY >= 0) and
&#40;AX <= 49&#41; and
&#40;AY <= 49&#41; then
Begin
AW &#58;= W + Offsets&#91;I&#93;.Cost;
If StringGrid1.Cells&#91;AX,AY&#93; = '' then
Begin
StringGrid1.Cells&#91;AX,AY&#93; &#58;= IntToStr&#40;AW&#41;;
// This block can be searched further
ListBox1.Items.Add&#40;SearchItem&#40;AX,AY,AW&#41;&#41;;
End;
End;
End;
End;


At this point it is possible to see how each square around the starting point is searched and how each of these squares is added to the search list in order of their priority.

The next step is to add multiple steps to the search. Part of the problem with AStar searches is that sometimes there is no path to the goal. Therefore we need to remember what state we are in when a search starts.



private
Searching, Found &#58; Boolean;

// In Form Create
Searching &#58;= False;
Found &#58;= False;


Now we need to modify the 1 Step menu procedure to check if we are starting the search or the search is busy, if the search is busy then it should use the highest priority search:



procedure TForm1.N1Step1Click&#40;Sender&#58; TObject&#41;;
Var
I, J, W, X, Y &#58; Integer;
S &#58; String;
begin
If Found then
Exit;
If Not Searching then
Begin
// Do the first Step in the search pattern
OneStep&#40;StartPoint.X, StartPoint.Y&#41;;
Searching &#58;= True;
End
Else
Begin
// Get the highest priority step in the listbox
S &#58;= ListBox1.Items&#91;0&#93;;
ListBox1.Items.Delete&#40;0&#41;;
W &#58;= StrToInt&#40;Copy&#40;S,1,Pos&#40;'&#58;',S&#41;-1&#41;&#41;;
S &#58;= Copy&#40;S,Pos&#40;'&#58;',S&#41;+1,Length&#40;S&#41;&#41;;
X &#58;= StrToInt&#40;Copy&#40;S,1,Pos&#40;',',S&#41;-1&#41;&#41;;
S &#58;= Copy&#40;S,Pos&#40;',',S&#41;+1,Length&#40;S&#41;&#41;;
Y &#58;= StrToInt&#40;S&#41;;
// Do one Step in the search pattern
OneStep&#40;X, Y&#41;;
End;
end;


At this point I would add a new menu option 10 Steps.



procedure TForm1.N10Steps1Click&#40;Sender&#58; TObject&#41;;
Var
I &#58; Integer;
begin
For I &#58;= 0 to 9 do
N1Step1Click&#40;Sender&#41;;
end;


Now you can see the search unfolding in larger steps.

We also need to check if the goal has been found.



Procedure TForm1.OneStep&#40;X,Y &#58; Integer&#41;;

AX &#58;= X + Offsets&#91;I&#93;.DX;
AY &#58;= Y + Offsets&#91;I&#93;.DY;
If &#40;AX = EndPoint.X&#41; and &#40;AY = EndPoint.Y&#41; then
Begin
Found &#58;= True;
Exit;
End;


Now we can add a Menu option to 'Find Path'



procedure TForm1.FindPath1Click&#40;Sender&#58; TObject&#41;;
begin
While Not Found do
N1Step1Click&#40;Sender&#41;;
end;


To find out which path is the quickest path from Point A to Point Z start at Z and follow the path of least resistance back to A.

The program to this point is stored in AStara.zip (http://www.cairnsgames.co.za/files/astar1.zip).

Being able to work out the line of least resistance doesn't help very much unless you could build this info into another structure that your units would be able to follow. For this I've created two structures - TPathStep and TPath.



TPathStep = Class
X, Y &#58; Integer;
End;
TPath = Class
private
FSteps &#58; TList;
function GetStep&#40;Index&#58; Integer&#41;&#58; TPathStep;
function GetCount&#58; Integer;
public
Constructor Create;
Destructor Destroy;
Property Step&#91;Index &#58; Integer&#93; &#58; TPathStep read GetStep; default;
Property Count &#58; Integer read GetCount;
Procedure Clear;
Function Add&#40;X,Y &#58; Integer&#41; &#58; TPathStep;
End;


A TPathStep object stores the information for th next step the unit should take.

The TPath object just steores a set of steps to allow the unit to follow them one by one.

A few words on optimisation

Obviously the use of a StringGrid is a no-no inside an application. This can easily be replaced by an Array that is initialized when the procedure starts.

I've noticed that the use of TPathStep sometimes causes problems as the unit stops at each step and this makes for rather erratic looking movement, this can be improved by only storing steps when the direction of movement changes.

A few words on Enhancements

Also interesting to note is that the weight stored in each Cell is completely independant from the weighting listed in the Listbox. This allows the option of adjusting the listbox priority to include the distance from the goal thereby forcing the process to search toward the goal.

By modifying OneStep with


// This block can be searched further
Dist &#58;= ABS&#40;AX-EndPoint.X&#41; + ABS&#40;AY-EndPoint.Y&#41;;
ListBox1.Items.Add&#40;SearchItem&#40;AX,AY,AW+&#40;Dist*5&#41;&#41;&#41;;


you can see the impact this has. Look carefully at the weightings displayed in the Grid. Some low cost searches are excluded while more expensive costs are searched because they are closer to the goal.

There are two different ways of including terrain cost in the path finding algorithm. Eirther add an adjustment to the movement cost when calculating AW in OneStep. The other way of calculating terrain cost is to multiply it into the AW in OneStep. I prefer the multiplication as it makes it easier to control the final cost of each step -


AW &#58;= W + &#40;Offsets&#91;I&#93;.Cost * TerrainCost&#41;

But the terrain cost would therefore need to be a real number and calculations would be more performance heavy.

I am certain there is a faster structure to use for the priority search than the StringList in the Listbox but I don't know what it is.

// Updated 2006/07/24 with new links to the download

JernejL
25-07-2006, 01:50 PM
for a little improved version of this path finding look here:

http://www.pascalgamedevelopment.com/forums/viewtopic.php?p=23808#23808