Code of web version 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/

    Converted to run in Smart Mobile Studio by PPS (2013)
}

interface

uses 
  w3system, w3lists, uNodeClass, uGlobalVariables;

function findShortestPath(startNode, targetNode : tNode; var exploredListOut : TObjectlist) : TObjectlist;
procedure setupPreNodes;

implementation

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 := TObjectList.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;

function findShortestPath(startNode, targetNode : tNode; var exploredListOut : TObjectlist) : TObjectlist;
//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 : TObjectList;
  searchComplete : boolean;

  procedure PickFrontNode; //Select the shortest path in the list.
  var
    count : integer;
    tempNode, shortestNode : tNode;
  begin
    if frontierList.Count > 0 then
      begin
        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]);
            //If current node checked is the shortest path so far ...
            if (tempNode.totalCost(targetNode) < shortestNode.totalCost(targetNode)) then
              begin
                shortestNode := tempNode;
              end;
          end;
        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(frontierList.IndexOf(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 : TObjectlist;
  var
    resultObjectList, resultObjectList_fixed : TObjectList;
    tempNode : tNode;
    count : integer;
  begin
    searchComplete := true;
    resultObjectList := TObjectList.Create;
    resultObjectList_fixed := TObjectList.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(frontierList.IndexOf(tempNode));
        exploredList.Add(tempNode);
      end;

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

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

    //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(resultObjectList_fixed); //Return the resulting list of nodes.
  end;

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

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

end.