Path Finding Bot

[Linux]

Hi all!

I created this code to find the best path between 2 point given by the user, using recursive function (the function CALC, calls itself inside)

The $field array is random( 0 = plain terrain, 99 = hilly terrain). This could reflect time or fuel used to travel that square. This is only an example. If you plan to use PathFinding you should also take a look at Toady Example HERE because the example I'm posting takes more time/iteractions.

This code can be improved to use GUI, User Selected Array, more speed, diagonal moves and other features.

ALLOWED TWEAKS:

You can change the size of the array, the starting point, End point, and $MaxSteps.

expandcollapse popup

#cs ----------------------------------------------------------------------------
    
    AutoIt Version: 3.2.12.0
    Author:         Linux
    
    Script Function: This Script will find the best path from the starting point to the finish point, using recursive function
    
#ce ----------------------------------------------------------------------------
#include <array.au3>
Global $Field[12][12]
Global $StartPoint = "0/0" ; Upper Left
Global $Endpoint = "10/10" ; 
Global $MaxSteps = 100 ; this is used to speed up the pathfinding
Global $Max_x = UBound($Field, 1) - 1
Global $Max_y = UBound($Field, 2) - 1
Global $Lowest = 99*$Max_x * $Max_y, $LowestPath = ""
Global $TotalNodeschecked = 0, $TotalPaths = 0,$LastSec = @sec,$lastnodes = 0

For $node_y = 0 To $Max_y
    For $node_x = 0 To $Max_x
        $Field[$node_x][$node_y] = Floor(Random() * 99)+1 ; 0 = plain, 100 = hilly
        ;this can be time used, Fuel used or any other factor
    Next
Next
;_ArrayDisplay($Field, "FIELD CONFIGURATION")
Global $timer = TimerInit()
Local $_TempArray = StringSplit($StartPoint,"/")
Calc($StartPoint, 0, $Field[number($_TempArray[1])][number($_TempArray[2])],number($_TempArray[1]),number($_TempArray[2]))
If $LowestPath = "" Then
    ConsoleWrite("Path not found! Try a higher $MaxSteps Value!")
    Exit
EndIf
ConsoleWrite(@CRLF & "Time: " & Floor(TimerDiff($timer)) & " ms")
ConsoleWrite(@CRLF & "Total Nodes: " & $TotalNodeschecked)
ConsoleWrite(@CRLF & "Total Paths: " & $TotalPaths)
ConsoleWrite(@CRLF & "Lowest Total: " & $Lowest)
ConsoleWrite(@CRLF & "Lowest Path: " &@crlf &  $LowestPath)
_ArrayDisplay($Field, "FIELD CONFIGURATION")

Func Calc($Path, $Step, $Total,$Node_x,$node_y)
    $TotalNodeschecked += 1 ; DEBUG ONLY
    $Step += 1
    ;#cs ; DEBUG ONLY 
    If @sec <> $LastSec Then
        ConsoleWrite(@crlf & "Sec: " & @sec & " Nodes per second: " & $TotalNodeschecked - $lastnodes)
        if $LowestPath <> "" then ConsoleWrite (" Paths: " & $TotalPaths & " LowestTotal: " & $Lowest)
        $LastSec = @SEC
        $lastnodes = $TotalNodeschecked
    EndIf
    ;#ce
    $Total += $Field[$Node_x][$node_y] ; add the node value to the total.
    If $Step > $MaxSteps or $total >= $Lowest Then Return 0 ; Speed up code
    If $node_x & "/" & $node_y = $Endpoint Then ; Path Found! 
        $TotalPaths += 1 
        If $Lowest > $Total Then ;If its lower
            $LowestPath = $Path ; SAVE CURRENT PATH
            $Lowest = $Total
        EndIf
        Return 0
    EndIf
    ;GO Down
    If $node_x < $Max_x And Not StringInStr($Path, $node_x + 1 & "/" & $node_y) And $Total + $Field[$node_x + 1][$node_y] < $Lowest Then Calc($Path & " Down " & $node_x + 1 & "/" & $node_y, $Step, $Total, $node_x + 1, $node_y)
    ;GO Right
    If $node_y < $Max_y And Not StringInStr($Path, $node_x & "/" & $node_y + 1) And $Total + $Field[$node_x][$node_y + 1] < $Lowest Then Calc($Path & " Right " & $node_x & "/" & $node_y + 1, $Step, $Total, $node_x , $node_y + 1)
    ;GO up
    If $node_y > 0 And Not StringInStr($Path, $node_x & "/" & $node_y - 1) And $Total + $Field[$node_x][$node_y - 1] < $Lowest Then Calc($Path & " Up " & $node_x & "/" & $node_y - 1, $Step, $Total,$node_x ,$node_y - 1)
    ;Go Left
    If $node_x > 0 And Not StringInStr($Path, $node_x - 1 & "/" & $node_y) And $Total + $Field[$node_x - 1][$node_y] < $Lowest Then Calc($Path & " Left " & $node_x - 1 & "/" & $node_y, $Step, $Total,$node_x - 1, $node_y)
EndFunc   ;==>Calc

Feel free to post your comments/critics here

[Zinthose]

Can you provide an example of it's use?

I'm not quite sure what this dose.

^{Never mind... I see the link to the example.}

Is this the beginning of a Real Time Strategy AI engine?

Edited June 19, 2008 by Zinthose

[Nbanonimous]

I dont understand...

[Linux]

This code will generate an array 12x12, with numbers between 1 and 99. that number can reflect the time used for a bot to travel that square. Sometimes the shortest path, isnt the quickest path, and there is a longest/quicker path.

This code will generate the random field, and then find the FASTEST path between 2 points!

1- Open the code.

2- Run the code.

3-Wait for it to generate random field, and search the quickest path. The quickest path is the one with the lowest SUM of the squares it uses to travel from Start point to End point. The code will try all combos, but it will preffer the squares with the lowest values.

Edited June 19, 2008 by Linux