##########Breadth First Pathfinding AI############
###
#variables used by the search engine: 
@name BFS plug n play
@inputs Search [Origin Destination]:vector
@outputs VectorList:array Completed Error #the final path, some useful numbers
@persist [CurNode SearchC GoalNode StartNode]:number #some useful numbers
@persist [Vars Nodes]:table #Vars includes all internal varaibles, Nodes is the nodegraph itself

#Usage: to start a search, set search=1 set Origin and Destination and set Completed=0
#For repeated searches reset Search=0 and Completed=0 If no origin or Destination are given a 
#default destination and origin are presumed. The C variable is used to count.
HideSearchInfo=0 #silent mode?
####
#errors
#Error=0 It worked! 
#Error=1 No end node found
#Error=2 No start node found
#Error=3 Start and End nodes are on separate nodegraph fragments
#Error=4 No search made
#Error=5 No start or end node
#Error=6 Search in progress
if(first()|duped()){

    Vars=table()
    Error=4
    Vars=table() #stores all our array variables
    Vars["SEARCHING",number]=0
    Vars["Filename",string]="nodegraphs/Nodegraph_6_"+map()+".txt"
    Vars["Offset",vector]=vec(0,0,10) #How high off the ground should a node be placed
    runOnFile(1)
    if(gGetStr("Nodes")){
        Nodes=vonDecodeTable(gGetStr("Nodes"))

    }else{
    runOnFile(1)
    fileLoad(Vars["Filename",string])
    print("loading "+Vars["Filename",string])
    }
}
if(fileLoaded()&!Nodes:count()&fileName()==Vars["Filename",string]){
    Read=fileRead()
    gSetStr("Nodes",Read)
    Nodes=vonDecodeTable(Read)
    
}

SearchC=changed(Search)
if(Nodes:count()&Search&(SearchC|~Search)){
    Vars["SEARCHING",number]=1 #trigger Search
    Vars["Begin",number]=1 #this only runs once when searching to prevent the goal from moving.
    Vars["Open",array]=array() #Numerical Node ID list of nodes to visit
    Vars["Closed",table]=table() #numerical table of node's visited
    Vars["Start",array]=array() #one use to find the starting podsition's nearest node
    Vars["StartK",array]=array() #saves node IDs for start array
    Vars["End",array]=array()   #one use to find the ending position's nearest node
    Vars["EndK",array]=array() #preserves the node IDs for end array
    Vars["NodeList",array]=array() #final path by nodes
    VectorList=array() #final path by vectors 
    timer("start",1)
    Vars["CurNode",number]=0
    Vars["Completed",number]=0
    Vars["Ready",number]=0
    Vars["Next",number]=0
    Vars["N",number]=1
    Vars["S",number]=1
    if(!Origin){Vars["Self",vector]=round(owner():pos())+Vars["Offset",vector]}else{Vars["Self",vector]=round(Origin+Vars["Offset",vector])}
    if(!Destination){Vars["Goal",vector]=round(owner():aimPos())+Vars["Offset",vector]}else{Vars["Goal",vector]=round(Destination+Vars["Offset",vector])}
    if(!HideSearchInfo){print("Starting search")}
    Error=6
}
if(Vars["SEARCHING",number]&(clk("next")|clk("start")|clk("continue"))){
    ######Let's find the start and end nodes that
    ######have Line of Sight to our target objects
    if(Vars["Begin",number]){
        #perpetuates the while statement if it's running "hot"
        if(Vars["N",number]<=Nodes:count()){
            timer("start",20)
        }else{
            Vars["Begin",number]=0 
            Vars["Next",number]=1
        }
        #Finds the nearest nodes to the start and your goal vectors
        
        while(Vars["N",number]<=Nodes:count()&perf()){
                Vars["V",vector]=Nodes[Vars["N",number],array][1,vector]
                if(Vars["V",vector]){
                    Vars["Start",array]:pushNumber(round(Vars["V",vector]:distance(Vars["Self",vector])))
                    Vars["StartK",array]:pushNumber(Vars["N",number])
                    Vars["End",array]:pushNumber(round(Vars["V",vector]:distance(Vars["Goal",vector])))
                }
                Vars["N",number]=Vars["N",number]+1
        }  
        
    }
    if(Vars["Next",number]){
        #Time to do ranger tests! 
        Vars["EndK",array]=Vars["StartK",array]:clone()
        rangerIgnoreWorld(0)
        rangerHitEntities(0)
        rangerHitWater(0)

        ##Test all nodes to see if we have LOS, first node with LOS wins
        if(Vars["S",number]<=Vars["Start",array]:count()&!perf()){timer("start",20)}

        while(Vars["S",number]<=Vars["Start",array]:count()&perf()){
            Vars["Min",number]=Vars["StartK",array][Vars["Start",array]:minIndex(),number]
            Vars["Trace",number]=rangerOffset(Vars["Self",vector],Nodes[Vars["Min",number],array][1,vector]):hit()
            if(!Vars["Trace",number]){
                CurNode=Vars["Min",number]
                break
            }else{
                Vars["StartK",array]:remove(Vars["Start",array]:minIndex())
                Vars["Start",array]:remove(Vars["Start",array]:minIndex())
            }
        Vars["S",number]=Vars["S",number]+1
        }
        
        if(Vars["E",number]<=Vars["End",array]:count()&!perf()){timer("start",20)}
       while(Vars["E",number]<Vars["End",array]:count()&perf()){
            Vars["Min",number]=Vars["EndK",array][Vars["End",array]:minIndex(),number]
           
            if(!rangerOffset(Vars["Goal",vector],Nodes[Vars["Min",number],array][1,vector]):hit()){
                GoalNode=Vars["Min",number]
                    break
            }else{
                Vars["EndK",array]:remove(Vars["End",array]:minIndex())
                Vars["End",array]:remove(Vars["End",array]:minIndex())
            }
       Vars["E",number]=Vars["E",number]+1
        }#Now that we've done the least ranger tests needed we move on. 
        if(!CurNode){
            Error=2
        }
        if(!GoalNode){
            Error=1
        }
        if(!CurNode&!GoalNode){Error=5} #report that both nodes were not found
        if(CurNode){
            StartNode=CurNode #This is used when reconstructing the path
            Vars["Open",array]:pushNumber(CurNode)
            Vars["Depth",number]=1 #This sets the search's starting depth
            CLO=Vars["Closed",table]
            CLO[CurNode,vector2]=vec2(CurNode,Vars["Depth",number])
            Vars["NodeList",array]:pushNumber(CurNode)
        }
        if(CurNode&GoalNode){
            Vars["Ready",number]=1
            Vars["Next",number]=0
        }else{Vars["Ready",number]=0 Vars["SEARCHING",number]=0}
    }#End Next
    Vars["BFS",number]=Vars["Open",array]:count()&Vars["Ready",number]&!Vars["Next",number]
    if(Vars["BFS",number]){ ##BFS=Bredth First Search
        timer("continue",50)
    }
    
    while(Vars["BFS",number]&perf()){###Time to do the actual path search
        CurNode=Vars["Open",array]:shiftNumber() #moves the first item off the list
        if(!CurNode){print("Error preforming search, open list depleted early.") Error=3 break}
        Vars["Depth",number]=Vars["Closed",table][CurNode,vector2]:y() #Current Node's depth
        if(CurNode==GoalNode){
            if(!HideSearchInfo){print("search complete")}
            Completed=1
            Vars["SEARCHING",number]=0
            Vars["Ready",number]=0
            timer("Parse",20)
            Vars["NodeList",array]=array()
            VectorList=array()
            Vars["NodeList",array]:unshiftNumber(GoalNode)
            VectorList:pushVector(Nodes[GoalNode,array][1,vector]) #don't forget the endnode
            VectorList:pushVector(Vars["Goal",vector]) #push the target's last known location into the list
            break
        }else{
            Vars["Links",array]=array()
            Vars["Links",array]=Nodes[CurNode,array]
            for(C=3,Vars["Links",array]:count()){
                Vars["LN",number]=Vars["Links",array][C,number]
                if(!Vars["Closed",table][Vars["LN",number],vector2]){ #keeps us from duplicating node info
                    Vars["Open",array]:pushNumber(Vars["LN",number]) #pushes a nodeID to be scanned
                    Vars["CLO",table]=Vars["Closed",table]
#####This is where paste ends#########       Vars["CLO",table][Vars["LN",number],vector2]=vec2(CurNode,Vars["Depth",number
                    Vars["CLO",table][Vars["LN",number],vector2]=vec2(CurNode,Vars["Depth",number]+1) #vec2(Parent,Depth of parent +1)
                }
            }
        }
    }
}
if(clk("Parse")){ 

    if(CurNode!=StartNode){timer("Parse",1)} #enable this when you got it working right!
    while(CurNode!=StartNode&perf()){
        if(CurNode){
            CurNode=Vars["Closed",table][CurNode,vector2]:x() #set the next node to the parent of the current
            Vars["NodeList",array]:unshiftNumber(CurNode)
            VectorList:unshiftVector(Nodes[CurNode,array][1,vector])
        }
    }
    if(CurNode==StartNode){
        stoptimer("Parse")
        if(!HideSearchInfo){print("SUCCESS! PATH FOUND!")}
        #NodeList=Vars["NodeList",array] #This is just an optional list that's human readable
        Error=0
        
    }
    
}
