package Ġde . rob ol ab . client . tra verser . navigation Ċ Ċ import Ġde . rob ol ab . common . planet . utils . Lookup Planet Ċ import Ġde . rob ol ab . client . tra verser . Navigator State Ċ import Ġde . rob ol ab . common . utils . Priority Queue Ċ import Ġde . rob ol ab . client . tra verser . navigation . Route . Companion . to Start Step Ċ import Ġde . rob ol ab . common . planet . Planet Point Ċ import Ġde . rob ol ab . common . planet . Planet Direction Ċ import Ġde . rob ol ab . common . planet . Planet Path Ċ import Ġde . rob ol ab . common . planet . Planet Ċ import Ġkotlin . math . min Ċ Ċ type alias ĠNe ighbours Function Ġ= Ġ( location : ĠPlan et Point ) Ġ-> ĠList < Route . End Step > Ċ Ċ object ĠD ijk stra Ġ{ ĊĠĠĠ Ġinline Ġfun Ġcreate Field ( ĊĠĠĠĠĠĠĠ Ġstart : ĠPlan et Point , ĊĠĠĠĠĠĠĠ Ġne ighbours : ĠNe ighbours Function , ĊĠĠĠĠĠĠĠ Ġequality Range : ĠFloat Ġ= Ġ 0 . 0 1 f ĊĠĠĠ Ġ): ĠNavigation Field Ġ= Ġcreate Field ( start , Ġne ighbours , ĠFloat . POSITIVE _ INFINITY , Ġequality Range ) ĊĊĠĠĠ Ġinline Ġfun Ġcreate Field ( ĊĠĠĠĠĠĠĠ Ġstart : ĠPlan et Point , ĊĠĠĠĠĠĠĠ Ġne ighbours : ĠNe ighbours Function , ĊĠĠĠĠĠĠĠ Ġcost Limit : ĠFloat , ĊĠĠĠĠĠĠĠ Ġequality Range : ĠFloat Ġ= Ġ 0 . 0 1 f ĊĠĠĠ Ġ): ĠNavigation Field Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġfield Ġ= ĠNavigation Field ( start ) ĊĠĠĠĠĠĠĠ Ġval Ġpri o Queue Ġ= ĠPriority Queue ( compare By ( field :: get Cost )) ĊĠĠĠĠĠĠĠ Ġval Ġvisited Ġ= Ġmutable Set Of < Planet Point >() ĊĠĠĠĠĠĠĠ Ġpri o Queue . add ( start ) ĊĠĠĠĠĠĠĠ Ġwhile Ġ( prio Queue . isNotEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcurrent Ġ= Ġpri o Queue . remove () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvisited . add ( current ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġbase Cost Ġ= Ġfield . get Cost ( current ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( base Cost Ġ> Ġcost Limit ) Ġreturn Ġfield ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( step Ġin Ġne ighbours ( current )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( step . cost Ġ< Ġ 0 Ġ|| Ġstep . end Ġin Ġvisited ) Ġcontinue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnew Cost Ġ= Ġbase Cost Ġ+ Ġstep . cost ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġold Cost Ġ= Ġfield . get Cost ( step . end ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnew Cost Ġ< Ġold Cost Ġ- Ġequality Range Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpri o Queue . remove ( step . end ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfield . set Pre decessor ( step . end , Ġstep . to Start Step ( current ). first , Ġnew Cost ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpri o Queue . add ( step . end ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnew Cost Ġ< Ġold Cost Ġ+ Ġequality Range Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfield . add Pre decessor ( step . end , Ġstep . to Start Step ( current ). first ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġfield ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġinline Ġfun Ġcreate Field ( ĊĠĠĠĠĠĠĠ Ġstart : ĠPlan et Point , ĊĠĠĠĠĠĠĠ Ġne ighbours : ĠNe ighbours Function , ĊĠĠĠĠĠĠĠ Ġcost Limit : ĠFloat Ġ= ĠFloat . POSITIVE _ INFINITY , ĊĠĠĠĠĠĠĠ Ġmatch Predicate : Ġ( Planet Point ) Ġ-> ĠBoolean , ĊĠĠĠĠĠĠĠ Ġstop On Match : ĠBoolean Ġ= Ġtrue , ĊĠĠĠĠĠĠĠ Ġequality Range : ĠFloat Ġ= Ġ 0 . 0 1 f ĊĠĠĠ Ġ): ĠNavigation Field Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġfield Ġ= ĠNavigation Field ( start ) ĊĠĠĠĠĠĠĠ Ġval Ġpri o Queue Ġ= ĠPriority Queue ( compare By ( field :: get Cost )) ĊĠĠĠĠĠĠĠ Ġval Ġvisited Ġ= Ġmutable Set Of < Planet Point >() ĊĠĠĠĠĠĠĠ Ġval Ġnot Matched Locations Ġ= Ġmutable Set Of < Planet Point >() ĊĠĠĠĠĠĠĠ Ġvar Ġmax Cost Ġ= Ġcost Limit Ġ+ Ġequality Range ĊĠĠĠĠĠĠĠ Ġpri o Queue . add ( start ) ĊĠĠĠĠĠĠĠ Ġwhile Ġ( prio Queue . isNotEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcurrent Ġ= Ġpri o Queue . remove () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvisited . add ( current ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġbase Cost Ġ= Ġfield . get Cost ( current ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( base Cost Ġ> Ġmax Cost ) Ġreturn Ġfield ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( step Ġin Ġne ighbours ( current )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnext : ĠPlan et Point Ġ= Ġstep . end ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( step . cost Ġ< Ġ 0 Ġ|| Ġnext Ġin Ġvisited ) Ġcontinue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnew Cost Ġ= Ġbase Cost Ġ+ Ġstep . cost ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( new Cost Ġ> Ġmax Cost ) Ġcontinue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġold Cost Ġ= Ġfield . get Cost ( next ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġupdated : ĠBoolean ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġupdated Ġ= Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnew Cost Ġ< Ġold Cost Ġ- Ġequality Range Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpri o Queue . remove ( next ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfield . set Pre decessor ( next , Ġstep . to Start Step ( current ). first , Ġnew Cost ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpri o Queue . add ( next ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnew Cost Ġ< Ġold Cost Ġ+ Ġequality Range Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfield . add Pre decessor ( next , Ġstep . to Start Step ( current ). first ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( updated Ġ&& Ġnext Ġ! in Ġnot Matched Locations ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! field . is Matched ( next )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! match Predicate ( next )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnot Matched Locations . add ( next ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcontinue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfield . add Matched ( next ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( stop On Match ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmax Cost Ġ= Ġmin ( max Cost , Ġnew Cost Ġ+ Ġequality Range ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġfield . filter Matched Ġ{ Ġfield . get Cost ( it ) Ġ< Ġmax Cost Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġfield ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġshortest Paths ( ĊĠĠĠĠĠĠĠ Ġstart : ĠPlan et Point , ĊĠĠĠĠĠĠĠ Ġne ighbours : ĠNe ighbours Function , ĊĠĠĠĠĠĠĠ Ġequality Range : ĠFloat Ġ= Ġ 0 . 0 1 f , ĊĠĠĠĠĠĠĠ Ġstop On Match : ĠBoolean Ġ= Ġtrue , ĊĠĠĠĠĠĠĠ Ġmatch Predicate : Ġ( Planet Point ) Ġ-> ĠBoolean , ĊĠĠĠ Ġ) Ġ= Ġcreate Field ( ĊĠĠĠĠĠĠĠ Ġstart , ĊĠĠĠĠĠĠĠ Ġne ighbours , ĊĠĠĠĠĠĠĠ Ġmatch Predicate Ġ= Ġmatch Predicate , ĊĠĠĠĠĠĠĠ Ġstop On Match Ġ= Ġstop On Match , ĊĠĠĠĠĠĠĠ Ġequality Range Ġ= Ġequality Range ĊĠĠĠ Ġ). find Routes To Matched ( true , Ġequality Range ) ĊĊĠĠĠ Ġfun Ġshortest Paths ( ĊĠĠĠĠĠĠĠ Ġstart : ĠPlan et Point , ĊĠĠĠĠĠĠĠ Ġne ighbours : ĠNe ighbours Function , ĊĠĠĠĠĠĠĠ Ġtarget : ĠPlan et Point , ĊĠĠĠĠĠĠĠ Ġequality Range : ĠFloat Ġ= Ġ 0 . 0 1 f , ĊĠĠĠĠĠĠĠ Ġstop On Match : ĠBoolean Ġ= Ġtrue ĊĠĠĠ Ġ): ĠList < Route > Ġ= Ġcreate Field ( ĊĠĠĠĠĠĠĠ Ġstart , ĊĠĠĠĠĠĠĠ Ġne ighbours , ĊĠĠĠĠĠĠĠ Ġmatch Predicate Ġ= Ġ{ Ġit Ġ== Ġtarget Ġ}, ĊĠĠĠĠĠĠĠ Ġstop On Match Ġ= Ġstop On Match , ĊĠĠĠĠĠĠĠ Ġequality Range Ġ= Ġequality Range ĊĠĠĠ Ġ). find Routes ( target ) Ċ } Ċ Ċ fun ĠLookup Planet . get Ne ighbours ( location : ĠPlan et Point ): ĠList < Route . End Step > Ġ= ĊĠĠĠ Ġget Paths ( location ). map NotNull Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( it . blocked ) Ġnull ĊĠĠĠĠĠĠĠ Ġelse ĠRoute . End Step ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġit . source Direction , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġit . target , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġit . weight . toFloat () ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ} Ċ Ċ fun ĠPlan et . create Ne ighbours Function (): ĠNe ighbours Function Ġ= ĠLookup Planet ( this ):: get Ne ighbours Ċ Ċ fun ĠMap < Planet Point , ĠMap < Planet Direction , ĠPlan et Path >> . get Ne ighbours ( location : ĠPlan et Point ): ĠList < Route . End Step > Ġ= ĊĠĠĠ Ġthis [ location ]?. map NotNull Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( it . value . blocked ) Ġreturn @ map NotNull Ġnull ĊĠĠĠĠĠĠĠ ĠRoute . End Step ( it . key , Ġit . value . target , Ġit . value . weight . toFloat ()) ĊĠĠĠ Ġ} Ġ?: Ġempty List () Ċ Ċ fun ĠNavigator State . get Ne ighbours ( location : ĠPlan et Point ): ĠList < Route . End Step > Ġ= Ġpaths . get Ne ighbours ( location ) Ċ