1. Post #41

    May 2007
    4 Posts
    Skurmedel posted:
    Yes in the case of NPCs you will. Let's say you wanna script an murderous box, in that case, creating a npc_rebel (for example) and setting his model to a box and a bunch of other stuff isn't really the optimal way of doing it. That NPC is made to behave like a rebel, which probably will do, unless you set a shitload of modifiers, and that will probably still present problems.

    If you had the real sourcecode you could easily derive the base NPC, add stuff to it and more or less there wouldn't be a limit to what you could do. But we just have Lua and the NPCs that are already there doesn't work in every scenario.
    Hasn't garry added scripted NPCs yet?

  2. Post #42
    Skurmedel's Avatar
    November 2006
    47 Posts
    No, and even if he had done so, what would you do if you wanted to do your own pathfinding.

    This is for pathfinding, it could be used for missiles, evil cars, animated cereal and whatnot. NCPs isn't the only use for it.

  3. Post #43

    May 2007
    4 Posts
    Skurmedel posted:
    No, and even if he had done so, what would you do if you wanted to do your own pathfinding.

    This is for pathfinding, it could be used for missiles, evil cars, animated cereal and whatnot. NCPs isn't the only use for it.
    He should have been able to hook the engine's NPC code for that stuff easily enough. I still think doing it all in lua is reinventing the wheel (and costs more having to run through the lua interpreter besides).

  4. Post #44
    LifeForm's Avatar
    May 2007
    2 Posts
    This woud be usful for that new zombie mod that's coming up where zombies are supposed to track down players and kill them.

  5. Post #45
    Skurmedel's Avatar
    November 2006
    47 Posts
    DaddyWarbox posted:
    He should have been able to hook the engine's NPC code for that stuff easily enough. I still think doing it all in lua is reinventing the wheel (and costs more having to run through the lua interpreter besides).
    How would he do that, bribe Garry for source access?

  6. Post #46
    lilezek's Avatar
    February 2009
    209 Posts
    Could someone reupload this script?

  7. Post #47
    Arbitration's Avatar
    July 2009
    472 Posts
    Excellent work Jinto.


    Wait what the fuck, Here I thought I was in for a tasty new treat, Turns out I get ancient threads dug up from the grave.

  8. Post #48
    Gold Member
    Nevec's Avatar
    June 2008
    1,094 Posts
    Could someone reupload this script?
    There you go..

    http://code.overvprojects.nl/viewcode.php?id=261

  9. Post #49
    lilezek's Avatar
    February 2009
    209 Posts

  10. Post #50
    Gold Member
    mastersrp's Avatar
    October 2005
    1,827 Posts
    Once again, Jinto makes something awesome for the gmod lua!
    GREAT Job, it'll be VERY useful in the future, if anyone gets themselves together to do stuff with this..
    I'm no lua coder myself, i've tried a few things, but i'm not really into it.

    Edited:

    i fail for not realizing the date of this. It's been done before, i KNEW it was a bit familiar..

  11. Post #51
    kahn's Avatar
    November 2008
    103 Posts
    Very cool.

  12. Post #52
    Gold Member
    Sillirion's Avatar
    June 2006
    426 Posts
    someone could code a sample to see how it works?

  13. Post #53
    Gold Member
    Deco Da Man's Avatar
    July 2007
    1,017 Posts
    This is kinda old.. if it doesn't work or you're looking for something a bit more dynamic when it comes to pathfinding, try my module:
    http://wiki.garrysmod.com/?title=A-S...finding_Module

  14. Post #54
    Gold Member
    Termy58's Avatar
    September 2006
    1,726 Posts
    This is kinda old.. if it doesn't work or you're looking for something a bit more dynamic when it comes to pathfinding, try my module:
    http://wiki.garrysmod.com/?title=A-S...finding_Module
    How is it faster and more efficient it looks messy as hell and unoptimized, jinto's was way more dynamic. Yours is just shortest a to b.

  15. Post #55
    Gold Member
    Deco Da Man's Avatar
    July 2007
    1,017 Posts
    How is it faster and more efficient
    If you'd take a look at the source code of my module, you'd see that I minimize unnecessary calls, having all the code in one function, and use of memory, this includes not using useless locals. In fact, swap line 34 and 35, and merge the local definition in with the definition now on line 34.

    Jinto has a more OO style in his, while mine is more low-level. The things he uses, including use of metatables, costs him a decent amount of speed.
    I aimed for speed with mine.
    You may say 'but metatables cost shit all speed'. True, however they are more expensive than how I do it, and I aimed for mine to be as fast as possible, while still maintaining it's dynamism.

    The reason I aim for absolute speed, is that the application I made it for required it to be so. This module was not intended for use in GMod, however I made it in a way that allows it to be used in any Lua situation.
    The application I was making was a simple RTS engine. I was experimenting with how to handle masses of units in an RTS engine. I found that my shoddy pathfinding was the real culprit when it came to slowing my application down, so I made the A* module which you see today. After I began using it, my application was so much faster.
    If you were to make an RTS engine, such as one that used in AoE or Empire Earth, you would understand the need for absolute speed, and the need for complete control in the pathfinding process.

    it looks messy as hell
    I admit that my coding stile is quite cluttered, and some people may disapprove of it, but I like my coding style and will continue to code in it. I like it, I find it easy to read.

    and unoptimized
    How so?

    , jinto's was way more dynamic.
    Jinto's was more handy than dynamic. It did what most GMod programmers would want to do, and that is to find the shortest clear path in a waypoint system. Jinto provides utilities that simplify the finding of this path, and even kindly provides tracing functions to help.

    Mine, however, offers dynamism and flexibility. With the multiple stages in which callbacks provided are called, the coder has complete control at every main stage throughout the process.

    When I use the word flexibility, I'm not simply using the word cause it sounds cool, I'm using it as my module can be adapted to any system (e.g tiles, hexagonal tiles, waypoint system (like source, and Jintos), anything!) with minimal sacrifice when it comes to the speed of and the control the coder has over the path finding process.

    Yours is just shortest a to b.
    This is just a silly statement on your behalf.
    Jinto's is simply "shortest a to b". In fact, Jinto's is just "shortest a to b in a waypoint-based system".
    Mine is "path from a to b that suits coder's need".
    If you wanted to consider, for example, lava that injured an NPC in Jinto's system, you'd have to override the heuristic function, which is not easy, as the Node table is local. You would have to recode Jinto's module to be suit your needs. I'm pretty sure that most coders, me included, would want to keep their code that states what path is best in the piece of code that launches the path find.
    My A* module gives the coder absolute control over how each node is considered in the process.

    You may not want to use my module. If you don't I don't really care.
    I released it as I thought someone else out there may be able to use it.

  16. Post #56
    GreyIOutcast's Avatar
    April 2008
    477 Posts
    Deco Da Man, your module would give an error.

    and table.call(walkable_checks, current_node, neighbour_node, startinging_node, target_node, heuristic, ...) -- ...or unwalkable...

    That's a direct paste from your codepad of it on the Gmod Wiki.

    There is no such thing as "startinging_node".

    Obviously, your module isn't ready for use yet.

  17. Post #57
    Gold Member
    Deco Da Man's Avatar
    July 2007
    1,017 Posts
    Deco Da Man, your module would give an error.

    and table.call(walkable_checks, current_node, neighbour_node, startinging_node, target_node, heuristic, ...) -- ...or unwalkable...

    That's a direct paste from your codepad of it on the Gmod Wiki.

    There is no such thing as "startinging_node".

    Obviously, your module isn't ready for use yet.
    Did a Find+Replace for 'start' in the latest version and didn't bother to test it.

    Thanks for spotting that :)

  18. Post #58
    GreyIOutcast's Avatar
    April 2008
    477 Posts
    Did a Find+Replace for 'start' in the latest version and didn't bother to test it.

    Thanks for spotting that :)
    No problem. I suggest you update the link on the gmod.com wiki. I'm in the middle of trying to make a pathfinding application (First I've got to set up a node graph, though) for the gamemode "Gmod TD"

    Would be a lot better if you could build mazes for the enemies, so I'm trying to do so.

    I think I may try yours first, if it's all working. After that I'll switch over to Jinto's to see how his works as well, since I have both.

  19. Post #59
    rute's Avatar
    August 2009
    212 Posts
    Has anyone made an simple addor for this? Something like Add Path tool or spawn them as entity.
    Reply With Quote Edit / Delete Reply Finland Show Events Dumb Dumb x 2 (list)

  20. Post #60
    Creator of Exsto
    Prefan's Avatar
    January 2009
    1,049 Posts
    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.
    Reply With Quote Edit / Delete Reply United States Show Events Agree Agree x 2Dumb Dumb x 1 (list)

  21. Post #61
    Reposting BUG threads since 2011!
    TehBigA's Avatar
    March 2007
    426 Posts
    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.
    I would also like Jinto's version, more flexable, anyone have it?

    EDIT: Found this on the Wayback Machine:
    /*------------------------------------
    	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 heuristic = ( endnode.position - link.position ):Length();		
    					
    					// calculate the total distance traveled so far.
    					local totaldist = current.StartCost + ( current.position - link.position ):Length();
    
    					// calculate costs
    					link:CalculateCost( totaldist, heuristic );
    					
    					// store previous so we can walk backwards
    					link.Previous = current;
    					
    					// add to the open list for examination
    					openlist:Put( link );
    				
    				end
    			
    			end
    		
    		end
    	
    	end
    	
    	// did we successfully find a path?
    	if( endnode.Previous == nil ) then return; end
    	
    	// walk backwards to get the path in the right order.
    	local ret = {};
    	
    	// start at the end!
    	current = endnode;
    	
    	// yay backwards!
    	while( current ) do
    	
    		// insert. ( have to use table.insert here ).
    		table.insert( ret, 1, current );
    		
    		// previous
    		current = current.Previous;
    	
    	end
    	
    	return ret;
    
    end
    
    
    /*------------------------------------
    	Solver:Save
    ------------------------------------*/
    function Solver:Save( filename )
    
    	local node, link;
    
    	// construct the save table
    	local save = {};
    	
    	// add points
    	for _, node in pairs( self.nodes ) do
    	
    		// setup the node.
    		local savenode = {
    			links = {},
    			extracost = node.ExtraCost,
    			data = node.data,
    			position = tostring( node.position ),
    		
    		};
    	
    		// write links.
    		for _, link in pairs( node.links ) do
    		
    			savenode.links[ #savenode.links + 1 ] = tostring( link.position );
    		
    		end
    		
    		// add to save
    		save[ #save + 1 ] = savenode;
    		
    	end
    	
    	// write to file
    	file.Write( filename, util.TableToKeyValues( save ) );
    	
    end
    
    /*------------------------------------
    	StringToVector
    ------------------------------------*/
    local function StringToVector( str )
    
    	local tbl = string.Explode( " ", str );
    	return Vector(
    		tonumber( tbl[1] ),
    		tonumber( tbl[2] ),
    		tonumber( tbl[3] )
    	);
    	
    end
    
    /*------------------------------------
    	Solver:Load
    ------------------------------------*/
    function Solver:Load( filename, wipeExisting )
    
    	local node, current, link, linked;
    
    	// load from file
    	local load = util.KeyValuesToTable( file.Read( filename ) or "" );
    	
    	// wipe the existing waypoints
    	if( wipeExisting ) then
    	
    		self.nodes = {};
    		
    	end
    
    	// create the nodes, then the links.
    	for _, node in pairs( load ) do
    	
    		self:AddNode(
    			StringToVector( node.position ),
    			tonumber( node.extracost ),
    			tonumber( node.data )
    		);
    	
    	end
    	
    	// add links
    	for _, node in pairs( load ) do
    	
    		// get the node for this position
    		current = self:GetNodeForPosition( StringToVector( node.position ) );
    		
    		// valid node?
    		if( current ) then
    		
    			// iterate links
    			for _, link in pairs( node.links ) do
    			
    				// get the node
    				linked = self:GetNodeForPosition( StringToVector( link ) );
    				
    				// valid?
    				if( linked ) then
    				
    					current:CreateLink( linked );
    				
    				end
    			
    			end
    		
    		end
    	
    	end
    	
    end
    
    /*------------------------------------
    	Solver:SaveMap
    ------------------------------------*/
    function Solver:SaveMap( name )
    
    	self:Save( ( "waypoints/%s/%s.txt" ):format( name, game.GetMap() ) );
    
    end
    
    /*------------------------------------
    	Solver:LoadMap
    ------------------------------------*/
    function Solver:LoadMap( name )
    
    	self:Load( ( "waypoints/%s/%s.txt" ):format( name, game.GetMap() ), true );
    
    end
    
    
    
    /*------------------------------------
    	CreateSolver
    ------------------------------------*/
    function CreateSolver( )
    
    	return Solver:Create();
    
    end
    
    Reply With Quote Edit / Delete Reply United States Show Events Useful Useful x 2Bad Reading Bad Reading x 1 (list)

  22. Post #62
    hogofwar's Avatar
    May 2008
    4,751 Posts
    Could someone make a decent example for this? I am in the mud about using this even though i really want to.
    Reply With Quote Edit / Delete Reply United Kingdom Show Events Dumb Dumb x 1 (list)

  23. Post #63
    Reposting BUG threads since 2011!
    TehBigA's Avatar
    March 2007
    426 Posts
    Could someone make a decent example for this? I am in the mud about using this even though i really want to.
    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.

  24. Post #64
    Gold Member
    Deco Da Man's Avatar
    July 2007
    1,017 Posts
    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.
    I've just released a new version of my module.

    It now allows for 'stepping' to be performed.

    See the wiki for documentation and a download.

  25. Post #65
    Reposting BUG threads since 2011!
    TehBigA's Avatar
    March 2007
    426 Posts
    I've just released a new version of my module.

    It now allows for 'stepping' to be performed.

    See the wiki for documentation and a download.
    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

  26. Post #66

    May 2010
    119 Posts
    Is Deco Da Man's module anywhere to be found now that the wiki is down?

  27. Post #67
    Gold Member
    Greetings's Avatar
    October 2011
    516 Posts
    Is Deco Da Man's module anywhere to be found now that the wiki is down?
    I assume this is it.

    http://bananatree.im/wiki/wiki.garry...finding_Module

  28. Post #68

    May 2010
    119 Posts
    Ah, thanks :) Wasn't able to find it on a mirror myself.
    Reply With Quote Edit / Delete Reply Windows XP Sweden Show Events Friendly Friendly x 1 (list)