Unit u_AStar_proc

The code of unit u_AStar_proc

unit u_AStar_proc;
{
    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+}

{$define LargeOutput} //Comment this line out if you don't want to see a flickering console.

interface

uses
  Classes, SysUtils, uNodeClass;

function findShortestPath(startNode, targetNode : tNode; out exploredListOut : tList) : tList;

implementation
                                                       //The out keyword lets us specify a variable
                                                       //we will output data to by reference.
function findShortestPath(startNode, targetNode : tNode; out exploredListOut : tList) : tList;
//This function is an implementation of the A* pathfinding algorithm.
//For a proper explanation, go to https://www.ai-class.com/home/ and watch Unit 2, Problem solving.
//The core concept behind A* is always select the shortest path that is also currently closest to the target node.
var
  frontNode : tNode; //This is the node we're always most interested in.
  frontierList, exploredList : tList;
  searchComplete : boolean;

  procedure PickFrontNode; //Select the shortest path in the list.
  var
    count : integer;
    tempNode, shortestNode : tNode;
  begin
    if (frontierList.Count > 0) then
      begin
        {$ifdef LargeOutput}
        writeln('Nodes in the frontier are:');
        {$endif}
        shortestNode := tNode(frontierList[0]);
        //Check all the nodes in the frontier list for the shortest.
        for count := 0 to (frontierList.count - 1) do
          begin
            tempNode := tNode(frontierList[count]);
            {$ifdef LargeOutput}
            writeln(tempNode.pathNodeNames,': ', FloatToStr(tempNode.totalCost(targetNode)));
            {$endif}
            //If current node checked is the shortest path so far ...
            if (tempNode.totalCost(targetNode) < shortestNode.totalCost(targetNode)) then
              begin
                shortestNode := tempNode;
              end;
          end;

        {$ifdef LargeOutput}
        writeln('Selected node ', shortestNode.pathNodeNames);
        writeln('-');
        {$endif}

        frontNode := shortestNode; //Set this to the node we want.
      end;
  end;

  procedure RemoveNodeFromFrontier;
  //Take out of the frontier, and shove in the explored.
  begin
    frontierList.Remove(frontNode);
    exploredList.Add(frontNode);
  end;

  function goalTestFrontNode() : boolean;
  begin
    if ( frontNode = targetNode ) then
      exit(true) //Return true if we've found the target node.
    else
      exit(false);
  end;

  procedure ExpandFrontNode;
  var
    count : integer;
    tempNode : tNode;
    tempNode2 : tNode;
  begin
    if (frontNode.adjacentNodes.Count > 0) then //If there are nodes to add to the frontier
      begin
        for count := 0 to (frontNode.adjacentNodes.Count - 1) do //Loop through all the adjacent nodes.
          begin
            tempNode := tNode(frontNode.adjacentNodes[count]);
            //If the node hasn't already been evaluated in one way or another ...
            if ((exploredList.IndexOf(tempNode) = -1) and (frontierList.IndexOf(tempNode) = -1)) then
              begin
                frontierList.Add(tempNode);
                tempNode.previousNode := frontNode; //Link the new node to the current node.
              end;
          end;
      end;
  end;

  function FinishSearch : tList;
  var
    resultList, resultList_fixed : tList;
    tempNode : tNode;
    count : integer;
  begin
    searchComplete := true;
    resultList := tList.Create();
    resultList_fixed := tList.Create();
    //Remove all the items from the frontier and place them in explored.
    while (frontierList.count > 0) do
      begin
        tempNode := tNode(frontierList[0]);
        frontierList.Remove(tempNode);
        exploredList.Add(tempNode);
      end;

    tempNode := frontNode;
    while(true) do //Pop back through the previous nodes to get the path chain.
      begin
        resultList.Add(tempNode);
        tempNode := tempNode.previousNode;
        if (tempNode = nil) then
          break;
      end;

    for count := (resultList.Count - 1) downto 0 do //Reverse the list.
      resultList_fixed.Add(resultList[count]);

    writeln('LENGTH: ', FloatToStr(frontNode.pathCost));
    //Clean all the affected nodes so this particular search doesn't affect the next.
    for count := 0 to (exploredList.Count - 1) do
      begin
        tempNode := tNode(exploredList[count]);
        tempNode.previousNode := nil;
      end;
    //Output the exploredList for the renderer, though this isn't strictly necessary.
    exploredListOut := exploredList;
    exit(resultList_fixed); //Return the resulting list of nodes.
  end;

begin
  frontierList := tList.Create; //This holds all the nodes we want to potentially expand upon.
  exploredList := tList.Create; //This holds all nodes we've already checked.
  searchComplete := false;
  frontierList.Add(startNode); //For example, we need to expand the first node first.

  writeln('----------------');

  while(searchComplete = false) do
    begin
      PickFrontNode;
      RemoveNodeFromFrontier;
      if (goalTestFrontNode = false) then
        ExpandFrontNode
      else
        exit(FinishSearch);
    end;
end;

end.
Programming - a skill for life!

by Christopher Winward: U6 Age 17