Artificial Intelligence - Bot path finding

[ConsultingJoe]

Ok this is starting to piss me off. I am just trying to make this without the gui right now, this is what i got, can you help me out on this but just giving me a simply start. thanks

expandcollapse popup

#include <array.au3>
Global $heuristic = 1
Global $rows = 3
Global $cols = 3
Dim $data[4]
$data[0] = "xxsx"
$data[1] = "xx  "
$data[2] = "xxx "
$data[3] = "xg  "
For $a = 0 To 3
$data[$a] = StringSplit( $data[$a], "" )
Next
_CreateMap($data,$rows,$cols)
;$SLocation = _GetStartingLocation($data,$rows,$cols) ;starting location
;$GLocation = _GetGoalLocation($data,$rows,$cols) ;goal location

;=============================================================================
; Replaces data grid with node objects
;=============================================================================
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
            $data[$i][$j] = _CreateNode($i & "," & $j,"null",0,0,0,$data[$i][$j])
        Next
    Next
EndFunc
;=============================================================================
; Creates a node struct object with the following parameters
; struct node {
;   char self_coord[8];
;   char parent_coord[8];
;   int f;
;   int g;
;   int h;
;   int value[8];
; }
;=============================================================================
Func _CreateNode($self, $parent, $f, $g, $h, $value) ;returns struct object
    Local $node[6] = [$self,$parent,$f,$g,$h,$value]
    Return $node
EndFunc
;=============================================================================
; Deletes the node objects
;=============================================================================
Func _DestoryObjects($data,$rows,$cols)
    For $i = 0 To $rows - 1
        For $j = 0 To $cols - 1
            $data[$i][$j] = 0
        Next
    Next
EndFunc
;=============================================================================
; 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
;=============================================================================
; 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
;=============================================================================
; Calculates the manhattan distance between two nodes
; Returns an integer
;=============================================================================
Func _MD(ByRef $node, ByRef $goal) ;returns integer
    Local $node_coord = StringSplit($node[0],",")
    Local $goal_coord = StringSplit($goal[0],",")
    Return (Abs($goal_coord[1] - $node_coord[1]) + Abs($goal_coord[2] - $node_coord[2]))
EndFunc
;=============================================================================
; Calculates the Euclidean distance between two nodes
; Returns an integer
; Note:
;=============================================================================
Func _ED(ByRef $node, ByRef $goal) ;returns integer
    Local $node_coord = StringSplit($node[0],",")
    Local $goal_coord = StringSplit($goal[0],",")
    Return Round(Sqrt((Abs($goal_coord[1] - $node_coord[1]))^2 + (Abs($goal_coord[2] - $node_coord[2]))^2),2)
EndFunc
;=============================================================================
; A * Searching Algorithm
; 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 node
    _ArrayAdd($openlist,$current_node) ;add current node to openlist
    _ArrayAdd($closedlist,$current_node[0]) ;add starting node to closedlist
    _RemoveFromOpenlist($openlist,$start_node) ;remove starting node from openlist
    _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
        _ArrayAdd($closedlist,$current_node[0]) ;add current node to closedlist
        _RemoveFromOpenlist($openlist,$current_node) ;remove current node from openlist
        _AddAdjacents_Openlist($map,$openlist,$closedlist,$current_node,$goal_node)
        If $current_node[0] = $goal_node[0] Then ExitLoop
    WEnd
    If _IsInClosedList($closedlist,$goal_node[0]) = 0 Then
        Return 0 ; no path found
    Else
        Return _GetPath($map, $current_node, $start_node) ;return array of coords
    EndIf
EndFunc
;=============================================================================
; 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 $index = 1 ;set the default index
        Local $obj = $openlist[1]
        Local $cost = $obj[2]
        For $i = 1 To UBound($openlist) - 1
            $obj = $openlist[$i]
            If $obj[2] < $cost Then ;its F cost is lower than previous
                $cost = $obj[2] ;set this cost as lowest
                $index = $i ;update index for lowest cost node
            EndIf
        Next ;go through each item and get index of openlist with lowest F cost
        Return $openlist[$index] ;return lowest F cost node
    EndIf
    Return 0 ;openlist is empty
EndFunc
;=============================================================================
; Start from goal node and traverse each parent node until starting node is
; reached.
; 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
        _ArrayAdd($path,$y & "," & $x) ;add the parent node to the list
        $obj = $data[$x][$y]
        $node_coord = StringSplit($obj[1],",")
        If $node_coord[0] = 1 Then ExitLoop
        $x = $node_coord[1]
        $y = $node_coord[2]
    WEnd
    _ArrayDelete($path,0)
    _ArrayReverse($path)
    Return $path
EndFunc
;=============================================================================
; Returns the parent coord of a node
;=============================================================================
Func _GetParent($node) ;returns a coord string
    Return $node[1]
EndFunc
;=============================================================================
; Removes a node from the open list
;=============================================================================
Func _RemoveFromOpenlist(ByRef $openlist, ByRef $node)
    Local $obj
    For $i = 1 To UBound($openlist) - 1
        $obj = $openlist[$i]
        If $node[0] =  $obj[0] Then
             _ArrayDelete($openlist,$i)
            ExitLoop
        EndIf
    Next
EndFunc
;=============================================================================
; 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
;=============================================================================
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 $md
    Local $obj = $data[$x][$y-1]
    If $obj[5] <> "x" And _ ;north
        Not _IsInClosedList($closedlist,$obj[0]) And _
        Not _IsInOpenList($openlist,$obj) Then ;If not in closed list or openlist and is not a barrier
        If $heuristic = 1  Then
            $md = _MD($obj,$goal)
        Else
            $md = _ED($obj,$goal)
        EndIf
        $obj[1] = $node[0] ;set nodes parent to last node
        $obj[3] = $node[3]+10 ;set g score
        $obj[4] = $md ;set h score
        $obj[2] = $obj[3] + $obj[4] ;set f = g + h score
        $data[$x][$y-1] = $obj
        _ArrayAdd($openlist,$obj)
    EndIf
    $obj = $data[$x][$y+1]
    If $obj[5] <> "x" And _ ;south
        Not _IsInClosedList($closedlist,$obj[0]) And _
        Not _IsInOpenList($openlist,$obj) Then
        If $heuristic = 1  Then
            $md = _MD($obj,$goal)
        Else
            $md = _ED($obj,$goal)
        EndIf
        $obj[1] = $node[0] ;set nodes parent to last node
        $obj[3] = $node[3]+10 ;set g score
        $obj[4] = $md ;set h score
        $obj[2] = $obj[3] + $obj[4] ;set f = g + h score
        $data[$x][$y+1] = $obj
        _ArrayAdd($openlist,$obj)
    EndIf
    $obj = $data[$x+1][$y]
    If $obj[5] <> "x" And _ ;east
        Not _IsInClosedList($closedlist,$obj[0]) And _
        Not _IsInOpenList($openlist,$obj) Then
        If $heuristic = 1  Then
            $md = _MD($obj,$goal)
        Else
            $md = _ED($obj,$goal)
        EndIf
        $obj[1] = $node[0] ;set nodes parent to last node
        $obj[3] = $node[3]+10 ;set g score
        $obj[4] = $md ;set h score
        $obj[2] = $obj[3] + $obj[4] ;set f = g + h score
        $data[$x+1][$y] = $obj
        _ArrayAdd($openlist,$obj)
    EndIf
    $obj = $data[$x-1][$y]
    If $obj[5] <> "x" And _ ;west
        Not _IsInClosedList($closedlist,$obj[0]) And _
        Not _IsInOpenList($openlist,$obj) Then
        If $heuristic = 1  Then
            $md = _MD($obj,$goal)
        Else
            $md = _ED($obj,$goal)
        EndIf
        $obj[1] = $node[0] ;set nodes parent to last node
        $obj[3] = $node[3]+10 ;set g score
        $obj[4] = $md ;set h score
        $obj[2] = $obj[3] + $obj[4] ;set f = g + h score
        $data[$x-1][$y] = $obj
        _ArrayAdd($openlist,$obj)
    EndIf
EndFunc
;=============================================================================
; Returns true if node is in closed list
;=============================================================================
Func _IsInClosedList(ByRef $closedlist, ByRef $node)
    For $i = 1 To UBound($closedlist) - 1
        If $node = $closedlist[$i] Then
            Return 1
        EndIf
    Next
    Return 0
EndFunc
;=============================================================================
; Returns true if node is in open list
;=============================================================================
Func _IsInOpenList(ByRef $openlist, ByRef $node)
    Local $obj
    For $i = 1 To UBound($openlist) - 1
        $obj = $openlist[$i]
        If $node[0] = $obj[0] Then
            Return 1
        EndIf
    Next
    Return 0
EndFunc
;=============================================================================
; Sets the parent of a node
;=============================================================================
Func _SetParent(ByRef $node, ByRef $parent) ;sets a nodes parent
    $node[1] = $parent[0]
EndFunc

[Richard Robertson]

3D path finding is usually left to a 2D space, based on the ground that the characters run on. If you have unlimited freedom of movement in the 3D space, you've got a lot of work to make that path found.

[Toady]

#include <array.au3>
Global $heuristic = 1
Global $rows = 3
Global $cols = 3
Dim $data[4]
$data[0] = "xxsx"
$data[1] = "xx  "
$data[2] = "xxx "
$data[3] = "xg  "
For $a = 0 To 3
$data[$a] = StringSplit( $data[$a], "" )
Next
_CreateMap($data,$rows,$cols)

You will need to modify this to a 3D array as well as a bunch of functions and the way they create the nodes.

[ConsultingJoe]

#include <array.au3>
Global $heuristic = 1
Global $rows = 3
Global $cols = 3
Dim $data[4]
$data[0] = "xxsx"
$data[1] = "xx  "
$data[2] = "xxx "
$data[3] = "xg  "
For $a = 0 To 3
$data[$a] = StringSplit( $data[$a], "" )
Next
_CreateMap($data,$rows,$cols)

You will need to modify this to a 3D array as well as a bunch of functions and the way they create the nodes.

ok thanks but that array is giving me an error,

$data = [["x","x","x","x"], ["x","x","s","x"], ["x","g","0","x"], ["x","x","x","x"]]

$data = ^ ERROR

[Toady]

....

Global $rows = 4
Global $cols = 4
Dim $data[$rows][$cols] = [["x","x","x","x"], _
       ["x","x","s","x"], _
       ["x","g","0","x"], _
       ["x","x","x","x"]]

[ConsultingJoe]

....

Global $rows = 4
Global $cols = 4
Dim $data[$rows][$cols] = [["x","x","x","x"], _
       ["x","x","s","x"], _
       ["x","g","0","x"], _
       ["x","x","x","x"]]

Ok, now that worked, thanks

[Toady]

UPDATED:

Made the AI bot a little smarter by allowing it to compensate for terrain obstacles. The new terrain types are:

This gives it a more realistic feel, think more like a human.

Flat Ground

Sand

Water

Hill

The bot will find the shortest path with the least amount of energy to get there.

Flat ground is easier than sand, sand is easier than water, and water is easier than a hill.

Let me know what you think, colors ect..

[CoderDunn]

UPDATED:

Made the AI bot a little smarter by allowing it to compensate for terrain obstacles. The new terrain types are:

This gives it a more realistic feel, think more like a human.

Flat Ground

Sand

Water

Hill

The bot will find the shortest path with the least amount of energy to get there.

Flat ground is easier than sand, sand is easier than water, and water is easier than a hill.

Let me know what you think, colors ect..

Wow now that is cool. I still cant believe how fast this thing works ... awesome job

Hallman

Edited June 9, 2007 by Hallman

[ConsultingJoe]

OMG you are amazing. this keeps getting smarter and more compicated and I am still confused.

I'm sorry but I have to take back my idea.

I know most of the OpenGL stuff but this seems tough.

[James]

WOW! :) That is incredible!

[Toady]

Thank you all, Im glad you like it. AI seems like a cool topic, am I right? Wonder if a game can be made out of this... hmm.

[CoderDunn]

Thank you all, Im glad you like it. AI seems like a cool topic, am I right? Wonder if a game can be made out of this... hmm.

Yes with this it would be MUCH easier to make a game such as pacman where the ghosts try to get pacman. Maybe a free placement tower defense?

BTW I rated this 5 stars

Edited June 9, 2007 by Hallman

[Uriziel01]

OMG, WOW ! Im really impressed with this project ! I think this may be basic for bot in 3d game, we just have to create a grid of 3d map and include yours script, i think we may use it for game like, some monster are chasing hero and we must flee. Or some footbal game i think, BTW meaby some course of creating project's like this one.

[NELyon]

Here's my idea:

1 3d map with any set path, and a 2d replica with basic detail, mostly just the path.

Bot tracks co-ordinates through the 2d maze, then makes the corresponding moves on the 3d map.

Tell me if i know what i am talking about :?:

[James]

Yeah I do. It's like a grid which you are looking down on, that way the bot can find the player/whatever easily.

[Toady]

Yes with this it would be MUCH easier to make a game such as pacman where the ghosts try to get pacman. Maybe a free placement tower defense?

BTW I rated this 5 stars

@Hallman - Thanks for the rating. I believe you it would be easy.

OMG, WOW ! Im really impressed with this project ! I think this may be basic for bot in 3d game, we just have to create a grid of 3d map and include yours script, i think we may use it for game like, some monster are chasing hero and we must flee. Or some footbal game i think, BTW meaby some course of creating project's like this one.

@Uriziel01 - Thank you for your interest. Yes this is a basis for a potential game. It could be used in any game if you know the coords of your character and the environment. I might eventually create some kind of 2d game out of this just for fun.

Here's my idea:

1 3d map with any set path, and a 2d replica with basic detail, mostly just the path.

Bot tracks co-ordinates through the 2d maze, then makes the corresponding moves on the 3d map.

Tell me if i know what i am talking about tongue.gif :?:

@Senton-Bomb - Yes thats like what the nintendo DS has for many games.

[Toady]

UPDATED:

Heavily commented code to make this as understandable as possible. Hopefully it helps anyone who wants to use this.

Also added the option to show the nodes that the algorithm searches. This will help people understand better of how this works and show people the reason why this algorithm is so fast. The nodes that are searched will be shown in yellow and have a "SN" inside them.

I added a label that shows the cost of the path and how many nodes were searched. Oh and I changed some colors to lessen the confusion.

Thank you all for your interest and support!

[Toady]

Updated:

Description on original post has new images and a short tutorial. Hope this helps

[Richard Robertson]

Wow, this just keeps going, good job Toady. It looks better every time you make it.

[James]

Toady, this rocks even more.

Dude, you are an absolute genius!