# Path Finding Bot

## Recommended Posts

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.

```#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
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```

You can help! Donate to AutoIt! or, visit ClimatePREDICTION.netMy posts:Travian Bot Example (100+ servers) BETAHow to Host you code/app for free! (unlimited team number) (Public or Private)"Sir, we're surrounded!" "Excellent. We can attack in any direction!"

##### Share on other sites

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 by Zinthose

--- TTFN

##### Share on other sites

I dont understand...

##### Share on other sites

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 by Linux

You can help! Donate to AutoIt! or, visit ClimatePREDICTION.netMy posts:Travian Bot Example (100+ servers) BETAHow to Host you code/app for free! (unlimited team number) (Public or Private)"Sir, we're surrounded!" "Excellent. We can attack in any direction!"

## Create an account

Register a new account

×

• Wiki

• Back

• Git