• A* Pathfinding Module
    67 replies, posted
  • Avatar of TehBigA
  • [QUOTE=Prefan;19241868]Sorry for the massive bump, but can someone upload Jinto's astar module again? I can't find it searching around. Deco's module confuses the hell out of me, I can't make sense of it.[/QUOTE] I would also like Jinto's version, more flexable, anyone have it? [b]EDIT:[/b] Found this on the Wayback Machine:[lua] /*------------------------------------ A* Module ------------------------------------*/ module( "astar", package.seeall ); /*------------------------------------ Blocking Functions ------------------------------------*/ BLOCKFUNC_TRACE_WORLD = function( a, b ) local trace = { start = a.position, endpos = b.position, mask = MASK_NPCWORLDSTATIC, }; local tr = util.TraceLine( trace ); return tr.Hit; end BLOCKFUNC_TRACE_ALL = function( a, b ) local trace = { start = a.position, endpos = b.position, }; local tr = util.TraceLine( trace ); return tr.Hit; end /*------------------------------------ List ------------------------------------*/ local List = {}; /*------------------------------------ List:create ------------------------------------*/ function List:Create( sortfunc ) local obj = {}; setmetatable( obj, self ); self.__index = self; // initialize the data obj.data = {}; // sorted obj.sortfunc = sortfunc; return obj; end /*------------------------------------ List:Grab ------------------------------------*/ function List:Grab( ) local data = self.data[1]; // remove the node. table.remove( self.data, 1 ); return data; end /*------------------------------------ List:Put ------------------------------------*/ function List:Put( node ) // add the node to the list self.data[ #self.data + 1 ] = node; // they provided a sort function? if( self.sortfunc ) then // sort table.sort( self.data, self.sortfunc ); end end /*------------------------------------ List:HasElement ------------------------------------*/ function List:HasElement( node ) return table.HasValue( self.data, node ); end /*------------------------------------ List:Empty ------------------------------------*/ function List:Empty( ) return #self.data <= 0; end /*------------------------------------ Node ------------------------------------*/ local Node = {}; /*------------------------------------ Node:__eq ------------------------------------*/ function Node.__eq( a, b ) // compare positions if b is a table if( type( b ) == "table" ) then return a.position == b.position; end // otherwise compare to my position return a.position == b; end /*------------------------------------ Node:Create ------------------------------------*/ function Node:Create( position, nodeData ) local obj = {}; setmetatable( obj, self ); self.__index = self; // set position and nodeData. obj.position = position; obj.data = nodeData; // links. obj.links = {}; // Total cost. obj.TotalCost = 0; // Cost to destination. obj.DestCost = 0; // Cost from start. obj.StartCost = 0; // Extra cost. obj.ExtraCost = 0; // So we can go backwards and construct the path. obj.Previous = nil; return obj; end /*------------------------------------ Node:CalculateCost ------------------------------------*/ function Node:CalculateCost( start, heuristic ) // calculate total cost. self.StartCost = start; self.DestCost = heuristic; self.TotalCost = self.StartCost + self.DestCost + self.ExtraCost; end /*------------------------------------ Node:CalculateCost ------------------------------------*/ function Node:SetExtraCost( cost ) self.ExtraCost = cost; end /*------------------------------------ Node:CreateLink ------------------------------------*/ function Node:CreateLink( node ) // check existing links if( table.HasValue( self.links, node ) ) then return false; end // add a link self.links[ #self.links + 1 ] = node; return true; end /*------------------------------------ Node:GetLinks ------------------------------------*/ function Node:GetLinks( ) return self.links; end /*------------------------------------ A* Solver ------------------------------------*/ local Solver = {}; /*------------------------------------ Solver:Create ------------------------------------*/ function Solver:Create( ) local obj = {}; setmetatable( obj, self ); self.__index = self; // node list obj.nodes = {}; return obj; end /*------------------------------------ Solver:AddNode ------------------------------------*/ function Solver:AddNode( position, extra, data ) // already exists? if( table.HasValue( self.nodes, position ) ) then return false; end // create a new node and add to the list local node = Node:Create( position, data ); node:SetExtraCost( extra ); self.nodes[ #self.nodes + 1 ] = node; return node; end /*------------------------------------ Solver:AddLink ------------------------------------*/ function Solver:AddLink( a, b ) // link the nodes if( !a:CreateLink( b ) || !b:CreateLink( a ) ) then return false; end return true; end /*------------------------------------ Solver:GetNodeForPosition ------------------------------------*/ function Solver:GetNodeForPosition( position ) local node; // get the node that matches this position for _, node in pairs( self.nodes ) do if( node.position == position ) then return node; end end end /*------------------------------------ Solver:ClosestNodeForPosition ------------------------------------*/ function Solver:ClosestNodeForPosition( position ) local node, closest; local dist = 2 ^ 15; // find the node that is closest to this position. for _, node in pairs( self.nodes ) do local length = ( node.position - position ):Length(); // closer than our previous best? if( length < dist ) then dist = length; closest = node; end end return closest; end /*------------------------------------ Solver:FindPath ------------------------------------*/ function Solver:FindPath( varianta, variantb, callback ) local current, link, links; // create the open and closed lists local openlist = List:Create( function( a, b ) return a.TotalCost < b.TotalCost; end ); local closedlist = List:Create(); // find out the two nodes to use local startnode = varianta; local endnode = variantb; if( type( varianta ) != "table" ) then startnode = self:ClosestNodeForPosition( varianta ); end if( type( variantb ) != "table" ) then endnode = self:ClosestNodeForPosition( variantb ); end // initialize the nodes startnode.StartCost = 0; endnode.Previous = nil; startnode.Previous = nil; // insert the starting node into the open list for examination >:) mwahha evil tf2 medic style openlist:Put( startnode ); // find the path! while( !openlist:Empty() ) do // get the node with the lowest cost from the open list and expand current = openlist:Grab(); // is this node the ending point? if so we hit our destination if( current == endnode ) then endnode.Previous = current.Previous; break; // not the end, branch it out and examine all adjacent nodes via links else // insert into the closed list, we're done with it. closedlist:Put( current ); // get this nodes links links = current:GetLinks(); // examine all of them for _, link in pairs( links ) do // add to the open list for examination? if( !openlist:HasElement( link ) && !closedlist:HasElement( link ) && ( !callback || !callback( current, link ) ) ) then // calculate the heuristic. // euclidean distance. ( damn did I spell that right? ) local h
  • Avatar of hogofwar
  • Could someone make a decent example for this? I am in the mud about using this even though i really want to.
  • Avatar of TehBigA
  • [QUOTE=hogofwar;19508135]Could someone make a decent example for this? I am in the mud about using this even though i really want to.[/QUOTE] You have to add positions to the solver and link each node with their neighbor. Problem is though , if the amount of nodes and neighbors gets big Lua will think it is an infinite loop when it tries to make a path.
  • Avatar of Deco Da Man
  • [QUOTE=TehBigA;19562893]You have to add positions to the solver and link each node with their neighbor. Problem is though , if the amount of nodes and neighbors gets big Lua will think it is an infinite loop when it tries to make a path.[/QUOTE] I've just released a new version of my module. It now allows for 'stepping' to be performed. See [url=http://wiki.garrysmod.com/?title=A-Star_Pathfinding_Module]the wiki[/url] for documentation and a download.
  • Avatar of TehBigA
  • [QUOTE=Deco Da Man;19569663]I've just released a new version of my module. It now allows for 'stepping' to be performed. See [url=http://wiki.garrysmod.com/?title=A-Star_Pathfinding_Module]the wiki[/url] for documentation and a download.[/QUOTE] Hm, I was just about to write my own stepper, but seeing as you did it for me I think I'll just use yours :D
  • Is Deco Da Man's module anywhere to be found now that the wiki is down?
  • Avatar of Greetings
  • [QUOTE=Noxic;36194964]Is Deco Da Man's module anywhere to be found now that the wiki is down?[/QUOTE] I assume this is it. [url]http://bananatree.im/wiki/wiki.garrysmod.com/indexc388.html?title=A-Star_Pathfinding_Module[/url]