package Ġworld . greg s . game . playground . path finding . hp ast ar Ċ Ċ import Ġch . eth z . glob is . p ht ree . v 1 3 . Ph Tree 1 3 Ċ import Ġjavafx . scene . layout . Pane Ċ import Ġjavafx . scene . paint . Color Ċ import Ġjavafx . scene . shape . Line Ċ import Ġjavafx . stage . Stage Ċ import Ġorg . j gr ap ht . alg . interfaces . A Star Ad miss ible He uristic Ċ import Ġorg . j gr ap ht . alg . short est path . A Star Short est Path Ċ import Ġorg . j gr ap ht . alg . short est path . Di jk stra Short est Path Ċ import Ġorg . j gr ap ht . graph . Default Weighted Edge Ċ import Ġorg . j gr ap ht . graph . Simple Weighted Graph Ċ import Ġt orn ad of x .* Ċ import Ġworld . greg s . game . playground . Boolean Grid Ċ import Ġworld . greg s . game . playground . Direction Ċ import Ġworld . greg s . game . playground . Node Ċ import Ġworld . greg s . game . playground . path finding . b fs . B read th First Search Ċ import Ġworld . greg s . game . playground . spatial . quad tree . Quad Tree Styles Ċ import Ġworld . greg s . game . playground . ui . zoom . grid Ċ import Ġjava . awt . Rectangle Ċ import Ġkotlin . math . abs Ċ import Ġkotlin . math . floor Ċ import Ġkotlin . system . measure Nano Time ĊĊ Ċ class ĠH ierarchical A Star View Ġ: ĠView (" Hierarchical A Star ") Ġ{ ĊĊĠĠĠ Ġcompanion Ġobject Ġ{ ĊĠĠĠĠĠĠĠ Ġconst Ġval ĠP ADDING Ġ= Ġ 1 0 0 . 0 ĊĠĠĠĠĠĠĠ Ġconst Ġval ĠCOL UMNS Ġ= Ġ 3 2 ĊĠĠĠĠĠĠĠ Ġconst Ġval ĠRO WS Ġ= Ġ 3 2 ĊĠĠĠĠĠĠĠ Ġconst Ġval ĠCL USTER _ SIZE Ġ= Ġ 8 ĊĠĠĠĠĠĠĠ Ġconst Ġval ĠW ALL _ PERCENT Ġ= Ġ 0 . 3 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġlateinit Ġvar Ġcontent : ĠP ane ĊĠĠĠ Ġprivate Ġval Ġb fs Ġ= ĠB read th First Search ( Direction . card inal ) ĊĠĠĠ Ġval Ġdirected Graph Ġ= ĠSimple Weighted Graph < Node , ĠDefault Weighted Edge >( Default Weighted Edge :: class . java ) ĊĠĠĠ Ġprivate Ġval Ġp ht Ġ= ĠPh Tree 1 3 < Int >( 2 ) ĊĠĠĠ Ġval Ġnodes Ġ= Ġmutable Map Of < Int , ĠNode >() ĊĊĠĠĠ Ġfun Ġsetup ( grid : ĠBoolean Grid ) Ġ{ ĊĠĠĠĠĠĠĠ Ġgrid . set ( 1 , Ġ 1 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 2 , Ġ 1 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 4 , Ġ 2 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 6 , Ġ 1 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 6 , Ġ 0 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 6 , Ġ 4 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 6 , Ġ 3 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 7 , Ġ 3 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 8 , Ġ 3 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 1 0 , Ġ 4 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 1 0 , Ġ 5 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 1 1 , Ġ 4 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 1 1 , Ġ 3 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 1 1 , Ġ 2 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 1 3 , Ġ 2 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 1 3 , Ġ 1 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 1 3 , Ġ 3 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 1 4 , Ġ 2 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 2 , Ġ 3 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 3 , Ġ 4 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 3 , Ġ 5 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 3 , Ġ 6 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 2 , Ġ 6 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 1 , Ġ 6 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 5 , Ġ 6 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 5 , Ġ 7 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 7 , Ġ 7 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 7 , Ġ 8 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 8 , Ġ 9 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 9 , Ġ 9 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 8 , Ġ 1 0 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 8 , Ġ 1 1 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 7 , Ġ 1 1 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 9 , Ġ 7 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 1 0 , Ġ 7 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 1 2 , Ġ 7 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 1 2 , Ġ 8 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 1 3 , Ġ 6 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 1 2 , Ġ 1 0 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 1 3 , Ġ 1 0 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 1 1 , Ġ 1 1 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 1 1 , Ġ 1 2 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 1 0 , Ġ 1 3 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 1 2 , Ġ 1 4 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 6 , Ġ 1 3 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 6 , Ġ 1 4 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 5 , Ġ 1 0 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 4 , Ġ 1 0 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 3 , Ġ 1 0 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 3 , Ġ 1 1 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 3 , Ġ 9 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 2 , Ġ 1 3 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 2 , Ġ 1 4 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 2 , Ġ 1 5 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 0 , Ġ 1 2 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrid . set ( 0 , Ġ 1 1 , Ġtrue ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠR enders Ġall Ġtiles ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġshow Grid () Ġ{ ĊĠĠĠĠĠĠĠ Ġfor Ġ( x Ġin Ġ 0 Ġuntil ĠCOL UMNS ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( y Ġin Ġ 0 Ġuntil ĠRO WS ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcell Ġ= Ġroot . grid . blocked ( x , Ġy ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( cell ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġroot . tile ( x , Ġy ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfill Ġ= ĠColor . BLACK ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġshow Clusters () Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġw Ġ= ĠCL USTER _ SIZE Ġ* Ġroot . tile Width ĊĠĠĠĠĠĠĠ Ġval Ġh Ġ= ĠCL USTER _ SIZE Ġ* Ġroot . tile Height ĊĠĠĠĠĠĠĠ Ġfor Ġ( x Ġin Ġw Ġuntil Ġroot . width Ġstep Ġw ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcontent . line ( x , Ġ 0 , Ġx , Ġroot . height ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġstroke Ġ= ĠColor . OR ANGE ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġfor Ġ( y Ġin Ġh Ġuntil Ġroot . height Ġstep Ġh ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcontent . line ( 0 , Ġy , Ġroot . width , Ġy ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġstroke Ġ= ĠColor . OR ANGE ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġadd Node ( x : ĠInt , Ġy : ĠInt ) Ġ: ĠNode Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġnode Ġ= ĠNode ( x , Ġy ) ĊĠĠĠĠĠĠĠ Ġnodes [ y Ġ+ Ġ( x Ġshl Ġ 1 4 )] Ġ= Ġnode ĊĠĠĠĠĠĠĠ Ġdirected Graph . add Vertex ( node ) ĊĠĠĠĠĠĠĠ Ġp ht . put ( long ArrayOf ( x . to Long (), Ġy . to Long ()), Ġy Ġ+ Ġ( x Ġshl Ġ 1 4 )) ĊĠĠĠĠĠĠĠ Ġreturn Ġnode ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġmark Entr ance ( x : ĠInt , Ġy : ĠInt , Ġoffset X : ĠInt , Ġoffset Y : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġstart X Ġ= Ġroot . grid To X ( x Ġ+ Ġoffset X Ġ+ Ġ 0 . 5 ) ĊĠĠĠĠĠĠĠ Ġval Ġstart Y Ġ= Ġroot . grid To Y ( y Ġ+ Ġoffset Y Ġ+ Ġ 0 . 5 ) ĊĠĠĠĠĠĠĠ Ġval Ġend X Ġ= Ġroot . grid To X ( x Ġ+ Ġ 0 . 5 ) ĊĠĠĠĠĠĠĠ Ġval Ġend Y Ġ= Ġroot . grid To Y ( y Ġ+ Ġ 0 . 5 ) ĊĠĠĠĠĠĠĠ Ġcontent . circle ( start X , Ġstart Y , Ġroot . tile Width Ġ/ Ġ 1 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfill Ġ= ĠColor . RED ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġcontent . circle ( end X , Ġend Y , Ġroot . tile Width Ġ/ Ġ 1 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfill Ġ= ĠColor . RED ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġroot . tile Line ( x , Ġy , Ġx Ġ+ Ġoffset X , Ġy Ġ+ Ġoffset Y ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġstroke Ġ= ĠColor . RED ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġa Ġ= Ġadd Node ( x , Ġy ) ĊĠĠĠĠĠĠĠ Ġval Ġb Ġ= Ġadd Node ( x Ġ+ Ġoffset X , Ġy Ġ+ Ġoffset Y ) ĊĠĠĠĠĠĠĠ Ġdirected Graph . add Edge ( a , Ġb ) ĊĠĠĠĠĠĠĠ Ġdirected Graph . set Edge Weight ( a , Ġb , Ġ 1 . 0 ) ĊĠĠĠĠĠĠĠ Ġprintln (" Add Ġedge Ġ$ a Ġ- Ġ$ b Ġ- Ġ 1 . 0 ") ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġshow Entr ances () Ġ{ ĊĠĠĠĠĠĠĠ Ġfor Ġ( x Ġin Ġ 0 Ġuntil ĠRO WS Ġstep ĠCL USTER _ SIZE ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġcount Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( y Ġin Ġ 0 Ġuntil ĠCOL UMNS ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( y . rem ( CLUSTER _ SIZE ) Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( count Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmark Entr ance ( x , Ġfloor ( y Ġ- Ġcount Ġ/ Ġ 2 . 0 ). toInt (), Ġ- 1 , Ġ 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcount Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( x Ġ!= Ġ 0 Ġ&& Ġx . rem ( CLUSTER _ SIZE ) Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġblocked Ġ= Ġroot . grid . blocked ( x , Ġy ) Ġ|| Ġroot . grid . blocked ( x Ġ- Ġ 1 , Ġy ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( blocked ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( count Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmark Entr ance ( x , Ġfloor ( y Ġ- Ġcount Ġ/ Ġ 2 . 0 ). toInt (), Ġ- 1 , Ġ 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcount Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcount ++ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( count Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmark Entr ance ( x , Ġfloor ( COLUMNS Ġ- Ġcount Ġ/ Ġ 2 . 0 ). toInt (), Ġ- 1 , Ġ 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfor Ġ( y Ġin Ġ 0 Ġuntil ĠCOL UMNS Ġstep ĠCL USTER _ SIZE ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġcount Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( x Ġin Ġ 0 Ġuntil ĠRO WS ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( x . rem ( CLUSTER _ SIZE ) Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( count Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmark Entr ance ( floor ( x Ġ- Ġcount Ġ/ Ġ 2 . 0 ). toInt (), Ġy , Ġ 0 , Ġ- 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcount Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( y Ġ!= Ġ 0 Ġ&& Ġy . rem ( CLUSTER _ SIZE ) Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġblocked Ġ= Ġroot . grid . blocked ( x , Ġy ) Ġ|| Ġroot . grid . blocked ( x , Ġy Ġ- Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( blocked ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( count Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmark Entr ance ( floor ( x Ġ- Ġcount Ġ/ Ġ 2 . 0 ). toInt (), Ġy , Ġ 0 , Ġ- 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcount Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcount ++ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( count Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmark Entr ance ( floor ( ROWS Ġ- Ġcount Ġ/ Ġ 2 . 0 ). toInt (), Ġy , Ġ 0 , Ġ- 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġshow Links () Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġgrid Ġ= ĠBoolean Grid ( CLUSTER _ SIZE , ĠCL USTER _ SIZE ) ĊĠĠĠĠĠĠĠ Ġfor Ġ( cluster X Ġin Ġ 0 Ġuntil Ġroot . grid . columns Ġstep ĠCL USTER _ SIZE ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( cluster Y Ġin Ġ 0 Ġuntil Ġroot . grid . rows Ġstep ĠCL USTER _ SIZE ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġgrid . clear () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( x Ġin Ġ 0 Ġuntil ĠCL USTER _ SIZE ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( y Ġin Ġ 0 Ġuntil ĠCL USTER _ SIZE ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġgrid . set ( x , Ġy , Ġroot . grid . blocked ( cluster X Ġ+ Ġx , Ġcluster Y Ġ+ Ġy )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( x Ġin Ġ 0 Ġuntil ĠCL USTER _ SIZE ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( y Ġin Ġ 0 Ġuntil ĠCL USTER _ SIZE ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdistances Ġ= Ġb fs . search N ( grid , ĠNode ( x , Ġy )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdistances . forEach Indexed Ġ{ Ġdx , Ġit Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġit . forEach Indexed Ġ{ Ġdy , Ġdistance Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif ( distance Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġa Ġ= Ġnodes [( cluster Y Ġ+ Ġy ) Ġ+ Ġ(( cluster X Ġ+ Ġx ) Ġshl Ġ 1 4 )] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġb Ġ= Ġnodes [( cluster Y Ġ+ Ġdy ) Ġ+ Ġ(( cluster X Ġ+ Ġdx ) Ġshl Ġ 1 4 )] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif ( a Ġ!= Ġnull Ġ&& Ġb Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdirected Graph . add Edge ( a , Ġb ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdirected Graph . set Edge Weight ( a , Ġb , Ġdistance ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġroot . tile Line ( a . x , Ġa . y , Ġb . x , Ġb . y ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġstroke Ġ= ĠColor . RED ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġroot . tile Text ( a . x , Ġa . y , Ġb . x , Ġb . y , Ġdistance . toString ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġstroke Ġ= ĠColor . BLUE ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġstart () Ġ{ Ċ // ĠĠĠĠĠĠĠ Ġsetup ( root . grid ) ĊĠĠĠĠĠĠĠ Ġreload () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠRe loads Ġgrid ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġreload () Ġ{ ĊĠĠĠĠĠĠĠ Ġroot . grid . fill Random ( WALL _ PERCENT ) ĊĠĠĠĠĠĠĠ Ġroot . reload Grid () ĊĠĠĠĠĠĠĠ Ġshow Grid () ĊĠĠĠĠĠĠĠ Ġshow Entr ances () ĊĠĠĠĠĠĠĠ Ġshow Clusters () ĊĠĠĠĠĠĠĠ Ġshow Links () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġval Ġpath Ġ= Ġmutable ListOf < Line >() ĊĠĠĠ Ġoverride Ġval Ġroot Ġ= Ġgrid ( ĊĠĠĠĠĠĠĠ ĠCOL UMNS , ĊĠĠĠĠĠĠĠ ĠRO WS , ĊĠĠĠĠĠĠĠ ĠP ADDING , ĊĠĠĠĠĠĠĠ ĠP ADDING , Ġ 1 . 0 , Ġ 1 0 . 0 ĊĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠ Ġthis @ Hierarchical A Star View . content Ġ= Ġcontent ĊĠĠĠĠĠĠĠ Ġupdate Size () ĊĊĠĠĠĠĠĠĠ Ġcontent . setOn Mouse Clicked Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprintln (" Clicked Ġ${ it . grid X } Ġ${ it . grid Y }") ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġthis @ Hierarchical A Star View . path . forEach Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis . content . children . remove ( it ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthis @ Hierarchical A Star View . path . clear () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġa star Ġ= ĠA Star Short est Path ( directed Graph , ĠMan h att an Distance ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġset Ġ= Ġdirected Graph . vertex Set () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġsource Ġ= Ġset . random () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtarget Ġ= Ġset . random () ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġprintln (" Source : Ġ$ source ĠTarget : Ġ$ target ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprintln (" A star Ġtook : Ġ${ measure Nano Time Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġa star . getPath ( source , Ġtarget ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ}} ns ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprintln (" Di jk stra 's : Ġ${ measure Nano Time Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠD ijk stra Short est Path . find Path Between ( directed Graph , Ġsource , Ġtarget ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ}} ns ") ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġpath Ġ= Ġa star . getPath ( source , Ġtarget ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġlast : ĠNode ? Ġ= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠ Ġpath ?. vertex List ?. forEach Ġ{ Ġnode Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif ( last Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtile Line ( last !!. x , Ġlast !!. y , Ġnode . x , Ġnode . y ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġstroke Ġ= ĠColor . CY AN ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠstrokeWidth Ġ+= Ġ 1 . 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis @ Hierarchical A Star View . path . add ( this ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlast Ġ= Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprintln ( path ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnearest Ġ= Ġp ht . nearest Ne ighbour ( 1 , Ġ 0 , Ġ 0 ). next () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprintln (" Nearest Ġneighbour : Ġ$ nearest Ġ${ nodes [ nearest ]} ") ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġclass ĠMan h att an Distance Ġ: ĠA Star Ad miss ible He uristic < Node > Ġ{ ĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġget Cost Estimate ( source Vertex : ĠNode , Ġtarget Vertex : ĠNode ): ĠDouble Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġ( abs ( source Vertex . x Ġ- Ġtarget Vertex . x ) Ġ+ Ġabs ( source Vertex . y Ġ- Ġtarget Vertex . y )). toDouble () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ Ċ class ĠH ierarchical A Star App Ġ: ĠApp ( Hierarchical A Star View :: class , ĠQuad Tree Styles :: class ) Ġ{ ĊĠĠĠ Ġoverride Ġfun Ġstart ( stage : ĠStage ) Ġ{ ĊĠĠĠĠĠĠĠ Ġsuper . start ( stage ) ĊĠĠĠĠĠĠĠ Ġfind < Hierarchical A Star View >(). start () ĊĠĠĠ Ġ} Ċ } Ċ Ċ fun Ġmain ( args : ĠArray < String >) Ġ{ ĊĠĠĠ Ġlaunch < Hierarchical A Star App >(* args ) Ċ }