#tilesize = 20 

XIncludeFile "pathfinding.pbi" 
InitSprite() 
InitMouse() 
InitKeyboard() 
#width = 30 
#height = 30 

#view_width = 30 
#view_height = 30 


Global Dim blocked.c(#width-1,#height-1) 
Global Dim priority.c(#width-1,#height-1) 

Structure monster 
  x.l 
  y.l 
  x2.l 
  y2.l 
  xto.l 
  yto.l 
  speed.c 
  Path.l 
  num.l 
  pathsize.l 
EndStructure 

Structure player 
  x.l 
  y.l 
  xto.l 
  yto.l 
  Path.l 
EndStructure 

Global Dim monster.monster(10) 
monster(0)\x = 0 
monster(0)\y = 1*#tilesize 
monster(0)\speed = Random(5)+1 
monster(1)\x = 0 
monster(1)\y = 2*#tilesize 
monster(1)\speed = Random(5)+1 
monster(2)\x = 0 
monster(2)\y = 3*#tilesize 
monster(2)\speed = Random(5)+1 
monster(3)\x = 0 
monster(3)\y = 4*#tilesize 
monster(3)\speed = Random(5)+1 

blocked(1,1) = 1 
blocked(1,2) = 1 
blocked(1,3) = 1 
blocked(1,4) = 1 
blocked(1,5) = 1 
blocked(1,6) = 1 
blocked(8,10) = 1 
blocked(12,10) = 1 
blocked(12,9) = 1 
blocked(11,9) = 1 
blocked(10,8) = 1 
blocked(10,12) = 1 

monsters = 4 

Global player.player 
player\x = 10*#tilesize 
player\y = 10*#tilesize 
goto_counter = -1 

pathfinding_structure.pathfinding_structure 
pathfinding_structure\Width = #width 
pathfinding_structure\height = #height 
pathfinding_structure\dynamic = @monster() 
pathfinding_structure\dynamic_size = SizeOf(monster) 
pathfinding_structure\dynamic_count = monsters 
pathfinding_structure\xoff = OffsetOf(monster\x) 
pathfinding_structure\yoff = OffsetOf(monster\y) 
pathfinding_structure\xto_off = OffsetOf(monster\xto) 
pathfinding_structure\yto_off = OffsetOf(monster\yto) 
pathfinding_structure\tilesize = #tilesize 
pathfinding_structure\blocked = @blocked() 
pathfinding_structure\cast_ray = 1 
pathfinding_structure\alt_copymemory = 0 

Procedure elapsed() 
  Static maxfreq.q 
  Protected t.q 
  If maxfreq=0 
    QueryPerformanceFrequency_(@maxfreq) 
    maxfreq=maxfreq/1000000 
  EndIf 
  QueryPerformanceCounter_(@t.q) 
  ProcedureReturn t/maxfreq 
EndProcedure 

Procedure monster_at(x,y,num_monsters,ignore) 
    For i = 0 To num_monsters-1 
      If i <> ignore 
        If monster(i)\x /#tilesize = x And monster(i)\y/#tilesize  = y 
          ProcedureReturn i 
        EndIf 
      EndIf 
    Next i 
    ProcedureReturn -1 
EndProcedure 

Procedure goto_player(num_monsters,*pathfinding_structure.pathfinding_structure) 
  Shared goto_counter 
  Shared average_time_path 
  goto_counter + 1 
  If goto_counter > num_monsters - 1 
    goto_counter = 0 
  EndIf 
  i = goto_counter 
    If monster(i)\Path = 0 
      xd = monster(i)\xto-player\x/#tilesize 
      yd = monster(i)\yto-player\y/#tilesize 
      If xd < 0 : xd * -1 : EndIf 
      If yd < 0 : yd * -1 : EndIf 
      If xd + yd > 1 
        monster(i)\xto = monster(i)\x/#tilesize 
        monster(i)\yto = monster(i)\y/#tilesize 
        t = elapsed() 
        monster(i)\Path = get_path(monster(i)\x/#tilesize,monster(i)\y/#tilesize,player\x/#tilesize,player\y/#tilesize,*pathfinding_structure,i) 
        t = elapsed()-t 
        If average_time_path > 0 
          average_time_path = (t+average_time_path)/2 
        Else 
          average_time_path = t 
        EndIf 
        If monster(i)\Path > 0 
          monster(i)\pathsize = path_get_size(monster(i)\Path) 
          monster(i)\num = 0 
          Debug "Got path" 
        EndIf 
      EndIf 
    EndIf 
EndProcedure 

Procedure walk(num_monsters,*pathfinding_structure.pathfinding_structure) 
  Shared average_time_validation 
  Shared failed_validations 
  For i = 0 To num_monsters-1 
    If monster(i)\Path > 0 
      m = monster_at(monster(i)\xto,monster(i)\yto,num_monsters,i) 
      If m = -1 
        m = monster_at(monster(i)\x / *pathfinding_structure\tilesize,monster(i)\y  /*pathfinding_structure\tilesize,num_monsters,i) 
      EndIf 
      If (monster(i)\x = monster(i)\xto*#tilesize And monster(i)\y = monster(i)\yto *#tilesize) Or m > -1 
        If monster(i)\num < monster(i)\pathsize-1 Or m > -1 
          If m = -1 
            monster(i)\xto = path_get_x(monster(i)\Path,monster(i)\num) 
            monster(i)\yto = path_get_y(monster(i)\Path,monster(i)\num) 
            monster(i)\num + 1 
            t = elapsed() 
            v = validate_path(monster(i)\Path,*pathfinding_structure,i) 
            t = elapsed()-t 
            If average_time_validation > 0 
              average_time_validation = (t+average_time_validation)/2 
            Else 
              average_time_validation = t 
            EndIf 
          EndIf 
          If v = 0 Or m > 0 
            failed_validations + 1 
            xd = monster(i)\x/#tilesize-player\x/#tilesize 
            yd = monster(i)\y/#tilesize-player\y/#tilesize 
            If xd < 0 : xd * -1 : EndIf 
            If yd < 0 : yd * -1 : EndIf 
            If xd + yd > 1 
              FreeMemory(monster(i)\Path) 
              t = elapsed() 
              monster(i)\Path = get_path(monster(i)\x/#tilesize,monster(i)\y/#tilesize,player\x/#tilesize,player\y/#tilesize,*pathfinding_structure,i) 
              t = elapsed()-t 
              If average_time_path > 0 
                average_time_path = (t+average_time_path)/2 
              Else 
                average_time_path = t 
              EndIf 
              If monster(i)\Path > 0 
                monster(i)\pathsize = path_get_size(monster(i)\Path) 
                monster(i)\num = 0 
                monster(i)\xto = path_get_x(monster(i)\Path,0) 
                monster(i)\yto = path_get_y(monster(i)\Path,0) 
              EndIf 
            EndIf 
          EndIf 
        EndIf 
      Else 
        If monster(i)\x < monster(i)\xto*#tilesize And blocked((monster(i)\x+monster(i)\speed)/#tilesize,monster(i)\y/#tilesize) = 0 
          monster(i)\x + monster(i)\speed 
          If monster(i)\x > monster(i)\xto*#tilesize 
            monster(i)\x = monster(i)\xto*#tilesize 
          EndIf 
          Continue 
        ElseIf monster(i)\x > monster(i)\xto*#tilesize And blocked((monster(i)\x-monster(i)\speed)/#tilesize,monster(i)\y/#tilesize)=0 
          monster(i)\x - monster(i)\speed 
          If monster(i)\x < monster(i)\xto*#tilesize 
            monster(i)\x = monster(i)\xto*#tilesize 
          EndIf 
          Continue 
        EndIf 
      
      
      
        If monster(i)\y < monster(i)\yto*#tilesize And blocked(monster(i)\x/#tilesize,(monster(i)\y+monster(i)\speed)/#tilesize)=0 
          monster(i)\y + monster(i)\speed 
          If monster(i)\y > monster(i)\yto*#tilesize 
            monster(i)\y = monster(i)\yto*#tilesize 
          EndIf 
          Continue 
        ElseIf monster(i)\y > monster(i)\yto*#tilesize And blocked(monster(i)\x/#tilesize,(monster(i)\y-monster(i)\speed)/#tilesize)=0 
          monster(i)\y - monster(i)\speed 
          If monster(i)\y < monster(i)\yto*#tilesize 
            monster(i)\y = monster(i)\yto*#tilesize 
          EndIf 
          Continue 
        EndIf 
      
      EndIf 
    EndIf 
  Next i 
EndProcedure 

Procedure draw(num_monsters) 
  Shared average_time_path 
  Shared average_time_validation 
  Shared failed_validations 
  Shared framerate 
  ClearScreen(#Black) 
  StartDrawing(ScreenOutput()) 

  For i = 0 To num_monsters-1 
    Box(monster(i)\x,monster(i)\y,#tilesize,#tilesize,#Green) 
    DrawingMode(#PB_2DDrawing_Outlined) 
    Box(monster(i)\x,monster(i)\y,#tilesize,#tilesize,#White) 
    DrawingMode(#PB_2DDrawing_Default) 
    If monster(i)\Path > 0 
    xx = monster(i)\x 
    yy = monster(i)\y 
    For z = monster(i)\num To monster(i)\pathsize-1 
      x = path_get_x(monster(i)\Path,z)*#tilesize 
      y = path_get_y(monster(i)\Path,z)*#tilesize 
      LineXY(xx+#tilesize/2,yy+#tilesize/2,x+#tilesize/2,y+#tilesize/2,#White) 
      xx = x 
      yy = y 
    Next z 
    EndIf 
  Next i 

  Box(player\x,player\y,#tilesize,#tilesize,#Blue) 
  DrawingMode(#PB_2DDrawing_Outlined) 
  Box(player\x,player\y,#tilesize,#tilesize,#White) 
  DrawingMode(#PB_2DDrawing_Default) 
  For x = 0 To #view_width-1 
    For y = 0 To #view_height-1 
      If blocked(x,y) = 1 
        Box(x*#tilesize,y*#tilesize,#tilesize,#tilesize,#Red) 
        DrawingMode(#PB_2DDrawing_Outlined) 
        Box(x*#tilesize,y*#tilesize,#tilesize,#tilesize,#White) 
        DrawingMode(#PB_2DDrawing_Default) 
      EndIf 
    Next y 
  Next x 
  DrawingMode(#PB_2DDrawing_Transparent) 
  DrawText(45,5," AVG path generation time: "+StrF(average_time_path/1000,3)+"ms",#White,#Black) 
  DrawText(45,5+TextHeight("P")," AVG path validation time: "+StrF(average_time_validation/1000,3)+"ms",#White,#Black) 
  DrawText(45,5+TextHeight("P")*2," Failed validations: "+Str(failed_validations),#White,#Black) 
  DrawText(45,5+TextHeight("P")*3," FPS: "+Str(framerate)+"/40",#White,#Black) 
  StopDrawing() 
  FlipBuffers(0) 
  
EndProcedure 

OpenWindow(0,#PB_Ignore,#PB_Ignore,#view_width*#tilesize,#view_height*#tilesize,"Example",#PB_Window_MinimizeGadget|#PB_Window_ScreenCentered|#PB_Window_SystemMenu) 
OpenWindowedScreen(WindowID(0),0,0,WindowWidth(0),WindowHeight(0),0,0,0) 
SetFrameRate(40) 
Repeat 
  walk(monsters,pathfinding_structure) 
  draw(monsters) 
  If ElapsedMilliseconds() < ft 
    fps + 1 
  Else 
    framerate = fps 
    fps = 0 
    ft = ElapsedMilliseconds() + 1000 
  EndIf 
  If sk = 4 
    sk = 0 
    goto_player(monsters,pathfinding_structure) 
  EndIf 
  sk + 1 
  event = WaitWindowEvent(1) 
Until event = #PB_Event_CloseWindow