A_star

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. Chris 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 Chris has colour-coded each node to demonstrate clearly its state. Congratulations to Christopher for his choice of topic and for his implementation!

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.

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

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;
{
    Copyright (c) 2011 Christopher Winward

    Licensed under the Apache License, Version 2.0 (the "License"); you may not
    use this file except in compliance with the License, as described at
    http://www.apache.org/licenses/ and http://www.pp4s.co.uk/licenses/
}

{$mode objfpc}{$H+}

uses
  {$IFDEF UNIX}{$IFDEF UseCThreads}
  cthreads,
  {$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');

  A.addLink(B); //Just linking up all the nodes
  A.addLink(D);
  B.addLink(A);
  B.addLink(C);
  B.addLink(F);
  D.addLink(A);
  D.addLink(C);
  D.addLink(E);
  C.addLink(B);
  C.addLink(D);
  C.addLink(E);
  E.addLink(D);
  E.addLink(C);
  E.addLink(F);
  F.addLink(B);
  F.addLink(E);

  listOfNodes := tList.Create;
  listOfNodes.Add(A); //Place all the nodes in the listOfNodes tList.
  listOfNodes.Add(B);
  listOfNodes.Add(C);
  listOfNodes.Add(D);
  listOfNodes.Add(E);
  listOfNodes.Add(F);
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;

      //Add new nodes.
      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;

      //Add node links

      //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.
                  //Link the two nodes if they aren't already linked.
                  if (selectedNode1.adjacentNodes.IndexOf(selectedNode2) = -1) then
                    selectedNode1.addLink(selectedNode2);
                  if (selectedNode2.adjacentNodes.IndexOf(selectedNode1) = -1) then
                    selectedNode2.addLink(selectedNode1);
                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}
  readln;
end.