/*------------------------------------
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
Register
Events
Popular
More
Post #41
Dumb x 2
Agree x 2
Useful x 2
Bad Reading x 1
Friendly x 1