//
/*
	VNS - Astar: Viral Noding System 
		-- Algorithm: A*
		-- Required Components
			-- VNS: Viral Noding System
		-- Component For TTT Clever Bot
			-- Author: Wattled Walnut
*/

if ( vns == nil ) then
	print( "VNS component missing" )
	return
end

vns.tr.filter = {}

vnsa = {
	gscores = {},
	hscores = {},
	fscores = {},
	disc_nodes = {}, // Discovered Nodes
	parents = {},
	path = {},
	startn = nil,
	endn = nil,
	search_complete = false,
	search_stop = false,
	no_path = false,
}

function vnsa:heuristic( current_node )
	return current_node:Distance( vns.nodes[ self.endn.x ][ self.endn.y ][ self.endn.z ][1] )
end

function vnsa:retrosearch( string_vector )
	local parent = self.parents[ string_vector ]
	if ( parent == nil ) then self.search_complete = true print( "retrosearch complete" ) return end
	
	local e = string.Explode( ",",parent )
	table.insert( self.path,Vector( e[1],e[2],e[3] ) )
	
	timer.Simple( .01,function()
		self:retrosearch( parent )
	end )
end

function vnsa:search( lx,ly,lz )
	if ( self.endsearch ) then self.search_stop = true print( "search ended by user" ) return end
	if ( !vns:node_exists( lx,ly,lz ) ) then print( "node does not exist, evaluation is impossible" ) return end
	if ( self.startn == nil || self.endn == nil ) then print( "start or end node does not exist" ) return end
	
	local current = vns.nodes[lx][ly][lz][1]
	
	if ( lx == self.endn.x && ly == self.endn.y && lz == self.endn.z ) then
		print( "Search Complete" )
		self:retrosearch( current.x .. "," .. current.y .. "," .. current.z )
		return
	end
	if ( lx == self.startn.x && ly == self.startn.y && lz == self.startn.z ) then
		if ( self.disc_nodes[lx] == nil ) then
			self.disc_nodes[lx] = {}
			if ( self.disc_nodes[lx][ly] == nil ) then
				self.disc_nodes[lx][ly] = {}
			end
			self.disc_nodes[lx][ly][lz] = true
			self.gscores[tostring( current )] = 0
			self.hscores[tostring( current )] = self:heuristic( current )
			self.fscores[tostring( current )] = self.gscores[tostring( current )] + self.hscores[tostring( current )]
		end
	end
	
	self.disc_nodes[lx][ly][lz] = false // Current node has been evaluated
	
	local nbours = { // Possible Neighbours
		{ lx + 1,ly,lz },
		{ lx + 1,ly,lz + 1 },
		{ lx + 1,ly,lz - 1 },
		{ lx - 1,ly,lz },
		{ lx - 1,ly,lz + 1 },
		{ lx - 1,ly,lz - 1 },
		{ lx,ly + 1,lz },
		{ lx,ly + 1,lz + 1 },
		{ lx,ly + 1,lz - 1 },
		{ lx,ly - 1,lz },
		{ lx,ly - 1,lz + 1 },
		{ lx,ly - 1,lz - 1 },
	}
	
	for k,v in pairs( nbours ) do
		if ( !vns:node_exists( v[1],v[2],v[3] ) ) then continue end
		local n = vns.nodes[v[1]][v[2]][v[3]][1] // Neighbour vector
		if ( vns:trace( current,n ).Hit ) then continue end
		
		if ( self.disc_nodes[v[1]] == nil ) then
			self.disc_nodes[v[1]] = {}
		end
		if ( self.disc_nodes[v[1]][v[2]] == nil ) then
			self.disc_nodes[v[1]][v[2]] = {}
		end
		if ( self.disc_nodes[v[1]][v[2]][v[3]] != false ) then
			self.disc_nodes[v[1]][v[2]][v[3]] = true // true = unevaluated, false = evaluated
			
			self.gscores[ tostring( n ) ] = self.gscores[ tostring( current ) ] + current:Distance( vns.nodes[v[1]][v[2]][v[3]][1] )
			self.hscores[ tostring( n ) ] = self:heuristic( n )
			self.fscores[ tostring( n ) ] = self.gscores[ tostring( n ) ] + self.hscores[ tostring( n ) ]
			self.parents[ n.x .. "," .. n.y .. ",".. n.z ] = current.x .. "," .. current.y .. "," ..current.z
		end
	end
	local bn = { 9999999,{ X = 0,Y = 0,Z = 0 } }
	for x,a in pairs( self.disc_nodes ) do
		for y,b in pairs( self.disc_nodes[x] ) do
			for z,c in pairs( self.disc_nodes[x][y] ) do
				if ( !self.disc_nodes[x][y][z] ) then continue end
				local fscore = self.fscores[ tostring( vns.nodes[x][y][z][1] ) ]
				if ( fscore < bn[1] ) then
					bn = { fscore,{ X = x,Y = y,Z = z } }
				end
			end
		end
	end
	if ( bn[1] == 9999999 ) then self.no_path = true print( "No viable path" ) return end
	// Node with lowest fscore has been found, now repeat the process
	
	timer.Simple( .001,function()
		self:search( bn[2].X,bn[2].Y,bn[2].Z )
	end )
end

-- The following code will not be in the final version

concommand.Add( "VNSA_EndSearch",function()	self.endsearch = true end )


/*
function vnsa:closest_node( vector )
	local best = { 9999,{ 0,0,0 } }
	for x,_ in pairs( vns.nodes ) do
		for y,__ in pairs( vns.nodes[x] ) do
			for z,___ in pairs( vns.nodes[x][y] ) do
				local dist = vns.nodes[x][y][z][1]:Distance( vector )
				if ( dist <= best[1] ) then
					best = { dist,{ x,y,z } } 
				end
			end
		end
	end
	if ( best[1] != 9999 ) then
		return { X = best[2][1],Y = best[2][2],Z = best[2][3] }
	end
end

local set = false

function vnsa:setup()
	local node = self:closest_node( LocalPlayer():GetPos() + Vector( 0,0,25 ) )
	if ( !set ) then
		set = !set
		
		-- Reset Data
		self.search_stop = false
		self.search_complete = false
		self.no_path = false
		self.gscores = {}
		self.hscores = {}
		self.fscores = {}
		self.disc_nodes = {}
		self.parents = {}
		self.path = {}
		--
		
		self.startn = { x = node.X,y = node.Y,z = node.Z }
	else
		set = !set
		
		self.endn = { x = node.X,y = node.Y,z = node.Z }
	end
end

concommand.Add( "VNSA_Setup",function() vnsa:setup() end )
concommand.Add( "VNSA_BeginSearch",function() vnsa:search( vnsa.startn.x,vnsa.startn.y,vnsa.startn.z ) end )


local function drawnodes() // will not be in final code
	for k,v in pairs( vnsa.path ) do
		debugoverlay.Cross( v,5,30,Color( 220,220,0,200 ),true )
	end
end
concommand.Add( "VNSA_DrawNodes",drawnodes )
*/