@name Delivery Dude
@persist [PrefixU PrefixL]:string [Lower Symbols]:table

if(first()) {
    # letters are 12x12    
    Lower=table(
        "a"=1,
        "b"=1,
        "c"=1,
        "d"=1,
        "e"=1,
        "f"=1,
        "g"=1,
        "h"=1,
        "i"=1,
        "j"=1,
        "k"=1,
        "l"=1,
        "m"=1,
        "n"=1,
        "o"=1,
        "p"=1,
        "q"=1,
        "r"=1,
        "s"=1,
        "t"=1,
        "u"=1,
        "v"=1,
        "w"=1,
        "x"=1,
        "y"=1,
        "z"=1
    )
    
    Symbols=table(
        "."="models/sprops/misc/alphanum/alphanum_prd.mdl",
        ","="models/sprops/misc/alphanum/alphanum_com.mdl",
        ":"="models/sprops/misc/alphanum/alphanum_colon.mdl",
        "?"="models/sprops/misc/alphanum/alphanum_qmark.mdl",
        "!"="models/sprops/misc/alphanum/alphanum_xmark.mdl",
        "'"="models/sprops/misc/alphanum/alphanum_apost.mdl"
    )
    
    
    function array writeProp(S:string,V:vector,A:angle) {
        local Len=S:length()
        local Size=Len*12
        local Offset=Size/2
        local Output=array()
        
        for(I=1,Len) {
            local Char=S:sub(I,I)
            if(Char!=" ") {
                local IsLower=Lower[Char,number]
                local Prefix=IsLower ? "models/sprops/misc/alphanum/alphanum_l_" : "models/sprops/misc/alphanum/alphanum_"
                local Model=Symbols[Char,string] ? Symbols[Char,string] : Prefix+Char:lower()+".mdl"
                local Prop=propSpawn(
                    Model,
                    V+A:forward()*-(I*12-Offset-6),
                    A,
                    1
                )
                Output:pushEntity(Prop)
            }
        }
        
        return Output
    }
    
    function number drawBeam(Index,V1:vector,V2:vector) {
        holoCreate(Index,(V1+V2)/2,vec((V1-V2):length()/47.45,0.1,0.1),(V1-V2):toAngle())
        holoModel(Index,"models/hunter/plates/plate1x1.mdl")
        holoColor(Index,vec(255,128,0))
        holoMaterial(Index,"debug/debugdrawflat")
        return Index
    }
}

if(first()) {
    #include "e2shared/graph_gm_construct"
    
    function table table:path2(Start:string,End:string) {
        local Open=table((Start)=1)
        local Parents=table((Start)="__END")
        
        local OpenCt=1
        local NodeGraph=This:clone()
        
        local StartPos=NodeGraph[Start,table]["Pos",vector]
        local EndPos=NodeGraph[End,table]["Pos",vector]
        
        local IterationCt=0
        local MaxIterations=500
        
        local Deny_Blocked_Routes=1 # Skip routes blocked by entities instead of penalizing them
        local Blocked_Route_Penalty=1000 # Blocked route heuristic penalty
        local BaseOffset=vec(0,0,20) # Offset for rangers, e.g. to prevent clipping below props
        local HullSize=vec(5) # Hull size for ranger
        
        NodeGraph[Start,table]["State",number]=1
        
        while(1) {
            # Edge case: Took too many tries
            IterationCt++
            if(IterationCt>MaxIterations) {
                return table(
                    "error"="Exceeded hard limit of "+MaxIterations+" iterations.",
                    "success"=0,
                    "path"=array()
                )
            }
            # Edge Cases
            if(OpenCt<=0) {
                return table(
                    "error"="Ran out of open nodes.  No path found.",
                    "success"=0,
                    "path"=array()
                )
            }
            
            # Select and delete best node
            local BestH=9e99
            local BestNode=""
            foreach(NodeName,State:number=Open) {
                if(State!=1) {continue}
                local NodeData=NodeGraph[NodeName,table]
                if(NodeData["H",number]<BestH) {
                    BestH=NodeData["H",number]
                    BestNode=NodeName
                }
            }
            
            NodeGraph[BestNode,table]["State",number]=2
            Open:removeNumber(BestNode)
            OpenCt--
            
            # Edge case: End reached
            if(BestNode==End) {
                local Output=array()
                local Parent=Parents[End,string]
                while(1) {
                    Output:unshiftString(Parent)
                    if(Parent!="__END") {
                        Parent=Parents[Parent,string]
                    } else {
                        break
                    }
                }
                
                Output:shiftString()
                Output:pushString(End)
                
                return table(
                    "error"="No error.",
                    "success"=1,
                    "path"=Output
                )
            }
            
            # Add neighbors to open set and continue
            local BaseH=NodeGraph[BestNode,table]["H",number]
            local LastPos=NodeGraph[BestNode,table]["Pos",vector]
            
            foreach(I,V:string=NodeGraph[BestNode,table]["N",array]) {
                if(NodeGraph[V,table]["State",number]!=0) {continue}
                local ThisPos=NodeGraph[V,table]["Pos",vector]
                local DistDiff=(ThisPos:distance(LastPos))
                local Ranger=rangerOffsetHull(ThisPos+BaseOffset,LastPos+BaseOffset,HullSize)
                local Hit=Ranger:hit()
                
                local Heuristic=
                    BaseH
                    +DistDiff
                    +ThisPos:distance(EndPos)
                    +(Hit ? Blocked_Route_Penalty : 0)
                
                NodeGraph[V,table]["H",number]=Heuristic
                NodeGraph[V,table]["State",number]=1
                
                if(!Deny_Blocked_Routes || !Hit) {
                    Parents[V,string]=BestNode
                    Open[V,number]=1
                } elseif (Deny_Blocked_Routes) {
                    NodeGraph[V,table]["State",number]=2
                }
                OpenCt++
            }
        }
    }
    
    local Path=GMGraph:path2("51772","90158")
    printTable(Path)
    
    foreach(I,V:string=Path["path",array]) {
        local Pos=GMGraph[V,table]["Pos",vector]
        foreach(Useless,V:entity=writeProp(I:toString(),Pos+vec(0,0,30),ang())) {
            V:setMaterial("debug/debugdrawflat")
            V:setColor(hsv2rgb((I/Path["path",array]:count())*360,1,1))
            V:setNoCollideAll()
        }
    }
}
