Artificial Intelligence - Bot path finding

Fabry · December 28, 2007

In my game, I will show it, there are only wall (x) and floor (F=1) then the lowest "F" cost of all the adjacent is always F=1.

The game is in real time and the coordinate of goal and start are costantly refreshed thus I need only the first 2 element because having the whole $path is useless because the goal is changed.

Posted Image

zxzxzx · December 29, 2007

A * Searching Algorithm - Pronounced "A star"
UPDATED: June 27, 2007
A bot path searching algorithm that will find the shortest and least cost path to the final state (goal). I wrote an example to visually explain how this is used in the real world. This type of bot searching is commonly used in games that are based on a grid system. The images below are taken from the example program that you can get below this description.
For example, say we have a map of some terrain. Shown below.
The bot must reach the goal with the shortest distance possible (if the path exists). The bot must also take into account different terrain types, each of them have their own difficulty level of traveling. The easiest type of terrain to move on is flat ground, so the bot will choose this over any other. The difficulty levels are ordered from easiest to hardest below.
Easy - Flat ground
Medium - Sand
Hard - Water
Very Hard - Hill
The bot then searches all possible nodes, only searching those that are the easiest to travel on as well as those closest to the goal. Below shows the nodes that the bot searches denoted with a yellow block "SN". Note that not all the nodes on the grid are searched, that is why this algorithm is so fast.
The bot then calculates the shortest and easiest path to get to the goal only using those searched nodes. Below is the path the bot takes.
NOTE RULES:
1. There must be a Start and a Goal.
2. The path does not have to exist.
Below is a GUI example that lets you see how this works. If you are wanting to use this in something of your own then download the attachment below named starterkit. It will get your started on the right track.

oks o ive posted my code!... its not very good scripting tho.. very noobish

Thank

Toady · May 21, 2008

*Update* - May 21, 2008

Gui constants were outdated. Now works properly.

BillLuvsU · May 22, 2008

very impressive toady. I can't believe I just now saw this. I created somthing similer earlier for my game but it was much slower. This solves alot of problems.

TnTProductions · May 22, 2008

cool cant wait to try it out!

WeMartiansAreFriendly · October 13, 2008

Quite impressive!

Actually it looks like it could be used to solve mazes

Edited October 13, 2008 by mrRevoked

Simucal · October 15, 2008

Toady,

Very nice application! It seems like a very good learning tool for those new to Graphs, Graph Traversal, and Pathing Algorithms.

If you feel like expanding it you might consider having a few other algorithms that the user can select and run against your maze so the user can see the physical difference of the nodes that each one evaluates.

Maybe something like:

* Dijkstra's Algorithm (Really A* is a specialized variant of Dijkastra's)

* B-Star (B*) - Storing Intervals of nodes of the tree

* D-Star (D*) - As far as I know places like Garmin/TomTom use specialized D* for finding best paths in partially known enviornments to plan your driving route.

* Depth and Breadth first traversal. Along with visually showing the user the nodes it is considering along the way.

and apart from path finding.. implementing something like the Floyd-Warshall algorithm to find the shortest point between all vertices would be kind of cool. Might be slow at O(V^3).. but with this small a graph it shouldn't be too bad.

Another expansion you could do is to find a flash game that is maze like and embed it into an autoit app. You can then have a maze-solver utilizing Depth-First or one of your Best-First algorithms. Watching it automate and solve the flash-games mazes would definately be cool!

Triblade · June 7, 2009

Looks great!!, and I can surely use this in a 'simulation' I'm cooking up.

Only, if I tick the allow diagonal moves box, it does do diagonal, but not with walls besides them.

See attachement above for what I mean. I have drawn two lines over the squares. The left one does not count and the right one does. Bug or feature?

Hawkwing · August 16, 2009

Feature I would guess. Me and UnknownWarrior are probably going to use this for the game we are making.

Very nice!

Shanheavel · January 31, 2011

Hello,

I know it's very old topic, but I need to make path finder without GUI.

I want to use arrays (for example):

$Array[1] = "0"
$Array[2] = "0"
$Array[3] = "1"
...

0 - open space

1 - wall

Can someone helps remove GUI?

Mat · February 1, 2011

Look at the code and you'll see that it is very well commented, and the GUI is clearly split from the logic. There is a line like this:

;==================== END OF MAIN =================

And after that it is the algorithm. You'll also see this:

;============ * How to use this code * ============
; Below is the A * Searching algorithm and its
; required functions to work.
; This is coded to work with 2D spaces only.
; Everything below is all you need to get started.

; 1. Initialize a 2D array
;     $data[5][5] = [["x","x","x","x","x"], _
;                    ["x","s","0","x","x"], _
;                    ["x","x","0","x","x"], _
;                    ["x","x","0","g","x"], _
;                    ["x","x","x","x","x"]]
;       NOTE: Array MUST have x's around entire paremeter
;       There must be a "s" and a "g". "0" means bot can walk here
; 2. Convert array into node objects
;       _CreateMap($data,5,5)
; 3. Calculate path
;       Dim $path = _FindPath($data,$data[1][1],$data[3][3])
; 4. Thats all!
;       The variable $path contains an array of the path in "x,y" format
;       _ArrayDisplay($path) will show the the full path
;==================================================

That should be enough to get you started.

Mat

cembry90 · February 1, 2011

Not bad. Done pretty well, to be honest.

Also, hello to you (Toady) from a fellow Louisville resident.

twitchyliquid64 · February 2, 2011

HI Toady, First let me say I love your script. It has alot of potential.

The idea of having a Grid based system seriously limits the range of programs that can be created. I would recommend creating a system where any node can be the neighbour of any other node, and there can be an unlimited number of nieghbours. From that implementation possiblities are endless...I could turn my P2P Engine into an onion router like tor...

ON on another note, I have done something similar in the past.

Last month I went on the australian national computer camp thingie (NCSS). As the all nighter project, we had to build a train network between the rooms, and have programmable robots as trains.

We put reflective tape on the ground and had the robot follow that, with special markers when one track split to two, or three. When we got to the stage that it was time to implement shortest path finding, we did. Eventually. I can't even remember how it works anymore. It was 2 in the morning.

Anyway, here is my C code specifically for the path finding. If you want the other parts of the code so you can see how it fits in, lemme know.

The init graph function holds all the nodes. We pre-programmed the map of the train network in.

This was written for arduino.

struct node {
    int north;
    int south;
    int east;
    int west;
};
node nodes[NUM_NODES];

bool seen[NUM_NODES];
int sourceNode[NUM_NODES];

int stationNodes[] = {
  30, //Flat White Fields  THESE ARE THE NAMES OF THE STATIONS
  5, //Latte Lake
  8, //Cappuccino Cavern
  28, //Risretto Rise
  18 //Macchiato Moor
};

void setEdges(int i, int n, int s, int e, int w) {
  nodes[i].north = n;
  nodes[i].south = s;
  nodes[i].east = e;
  nodes[i].west = w;
}

void initGraph() {
  setEdges(0, 16, -1, -1, 1);
  setEdges(1, 12, -1, -1, 2);
  setEdges(2, -1, 3, -1,  -1);
  setEdges(3, -1, -1, 4, -1);
  setEdges(4, -1, 5, -1, -1);
  setEdges(5, -1, 6, -1, -1);
  setEdges(6, -1, -1, -1, 7);
  setEdges(7, 8, -1, -1, -1);
  setEdges(8, 9, -1, -1, -1);
  
  //setEdges(9, 3, -1, 10, -1);
  setEdges(9, -1, -1, -1, 10);
  
  setEdges(10, 11, -1, -1, -1);
  setEdges(11, -1, -1, 12, -1);
  setEdges(12, -1, -1, 13, -1);
  setEdges(13, 14, -1, 15, -1);
  setEdges(14, -1, -1, 28, -1);
  setEdges(28, -1, -1, 29, -1);
  setEdges(29, -1, 15, -1, -1);
  setEdges(15, -1, -1, 16, -1);
  setEdges(16, -1, -1, 17, -1);
  setEdges(17, -1, 18, -1, -1);
  setEdges(18, -1, 19, -1, -1);
  setEdges(19, -1, -1, -1, 20);
  setEdges(20, 21, -1, -1, -1);
  setEdges(21, 24, -2, -2, 22);
  setEdges(22, 23, -1, -1, -1);
  setEdges(23, -1, -1, 24, -1);
  setEdges(24, 25, -1, -1, -1);
  setEdges(25, -1, -1, 26, -1);
  setEdges(26, 27, -1, -1, -1);
  setEdges(27, -1, -1, -1, 30);
  setEdges(30, -1, -1, -1, 0);
}

int leftNode(int cur, int next) {
  if (nodes[cur].north == next) {
    return nodes[next].west;
  } else if (nodes[cur].east == next) {
    return nodes[next].north;
  } else if (nodes[cur].south == next) {
    return nodes[next].east;
  } else if (nodes[cur].west == next) {
    return nodes[next].south;
  }
}

int rightNode(int cur, int next) {
  if (nodes[cur].north == next) {
    return nodes[next].east;
  } else if (nodes[cur].east == next) {
    return nodes[next].south;
  } else if (nodes[cur].south == next) {
    return nodes[next].west;
  } else if (nodes[cur].west == next) {
    return nodes[next].north;
  }
}

int straightNode(int cur, int next) {
  if (nodes[cur].north == next) {
    return nodes[next].north;
  } else if (nodes[cur].east == next) {
    return nodes[next].east;
  } else if (nodes[cur].south == next) {
    return nodes[next].south;
  } else if (nodes[cur].west == next) {
    return nodes[next].west;
  }
}

void findPath(int startNode, int endNode) {
  memset(seen, 0, sizeof(seen));
  for (int i=0; i<NUM_NODES; i++) {
    sourceNode[i] = -1;
  }
    
  int q[NUM_NODES+1];
  int q_top = 0, q_front = 0;
  q[q_top++] = startNode;
  seen[startNode] = true;
  
  //LOG_PRINT("begin\n");
  
  while (q_front < q_top) {
    int cur = q[q_front++];
    
    //LOG_PRINT("cur %d\n", cur);
    
    if (nodes[cur].north >= 0 && !seen[nodes[cur].north]) {
      q[q_top++] = nodes[cur].north;
      seen[nodes[cur].north] = true;
      sourceNode[nodes[cur].north] = cur;
    }
    if (nodes[cur].south >= 0 && !seen[nodes[cur].south]) {
      q[q_top++] = nodes[cur].south;
      seen[nodes[cur].south] = true;
      sourceNode[nodes[cur].south] = cur;
    }
    if (nodes[cur].east >= 0 && !seen[nodes[cur].east]) {
      q[q_top++] = nodes[cur].east;
      seen[nodes[cur].east] = true;
      sourceNode[nodes[cur].east] = cur;
    }
    if (nodes[cur].west >= 0 && !seen[nodes[cur].west]) {
      q[q_top++] = nodes[cur].west;
      seen[nodes[cur].west] = true;
      sourceNode[nodes[cur].west] = cur;
    }
  }
  
  pathIndex = 0;
  int c = endNode;
  while (sourceNode[c] != -1 && sourceNode[c] != startNode) {
    c = sourceNode[c];
    path[pathIndex++] = c;
    //LOG_PRINT("%d\n", c);
  }
  
  pathIndex--;
  
}

I was also wondering; and im sure im not the only one, how you search worked. What is the open list and closed list?

Edited February 2, 2011 by hyperzap

mehul · February 23, 2011

cool

August 15, 2011

There's something I'm doing wrong or it only supports square-shaped maps? it fails at function called "_CreateMap"

Posting part of my prog here

#NoTrayIcon
#include <array.au3>
Global $estimate
Global $closedList_data
Global $closedList_Str = "_"
Global $openList_Str = "_"
Global $start_handel[3]
Global $end_handel[3]
Global $barrier = _ArrayCreate(-1)
Global $allow_diagonals_Boolean = 1
Global $allow_overestimate_Boolean = 1

If $allow_overestimate_Boolean = 1 Then
    $estimate = 1.001 ;used to overestimate heuristic by a small amount
Else
    $estimate = 1
EndIf

Global $heuristic = 1

$Rawdataz = "x,x,x,x,x,x|x,x,s,0,x,x|x,x,x,0,x,x|x,x,x,0,x,x|x,x,x,0,0,x|x,x,x,x,0,x|x,x,x,0,0,x|x,x,x,0,x,x|x,x,x,0,x,x|x,x,x,g,x,x|x,x,x,x,x,x"

    $rowsdataz = StringSplit($Rawdataz, "|")
    $rows = UBound($rowsdataz) - 1
    $cols = UBound(StringSplit($rowsdataz[1], ",")) - 1

$dataz = _ST2DA($Rawdataz)

_ArrayDisplay($dataz)

$map = $dataz
_CreateMap($map,$rows,$cols)    ;Create map

$closedList_Str = "_"
$openList_Str = "_"

$SLocation = _GetStartingLocation($dataz, $rows, $cols) ;starting location
$GLocation = _GetGoalLocation($dataz, $rows, $cols) ;goal location

If $SLocation = 0 Or $GLocation = 0 Then
    MsgBox(0, "Error", "Goal/start missing!")
    $map = $dataz
Else
    If $allow_overestimate_Boolean = 1 Then
        $estimate = 1.001 ;used to overestimate heuristic by a small amount
    Else
        $estimate = 1
    EndIf
;~  ConsoleWrite("Processing..." & @CRLF)
    $map = $dataz
    _CreateMap($dataz, $cols, $rows) ;replaces dataz with node objects
    Dim $path = _FindPath($dataz, $dataz[$SLocation[1]][$SLocation[0]], $dataz[$GLocation[1]][$GLocation[0]])
;~  ConsoleWrite("Done! displaying array..." & @CRLF)
    _ArrayDisplay($path)
EndIf

Func _ST2DA($Rawdataz)
    $rowsdataz = StringSplit($Rawdataz, "|")
    $rows = UBound($rowsdataz) - 1
    $cols = UBound(StringSplit($rowsdataz[1], ",")) - 1

    Dim $dataz[$rows][$cols]

    For $i = 1 to $rows
        $split = StringSplit($rowsdataz[$i], ",")
        For $ii = 1 to $cols
            $dataz[$i - 1][$ii - 1] = $split[$ii]
        Next
    Next
    Return $dataz
EndFunc

;============ * How to use this code * ============
; Below is the A * Searching algorithm and its
; required functions to work.
; This is coded to work with 2D spaces only.
; Everything below is all you need to get started.

; 1. Initialize a 2D array
;     $data[5][5] = [["x","x","x","x","x"], _
;                    ["x","s","0","x","x"], _
;                    ["x","x","0","x","x"], _
;                    ["x","x","0","g","x"], _
;                    ["x","x","x","x","x"]]
;       NOTE: Array MUST have x's around entire paremeter
;       There must be a "s" and a "g". "0" means bot can walk here
; 2. Convert array into node objects
;       _CreateMap($data,5,5)
; 3. Calculate path
;       Dim $path = _FindPath($data,$data[1][1],$data[3][3])
; 4. Thats all!
;       The variable $path contains an array of the path in "x,y" format
;       _ArrayDisplay($path) will show the the full path
;==================================================

;=============================================================================
; Replaces data grid with node objects
; Converts $data into a 2D array of node objects from previous $data array
; consisting of only string characters.
;=============================================================================
Func _CreateMap(ByRef $data, $x, $y) ;converts a 2D array of data to node objects
;~  MsgBox(0, "", $x & "|" & $y)
    For $i = 0 To $y - 1 ;for each row
        For $j = 0 To $x - 1 ;for each column
            If StringRegExp($data[$i][$j], "[x,s,g]") <> 1 Then;if not a x,s,g
                $data[$i][$j] = _CreateNode($i & "," & $j, "null", 0, $data[$i][$j], 0, $data[$i][$j])
            Else
                If $data[$i][$j] = "s" Then
                    $data[$i][$j] = _CreateNode($i & "," & $j, "null", 0, 0, 0, $data[$i][$j])
                Else
                    $data[$i][$j] = _CreateNode($i & "," & $j, "null", 0, 1, 0, $data[$i][$j])
                EndIf
            EndIf
        Next
    Next
EndFunc   ;==>_CreateMap
;=============================================================================
; Creates a node struct object with the following parameters
; struct node {
;   char self_coord[8];          // Format = "x,y"
;   char parent_coord[8];        // Format = "x,y"
;   int f;                       // F = G + H
;   int g;                       // G = current cost to this node from start node
;   int h;                       // H = Heuristic cost, this node to goal node
;   char value[8];               // Type of node (ex. "s","g","x","1,2,3..n")
;   int cost;                    // Cost of node (difficulty of traveling on this)
; }
;=============================================================================
Func _CreateNode($self, $parent, $f, $g, $h, $value) ;returns struct object
    Local $node[6] = [$self, $parent, $f, $g, $h, $value]
    Return $node
EndFunc   ;==>_CreateNode
;=============================================================================
; Checks to see if start node exists in map
; Returns an array: [y,x]
;=============================================================================
Func _GetStartingLocation(ByRef $data, $cols, $rows)
    For $i = 0 To $cols - 1
        For $j = 0 To $rows - 1
            If $data[$i][$j] = "s" Then
                Local $pos[2] = [$j, $i]
                Return $pos
            EndIf
        Next
    Next
    Return 0 ;no starting location found
EndFunc   ;==>_GetStartingLocation
;=============================================================================
; Checks to see if goal node exists in map
; Returns an array: [y,x]
;=============================================================================
Func _GetGoalLocation(ByRef $data, $cols, $rows)
    For $i = 0 To $cols - 1
        For $j = 0 To $rows - 1
            If $data[$i][$j] = "g" Then
                Local $pos[2] = [$j, $i]
                Return $pos
            EndIf
        Next
    Next
    Return 0 ;no starting location found
EndFunc   ;==>_GetGoalLocation
;=============================================================================
; Calculates the manhattan distance between two nodes
; MD = |G(x) - N(x)| + |G(y) - N(x)|
; Returns an integer
;=============================================================================
Func _MD(ByRef $node, ByRef $goal) ;returns integer
    Local $node_coord = StringSplit($node[0], ",") ;current node
    Local $goal_coord = StringSplit($goal[0], ",") ;goal node
    Return (Abs($goal_coord[1] - $node_coord[1]) + Abs($goal_coord[2] - $node_coord[2])) * $estimate
EndFunc   ;==>_MD
;=============================================================================
; Calculates the Euclidean distance between two nodes
; MD = SquareRoot ( (G(x) - N(x))^2 + (G(y) - N(x))^2 )
; Returns an integer
;=============================================================================
Func _ED(ByRef $node, ByRef $goal) ;returns integer
    Local $node_coord = StringSplit($node[0], ",") ;current node
    Local $goal_coord = StringSplit($goal[0], ",") ;goal node
    Return Sqrt(($goal_coord[1] - $node_coord[1]) ^ 2 + ($goal_coord[2] - $node_coord[2]) ^ 2) * $estimate
EndFunc   ;==>_ED
;=============================================================================
; A * Searching Algorithm
; Keep searching nodes until the goal is found.
; Returns: Array if path found
; Returns: 0 if no path
;=============================================================================
Func _FindPath(ByRef $map, $start_node, $goal_node) ;returns array of coords
    Local $openlist = _ArrayCreate("empty") ;start with empty open list
    Local $closedlist = _ArrayCreate("empty") ;start with empty closed list
    Local $current_node = $start_node ;set current node to start nodeF
    $closedList_Str &= $current_node[0] & "_"
    $openList_Str &= $current_node[0] & "_"
    _AddAdjacents_Openlist($map, $openlist, $closedlist, $current_node, $goal_node) ;add all possible adjacents to openlist
    While 1 ;while goal is not in closed list, or open list is not empty
        If UBound($openlist) = 1 Then ExitLoop ;if open list is empty then no path found
        $current_node = _GetLowest_F_Cost_Node($openlist) ;pick node with lowest F cost
        $closedList_Str &= $current_node[0] & "_"
        _AddAdjacents_Openlist($map, $openlist, $closedlist, $current_node, $goal_node) ;add all possible adjacents to openlist
        If $current_node[0] = $goal_node[0] Then ExitLoop ;if current node is goal then path is found!
    WEnd
    If _IsInClosedList($goal_node[0]) = 0 Then ;if no goal found then return 0
        Return 0 ; no path found
    Else
        Return _GetPath($map, $current_node, $start_node) ;return array of coords (x,y) in string format
    EndIf
EndFunc   ;==>_FindPath
;=============================================================================
; Returns node object with the lowest F cost
; F = G + H
; Returns 0 with openlist is emtpy, there is no path
;=============================================================================
Func _GetLowest_F_Cost_Node(ByRef $openlist)
    If UBound($openlist) > 1 Then ;If open list is not empty
        Local $obj = $openlist[1] ;Pop first item in the queue
        _ArrayDelete($openlist, 1) ;remove this node from openlist
        Return $obj ;return lowest F cost node
    EndIf
    Return 0 ;openlist is empty
EndFunc   ;==>_GetLowest_F_Cost_Node
;=============================================================================
; Start from goal node and traverse each parent node until starting node is
; reached.
; Each node will have a parent node (use this to get path bot will take)
; Returns: Array of coords, first index is starting location
;=============================================================================
Func _GetPath(ByRef $data, ByRef $ending_node, ByRef $start_node)
    Local $path = _ArrayCreate($ending_node[0]) ;start from goal node
    Local $node_coord = StringSplit($path[0], ",")
    Local $x = $node_coord[1]
    Local $y = $node_coord[2]
    Local $start = $start_node[0] ;starting nodes coord
    Local $obj = $data[$x][$y] ;current node starting from the goal
    While $obj[1] <> $start ;keep adding until reached starting node
        _Add_List($path, $y & "," & $x) ;add the parent node to the list
        $obj = $data[$x][$y] ;get node from 2D data array
        $node_coord = StringSplit($obj[1], ",")
        If $node_coord[0] = 1 Then ExitLoop
        $x = $node_coord[1]
        $y = $node_coord[2]
    WEnd
    _ArrayDelete($path, 0) ;no need to starting node
    _ArrayReverse($path) ;flip array to make starting node at index 0
    Return $path ;return path as array in "x,y" format for each item
EndFunc   ;==>_GetPath
;=============================================================================
; Adds adjacent nodes to the open list if:
; 1. Node is not a barrier "x"
; 2. Node is not in open list
; 3. Node is not in closed list
; Set newly added node's parent to the current node and update its F,G, and H
; Only need to check North, South, East and West nodes.
;=============================================================================
Func _AddAdjacents_Openlist(ByRef $data, ByRef $openlist, ByRef $closedlist, ByRef $node, ByRef $goal)
    Local $current_coord = StringSplit($node[0], ",")
    Local $x = $current_coord[1]
    Local $y = $current_coord[2]
    Local $h ; heuristic
    Local $north = 0
    Local $south = 0
    Local $east = 0
    Local $west = 0
    Local $obj = $data[$x][$y - 1]
    If $obj[5] <> "x" And _ ;north
            Not _IsInAnyList($obj[0]) Then ;If not in closed list or openlist and is not a barrier
        If $heuristic = 1 Then
            $h = _MD($obj, $goal)
        Else
            $h = _ED($obj, $goal)
        EndIf
        $obj[1] = $node[0] ;set nodes parent to last node
        $obj[3] = $node[3] + $obj[3] ;set g score (current node's G score + adjacent node's G score)
        $obj[2] = $obj[3] + $h ;set f = g + h score
        $data[$x][$y - 1] = $obj
        $north = 1
        $openList_Str &= $obj[0] & "_"
        _Insert_PQ($openlist, $obj)
    EndIf
    $obj = $data[$x][$y + 1]
    If $obj[5] <> "x" And _ ;south
            Not _IsInAnyList($obj[0]) Then
        If $heuristic = 1 Then
            $h = _MD($obj, $goal)
        Else
            $h = _ED($obj, $goal)
        EndIf
        $obj[1] = $node[0] ;set nodes parent to last node
        $obj[3] = $node[3] + $obj[3]  ;set g score (current node's G score + adjacent node's G score)
        $obj[2] = $obj[3] + $h ;set f = g + h score
        $data[$x][$y + 1] = $obj
        $south = 1
        $openList_Str &= $obj[0] & "_"
        _Insert_PQ($openlist, $obj)
    EndIf
    $obj = $data[$x + 1][$y]
    If $obj[5] <> "x" And _ ;east
            Not _IsInAnyList($obj[0]) Then
        If $heuristic = 1 Then
            $h = _MD($obj, $goal)
        Else
            $h = _ED($obj, $goal)
        EndIf
        $obj[1] = $node[0] ;set nodes parent to last node
        $obj[3] = $node[3] + $obj[3]  ;set g score (current node's G score + adjacent node's G score)
        $obj[2] = $obj[3] + $h ;set f = g + h score
        $data[$x + 1][$y] = $obj
        $east = 1
        $openList_Str &= $obj[0] & "_"
        _Insert_PQ($openlist, $obj)
    EndIf
    $obj = $data[$x - 1][$y]
    If $obj[5] <> "x" And _ ;west
            Not _IsInAnyList($obj[0]) Then
        If $heuristic = 1 Then
            $h = _MD($obj, $goal)
        Else
            $h = _ED($obj, $goal)
        EndIf
        $obj[1] = $node[0] ;set nodes parent to last node
        $obj[3] = $node[3] + $obj[3]  ;set g score (current node's G score + adjacent node's G score)
        $obj[2] = $obj[3] + $h ;set f = g + h score
        $data[$x - 1][$y] = $obj
        $west = 1
        $openList_Str &= $obj[0] & "_"
        _Insert_PQ($openlist, $obj)
    EndIf
    ;diagonals moves
    If $allow_diagonals_Boolean Then ;if GUI checkbox is checked, then check other 4 directions
        If $north + $east = 2 Then ;Not allowed to cut around corners, not realistic
            $obj = $data[$x + 1][$y - 1]
            If $obj[5] <> "x" And _ ;northeast
                    Not _IsInAnyList($obj[0]) Then
                If $heuristic = 1 Then
                    $h = _MD($obj, $goal)
                Else
                    $h = _ED($obj, $goal)
                EndIf
                $obj[1] = $node[0] ;set nodes parent to last node
                $obj[3] = $node[3] + (Sqrt(2) * $obj[3])  ;set g score (current node's G score + adjacent node's G score* Sqrt(2))
                $obj[2] = $obj[3] + $h ;set f = g + h score
                $data[$x + 1][$y - 1] = $obj
                $openList_Str &= $obj[0] & "_"
                _Insert_PQ($openlist, $obj)
            EndIf
        EndIf
        If $north + $west = 2 Then
            $obj = $data[$x - 1][$y - 1]
            If $obj[5] <> "x" And _ ;north west
                    Not _IsInAnyList($obj[0]) Then
                If $heuristic = 1 Then
                    $h = _MD($obj, $goal)
                Else
                    $h = _ED($obj, $goal)
                EndIf
                $obj[1] = $node[0] ;set nodes parent to last node
                $obj[3] = $node[3] + (Sqrt(2) * $obj[3])  ;set g score (current node's G score + adjacent node's G score* Sqrt(2))
                $obj[2] = $obj[3] + $h  ;set f = g + h score
                $data[$x - 1][$y - 1] = $obj
                $openList_Str &= $obj[0] & "_"
                _Insert_PQ($openlist, $obj)
            EndIf
        EndIf
        If $south + $east = 2 Then
            $obj = $data[$x + 1][$y + 1]
            If $obj[5] <> "x" And _ ;southeast
                    Not _IsInAnyList($obj[0]) Then
                If $heuristic = 1 Then
                    $h = _MD($obj, $goal)
                Else
                    $h = _ED($obj, $goal)
                EndIf
                $obj[1] = $node[0] ;set nodes parent to last node
                $obj[3] = $node[3] + (Sqrt(2) * $obj[3])  ;set g score (current node's G score + adjacent node's G score)
                $obj[2] = $obj[3] + $h  ;set f = g + h score
                $data[$x + 1][$y + 1] = $obj
                $openList_Str &= $obj[0] & "_"
                _Insert_PQ($openlist, $obj)
            EndIf
        EndIf
        If $south + $west = 2 Then
            $obj = $data[$x - 1][$y + 1]
            If $obj[5] <> "x" And _ ;southwest
                    Not _IsInAnyList($obj[0]) Then
                If $heuristic = 1 Then
                    $h = _MD($obj, $goal)
                Else
                    $h = _ED($obj, $goal)
                EndIf
                $obj[1] = $node[0] ;set nodes parent to last node
                $obj[3] = $node[3] + (Sqrt(2) * $obj[3])  ;set g score (current node's G score + adjacent node's G score)
                $obj[2] = $obj[3] + $h  ;set f = g + h score
                $data[$x - 1][$y + 1] = $obj
                $openList_Str &= $obj[0] & "_"
                _Insert_PQ($openlist, $obj)
            EndIf
        EndIf
    EndIf
EndFunc   ;==>_AddAdjacents_Openlist
;=============================================================================
; Returns true if node is in closed list
; Search the list backwards, its faster
;=============================================================================
Func _IsInClosedList(ByRef $node)
    If StringRegExp($closedList_Str, "_" & $node & "_") Then
        Return 1
    Else
        Return 0
    EndIf
EndFunc   ;==>_IsInClosedList
;=============================================================================
; Returns true if node is in open list
; Regular expressions are used rather than searching an array list for speed.
;=============================================================================
Func _IsInAnyList(ByRef $node)
    If StringRegExp($openList_Str, "_" & $node & "_") Then
        Return 1
    Else
        Return 0
    EndIf
EndFunc   ;==>_IsInAnyList
;=============================================================================
; Inserts object into openlist and preserves ascending order
; This way will result in a priority queue with the lowest F cost at
; position 1 in the openlist array.
;=============================================================================
Func _Insert_PQ(ByRef $openlist, $node)
    Local $obj
    For $i = 1 To UBound($openlist) - 1
        Local $obj = $openlist[$i]
        If $node[2] < $obj[2] Then
            _ArrayInsert($openlist, $i, $node)
            Return
        EndIf
    Next
    _Add_List($openlist, $node)
EndFunc   ;==>_Insert_PQ
;=============================================================================
; Adds nodes the a list
;=============================================================================
Func _Add_List(ByRef $list, $node)
    ReDim $list[UBound($list) + 1]
    $list[UBound($list) - 1] = $node
EndFunc   ;==>_Add_List
;============================================================================
; End of Algorithm
;============================================================================

As far as I traced it, the array I'm passing is fine, array dimensions are also right, so, I'm kinda stuck, I tried reading the code too and even understood how it's made, still I have no idea why it doesn't work

note: using autoit v3.3.6.1

iFFgen · November 12, 2013

Please сan someone find in what could be the reason of the wrong way (not the shortest)?

(sorry for my english :oops: )

Edited November 12, 2013 by iFFgen

Triblade · December 31, 2014

I know this topic is _very_ old, but I am trying to use this fantastic path finding algorithm right now and it doesn't work anymore. I have tried to hack it to make it work, but my brain seems too limited to grasp the whole thing to fix it...

There are two things:

1) I edited out the _ArrayCreate with: Local $var[1] = ["empty"] or things like: $closedList_Str = ""

2) It works great now, except when having multiple routes to the goal... With only one route, it does it well, but when I add two routes I get:

"C:\Users\Admin\Desktop\test.au3" (253) : ==> Subscript used on non-accessible variable.:
$closedList_Str &= $current_node[0] & "_"
$closedList_Str &= $current_node^ ERROR

Has anyone an updates version? :sweating:

There are not many (I could find none) other path finding scripts out there...

Edit:

Finally! Just before Newyear I found something which works!

I added +1 to the $i. Somehow it pushed the goal coord as plain text in the wong place

Func _Insert_PQ(ByRef $openlist, $node)
;Local $obj ;Unneeded
For $i = 1 To UBound($openlist) - 1
Local $obj = $openlist[$i]
If $node[2] < $obj[2] Then
_ArrayInsert($openlist, $i + 1, $node)
Return
EndIf
Next
_Add_List($openlist, $node)
EndFunc   ;==>_Insert_PQ

Edited December 31, 2014 by Triblade

Gianni · January 1, 2015

I just changed the following lines and it seems to work again with new AutoiT version.
lines changed: 32, 33, 35, 390, 391, 429

In short. I just Changed the lines containing the _ArrayCreate() function now no more available
with the direct array creation sintax, allowed by new versions of AutoIt

Here the changed line

Global $barrier = [-1] ; ex line 32 Global $barrier = _ArrayCreate(-1)
Global $data[16][16] ; ex line 33 Dim $data[16][16]
Global $gridboxes = ["none"] ; ex line 35 Dim $gridboxes = _ArrayCreate("none")
Local $openlist = ["empty"] ; ex line 390 Local $openlist = _ArrayCreate("empty") ;start with empty open list
Local $closedlist = ["empty"] ; ex line 391 Local $closedlist = _ArrayCreate("empty") ;start with empty closed list
Local $path = [$ending_node[0]] ; ex line 429 Local $path = _ArrayCreate($ending_node[0]) ;start from goal node

Here the whole script modified as indicated in the above lines

;==============================
; Author: Toady
; Site: www.itoady.com
; Updated: May 21, 2008
; AutoIt Ver: 3.2.12.0
;
; A * Searching Alorithm
; Artificial Intelligence
; Robot path finding
;==============================
#include <array.au3>
#include <StaticConstants.au3>
#include <GuiConstants.au3>
#include <WindowsConstants.au3>

;==================== START OF MAIN =================
; Example GUI by, Hallman and Toady

ProcessSetPriority("Autoit3.exe", 4)
Global $first_label = 0
Global $last_label = 0

Global Const $rows = 16
Global Const $cols = 16

Global $estimate
Global $closedList_data
Global $closedList_Str = "_"
Global $openList_Str = "_"
Global $start_handel[3]
Global $end_handel[3]
Global $barrier = [-1] ; Global $barrier = _ArrayCreate(-1)
Global $data[16][16] ; Dim $data[16][16]
$MainWindow = GUICreate("A * Search Algorithm - Bot pathing", 400, 540)
Global $gridboxes = ["none"] ; Dim $gridboxes = _ArrayCreate("none")
For $i = 1 To 16 Step 1
    For $ii = 1 To 16 Step 1
        If $i <> 1 And $i <> 16 And $ii <> 1 And $ii <> 16 Then
            $temp = GUICtrlCreateLabel("", (($i - 1) * 25), (($ii - 1) * 25), 25, 25, $SS_SUNKEN )
            _ArrayAdd($gridboxes, $temp)
            GUICtrlSetBkColor(-1, 0x000000)
        Else
            $temp = GUICtrlCreateLabel("", (($i - 1) * 25), (($ii - 1) * 25), 25, 25)
            GUICtrlSetBkColor(-1, 0x0220099)
        EndIf
        $data[$i - 1][$ii - 1] = "x"
        If $i = 1 And $ii = 1 Then
            $first_label = $temp
            $start_handel[0] = $temp
            $start_handel[1] = 1
            $start_handel[2] = 1
        EndIf
        If $i = 16 And $ii = 16 Then
            $last_label = $temp
            $end_handel[0] = $temp
            $end_handel[1] = 16
            $end_handel[2] = 16
        EndIf
        If $ii = 1 Or $ii = 16 Then
            _ArrayAdd($barrier, $temp)
        EndIf
    Next
Next

Dim $map = $data
Dim $resetData = $data

$Wall_Radio = GUICtrlCreateRadio("Wall", 90, 410, 50, 20)
GUICtrlSetState($Wall_Radio, $GUI_CHECKED)
$Space_Radio = GUICtrlCreateRadio("Flat ground", 10, 410, 80, 20)
$sand_Radio = GUICtrlCreateRadio("Sand", 10, 450, 70, 20)
$water_Radio = GUICtrlCreateRadio("Water", 10, 475, 70, 20)
$hill_Radio = GUICtrlCreateRadio("Hill", 10, 500, 70, 20)
$Start_Radio = GUICtrlCreateRadio("Start", 150, 410, 70, 20)
$End_Radio = GUICtrlCreateRadio("Goal", 220, 410, 70, 20)
GUICtrlSetBkColor($End_Radio, 0xff0000)
GUICtrlCreateGroup("Searching Heuristic", 80, 435, 200, 100)
$md_Radio = GUICtrlCreateRadio("Manhattan", 100, 450, 70, 20)
GUICtrlSetState(-1, $GUI_CHECKED)
$ed_Radio = GUICtrlCreateRadio("Euclidean", 180, 450, 70, 20)
GUICtrlCreateGroup("", -99, -99, 1, 1)  ;close group
GUICtrlSetBkColor($Start_Radio, 0x00ff00)
GUICtrlSetBkColor($End_Radio, 0xff0000)
$show_searched_nodes = GUICtrlCreateCheckbox("Show searched nodes (SN)", 100, 470)
$allow_diagonals = GUICtrlCreateCheckbox("Allow diagonal moves", 100, 490)
$allow_overestimate = GUICtrlCreateCheckbox("Overestimate", 100, 510)
GUICtrlSetTip($allow_overestimate, "Faster, no guaranteed shortest path")
$go_btn = GUICtrlCreateButton("Go!", 300, 410, 80, 20)
$reset_btn = GUICtrlCreateButton("Reset", 300, 435, 80, 20)
GUICtrlCreateLabel("Total cost:", 300, 470)
$total_cost = GUICtrlCreateLabel("0", 355, 470, 40)
GUICtrlCreateLabel("Nodes:", 300, 490)
$total_nodes = GUICtrlCreateLabel("0", 355, 490, 40)
GUICtrlCreateLabel("Time (ms):", 300, 510)
$total_time = GUICtrlCreateLabel("0", 355, 510, 40)
Global $Sel_Type = 1
GUISetState()

While 1
    $msg = GUIGetMsg()
    Select
        Case $msg = $GUI_EVENT_CLOSE
            Exit
        Case $msg = $go_btn
            $buffer = ""
            $closedList_Str = "_"
            $openList_Str = "_"
            Global $heuristic = BitAND(GUICtrlRead($md_Radio), $GUI_CHECKED)
            $SLocation = _GetStartingLocation($data, $rows, $cols) ;starting location
            $GLocation = _GetGoalLocation($data, $rows, $cols) ;goal location
            If $SLocation = 0 Or $GLocation = 0 Then
                MsgBox(0, "Error", "A Goal and a Start must be placed")
                $map = $data
            Else
                Dim $temp[16][16]
                $temp = $data
                Local $allow_overestimate_Boolean = BitAND(GUICtrlRead($allow_overestimate), $GUI_CHECKED)
                If $allow_overestimate_Boolean = 1 Then
                    $estimate = 1.001 ;used to overestimate heuristic by a small amount
                Else
                    $estimate = 1
                EndIf
                Global $allow_diagonals_Boolean = BitAND(GUICtrlRead($allow_diagonals), $GUI_CHECKED)
                SplashTextOn("A * Algorithm processing", "Please wait until bot is finished", 200, 100)
                GUICtrlSetState($go_btn, $GUI_DISABLE)
                GUICtrlSetState($reset_btn, $GUI_DISABLE)
                $map = $data
                _CreateMap($data, $cols, $rows) ;replaces data with node objects
                Local $timer = TimerInit()
                Dim $path = _FindPath($data, $data[$SLocation[1]][$SLocation[0]], $data[$GLocation[1]][$GLocation[0]])
                Local $timerend = TimerDiff($timer)
                $closedList_data = StringSplit($closedList_Str, '_', 1) ;not part of algorithm, used in gui
                GUICtrlSetData($total_nodes, UBound($closedList_data) - 4) ;used in gui also
                GUICtrlSetData($total_time, Round($timerend, 0))
                SplashOff()
                ;display searched nodes
                Local $show_searched_Boolean = BitAND(GUICtrlRead($show_searched_nodes), $GUI_CHECKED)
                If $show_searched_Boolean Then
                    Dim $searchedNodes[UBound($closedList_data) ]
                    For $i = 3 To UBound($closedList_data) - 3
                        Local $coord = StringSplit($closedList_data[$i], ",")
                        Local $coord_last = StringSplit($closedList_data[$i - 1], ",")
                        $searchedNodes[$i] = GUICtrlCreateLabel(" SN", $coord[1] * 25, $coord[2] * 25, 25, 25, BitOR($SS_SUNKEN, $SS_CENTERIMAGE))
                        ;GUICtrlSetBkColor(-1, $GUI_BKCOLOR_TRANSPARENT) ;uses this if you want transparent nodes
                        GUICtrlSetBkColor(-1, 0xFFFF00)
                        Sleep(100)
                    Next
                EndIf
                If IsArray($path) Then ;if path exists
                    Dim $trail[UBound($path) ]
                    $label = GUICtrlCreateLabel("", 0, 0, 25, 25)
                    Local $last_temp[3] = [2, 1, 1]
                    For $i = 0 To (UBound($path) - 1) Step 1
                        If UBound($path) = 1 Then
                            Local $nextToCoord = StringSplit($path[0], ",")
                            GUICtrlSetPos($label, $nextToCoord[1] * 25, $nextToCoord[2] * 25)
                            GUICtrlSetBkColor(-1, 0xccffff)
                            GUICtrlSetData($total_cost, 1)
                            ExitLoop
                        EndIf
                        $temp = $path[$i]
                        $temp = StringSplit(StringReplace($temp, "|", ""), ",")
                        If $i > 0 Then
                            $last_temp = $path[$i - 1]
                            $last_temp = StringSplit(StringReplace($last_temp, "|", ""), ",")
                        EndIf
                        GUICtrlSetPos($label, $temp[2] * 25, $temp[1] * 25)
                        GUICtrlSetBkColor(-1, 0xccffff)
                        $trail[$i] = GUICtrlCreateLabel("", $temp[2] * 25, $temp[1] * 25, 25, 25, $SS_SUNKEN)
                        GUICtrlSetBkColor($trail[$i], 0x00dddd)
                        Local $obj = $data[$temp[2]][$temp[1]]
                        GUICtrlSetData($total_cost, Round($obj[3], 2))
                        If Abs($temp[1] - $last_temp[1]) + Abs($temp[2] - $last_temp[2]) < 2 Then
                            Sleep(200)
                        Else
                            Sleep(280) ;delay a little long to make animation smooth
                        EndIf
                    Next
                    Sleep(500)
                    GUICtrlDelete($label)
                    For $i = 0 To UBound($path) - 1
                        GUICtrlDelete($trail[$i])
                    Next
                    If $show_searched_Boolean Then
                        If IsArray($searchedNodes) Then
                            For $i = 0 To UBound($searchedNodes) - 1
                                GUICtrlDelete($searchedNodes[$i])
                            Next
                        EndIf
                    EndIf
                    GUICtrlSetState($Wall_Radio, $GUI_CHECKED)
                    $data = $map
                Else
                    MsgBox(0, "", "No path to goal") ;if goal can't be reached
                    If $show_searched_Boolean Then
                        If IsArray($searchedNodes) Then
                            For $i = 0 To UBound($searchedNodes) - 1
                                GUICtrlDelete($searchedNodes[$i])
                            Next
                        EndIf
                    EndIf
                    $data = $map
                    GUICtrlSetState($Wall_Radio, $GUI_CHECKED)
                    $Sel_Type = 1
                EndIf
                GUICtrlSetState($go_btn, $GUI_ENABLE)
                GUICtrlSetState($reset_btn, $GUI_ENABLE)
            EndIf
        Case $msg >= $first_label + 16 And $msg <= $last_label - 16 And _ArraySearch($barrier, $msg) < 0
            $sel_X = Ceiling(($msg - $first_label + 1) / 16)
            $sel_Y = Ceiling($msg - $first_label + 1) - ($sel_X - 1) * 16
            If $Sel_Type = 1 Then
                GUICtrlSetBkColor($msg, 0x000000)
                $data[$sel_X - 1][$sel_Y - 1] = "x"
            ElseIf $Sel_Type = 2 Then
                GUICtrlSetBkColor($msg, 0xeeeeee)
                $data[$sel_X - 1][$sel_Y - 1] = "1"
            ElseIf $Sel_Type = 3 Then
                If $data[$start_handel[1] - 1][$start_handel[2] - 1] = "s" Then
                    GUICtrlSetBkColor($start_handel[0], 0xeeeeee)
                    $data[$start_handel[1] - 1][$start_handel[2] - 1] = "1"
                EndIf
                $start_handel[0] = $msg
                $start_handel[1] = $sel_X
                $start_handel[2] = $sel_Y
                GUICtrlSetBkColor($msg, 0x00ff00)
                $data[$sel_X - 1][$sel_Y - 1] = "s"
            ElseIf $Sel_Type = 4 Then
                If $data[$end_handel[1] - 1][$end_handel[2] - 1] = "g" Then
                    GUICtrlSetBkColor($end_handel[0], 0xeeeeee)
                    $data[$end_handel[1] - 1][$end_handel[2] - 1] = "1"
                EndIf
                $end_handel[0] = $msg
                $end_handel[1] = $sel_X
                $end_handel[2] = $sel_Y
                GUICtrlSetBkColor($msg, 0xff0000)
                $data[$sel_X - 1][$sel_Y - 1] = "g"
            ElseIf $Sel_Type = 5 Then;sand
                GUICtrlSetBkColor($msg, 0xFFdd44)
                $data[$sel_X - 1][$sel_Y - 1] = "2" ;2 times harder than flat ground
            ElseIf $Sel_Type = 6 Then;water
                GUICtrlSetBkColor($msg, 0x2222FF)
                $data[$sel_X - 1][$sel_Y - 1] = "3" ;3 times harder than flat ground
            ElseIf $Sel_Type = 7 Then;hill
                GUICtrlSetBkColor($msg, 0x885500)
                $data[$sel_X - 1][$sel_Y - 1] = "4" ;4 times harder than flat ground
            EndIf
        Case $msg = $Wall_Radio
            $Sel_Type = 1
        Case $msg = $Space_Radio
            $Sel_Type = 2
        Case $msg = $Start_Radio
            $Sel_Type = 3
        Case $msg = $End_Radio
            $Sel_Type = 4
        Case $msg = $sand_Radio
            $Sel_Type = 5
        Case $msg = $water_Radio
            $Sel_Type = 6
        Case $msg = $hill_Radio
            $Sel_Type = 7
        Case $msg = $reset_btn
            $data = $resetData
            For $i = 1 To UBound($gridboxes) - 1
                GUICtrlSetBkColor($gridboxes[$i], 0x000000)
            Next
            GUICtrlSetData($total_cost, "0")
            GUICtrlSetData($total_nodes, "0")
            GUICtrlSetData($total_time, "0")
    EndSelect
WEnd
;==================== END OF MAIN =================

;============ * How to use this code * ============
; Below is the A * Searching algorithm and its
; required functions to work.
; This is coded to work with 2D spaces only.
; Everything below is all you need to get started.

; 1. Initialize a 2D array
;     $data[5][5] = [["x","x","x","x","x"], _
;                    ["x","s","0","x","x"], _
;                    ["x","x","0","x","x"], _
;                    ["x","x","0","g","x"], _
;                    ["x","x","x","x","x"]]
;       NOTE: Array MUST have x's around entire paremeter
;       There must be a "s" and a "g". "0" means bot can walk here
; 2. Convert array into node objects
;       _CreateMap($data,5,5)
; 3. Calculate path
;       Dim $path = _FindPath($data,$data[1][1],$data[3][3])
; 4. Thats all!
;       The variable $path contains an array of the path in "x,y" format
;       _ArrayDisplay($path) will show the the full path
;==================================================

;=============================================================================
; Replaces data grid with node objects
; Converts $data into a 2D array of node objects from previous $data array
; consisting of only string characters.
;=============================================================================
Func _CreateMap(ByRef $data, $x, $y) ;converts a 2D array of data to node objects
    For $i = 0 To $y - 1 ;for each row
        For $j = 0 To $x - 1 ;for each column
            If StringRegExp($data[$i][$j], "[x,s,g]") <> 1 Then;if not a x,s,g
                $data[$i][$j] = _CreateNode($i & "," & $j, "null", 0, $data[$i][$j], 0, $data[$i][$j])
            Else
                If $data[$i][$j] = "s" Then
                    $data[$i][$j] = _CreateNode($i & "," & $j, "null", 0, 0, 0, $data[$i][$j])
                Else
                    $data[$i][$j] = _CreateNode($i & "," & $j, "null", 0, 1, 0, $data[$i][$j])
                EndIf
            EndIf
        Next
    Next
EndFunc   ;==>_CreateMap
;=============================================================================
; Creates a node struct object with the following parameters
; struct node {
;   char self_coord[8];          // Format = "x,y"
;   char parent_coord[8];        // Format = "x,y"
;   int f;                       // F = G + H
;   int g;                       // G = current cost to this node from start node
;   int h;                       // H = Heuristic cost, this node to goal node
;   char value[8];               // Type of node (ex. "s","g","x","1,2,3..n")
;   int cost;                    // Cost of node (difficulty of traveling on this)
; }
;=============================================================================
Func _CreateNode($self, $parent, $f, $g, $h, $value) ;returns struct object
    Local $node[6] = [$self, $parent, $f, $g, $h, $value]
    Return $node
EndFunc   ;==>_CreateNode
;=============================================================================
; Checks to see if start node exists in map
; Returns an array: [y,x]
;=============================================================================
Func _GetStartingLocation(ByRef $data, $cols, $rows)
    For $i = 0 To $cols - 1
        For $j = 0 To $rows - 1
            If $data[$i][$j] = "s" Then
                Local $pos[2] = [$j, $i]
                Return $pos
            EndIf
        Next
    Next
    Return 0 ;no starting location found
EndFunc   ;==>_GetStartingLocation
;=============================================================================
; Checks to see if goal node exists in map
; Returns an array: [y,x]
;=============================================================================
Func _GetGoalLocation(ByRef $data, $cols, $rows)
    For $i = 0 To $cols - 1
        For $j = 0 To $rows - 1
            If $data[$i][$j] = "g" Then
                Local $pos[2] = [$j, $i]
                Return $pos
            EndIf
        Next
    Next
    Return 0 ;no starting location found
EndFunc   ;==>_GetGoalLocation
;=============================================================================
; Calculates the manhattan distance between two nodes
; MD = |G(x) - N(x)| + |G(y) - N(x)|
; Returns an integer
;=============================================================================
Func _MD(ByRef $node, ByRef $goal) ;returns integer
    Local $node_coord = StringSplit($node[0], ",") ;current node
    Local $goal_coord = StringSplit($goal[0], ",") ;goal node
    Return (Abs($goal_coord[1] - $node_coord[1]) + Abs($goal_coord[2] - $node_coord[2])) * $estimate
EndFunc   ;==>_MD
;=============================================================================
; Calculates the Euclidean distance between two nodes
; MD = SquareRoot ( (G(x) - N(x))^2 + (G(y) - N(x))^2 )
; Returns an integer
;=============================================================================
Func _ED(ByRef $node, ByRef $goal) ;returns integer
    Local $node_coord = StringSplit($node[0], ",") ;current node
    Local $goal_coord = StringSplit($goal[0], ",") ;goal node
    Return Sqrt(($goal_coord[1] - $node_coord[1]) ^ 2 + ($goal_coord[2] - $node_coord[2]) ^ 2) * $estimate
EndFunc   ;==>_ED
;=============================================================================
; A * Searching Algorithm
; Keep searching nodes until the goal is found.
; Returns: Array if path found
; Returns: 0 if no path
;=============================================================================
Func _FindPath(ByRef $map, $start_node, $goal_node) ;returns array of coords
    Local $openlist = ["empty"] ; Local $openlist = _ArrayCreate("empty") ;start with empty open list
    Local $closedlist = ["empty"] ; Local $closedlist = _ArrayCreate("empty") ;start with empty closed list
    Local $current_node = $start_node ;set current node to start nodeF
    $closedList_Str &= $current_node[0] & "_"
    $openList_Str &= $current_node[0] & "_"
    _AddAdjacents_Openlist($map, $openlist, $closedlist, $current_node, $goal_node) ;add all possible adjacents to openlist
    While 1 ;while goal is not in closed list, or open list is not empty
        If UBound($openlist) = 1 Then ExitLoop ;if open list is empty then no path found
        $current_node = _GetLowest_F_Cost_Node($openlist) ;pick node with lowest F cost
        $closedList_Str &= $current_node[0] & "_"
        _AddAdjacents_Openlist($map, $openlist, $closedlist, $current_node, $goal_node) ;add all possible adjacents to openlist
        If $current_node[0] = $goal_node[0] Then ExitLoop ;if current node is goal then path is found!
    WEnd
    If _IsInClosedList($goal_node[0]) = 0 Then ;if no goal found then return 0
        Return 0 ; no path found
    Else
        Return _GetPath($map, $current_node, $start_node) ;return array of coords (x,y) in string format
    EndIf
EndFunc   ;==>_FindPath
;=============================================================================
; Returns node object with the lowest F cost
; F = G + H
; Returns 0 with openlist is emtpy, there is no path
;=============================================================================
Func _GetLowest_F_Cost_Node(ByRef $openlist)
    If UBound($openlist) > 1 Then ;If open list is not empty
        Local $obj = $openlist[1] ;Pop first item in the queue
        _ArrayDelete($openlist, 1) ;remove this node from openlist
        Return $obj ;return lowest F cost node
    EndIf
    Return 0 ;openlist is empty
EndFunc   ;==>_GetLowest_F_Cost_Node
;=============================================================================
; Start from goal node and traverse each parent node until starting node is
; reached.
; Each node will have a parent node (use this to get path bot will take)
; Returns: Array of coords, first index is starting location
;=============================================================================
Func _GetPath(ByRef $data, ByRef $ending_node, ByRef $start_node)
    Local $path = [$ending_node[0]] ; Local $path = _ArrayCreate($ending_node[0]) ;start from goal node
    Local $node_coord = StringSplit($path[0], ",")
    Local $x = $node_coord[1]
    Local $y = $node_coord[2]
    Local $start = $start_node[0] ;starting nodes coord
    Local $obj = $data[$x][$y] ;current node starting from the goal
    While $obj[1] <> $start ;keep adding until reached starting node
        _Add_List($path, $y & "," & $x) ;add the parent node to the list
        $obj = $data[$x][$y] ;get node from 2D data array
        $node_coord = StringSplit($obj[1], ",")
        If $node_coord[0] = 1 Then ExitLoop
        $x = $node_coord[1]
        $y = $node_coord[2]
    WEnd
    _ArrayDelete($path, 0) ;no need to starting node
    _ArrayReverse($path) ;flip array to make starting node at index 0
    Return $path ;return path as array in "x,y" format for each item
EndFunc   ;==>_GetPath
;=============================================================================
; Adds adjacent nodes to the open list if:
; 1. Node is not a barrier "x"
; 2. Node is not in open list
; 3. Node is not in closed list
; Set newly added node's parent to the current node and update its F,G, and H
; Only need to check North, South, East and West nodes.
;=============================================================================
Func _AddAdjacents_Openlist(ByRef $data, ByRef $openlist, ByRef $closedlist, ByRef $node, ByRef $goal)
    Local $current_coord = StringSplit($node[0], ",")
    Local $x = $current_coord[1]
    Local $y = $current_coord[2]
    Local $h ; heuristic
    Local $north = 0
    Local $south = 0
    Local $east = 0
    Local $west = 0
    Local $obj = $data[$x][$y - 1]
    If $obj[5] <> "x" And _ ;north
            Not _IsInAnyList($obj[0]) Then ;If not in closed list or openlist and is not a barrier
        If $heuristic = 1 Then
            $h = _MD($obj, $goal)
        Else
            $h = _ED($obj, $goal)
        EndIf
        $obj[1] = $node[0] ;set nodes parent to last node
        $obj[3] = $node[3] + $obj[3] ;set g score (current node's G score + adjacent node's G score)
        $obj[2] = $obj[3] + $h ;set f = g + h score
        $data[$x][$y - 1] = $obj
        $north = 1
        $openList_Str &= $obj[0] & "_"
        _Insert_PQ($openlist, $obj)
    EndIf
    $obj = $data[$x][$y + 1]
    If $obj[5] <> "x" And _ ;south
            Not _IsInAnyList($obj[0]) Then
        If $heuristic = 1 Then
            $h = _MD($obj, $goal)
        Else
            $h = _ED($obj, $goal)
        EndIf
        $obj[1] = $node[0] ;set nodes parent to last node
        $obj[3] = $node[3] + $obj[3]  ;set g score (current node's G score + adjacent node's G score)
        $obj[2] = $obj[3] + $h ;set f = g + h score
        $data[$x][$y + 1] = $obj
        $south = 1
        $openList_Str &= $obj[0] & "_"
        _Insert_PQ($openlist, $obj)
    EndIf
    $obj = $data[$x + 1][$y]
    If $obj[5] <> "x" And _ ;east
            Not _IsInAnyList($obj[0]) Then
        If $heuristic = 1 Then
            $h = _MD($obj, $goal)
        Else
            $h = _ED($obj, $goal)
        EndIf
        $obj[1] = $node[0] ;set nodes parent to last node
        $obj[3] = $node[3] + $obj[3]  ;set g score (current node's G score + adjacent node's G score)
        $obj[2] = $obj[3] + $h ;set f = g + h score
        $data[$x + 1][$y] = $obj
        $east = 1
        $openList_Str &= $obj[0] & "_"
        _Insert_PQ($openlist, $obj)
    EndIf
    $obj = $data[$x - 1][$y]
    If $obj[5] <> "x" And _ ;west
            Not _IsInAnyList($obj[0]) Then
        If $heuristic = 1 Then
            $h = _MD($obj, $goal)
        Else
            $h = _ED($obj, $goal)
        EndIf
        $obj[1] = $node[0] ;set nodes parent to last node
        $obj[3] = $node[3] + $obj[3]  ;set g score (current node's G score + adjacent node's G score)
        $obj[2] = $obj[3] + $h ;set f = g + h score
        $data[$x - 1][$y] = $obj
        $west = 1
        $openList_Str &= $obj[0] & "_"
        _Insert_PQ($openlist, $obj)
    EndIf
    ;diagonals moves
    If $allow_diagonals_Boolean Then ;if GUI checkbox is checked, then check other 4 directions
        If $north + $east = 2 Then ;Not allowed to cut around corners, not realistic
            $obj = $data[$x + 1][$y - 1]
            If $obj[5] <> "x" And _ ;northeast
                    Not _IsInAnyList($obj[0]) Then
                If $heuristic = 1 Then
                    $h = _MD($obj, $goal)
                Else
                    $h = _ED($obj, $goal)
                EndIf
                $obj[1] = $node[0] ;set nodes parent to last node
                $obj[3] = $node[3] + (Sqrt(2) * $obj[3])  ;set g score (current node's G score + adjacent node's G score* Sqrt(2))
                $obj[2] = $obj[3] + $h ;set f = g + h score
                $data[$x + 1][$y - 1] = $obj
                $openList_Str &= $obj[0] & "_"
                _Insert_PQ($openlist, $obj)
            EndIf
        EndIf
        If $north + $west = 2 Then
            $obj = $data[$x - 1][$y - 1]
            If $obj[5] <> "x" And _ ;north west
                    Not _IsInAnyList($obj[0]) Then
                If $heuristic = 1 Then
                    $h = _MD($obj, $goal)
                Else
                    $h = _ED($obj, $goal)
                EndIf
                $obj[1] = $node[0] ;set nodes parent to last node
                $obj[3] = $node[3] + (Sqrt(2) * $obj[3])  ;set g score (current node's G score + adjacent node's G score* Sqrt(2))
                $obj[2] = $obj[3] + $h  ;set f = g + h score
                $data[$x - 1][$y - 1] = $obj
                $openList_Str &= $obj[0] & "_"
                _Insert_PQ($openlist, $obj)
            EndIf
        EndIf
        If $south + $east = 2 Then
            $obj = $data[$x + 1][$y + 1]
            If $obj[5] <> "x" And _ ;southeast
                    Not _IsInAnyList($obj[0]) Then
                If $heuristic = 1 Then
                    $h = _MD($obj, $goal)
                Else
                    $h = _ED($obj, $goal)
                EndIf
                $obj[1] = $node[0] ;set nodes parent to last node
                $obj[3] = $node[3] + (Sqrt(2) * $obj[3])  ;set g score (current node's G score + adjacent node's G score)
                $obj[2] = $obj[3] + $h  ;set f = g + h score
                $data[$x + 1][$y + 1] = $obj
                $openList_Str &= $obj[0] & "_"
                _Insert_PQ($openlist, $obj)
            EndIf
        EndIf
        If $south + $west = 2 Then
            $obj = $data[$x - 1][$y + 1]
            If $obj[5] <> "x" And _ ;southwest
                    Not _IsInAnyList($obj[0]) Then
                If $heuristic = 1 Then
                    $h = _MD($obj, $goal)
                Else
                    $h = _ED($obj, $goal)
                EndIf
                $obj[1] = $node[0] ;set nodes parent to last node
                $obj[3] = $node[3] + (Sqrt(2) * $obj[3])  ;set g score (current node's G score + adjacent node's G score)
                $obj[2] = $obj[3] + $h  ;set f = g + h score
                $data[$x - 1][$y + 1] = $obj
                $openList_Str &= $obj[0] & "_"
                _Insert_PQ($openlist, $obj)
            EndIf
        EndIf
    EndIf
EndFunc   ;==>_AddAdjacents_Openlist
;=============================================================================
; Returns true if node is in closed list
; Search the list backwards, its faster
;=============================================================================
Func _IsInClosedList(ByRef $node)
    If StringRegExp($closedList_Str, "_" & $node & "_") Then
        Return 1
    Else
        Return 0
    EndIf
EndFunc   ;==>_IsInClosedList
;=============================================================================
; Returns true if node is in open list
; Regular expressions are used rather than searching an array list for speed.
;=============================================================================
Func _IsInAnyList(ByRef $node)
    If StringRegExp($openList_Str, "_" & $node & "_") Then
        Return 1
    Else
        Return 0
    EndIf
EndFunc   ;==>_IsInAnyList
;=============================================================================
; Inserts object into openlist and preserves ascending order
; This way will result in a priority queue with the lowest F cost at
; position 1 in the openlist array.
;=============================================================================
Func _Insert_PQ(ByRef $openlist, $node)
    Local $obj
    For $i = 1 To UBound($openlist) - 1
        Local $obj = $openlist[$i]
        If $node[2] < $obj[2] Then
            _ArrayInsert($openlist, $i, $node)
            Return
        EndIf
    Next
    _Add_List($openlist, $node)
EndFunc   ;==>_Insert_PQ
;=============================================================================
; Adds nodes the a list
;=============================================================================
Func _Add_List(ByRef $list, $node)
    ReDim $list[UBound($list) + 1]
    $list[UBound($list) - 1] = $node
EndFunc   ;==>_Add_List
;============================================================================
; End of Algorithm
;============================================================================

Edited January 1, 2015 by Chimp

Toady · December 1, 2015

Thanks Chimp for the fixes and getting this running with the latest version of AutoIt.

I've updated the script on the main post.

UEZ · December 1, 2015

I'm getting this error message:

Line 633  (File "C:\_Downloads\A_Star.au3"):

If $node[2] < $obj[2] Then
If $node[2] < $obj^ ERROR

Error: Subscript used on non-accessible variable.

Here the map:

Sign In

Artificial Intelligence - Bot path finding

Recommended Posts

Fabry

Top Posters In This Topic

Top Posters In This Topic

Popular Posts

Toady

Gianni

Posted Images

zxzxzx

Toady

BillLuvsU

TnTProductions

WeMartiansAreFriendly

Simucal

Triblade

Hawkwing

Shanheavel

Mat

cembry90

twitchyliquid64

mehul

00000

iFFgen

Triblade

Gianni

Toady

UEZ

Create an account or sign in to comment

Create an account

Sign in

Recently Browsing 0 members

Browse

AutoIt Resources

Release

Beta