[dbc] path finder flow - GameCreators Forum

Author

Message

Alien 001

19

Years of Service

User Offline

Joined: 4th Jul 2005

Location: Gateshead UK

Posted: 9th Oct 2007 13:17

Link

Here is an new way of finding an path. I have check the net and i can not find another path finder like it. it you do could you post an message. time to get to the snippet. It is an old version but it shows the basic of how it works. sorry no comments within the snippet. There are few way to make it faster also some that works for an RTS game. I still have one or two to test out. The path finder is in two parts one that generates the map data and the other one that finds the path. you will find that it is faster that A* path finder. about 80ms for A* , 0-16ms . but the times are depend on the type of map.

here is the snippet.

SET EMULATION ON
sync rate 0
sync on
cls 0

gosub _Veribles

gosub _gen_Grid

do
   cls 0

gosub _Print_info

gosub _buttons

gosub _Draw_Grid

gosub _draw_path

sync
loop

_draw_path:
   path_X = Start_Pos(1) : path_Y = Start_Pos(2)
   path_value = Flow_Data( path_X , path_Y )
   path_direction = 0
   IF path_value > -1
      IF show_path = 1
         start_stage_two = timer()
         while path_value > 1

IF Flow_Data( (path_X - 1) , (path_Y - 1) ) = path_value - 1 then path_direction = 1
            IF Flow_Data( (path_X + 1) , (path_Y - 1) ) = path_value- 1 then path_direction = 3
            IF Flow_Data( (path_X - 1) , (path_Y + 1) ) = path_value - 1 then path_direction = 7
            IF Flow_Data( (path_X + 1) , (path_Y + 1) ) = path_value - 1 then path_direction = 9

IF Flow_Data( path_X , (path_Y - 1) ) = path_value - 1 then path_direction = 2
            IF Flow_Data( (path_X - 1) , path_Y ) = path_value - 1 then path_direction = 4
            IF Flow_Data( (path_X + 1) , path_Y ) = path_value - 1 then path_direction = 6
            IF Flow_Data( path_X , (path_Y + 1 ) ) = path_value - 1 then path_direction = 8

path_X = path_X - 1 : path_Y = path_Y - 1
            rem top left
            IF path_direction = 1
               Temp_X = (path_X-1) * 16 : Temp_Y = (path_Y-1) * 16
               ink RGB(0,0,255) , 0 : box Temp_X , Temp_Y , Temp_X + 14 , Temp_Y + 14
               path_X = path_X - 1 : path_Y = path_Y - 1
               path_value = path_value - 1
            endif
            rem top middle
            IF path_direction = 2
               Temp_X = (path_X ) * 16 : Temp_Y = (path_Y-1) * 16
               ink RGB(0,0,255) , 0 : box Temp_X , Temp_Y , Temp_X + 14 , Temp_Y + 14
               path_X = path_X : path_Y = path_Y - 1
               path_value = path_value - 1
            endif
            rem top right
            IF path_direction = 3
               Temp_X = (path_X+1) * 16 : Temp_Y = (path_Y-1) * 16
               ink RGB(0,0,255) , 0 : box Temp_X , Temp_Y , Temp_X + 14 , Temp_Y + 14
               path_X = path_X + 1 : path_Y = path_Y - 1
               path_value = path_value - 1
            endif

rem left
            IF path_direction = 4
               Temp_X = (path_X-1) * 16 : Temp_Y = (path_Y) * 16
               ink RGB(0,0,255) , 0 : box Temp_X , Temp_Y , Temp_X + 14 , Temp_Y + 14
               path_X = path_X - 1 : path_Y = path_Y
               path_value = path_value - 1
            endif
            rem right
            IF path_direction = 6
               Temp_X = (path_X+1) * 16 : Temp_Y = (path_Y) * 16
               ink RGB(0,0,255) , 0 : box Temp_X , Temp_Y , Temp_X + 14 , Temp_Y + 14
               path_X = path_X + 1 : path_Y = path_Y
               path_value = path_value - 1
            endif

rem bottom left
            IF path_direction = 7
               Temp_X = (path_X-1) * 16 : Temp_Y = (path_Y+1) * 16
               ink RGB(0,0,255) , 0 : box Temp_X , Temp_Y , Temp_X + 14 , Temp_Y + 14
               path_X = path_X - 1 : path_Y = path_Y + 1
               path_value = path_value - 1
            endif
            rem bottom middle
            IF path_direction = 8
               Temp_X = (path_X ) * 16 : Temp_Y = (path_Y+1) * 16
               ink RGB(0,0,255) , 0 : box Temp_X , Temp_Y , Temp_X + 14 , Temp_Y + 14
               path_X = path_X : path_Y = path_Y + 1
               path_value = path_value - 1
            endif
            rem bottom right
            IF path_direction = 9
               Temp_X = (path_X+1) * 16 : Temp_Y = (path_Y+1) * 16
               ink RGB(0,0,255) , 0 : box Temp_X , Temp_Y , Temp_X + 14 , Temp_Y + 14
               path_X = path_X + 1 : path_Y = path_Y + 1
               path_value = path_value - 1
            endif

path_X = path_X + 1 : path_Y = path_Y + 1

endwhile
         end_stage_two = TIMER()
      endif
   endif
return

_path_finder:
   show_path = 1

temp_Places_count = 0
   FOR Y = 1 to 30
   FOR X = 1 to 30
      IF Grid(X,Y) = 1 then Flow_Data(X,Y) = -1 : temp_Places_count = temp_Places_count + 1
      IF Grid(X,Y) = 0 then Flow_Data(X,Y) = -2
   NEXT X
   NEXT Y

Flow_Data( Target_pos(1) , Target_pos(2) ) = 0
   temp_Places_count = temp_Places_count - 1

current_number = 0
   while temp_Places_count > 0
      FOR Y = 2 to 29
      FOR X = 2 to 29
         IF Flow_Data( X , Y ) = current_number

rem top left
            IF Grid(X-1,Y) = 1 and Grid(X,Y-1) = 1
               IF Flow_Data( X-1 , Y-1 ) = -1 then Flow_Data( X-1 , Y-1 ) = current_number + 1 : temp_Places_count = temp_Places_count - 1
            endif
            rem top
            IF Flow_Data( X , Y-1 ) = -1 then Flow_Data( X , Y-1 ) = current_number + 1 : temp_Places_count = temp_Places_count - 1
            rem top right
            IF Grid(X+1,Y) = 1 and Grid(X,Y-1) = 1
               IF Flow_Data( X+1 , Y-1 ) = -1 then Flow_Data( X+1 , Y-1 ) = current_number + 1 : temp_Places_count = temp_Places_count - 1
            endif

rem left
            IF Flow_Data( X-1 , Y ) = -1 then Flow_Data( X-1 , Y ) = current_number + 1 : temp_Places_count = temp_Places_count - 1
            rem right
            IF Flow_Data( X+1 , Y ) = -1 then Flow_Data( X+1 , Y ) = current_number + 1 : temp_Places_count = temp_Places_count - 1

rem dottom left
            IF Grid(X-1,Y) = 1 and Grid(X,Y+1) = 1
               IF Flow_Data( X-1 , Y+1 ) = -1 then Flow_Data( X-1 , Y+1 ) = current_number + 1 : temp_Places_count = temp_Places_count - 1
            endif
            rem dottom
            IF Flow_Data( X , Y+1 ) = -1 then Flow_Data( X , Y+1 ) = current_number + 1 : temp_Places_count = temp_Places_count - 1
            rem dottom right
            IF Grid(X+1,Y) = 1 and Grid(X,Y+1) = 1
               IF Flow_Data( X+1 , Y+1 ) = -1 then Flow_Data( X+1 , Y+1 ) = current_number + 1 : temp_Places_count = temp_Places_count - 1
            endif

endif
      NEXT X
      NEXT Y
      current_number = current_number + 1
   endwhile

Return

_buttons:
   Button_X = 500 : Button_Y = 300 : button_Width = 100 : button_height = 20
   Draw_3D_button( Button_X , Button_Y , button_Width , button_height , "Map Edit")
   IF Mouse_Within_button( Button_X , Button_Y , button_Width , button_height ) = 1 and mouseclick() = 1
      Mode = 1
   endif

Button_X = 500 : Button_Y = 330 : button_Width = 100 : button_height = 20
   Draw_3D_button( Button_X , Button_Y , button_Width , button_height , "Start Pos")
   IF Mouse_Within_button( Button_X , Button_Y , button_Width , button_height ) = 1 and mouseclick() = 1
      Mode = 2
   endif

Button_X = 500 : Button_Y = 360 : button_Width = 100 : button_height = 20
   Draw_3D_button( Button_X , Button_Y , button_Width , button_height , "Target Pos")
   IF Mouse_Within_button( Button_X , Button_Y , button_Width , button_height ) = 1 and mouseclick() = 1
      Mode = 3
   endif

Button_X = 500 : Button_Y = 390 : button_Width = 100 : button_height = 20
   Draw_3D_button( Button_X , Button_Y , button_Width , button_height , "Start")
   IF Mouse_Within_button( Button_X , Button_Y , button_Width , button_height ) = 1 and mouseclick() = 1
      start_stage_one = TIMER()
      Gosub _path_finder
      end_stage_one = TIMER()
   endif

Button_X = 500 : Button_Y = 420 : button_Width = 100 : button_height = 20
   Draw_3D_button( Button_X , Button_Y , button_Width , button_height , "Clear map")
   IF Mouse_Within_button( Button_X , Button_Y , button_Width , button_height ) = 1 and mouseclick() = 1
      gosub _gen_Grid
      Start_Pos(1) = 0 : Start_Pos(2) = 0
      Target_pos(1) = 0 : Target_pos(2) = 0
      FOR Y = 1 to 30
      FOR X = 1 to 30
         Flow_Data(X,Y) = 0
      NEXT X
      NEXT Y
      show_path = 0
   endif

Button_X = 500 : Button_Y = 450 : button_Width = 100 : button_height = 20
   Draw_3D_button( Button_X , Button_Y , button_Width , button_height , "Exit")
   IF Mouse_Within_button( Button_X , Button_Y , button_Width , button_height ) = 1 and mouseclick() = 1 then Cls 0 : sync : end

For X = 1 to 30
      For Y = 1 to 30
         Button_X = (x-1) * 16 : Button_Y = (y-1) * 16 : button_Width = 15 : button_height = 15

IF mode = 1
            IF X > 1 and X < 30
               IF Y > 1 and Y < 30
                  IF Mouse_Within_button( Button_X , Button_Y , button_Width , button_height ) = 1 and mouseclick() = 1 then Grid(X,Y) = 0
                  IF Mouse_Within_button( Button_X , Button_Y , button_Width , button_height ) = 1 and mouseclick() = 2 then Grid(X,Y) = 1
               endif
            endif
         endif

IF Mode = 2
            IF Grid(X,Y) = 1
               IF Mouse_Within_button( Button_X , Button_Y , button_Width , button_height ) = 1 and mouseclick() = 1
                  Start_Pos(1) = X  : Start_Pos(2) = Y
               endif
            endif
         endif

If mode = 3
            if Grid(X,Y) = 1
               IF Mouse_Within_button( Button_X , Button_Y , button_Width , button_height ) = 1 and mouseclick() = 1
                  Target_pos(1) = X : Target_pos(2) = Y
               endif
            endif
         endif

Next X
   Next X
return

_Print_info:
   ink RGB(255,255,255) , 0
   text 500 , 20 , "Path finder Flow"
   text 500 , 40 , "Joseph Allen (ALIEN)"

IF Mode = 1 then text 500 , 60 , "mode: Map edit"
   IF Mode = 2 then text 500 , 60 , "mode: Start Pos"
   IF Mode = 3 then text 500 , 60 , "mode: Target Pos"

text 500 , 100 , "Start Pos X: " + str$( Start_Pos( 1 ) )
   text 500 , 120 , "Start Pos Y: " + str$( Start_Pos( 2 ) )
   text 500 , 140 , "Target Pos X: " + str$( Target_pos( 1 ) )
   text 500 , 160 , "Target Pos Y: " + str$( Target_pos( 2 ) )

text 500 , 180 , "Stage 1 " + str$( end_stage_one - start_stage_one ) + " ms"
   text 500 , 200 , "Stage 2 " + str$( end_stage_two - start_stage_two ) + " ms"

text 500 , 220 , "# of steps: " + str$( Flow_Data( Start_Pos( 1 ) , Start_Pos( 2 ) ) )

return

_Draw_Grid:
   ink RGB(128,0,0) , 0
   box 0 , 0 , 479 , 479

For X = 1 to 30
      For Y = 1 to 30
         IF Grid(X,Y) = 0 then ink RGB(0,0,0) , 0
         IF Grid(X,Y) > 0 then ink RGB(128,128,128) , 0

Temp_X = (x-1) * 16 : Temp_Y = (y-1) * 16
         box Temp_X , Temp_Y , Temp_X + 14 , Temp_Y + 14
         rem ink RGB(255,255,255) , 0 : text (x-1) * 16 , (y-1) * 16 , str$(Grid(X,Y,0))

IF X = Start_Pos(1) and Y = Start_Pos(2)
            ink RGB(0,128,0) , 0
            Temp_X = (x-1) * 16 : Temp_Y = (Y-1) * 16
            Box Temp_X , Temp_Y , Temp_X + 14 , Temp_Y + 14
         endif

IF X = Target_pos(1) and Y = Target_pos(2)
            ink RGB(128,0,0) , 0
            Temp_X = (x-1) * 16 : Temp_Y = (Y-1) * 16
            Box Temp_X , Temp_Y , Temp_X + 14 , Temp_Y + 14
         endif

if spacekey() = 1
            if Flow_Data(X,Y) >= 0
               ink RGB(255,255,255) , 0 : text Temp_X , Temp_Y , str$( Flow_Data(X,Y) )
            endif
         endif

Next Y
   Next X
return

_gen_Grid:
   for x=1 to 30
      for y=1 to 30
         grid(x,y)=1
         if x=1 or x=30 or y=1 or y=30 then grid(x,y)=0
      next y
   next x
return

_Veribles:
   Dim Grid(30,30)
   Dim Start_Pos(2)
   Dim Target_pos(2)

Mode = 1
   DIM Flow_Data(30,30)
   show_path = 0

return

Function Draw_3D_button( X , Y , Width , Height , Text$ )
   Ink rgb( 120 , 120 , 120 ) , 0 : Box X , Y ,  X + Width  , Y + Height : rem Top left
   ink rgb( 250 , 250 , 250 ) , 0 : Box X + 1 , Y + 1 , X + Width , Y + Height : rem bottom right
   Ink rgb( 220 , 220 , 220 ) , 0 : box X + 1 , Y + 1 , X + Width - 1 , Y + Height - 1 : rem panel
   Temp_text_X = X + (Width / 2)
   Temp_Text_Y = Y + ((Height - 15) / 2)
   Ink rgb(0,0,0),0 : CENTER TEXT Temp_text_X , Temp_Text_Y , Text$
endfunction

Function Mouse_Within_button( X , Y , Width , Height )
   YesORNo = 0
   IF MouseX() >= X and MouseX() <= X + width and MOUSEY() >= Y and MOUSEY() <= Y + HEIGHT
      YesORNo = 1
   endif
endfunction YesORNo

+ Code Snippet

SET EMULATION ON
sync rate 0
sync on
cls 0

gosub _Veribles

gosub _gen_Grid

do
   cls 0

   gosub _Print_info

   gosub _buttons

   gosub _Draw_Grid

   gosub _draw_path

   sync
loop

_draw_path:
   path_X = Start_Pos(1) : path_Y = Start_Pos(2)
   path_value = Flow_Data( path_X , path_Y )
   path_direction = 0
   IF path_value > -1
      IF show_path = 1
         start_stage_two = timer()
         while path_value > 1

            IF Flow_Data( (path_X - 1) , (path_Y - 1) ) = path_value - 1 then path_direction = 1
            IF Flow_Data( (path_X + 1) , (path_Y - 1) ) = path_value- 1 then path_direction = 3
            IF Flow_Data( (path_X - 1) , (path_Y + 1) ) = path_value - 1 then path_direction = 7
            IF Flow_Data( (path_X + 1) , (path_Y + 1) ) = path_value - 1 then path_direction = 9

            IF Flow_Data( path_X , (path_Y - 1) ) = path_value - 1 then path_direction = 2
            IF Flow_Data( (path_X - 1) , path_Y ) = path_value - 1 then path_direction = 4
            IF Flow_Data( (path_X + 1) , path_Y ) = path_value - 1 then path_direction = 6
            IF Flow_Data( path_X , (path_Y + 1 ) ) = path_value - 1 then path_direction = 8

            path_X = path_X - 1 : path_Y = path_Y - 1
            rem top left
            IF path_direction = 1
               Temp_X = (path_X-1) * 16 : Temp_Y = (path_Y-1) * 16
               ink RGB(0,0,255) , 0 : box Temp_X , Temp_Y , Temp_X + 14 , Temp_Y + 14
               path_X = path_X - 1 : path_Y = path_Y - 1
               path_value = path_value - 1
            endif
            rem top middle
            IF path_direction = 2
               Temp_X = (path_X ) * 16 : Temp_Y = (path_Y-1) * 16
               ink RGB(0,0,255) , 0 : box Temp_X , Temp_Y , Temp_X + 14 , Temp_Y + 14
               path_X = path_X : path_Y = path_Y - 1
               path_value = path_value - 1
            endif
            rem top right
            IF path_direction = 3
               Temp_X = (path_X+1) * 16 : Temp_Y = (path_Y-1) * 16
               ink RGB(0,0,255) , 0 : box Temp_X , Temp_Y , Temp_X + 14 , Temp_Y + 14
               path_X = path_X + 1 : path_Y = path_Y - 1
               path_value = path_value - 1
            endif

            rem left
            IF path_direction = 4
               Temp_X = (path_X-1) * 16 : Temp_Y = (path_Y) * 16
               ink RGB(0,0,255) , 0 : box Temp_X , Temp_Y , Temp_X + 14 , Temp_Y + 14
               path_X = path_X - 1 : path_Y = path_Y
               path_value = path_value - 1
            endif
            rem right
            IF path_direction = 6
               Temp_X = (path_X+1) * 16 : Temp_Y = (path_Y) * 16
               ink RGB(0,0,255) , 0 : box Temp_X , Temp_Y , Temp_X + 14 , Temp_Y + 14
               path_X = path_X + 1 : path_Y = path_Y
               path_value = path_value - 1
            endif

            rem bottom left
            IF path_direction = 7
               Temp_X = (path_X-1) * 16 : Temp_Y = (path_Y+1) * 16
               ink RGB(0,0,255) , 0 : box Temp_X , Temp_Y , Temp_X + 14 , Temp_Y + 14
               path_X = path_X - 1 : path_Y = path_Y + 1
               path_value = path_value - 1
            endif
            rem bottom middle
            IF path_direction = 8
               Temp_X = (path_X ) * 16 : Temp_Y = (path_Y+1) * 16
               ink RGB(0,0,255) , 0 : box Temp_X , Temp_Y , Temp_X + 14 , Temp_Y + 14
               path_X = path_X : path_Y = path_Y + 1
               path_value = path_value - 1
            endif
            rem bottom right
            IF path_direction = 9
               Temp_X = (path_X+1) * 16 : Temp_Y = (path_Y+1) * 16
               ink RGB(0,0,255) , 0 : box Temp_X , Temp_Y , Temp_X + 14 , Temp_Y + 14
               path_X = path_X + 1 : path_Y = path_Y + 1
               path_value = path_value - 1
            endif

            path_X = path_X + 1 : path_Y = path_Y + 1

         endwhile
         end_stage_two = TIMER()
      endif
   endif
return

_path_finder:
   show_path = 1

   temp_Places_count = 0
   FOR Y = 1 to 30
   FOR X = 1 to 30
      IF Grid(X,Y) = 1 then Flow_Data(X,Y) = -1 : temp_Places_count = temp_Places_count + 1
      IF Grid(X,Y) = 0 then Flow_Data(X,Y) = -2
   NEXT X
   NEXT Y

   Flow_Data( Target_pos(1) , Target_pos(2) ) = 0
   temp_Places_count = temp_Places_count - 1

   current_number = 0
   while temp_Places_count > 0
      FOR Y = 2 to 29
      FOR X = 2 to 29
         IF Flow_Data( X , Y ) = current_number

            rem top left
            IF Grid(X-1,Y) = 1 and Grid(X,Y-1) = 1
               IF Flow_Data( X-1 , Y-1 ) = -1 then Flow_Data( X-1 , Y-1 ) = current_number + 1 : temp_Places_count = temp_Places_count - 1
            endif
            rem top
            IF Flow_Data( X , Y-1 ) = -1 then Flow_Data( X , Y-1 ) = current_number + 1 : temp_Places_count = temp_Places_count - 1
            rem top right
            IF Grid(X+1,Y) = 1 and Grid(X,Y-1) = 1
               IF Flow_Data( X+1 , Y-1 ) = -1 then Flow_Data( X+1 , Y-1 ) = current_number + 1 : temp_Places_count = temp_Places_count - 1
            endif

            rem left
            IF Flow_Data( X-1 , Y ) = -1 then Flow_Data( X-1 , Y ) = current_number + 1 : temp_Places_count = temp_Places_count - 1
            rem right
            IF Flow_Data( X+1 , Y ) = -1 then Flow_Data( X+1 , Y ) = current_number + 1 : temp_Places_count = temp_Places_count - 1

            rem dottom left
            IF Grid(X-1,Y) = 1 and Grid(X,Y+1) = 1
               IF Flow_Data( X-1 , Y+1 ) = -1 then Flow_Data( X-1 , Y+1 ) = current_number + 1 : temp_Places_count = temp_Places_count - 1
            endif
            rem dottom
            IF Flow_Data( X , Y+1 ) = -1 then Flow_Data( X , Y+1 ) = current_number + 1 : temp_Places_count = temp_Places_count - 1
            rem dottom right
            IF Grid(X+1,Y) = 1 and Grid(X,Y+1) = 1
               IF Flow_Data( X+1 , Y+1 ) = -1 then Flow_Data( X+1 , Y+1 ) = current_number + 1 : temp_Places_count = temp_Places_count - 1
            endif

         endif
      NEXT X
      NEXT Y
      current_number = current_number + 1
   endwhile

Return

_buttons:
   Button_X = 500 : Button_Y = 300 : button_Width = 100 : button_height = 20
   Draw_3D_button( Button_X , Button_Y , button_Width , button_height , "Map Edit")
   IF Mouse_Within_button( Button_X , Button_Y , button_Width , button_height ) = 1 and mouseclick() = 1
      Mode = 1
   endif

   Button_X = 500 : Button_Y = 330 : button_Width = 100 : button_height = 20
   Draw_3D_button( Button_X , Button_Y , button_Width , button_height , "Start Pos")
   IF Mouse_Within_button( Button_X , Button_Y , button_Width , button_height ) = 1 and mouseclick() = 1
      Mode = 2
   endif

   Button_X = 500 : Button_Y = 360 : button_Width = 100 : button_height = 20
   Draw_3D_button( Button_X , Button_Y , button_Width , button_height , "Target Pos")
   IF Mouse_Within_button( Button_X , Button_Y , button_Width , button_height ) = 1 and mouseclick() = 1
      Mode = 3
   endif

   Button_X = 500 : Button_Y = 390 : button_Width = 100 : button_height = 20
   Draw_3D_button( Button_X , Button_Y , button_Width , button_height , "Start")
   IF Mouse_Within_button( Button_X , Button_Y , button_Width , button_height ) = 1 and mouseclick() = 1
      start_stage_one = TIMER()
      Gosub _path_finder
      end_stage_one = TIMER()
   endif

   Button_X = 500 : Button_Y = 420 : button_Width = 100 : button_height = 20
   Draw_3D_button( Button_X , Button_Y , button_Width , button_height , "Clear map")
   IF Mouse_Within_button( Button_X , Button_Y , button_Width , button_height ) = 1 and mouseclick() = 1
      gosub _gen_Grid
      Start_Pos(1) = 0 : Start_Pos(2) = 0
      Target_pos(1) = 0 : Target_pos(2) = 0
      FOR Y = 1 to 30
      FOR X = 1 to 30
         Flow_Data(X,Y) = 0
      NEXT X
      NEXT Y
      show_path = 0
   endif

   Button_X = 500 : Button_Y = 450 : button_Width = 100 : button_height = 20
   Draw_3D_button( Button_X , Button_Y , button_Width , button_height , "Exit")
   IF Mouse_Within_button( Button_X , Button_Y , button_Width , button_height ) = 1 and mouseclick() = 1 then Cls 0 : sync : end

   For X = 1 to 30
      For Y = 1 to 30
         Button_X = (x-1) * 16 : Button_Y = (y-1) * 16 : button_Width = 15 : button_height = 15

         IF mode = 1
            IF X > 1 and X < 30
               IF Y > 1 and Y < 30
                  IF Mouse_Within_button( Button_X , Button_Y , button_Width , button_height ) = 1 and mouseclick() = 1 then Grid(X,Y) = 0
                  IF Mouse_Within_button( Button_X , Button_Y , button_Width , button_height ) = 1 and mouseclick() = 2 then Grid(X,Y) = 1
               endif
            endif
         endif

         IF Mode = 2
            IF Grid(X,Y) = 1
               IF Mouse_Within_button( Button_X , Button_Y , button_Width , button_height ) = 1 and mouseclick() = 1
                  Start_Pos(1) = X  : Start_Pos(2) = Y
               endif
            endif
         endif

         If mode = 3
            if Grid(X,Y) = 1
               IF Mouse_Within_button( Button_X , Button_Y , button_Width , button_height ) = 1 and mouseclick() = 1
                  Target_pos(1) = X : Target_pos(2) = Y
               endif
            endif
         endif

      Next X
   Next X
return

_Print_info:
   ink RGB(255,255,255) , 0
   text 500 , 20 , "Path finder Flow"
   text 500 , 40 , "Joseph Allen (ALIEN)"

   IF Mode = 1 then text 500 , 60 , "mode: Map edit"
   IF Mode = 2 then text 500 , 60 , "mode: Start Pos"
   IF Mode = 3 then text 500 , 60 , "mode: Target Pos"

   text 500 , 100 , "Start Pos X: " + str$( Start_Pos( 1 ) )
   text 500 , 120 , "Start Pos Y: " + str$( Start_Pos( 2 ) )
   text 500 , 140 , "Target Pos X: " + str$( Target_pos( 1 ) )
   text 500 , 160 , "Target Pos Y: " + str$( Target_pos( 2 ) )

   text 500 , 180 , "Stage 1 " + str$( end_stage_one - start_stage_one ) + " ms"
   text 500 , 200 , "Stage 2 " + str$( end_stage_two - start_stage_two ) + " ms"

   text 500 , 220 , "# of steps: " + str$( Flow_Data( Start_Pos( 1 ) , Start_Pos( 2 ) ) )

return

_Draw_Grid:
   ink RGB(128,0,0) , 0
   box 0 , 0 , 479 , 479

   For X = 1 to 30
      For Y = 1 to 30
         IF Grid(X,Y) = 0 then ink RGB(0,0,0) , 0
         IF Grid(X,Y) > 0 then ink RGB(128,128,128) , 0

         Temp_X = (x-1) * 16 : Temp_Y = (y-1) * 16
         box Temp_X , Temp_Y , Temp_X + 14 , Temp_Y + 14
         rem ink RGB(255,255,255) , 0 : text (x-1) * 16 , (y-1) * 16 , str$(Grid(X,Y,0))

         IF X = Start_Pos(1) and Y = Start_Pos(2)
            ink RGB(0,128,0) , 0
            Temp_X = (x-1) * 16 : Temp_Y = (Y-1) * 16
            Box Temp_X , Temp_Y , Temp_X + 14 , Temp_Y + 14
         endif

         IF X = Target_pos(1) and Y = Target_pos(2)
            ink RGB(128,0,0) , 0
            Temp_X = (x-1) * 16 : Temp_Y = (Y-1) * 16
            Box Temp_X , Temp_Y , Temp_X + 14 , Temp_Y + 14
         endif

         if spacekey() = 1
            if Flow_Data(X,Y) >= 0
               ink RGB(255,255,255) , 0 : text Temp_X , Temp_Y , str$( Flow_Data(X,Y) )
            endif
         endif

      Next Y
   Next X
return

_gen_Grid:
   for x=1 to 30
      for y=1 to 30
         grid(x,y)=1
         if x=1 or x=30 or y=1 or y=30 then grid(x,y)=0
      next y
   next x
return

_Veribles:
   Dim Grid(30,30)
   Dim Start_Pos(2)
   Dim Target_pos(2)

   Mode = 1
   DIM Flow_Data(30,30)
   show_path = 0

return

Function Draw_3D_button( X , Y , Width , Height , Text$ )
   Ink rgb( 120 , 120 , 120 ) , 0 : Box X , Y ,  X + Width  , Y + Height : rem Top left
   ink rgb( 250 , 250 , 250 ) , 0 : Box X + 1 , Y + 1 , X + Width , Y + Height : rem bottom right
   Ink rgb( 220 , 220 , 220 ) , 0 : box X + 1 , Y + 1 , X + Width - 1 , Y + Height - 1 : rem panel
   Temp_text_X = X + (Width / 2)
   Temp_Text_Y = Y + ((Height - 15) / 2)
   Ink rgb(0,0,0),0 : CENTER TEXT Temp_text_X , Temp_Text_Y , Text$
endfunction

Function Mouse_Within_button( X , Y , Width , Height )
   YesORNo = 0
   IF MouseX() >= X and MouseX() <= X + width and MOUSEY() >= Y and MOUSEY() <= Y + HEIGHT
      YesORNo = 1
   endif
endfunction YesORNo

if you want to see the code in an rts game here is the link.
http://forum.thegamecreators.com/?m=forum_view&t=110489&b=8
still working on the game.

Back to top

Profile PM

luke810

18

Years of Service

User Offline

Joined: 4th Sep 2006

Location: United States

Posted: 15th Oct 2007 05:39

Link

It looks really good but gets stuck up on certain arrangements of blocks and sometimes it just goes over a block like it isn't there. You might want to check that out before you finish the game or the player's custom maps could have arrangements that freeze up the game. I did my own Astar algorithm for my RTS but your's runs quite a bit faster on average.

Back to top

Profile PM

Green7

18

Years of Service

User Offline

Joined: 23rd Nov 2005

Location: Switzerland

Posted: 15th Oct 2007 23:59 Edited at: 16th Oct 2007 00:02

Link

@luke810: this is no offense, but are you sure? did you always hit START after drawing new blocks? i noticed that he goes over blocks if i did not hit start. but that is how it should be i think, no recalculation without START. i could not manage to make it fail...

EDIT: ok, it hangs itself if you set the target into a closed room...

Back to top

Profile PM Website

luke810

18

Years of Service

User Offline

Joined: 4th Sep 2006

Location: United States

Posted: 16th Oct 2007 05:16

Link

It must have been the start thing for the draw over blocks. But if you do a couple sworls and try to find a path out it hangs up.

Back to top

Profile PM

Green7

18

Years of Service

User Offline

Joined: 23rd Nov 2005

Location: Switzerland

Posted: 17th Oct 2007 00:21

Link

that's true... and if you set no start and end it does too. but its a nice thing at all. so, respect, i think i could never do such a thing. im more for optical stuff, less the logical one.

Back to top

Profile PM Website

Ankillito

17

Years of Service

User Offline

Joined: 10th Dec 2006

Location: Litigious California

Posted: 18th Oct 2007 01:48

Link

wow. I have never understood how a COMPUTER could find a way out of a maze, especially that quickly! I deffinately need to figure out your code once I have time...

http://forum.thegamecreators.com/xt/xt_apollo_pic.php?i=1234759

Back to top

Profile PM

Libervurto

18

Years of Service

User Offline

Joined: 30th Jun 2006

Location: On Toast

Posted: 24th Oct 2007 17:30

Link

I came up with something a lot like this but could never get it to work properly. Nice work

The only thing I don't like is that it can move diagonally; when on a square grid that is going through a single pixel.
why do you set emulation on?

If you have the time could you please annotate your code, I'm having trouble following it.

Back to top

Profile PM Email

Alien 001

19

Years of Service

User Offline

Joined: 4th Jul 2005

Location: Gateshead UK

Posted: 2nd Nov 2007 12:35 Edited at: 2nd Nov 2007 12:36

Link

I made the snippet to test the idear of an path finder. I have tried to make an A* path finder but i could not get it to work. Then one night i was think about how i could do one. then it come to me, What about you start at the desition position and direct all position around the point to that direction. here is what is does. in an 5x5 grid

where 0 is the desition position.
where -1 is an blank space you can move to this position
where -2 is an wall you cannot move to this position
where S is the starting postion of something that is going to move to D
Where D is the desition.
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 D -2 S -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1

set the desition position to the value of 0.
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 0 -2 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1

search for current number which at the start is 0. If there is -1 around that position then that position value = current value + 1. here is the next setp.
-1 -1 -1 -1 -1
1 1 -1 -1 -1
1 0 -2 -1 -1
1 1 -1 -1 -1
-1 -1 -1 -1 -1

2 2 2 -1 -1
1 1 2 -1 -1
1 0 -2 -1 -1
1 1 2 -1 -1
2 2 2 -1 -1

2 2 2 3 -1
1 1 2 3 -1
1 0 -2 -1 -1
1 1 2 3 -1
2 2 2 3 -1

2 2 2 3 4
1 1 2 3 4
1 0 -2 4 4
1 1 2 3 4
2 2 2 3 4

This is where is a found a good name for it. All to position point to the desition on the map. or all the point flow to the desition.

that is it for the calulate the map data. now for the path
it is very simple all it does is search around the current position and if there is a value = current value - 1 then move to that position. and that is that. so the path would be 3,2,1,0.
2 2 2 3 4
1 s1 s2 s3 4
1 s0 -2 s4 4
1 s1 s2 s3 4
2 2 2 3 4
The s show the path but there are 2 of then so whick on to take. there both have to same distance. in the snippet it is decided by the order of the if endif staments.

Green7 ... you do have to hit the start button when you have draw new walls. but not when you change to start position.

luke810... it could be that is does not cut the walls.

OBese87... the example at the top sould help you.

Back to top

Profile PM

Latch

18

Years of Service

User Offline

Joined: 23rd Jul 2006

Location:

Posted: 2nd Nov 2007 19:44 Edited at: 2nd Nov 2007 19:47

Link

Very Clever. You come up with some very interesting programs.

You should enter the DBC challenges.

Enjoy your day.

Back to top

Profile PM

PALMER

16

Years of Service

User Offline

Joined: 20th Jan 2008

Location: West Sussex

Posted: 17th Feb 2008 17:38

Link

I read you made a A* finder had problems with it.
If you search Codebase "Pathfinder" or "AI" You will find A* By Mince.

I wrote it recently its well documented and very easy to understand.

I am currently making a RTS too, I have just made A Path finder (Today)that can work in the background.
It also has a stack so just add path_needed(startx,starty,destx,desty,unit) to the stack, then
when each path is found flag it,> unit(unit_num).has_path = 1.

I have worker units, fighting units and I think it would be a good idea to make a seperate pathfinder for each type.

Maybe you got it all sorted now, but if not it may help you.
I will post the new Pathfinder to codebase tomo I am sure it will help.

Back to top

Profile PM Email Website

Sorry your browser is not supported!

Code Snippets / [dbc] path finder flow