ConsultingJoe Posted June 8, 2007 Posted June 8, 2007 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 Check out ConsultingJoe.com
Richard Robertson Posted June 8, 2007 Posted June 8, 2007 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 Posted June 8, 2007 Author Posted June 8, 2007 #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. www.itoady.com A* (A-star) Searching Algorithm - A.I. Artificial Intelligence bot path finding
ConsultingJoe Posted June 8, 2007 Posted June 8, 2007 #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 Check out ConsultingJoe.com
Toady Posted June 8, 2007 Author Posted June 8, 2007 .... 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"]] www.itoady.com A* (A-star) Searching Algorithm - A.I. Artificial Intelligence bot path finding
ConsultingJoe Posted June 8, 2007 Posted June 8, 2007 .... 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 Check out ConsultingJoe.com
Toady Posted June 9, 2007 Author Posted June 9, 2007 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.. www.itoady.com A* (A-star) Searching Algorithm - A.I. Artificial Intelligence bot path finding
CoderDunn Posted June 9, 2007 Posted June 9, 2007 (edited) 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 GroundSandWaterHillThe 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 Posted June 9, 2007 Posted June 9, 2007 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. Check out ConsultingJoe.com
James Posted June 9, 2007 Posted June 9, 2007 WOW! :) That is incredible! Blog - Seriously epic web hosting - Twitter - GitHub - Cachet HQ
Toady Posted June 9, 2007 Author Posted June 9, 2007 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. www.itoady.com A* (A-star) Searching Algorithm - A.I. Artificial Intelligence bot path finding
CoderDunn Posted June 9, 2007 Posted June 9, 2007 (edited) 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 Posted June 9, 2007 Posted June 9, 2007 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 Posted June 10, 2007 Posted June 10, 2007 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 Posted June 10, 2007 Posted June 10, 2007 Yeah I do. It's like a grid which you are looking down on, that way the bot can find the player/whatever easily. Blog - Seriously epic web hosting - Twitter - GitHub - Cachet HQ
Toady Posted June 10, 2007 Author Posted June 10, 2007 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. www.itoady.com A* (A-star) Searching Algorithm - A.I. Artificial Intelligence bot path finding
Toady Posted June 11, 2007 Author Posted June 11, 2007 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! www.itoady.com A* (A-star) Searching Algorithm - A.I. Artificial Intelligence bot path finding
Toady Posted June 11, 2007 Author Posted June 11, 2007 Updated: Description on original post has new images and a short tutorial. Hope this helps www.itoady.com A* (A-star) Searching Algorithm - A.I. Artificial Intelligence bot path finding
Richard Robertson Posted June 11, 2007 Posted June 11, 2007 Wow, this just keeps going, good job Toady. It looks better every time you make it.
James Posted June 12, 2007 Posted June 12, 2007 Toady, this rocks even more. Dude, you are an absolute genius! Blog - Seriously epic web hosting - Twitter - GitHub - Cachet HQ
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now