# A_star

by Christopher Winward: U6 Age 17

## Introduction

Study program A_star to see how to use the A* algorithm for finding the shortest path from a starting node to a destination node via intermediary nodes. Christopher has commented the code thoroughly for your benefit. Read the on-screen instructions to see how to move, delete, and add nodes and also add a connection between two nodes. The following screenshots show the program detecting slight changes in the position in the destination node F and changing the shortest path accordingly. Note how Christopher has colour-coded each node to demonstrate clearly its state. Congratulations to Christopher for his choice of topic and for his implementation! We now provide a web version to encourage you to try the program.

Shortest Path ABF

Here are some points to consider.
• Individual path lengths are rounded to whole numbers for display. Adding them gives an approximate shortest path distance.
• Avoid dragging one node on top of another. This will conceal the one below and then the nodes will drag together.
• White nodes are "unexplored;" because A* has reached the goal before needing to examine them.
• To prevent the console from flickering, comment out the compiler directive {\$define LargeOutput} in unit u_AStar_proc or just drag the console almost off the screen.

Wikipedia explains that the algorithm follows the "path of the lowest known cost, keeping a sorted priority queue of alternate path segments along the way. If, at any point, a segment of the path being traversed has a higher cost than another encountered path segment, it abandons the higher-cost path segment and traverses the lower-cost path segment instead. This process continues until the goal is reached." Christopher provides a further reference in his program comments. The program calculates the cost as the length of the existing path plus the direct distance "as the crow flies" to the goal. The following screenshots show the algorithm in action.

Unexplored node E

A-D + D-F = 139.8 and A-B + B-F = 137.3. The goal is found before node E is examined.

Explored node E

A-D + D-F = 139.8 as before. This time A-B + B-F = 140.6, which now loses priority so node E is examined before the shortest path is found.

The code to the main program is below. Follow the links at the bottom of the page to view the code of the units.

You can download A_star.zip which contains all of the code. Other files required are: SDL.pas, jedi-sdl.inc, SDL_gfx.pas, SDL.dll and SDL_gfx.dll. See Cow Game for download details.

```program A_star;
{

use this file except in compliance with the License, as described at
}

{\$mode objfpc}{\$H+}

uses
{\$ENDIF}{\$ENDIF}
Classes, uNodeClass, u_AStar_proc, sdl, sdl_gfx, uRendering, uInput,
uGlobalVariables;

{\$R *.res}{\$define GUI}

var
count, deleted : integer;
fpsTimer : int64;
newNodeLetter : char = 'G';

procedure setupPreNodes;
begin
//Call each node constructor to set X, Y and name.
A := tNode.create(2 * 32, 4 * 32, 'A');
B := tNode.create(3 * 32, 3 * 32, 'B');
C := tNode.create(4 * 32, 5 * 32, 'C');
D := tNode.create(3 * 32, 6 * 32, 'D');
E := tNode.create(4 * 32, 7 * 32, 'E');
F := tNode.create(5 * 32, 4 * 32, 'F');

listOfNodes := tList.Create;
listOfNodes.Add(A); //Place all the nodes in the listOfNodes tList.
end;

begin

setupPreNodes;

///////////////////////////////////////////////////////////////////////////////////////
//ANYTHING PAST THIS LINE CAN BE IGNORED IF YOU'RE ONLY INTERESTED IN THE PATHFINDING//
///////////////////////////////////////////////////////////////////////////////////////

{\$ifdef GUI}
createRenderDevice;

while True do
begin
fpsTimer := SDL_GetTicks;

//Update key input.
updateInputs;

if (insertButton = true) then
begin
insertButton := false; //So we don't accidentally spawn hundreds of nodes
listOfNodes.Add(tNode.create(mouseX - 16, mouseY - 16, newNodeLetter));
newNodeLetter := chr(ord(newNodeLetter) + 1); //Increment the new node letter.
end;

//If an initial node has been selected for path linking ...
if ((selectedNode1 <> nil) and (mouse2Down = false)) then
begin
if (selectedNode2 <> nil) then //If a second node was selected
begin
if not (((selectedNode1 = A) and  (selectedNode2 = F)) or
((selectedNode1 = F) and (selectedNode2 = A))) then
begin //We don't want a direct connection between A and F.
end;
end;

selectedNode1 := nil; //Clear up the selections.
selectedNode2 := nil;
end;

//Update all the nodes.
count := 0;
deleted := 0;
while(count - deleted < listOfNodes.Count) do
begin                                  //updateNode returns a true if it needs to be deleted
if (tNode(listOfNodes[count - deleted]).updateNode = true) then
begin
listOfNodes.Remove(tNode(listOfNodes[count - deleted]));
inc(deleted);
end;
inc(count);
end;

//Find the new best path.
pathfoundList := findShortestPath(A, F, exploredListTemp);
//Clear the screen.
SDL_FillRect(SDL_GetVideoSurface, nil, SDL_MapRGB(SDL_GetVideoSurface^.format, 80, 80, 160));

//Draw everything.
RenderScene;

//Flip the screen, then wait.
SDL_Flip(mainSurface);
while (SDL_GetTicks - fpsTimer < 1000 div 60) do
count := 0;
end;
{\$endif}