/* Ċ Ġ* ĠCopyright Ġ( C ) Ġ 2 0 1 0 - 2 0 2 0 , ĠD ani lo ĠP ian ini Ġand Ġcontributors Ċ Ġ* Ġlisted Ġin Ġthe Ġmain Ġproject 's Ġal che mist / build . gradle . k ts Ġfile . Ċ Ġ* Ċ Ġ* ĠThis Ġfile Ġis Ġpart Ġof ĠAl che mist , Ġand Ġis Ġdistributed Ġunder Ġthe Ġterms Ġof Ġthe Ċ Ġ* ĠGNU ĠGeneral ĠPublic ĠLicense , Ġwith Ġa Ġlinking Ġexception , Ċ Ġ* Ġas Ġdescribed Ġin Ġthe Ġfile ĠLICENSE Ġin Ġthe ĠAl che mist Ġdistribution 's Ġtop Ġdirectory . Ċ Ġ*/ Ċ Ċ package Ġit . uni bo . al che mist . model . implement ations . nodes Ċ Ċ import Ġit . uni bo . al che mist . model . implement ations . actions . take Percentage Ċ import Ġit . uni bo . al che mist . model . implement ations . geometry . e uclidean 2 d . graph . Un directed Navigation Graph Ċ import Ġit . uni bo . al che mist . model . implement ations . geometry . e uclidean 2 d . graph . path Exists Ċ import Ġit . uni bo . al che mist . model . interfaces . Node Ċ import Ġit . uni bo . al che mist . model . interfaces . Orient ing Pe de stri an Ċ import Ġit . uni bo . al che mist . model . interfaces . Pe de stri an Group Ċ import Ġit . uni bo . al che mist . model . interfaces . Position Ċ import Ġit . uni bo . al che mist . model . interfaces . environments . Environment With Graph Ċ import Ġit . uni bo . al che mist . model . interfaces . geometry . Convex Ge ometric Shape Ċ import Ġit . uni bo . al che mist . model . interfaces . geometry . Ge ometric Shape Factory Ċ import Ġit . uni bo . al che mist . model . interfaces . geometry . Ge ometric Transformation Ċ import Ġit . uni bo . al che mist . model . interfaces . geometry . Vector Ċ import Ġit . uni bo . al che mist . model . interfaces . geometry . e uclidean 2 d . graph . Navigation Graph Ċ import Ġit . uni bo . al che mist . sh uffled Ċ import Ġorg . apache . commons . math 3 . random . Random Generator Ċ import Ġorg . j gr ap ht . alg . short est path . Di jk stra Short est Path Ċ import Ġorg . j gr ap ht . alg . span ning . Prim Minimum Sp anning Tree Ċ import Ġorg . j gr ap ht . graph . As Weighted Graph Ċ import Ġorg . j gr ap ht . graph . Default Edge Ċ Ċ /** Ċ Ġ* ĠAn Ġabstract Ġ[ Orient ing Pe de stri an ], Ġcontains Ġan Ġalgorithm Ġfor Ġthe Ġgeneration Ġof Ġa Ġpseudo - random Ġ[ cognitive Map ]. ĠThe Ċ Ġ* Ġcreation Ġof Ġland marks Ġis Ġleft Ġto Ġsubclasses Ġvia Ġfactory Ġmethod Ġ( see Ġ[ create Land mark In ]). Ċ Ġ* Ċ Ġ* ĠThe Ġ[ environment ] Ġmust Ġfeature Ġa Ġnavigation Ġgraph . Ċ Ġ* Ċ Ġ* Ġ@ param ĠT Ġthe Ġconcent ration Ġtype . Ċ Ġ* Ġ@ param ĠP Ġthe Ġ[ Position ] Ġtype Ġand Ġ[ Vector ] Ġtype Ġfor Ġthe Ġspace Ġthis Ġpe de stri an Ġis Ġinside . Ċ Ġ* Ġ@ param ĠA Ġthe Ġtransformations Ġsupported Ġby Ġthe Ġshapes Ġin Ġthis Ġspace . Ċ Ġ* Ġ@ param ĠL Ġthe Ġtype Ġof Ġland marks Ġin Ġthe Ġpe de stri an 's Ġ[ cognitive Map ]. Ċ Ġ* Ġ@ param ĠN Ġthe Ġtype Ġof Ġnodes Ġof Ġthe Ġnavigation Ġgraph Ġprovided Ġby Ġthe Ġenvironment . Ċ Ġ* Ġ@ param ĠE Ġthe Ġtype Ġof Ġedges Ġof Ġthe Ġnavigation Ġgraph Ġprovided Ġby Ġthe Ġenvironment . Ċ Ġ* Ġ@ param ĠF Ġthe Ġtype Ġof Ġthe Ġshape Ġfactory Ġprovided Ġby Ġthe Ġenvironment . Ċ Ġ*/ Ċ abstract Ġclass ĠAbstract Orient ing Pe de stri an < T , ĠP , ĠA , ĠL , ĠN , ĠE , ĠF >( ĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThe Ġrandom Ġgenerator Ġto Ġuse Ġin Ġorder Ġto Ġpreserve Ġreproduc ibility . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġrandom Generator : ĠRandom Generator , ĊĠĠĠ Ġopen Ġval Ġenvironment : ĠEnvironment With Graph < *, ĠT , ĠP , ĠA , ĠN , ĠE >, ĊĠĠĠ Ġbacking Node : ĠNode < T >, ĊĠĠĠ Ġfinal Ġoverride Ġval Ġknowledge Degree : ĠDouble , ĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThe Ġenvironment Ġthis Ġpe de stri an Ġis Ġinto . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġgroup : ĠPe de stri an Group < T , ĠP , ĠA >? Ġ= Ġnull , ĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠEnvironment 's Ġareas Ġwhose Ġdiameter Ġis Ġsmaller Ġthan Ġ([ min Area ] Ġ* Ġthe Ġdiameter Ġof Ġthis Ġpe de stri an ) Ġwill Ġbe ĊĠĠĠĠ Ġ* Ġreg arded Ġas Ġtoo Ġsmall Ġand Ġdiscarded Ġwhen Ġgenerating Ġthe Ġc ognitive Ġmap Ġ( i . e . Ġno Ġland mark Ġwill Ġbe Ġplaced Ġinside ĊĠĠĠĠ Ġ* Ġthem ). ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġval Ġmin Area : ĠDouble Ġ= Ġ 1 0 . 0 , Ċ ) Ġ: ĠOrient ing Pe de stri an < T , ĠP , ĠA , ĠL , ĠDefault Edge >, ĊĠĠĠ ĠAbstract Hom ogeneous Pe de stri an < T , ĠP , ĠA , ĠF >( random Generator , Ġbacking Node , Ġgroup ) ĊĠĠĠ Ġwhere Ċ P Ġ: ĠPosition < P >, Ċ P Ġ: ĠVector < P >, Ċ A Ġ: ĠGe ometric Transformation < P >, Ċ L Ġ: ĠConv ex Ge ometric Shape < P , ĠA >, Ċ N Ġ: ĠConv ex Ge ometric Shape < P , ĠA >, Ċ F Ġ: ĠGe ometric Shape Factory < P , ĠA > Ġ{ ĊĊĠĠĠ Ġinit Ġ{ ĊĠĠĠĠĠĠĠ Ġrequire ( knowledge Degree Ġin Ġ 0 . 0 .. 1 . 0 ) Ġ{ Ġ" knowledge Ġdegree Ġmust Ġbe Ġin Ġ[ 0 , 1 ]" Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġval Ġvolatile Memory : ĠMutable Map < Convex Ge ometric Shape < P , ĠA >, ĠInt > Ġ= ĠHashMap () ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThe Ġc ognitive Ġmap Ġof Ġthe Ġpe de stri an . ĠThis Ġis Ġgenerated Ġfrom Ġthe Ġ[ environment ]' s Ġgraph Ġas Ġfollows : Ġwe Ġrandomly ĊĠĠĠĠ Ġ* Ġselect Ġa Ġ% Ġof Ġenvironment 's Ġareas Ġequal Ġto Ġthe Ġknowledge Ġdegree Ġof Ġthe Ġpe de stri an , Ġwe Ġthen Ġcreate Ġa Ġland mark ĊĠĠĠĠ Ġ* Ġin Ġeach Ġof Ġthem . ĠThose Ġland marks Ġwill Ġbe Ġthe Ġnodes Ġof Ġthe Ġc ognitive Ġmap . ĠCon cerning Ġthe Ġconnections Ġbetween ĊĠĠĠĠ Ġ* Ġthem , Ġwe Ġproduce Ġa Ġgraph Ġin Ġwhich Ġeach Ġgenerated Ġland mark Ġis Ġconnected Ġto Ġany Ġother Ġland mark Ġreachable Ġfrom Ġit , ĊĠĠĠĠ Ġ* Ġwith Ġan Ġedge Ġwhose Ġweight Ġdepends Ġon Ġthe Ġnumber Ġof Ġareas Ġthat Ġneed Ġto Ġbe Ġtra versed . ĠFinally , Ġthe Ġc ognitive Ġmap ĊĠĠĠĠ Ġ* Ġis Ġa Ġminimum Ġsp anning Ġtree Ġof Ġthe Ġdescribed Ġfull Ġconnected Ġgraph . ĊĠĠĠĠ Ġ* ĠNote Ġthat Ġedges Ġare Ġplain Ġ[ Default Edge ] s , Ġwhich Ġmeans Ġno Ġextra Ġinfo Ġregarding Ġthe Ġconnection Ġbetween Ġland marks ĊĠĠĠĠ Ġ* Ġis Ġstored Ġin Ġthe Ġc ognitive Ġmap . ĠIf Ġtwo Ġland marks Ġare Ġconnected , Ġthe Ġpe de stri an Ġknows Ġthere 's Ġa Ġpath Ġbetween Ġthem ĊĠĠĠĠ Ġ* Ġ( this Ġmay Ġbe Ġsimple Ġor Ġnot , Ġi . e . Ġrepresent able Ġas Ġa Ġsingle Ġsegment , Ġbut Ġthe Ġpe de stri an Ġdoesn 't Ġknow Ġit ). ĠIf Ġtwo ĊĠĠĠĠ Ġ* Ġland marks Ġare Ġnot Ġconnected , Ġthe Ġpe de stri an Ġdoesn 't Ġhave Ġinfo Ġregarding Ġany Ġpath Ġbetween Ġthem , Ġwhich Ġmay ĊĠĠĠĠ Ġ* Ġanyway Ġexist . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġoverride Ġval Ġc ognitive Map : ĠNavigation Graph < P , ĠA , ĠL , ĠDefault Edge > Ġby Ġlazy Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġenvironment Graph Ġ= Ġenvironment . graph ĊĠĠĠĠĠĠĠ Ġ/* ĊĠĠĠĠĠĠĠĠ Ġ* ĠThe Ġrooms Ġin Ġwhich Ġland marks Ġwill Ġbe Ġplaced . ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġval Ġrooms Ġ= Ġenvironment Graph . vertex Set () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. filter Ġ{ Ġit . diameter Ġ> Ġshape . diameter Ġ* Ġmin Area Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. sh uffled ( random Generator ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. toList () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. take Percentage ( knowledge Degree ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. to Mutable List () ĊĠĠĠĠĠĠĠ Ġ/* ĊĠĠĠĠĠĠĠĠ Ġ* Ġland marks [ i ] Ġwill Ġcontain Ġthe Ġland mark Ġgenerated Ġin Ġrooms [ i ]. ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġval Ġland marks Ġ= Ġrooms . map Ġ{ Ġcreate Land mark In ( it ) Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġfull Graph Ġ= ĠUnd irect ed Navigation Graph < P , ĠA , ĠL , ĠDefault Edge >( Default Edge :: class . java ) ĊĠĠĠĠĠĠĠ Ġland marks . forEach Ġ{ Ġfull Graph . add Vertex ( it ) Ġ} ĊĠĠĠĠĠĠĠ Ġrooms . indices . forEach Ġ{ Ġi Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrooms . indices . forEach Ġ{ Ġj Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( i Ġ!= Ġj Ġ&& Ġenvironment Graph . path Exists ( rooms [ i ], Ġrooms [ j ])) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfull Graph . add Edge ( land marks [ i ], Ġland marks [ j ]) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ/* ĊĠĠĠĠĠĠĠĠ Ġ* ĠThe Ġenvironment 's Ġgraph Ġis Ġun weighted , Ġbut Ġedges ' Ġweights Ġdefaults Ġto Ġ 1 . 0 ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġval Ġdi jk stra Ġ= ĠD ijk stra Short est Path ( environment Graph ) ĊĠĠĠĠĠĠĠ Ġval Ġweight Function : Ġ( Default Edge ) Ġ-> ĠDouble Ġ= Ġ{ Ġedge Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtail Ġ= Ġfull Graph . get Edge Source ( edge ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġhead Ġ= Ġfull Graph . get Edge Target ( edge ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ/* ĊĠĠĠĠĠĠĠĠĠĠĠĠ Ġ* ĠThe Ġweight Ġof Ġthe Ġshortest Ġpath Ġbetween Ġtwo Ġrooms Ġ( tail , Ġhead ) Ġis Ġthe Ġnumber ĊĠĠĠĠĠĠĠĠĠĠĠĠ Ġ* Ġof Ġrooms Ġthat Ġneed Ġto Ġbe Ġtra versed Ġto Ġgo Ġfrom Ġtail Ġto Ġhead . ĊĠĠĠĠĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdi jk stra . getPath Weight ( rooms [ land marks . indexOf ( tail )], Ġrooms [ land marks . indexOf ( head )]) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġfull Graph Weighted Ġ= ĠAs Weighted Graph ( full Graph , Ġweight Function , Ġfalse , Ġfalse ) ĊĠĠĠĠĠĠĠ Ġ/* ĊĠĠĠĠĠĠĠĠ Ġ* ĠOnly Ġthe Ġedges Ġin Ġthe Ġsp anning Ġtree Ġare Ġmaintained . ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġfull Graph . removeAll Edges ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfull Graph . edge Set () Ġ- ĠPrim Minimum Sp anning Tree ( full Graph Weighted ). span ning Tree . edges ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġfull Graph ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠCreates Ġa Ġland mark Ġentirely Ġcontained Ġin Ġthe Ġgiven Ġarea . ĠIf Ġsuch Ġarea Ġcontains Ġone Ġor Ġmore Ġdest inations , Ġthe ĊĠĠĠĠ Ġ* Ġreturned Ġland mark Ġmust Ġcontain Ġat Ġleast Ġone Ġof Ġthem . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprotected Ġabstract Ġfun Ġcreate Land mark In ( area : ĠN ): ĠL Ċ } Ċ