any pathfinding algorytm?

Advanced game related topics
SeregaZ
Enthusiast
Enthusiast
Posts: 617
Joined: Fri Feb 20, 2009 9:24 am
Location: Almaty (Kazakhstan. not Borat, but Triple G)
Contact:

any pathfinding algorytm?

Post by SeregaZ »

problem: Genesis\Mega Drive 2 game's Dune have some not very well working algorythm for waypoints. turn off sound - because it is russian :) just watch what happen. if game have big line of obstacles, it starts move to wrong direction. even worse - some time it can have infinity loop of moving.

https://www.youtube.com/watch?v=3gxbLt6Yt8Q

we no have source for that, but probably PC's version have same algorythm, but actualy i am not understand what happen into that code.

Code: Select all

/**
 * Calculate the route to a tile.
 *
 * Stack: 1 - An encoded tile to calculate the route to.
 *
 * @param script The script engine to operate on.
 * @return 0 if we arrived on location, 1 otherwise.
 */
uint16 Script_Unit_CalculateRoute(ScriptEngine *script)
{
	Unit *u;
	uint16 encoded;
	uint16 packedSrc;
	uint16 packedDst;

	u = g_scriptCurrentUnit;
	encoded = STACK_PEEK(1);

	if (u->currentDestination.x != 0 || u->currentDestination.y != 0 || !Tools_Index_IsValid(encoded)) return 1;

	packedSrc = Tile_PackTile(u->o.position);
	packedDst = Tools_Index_GetPackedTile(encoded);

	if (packedDst == packedSrc) {
		u->route[0] = 0xFF;
		u->targetMove = 0;
		return 0;
	}

	if (u->route[0] == 0xFF) {
		Pathfinder_Data res;
		uint8 buffer[42];

		res = Script_Unit_Pathfinder(packedSrc, packedDst, buffer, 40);

		memcpy(u->route, res.buffer, min(res.routeSize, 14));

		if (u->route[0] == 0xFF) {
			u->targetMove = 0;
			if (u->o.type == UNIT_SANDWORM) {
				script->delay = 720;
			}
		}
	} else {
		uint16 distance;

		distance = Tile_GetDistancePacked(packedDst, packedSrc);
		if (distance < 14) u->route[distance] = 0xFF;
	}

	if (u->route[0] == 0xFF) return 1;

	if (u->orientation[0].current != (int8)(u->route[0] * 32)) {
		Unit_SetOrientation(u, (int8)(u->route[0] * 32), false, 0);
		return 1;
	}

	if (!Unit_StartMovement(u)) {
		u->route[0] = 0xFF;
		return 0;
	}

	memmove(&u->route[0], &u->route[1], 13);
	u->route[13] = 0xFF;
	return 1;
}

i start to write my own, but fail with first step :) how to make correct detour? (set left and right click on a field it will set from and into boxes and try to count way)

Code: Select all

Enumeration
  #Window
  
  #MainCanvas
EndEnumeration


Structure MAPy
  MAPx.b[16]
EndStructure
Global Dim MAPArry.MAPy(16)

Structure MAPPoint
  MAPPointX.b
  MAPPointY.b
EndStructure
Global OldPoint.MAPPoint
Global OldToPoint.MAPPoint
OldPoint\MAPPointX = -1
OldPoint\MAPPointY = -1
OldToPoint\MAPPointX = -1
OldToPoint\MAPPointY = -1
  


Procedure.a SetRedMark(x, y)
  
  ret.a
  
  If MAPArry(y)\MAPx[x] = 0
    MAPArry(y)\MAPx[x] = 1
    ret = 1
  EndIf
  
  ProcedureReturn ret
  
EndProcedure

For i = 1 To 20
  ret = 0
  Repeat
    x = Random(15, 1)
    y = Random(15, 1)
    ret = SetRedMark(x, y)
  Until ret = 1
Next

Procedure CountPathNext(fromx, intox, fromy, intoy)
  
    If fromx > intox
      xnext = -1
    ElseIf fromx < intox
      xnext = 1
    Else ; =
      xnext = 0
    EndIf
    
    If fromy > intoy
      ynext = -1
    ElseIf fromy < intoy
      ynext = 1
    Else ; =
      ynext = 0
    EndIf
    
    If MAPArry(fromy + ynext)\MAPx[fromx + xnext] = 0
      MAPArry(fromy + ynext)\MAPx[fromx + xnext] = -3
      
      CountPathNext(fromx + xnext, intox, fromy + ynext, intoy)
      
    EndIf
    
    
  
EndProcedure

Procedure PaintCanvas()
  
  color.l
  
  If OldPoint\MAPPointX > -1 And OldToPoint\MAPPointX > -1
    ; means both points is sets. 
    
    ; start count
    
    CountPathNext(OldPoint\MAPPointX, OldToPoint\MAPPointX, OldPoint\MAPPointY, OldToPoint\MAPPointY)
  EndIf
  
  If StartDrawing(CanvasOutput(#MainCanvas))
    
    For y = 0 To 14
      For x = 0 To 14
        Select MAPArry(y)\MAPx[x]
          Case 0
            color = RGB(100, 200, 100)
          Case 1
            color = RGB(200, 100, 100)
          Case -1
            color = RGB(50, 50, 200)
          Case -2
            color = RGB(100, 100, 200)
          Case -3 
            color = RGB(150, 150, 200)
        EndSelect
        Box(x*32, y*32, 32, 32, color)
      Next
    Next
   
    StopDrawing()
  EndIf
  
EndProcedure
  


If OpenWindow(#Window, 100, 100, 500, 500, "", #PB_Window_MinimizeGadget | #PB_Window_ScreenCentered)
  
  CanvasGadget(#MainCanvas, 10, 10, 480, 480)
  
  PaintCanvas()
  
  Repeat
     Select WaitWindowEvent()

       Case #PB_Event_Gadget

         Select EventGadget()
           
           Case #MainCanvas
             Select EventType() 
               Case #PB_EventType_LeftClick
                 ; select box
                 x = GetGadgetAttribute(#MainCanvas, #PB_Canvas_MouseX)
                 x / 32
                 y = GetGadgetAttribute(#MainCanvas, #PB_Canvas_MouseY)
                 y / 32
                 If MAPArry(y)\MAPx[x] = 0                   
                   If OldPoint\MAPPointX > -1 And OldPoint\MAPPointY > -1
                     MAPArry(OldPoint\MAPPointY)\MAPx[OldPoint\MAPPointX] = 0
                   EndIf                   
                   MAPArry(y)\MAPx[x] = -1
                   OldPoint\MAPPointX = x
                   OldPoint\MAPPointY = y
                   
                   ; clear old path counting
                   For y = 0 To 14
                     For x = 0 To 14
                       If MAPArry(y)\MAPx[x] = -3 
                         MAPArry(y)\MAPx[x] = 0
                       EndIf
                     Next
                   Next
                   
                   PaintCanvas()
                 EndIf
                 
               Case #PB_EventType_RightClick
                 ; go to box
                 x = GetGadgetAttribute(#MainCanvas, #PB_Canvas_MouseX)
                 x / 32
                 y = GetGadgetAttribute(#MainCanvas, #PB_Canvas_MouseY)
                 y / 32
                 If MAPArry(y)\MAPx[x] = 0                   
                   If OldToPoint\MAPPointX > -1 And OldToPoint\MAPPointY > -1
                     MAPArry(OldToPoint\MAPPointY)\MAPx[OldToPoint\MAPPointX] = 0
                   EndIf                   
                   MAPArry(y)\MAPx[x] = -2
                   OldToPoint\MAPPointX = x
                   OldToPoint\MAPPointY = y
                   
                   ; clear old path counting
                   For y = 0 To 14
                     For x = 0 To 14
                       If MAPArry(y)\MAPx[x] = -3 
                         MAPArry(y)\MAPx[x] = 0
                       EndIf
                     Next
                   Next
                   
                   PaintCanvas()
                 EndIf
                 
               Case #PB_EventType_MiddleButtonUp
                 ; third mouse button - to set walls
                 x = GetGadgetAttribute(#MainCanvas, #PB_Canvas_MouseX)
                 x / 32
                 y = GetGadgetAttribute(#MainCanvas, #PB_Canvas_MouseY)
                 y / 32
                 If MAPArry(y)\MAPx[x] = 1
                   MAPArry(y)\MAPx[x] = 0
                   ; clear old path counting
                   For y = 0 To 14
                     For x = 0 To 14
                       If MAPArry(y)\MAPx[x] = -3 
                         MAPArry(y)\MAPx[x] = 0
                       EndIf
                     Next
                   Next
                   
                   PaintCanvas()
                 ElseIf MAPArry(y)\MAPx[x] = 0
                   MAPArry(y)\MAPx[x] = 1
                   
                   ; clear old path counting
                   For y = 0 To 14
                     For x = 0 To 14
                       If MAPArry(y)\MAPx[x] = -3 
                         MAPArry(y)\MAPx[x] = 0
                       EndIf
                     Next
                   Next
                   
                   PaintCanvas()
                 EndIf
                 
             EndSelect

         EndSelect

       Case #PB_Event_CloseWindow
         qiut = 1
   
     EndSelect
   Until qiut = 1

EndIf

End
is any way to make some algo with minimum commands? to transfer it into old game for old hardware.
Comfort
User
User
Posts: 22
Joined: Thu Jul 05, 2018 11:52 pm

Re: any pathfinding algorytm?

Post by Comfort »

https://www.redblobgames.com/pathfindin ... ation.html

Breadth First Search should be enough.
SeregaZ
Enthusiast
Enthusiast
Posts: 617
Joined: Fri Feb 20, 2009 9:24 am
Location: Almaty (Kazakhstan. not Borat, but Triple G)
Contact:

Re: any pathfinding algorytm?

Post by SeregaZ »

i see that "A*" and better is "Jump how it names"... but it is not clear for me :) i have some grid and it have some flag = can move or cant. but didnt see how system deside wich boxes can be choiced for path.
Comfort
User
User
Posts: 22
Joined: Thu Jul 05, 2018 11:52 pm

Re: any pathfinding algorytm?

Post by Comfort »

My reply may have not been useful in the way you wished, but I think it is required reading for any game developer.

I will try to add a BFS pathfinder code to yours by the end of today.
Comfort
User
User
Posts: 22
Joined: Thu Jul 05, 2018 11:52 pm

Re: any pathfinding algorytm?

Post by Comfort »

https://prnt.sc/18s3uiq

This image shows how a BFS works.

The numbers indicate the depth at which each cell was examined. Once the destination/enemy/exit has been reached, we trace it back.
SeregaZ
Enthusiast
Enthusiast
Posts: 617
Joined: Fri Feb 20, 2009 9:24 am
Location: Almaty (Kazakhstan. not Borat, but Triple G)
Contact:

Re: any pathfinding algorytm? [cancel]

Post by SeregaZ »

question is canceled. all that algorytm is nice. but you image how many memory it will eat? for our case it is Sega Genesis\Mega Drive. it no have memory :) only very small count...
Comfort
User
User
Posts: 22
Joined: Thu Jul 05, 2018 11:52 pm

Re: any pathfinding algorytm?

Post by Comfort »

The memory used depends of the size of the map.

easycalc = mapWidth * mapHeight * cellStructureSize

The cell structure I use is 16 bytes long and can be reduced because it has a memory pointer, which can be replaced with byte coordinates.

Then there is the queue, a linked list with each item being deleted once processed... again, only coordinates.
SeregaZ
Enthusiast
Enthusiast
Posts: 617
Joined: Fri Feb 20, 2009 9:24 am
Location: Almaty (Kazakhstan. not Borat, but Triple G)
Contact:

Re: any pathfinding algorytm?

Post by SeregaZ »

maps is 32x32, 64x64 and 128x128

cellStructureSize - it is directions? 8.
Comfort
User
User
Posts: 22
Joined: Thu Jul 05, 2018 11:52 pm

Re: any pathfinding algorytm?

Post by Comfort »

Direction information is separate, in an array.

Code: Select all

#iDir_South = 1
#iDir_West = 2
#iDir_East = 4
#iDir_North = 8
#iDir_SouthWest = 16
#iDir_SouthEast = 32
#iDir_NorthWest = 64
#iDir_NorthEast = 128

Structure iDir
  xo.l
  yo.l
  v.l
EndStructure

Global Dim iDir.iDir(7), Dim iDir$(7)

Enumeration
  #iNorth    
  #iWest
  #iEast
  #iSouth
  #iSouthWest
  #iSouthEast
  #iNorthWest
  #iNorthEast
EndEnumeration


iDir(#iNorth)\xo=0 : iDir(#iNorth)\yo=-1  : iDir(#iNorth)\v=8 
iDir(#iEast)\xo=1 : iDir(#iEast)\yo=0  : iDir(#iEast)\v=4 
iDir(#iSouth)\xo=0 : iDir(#iSouth)\yo=1 : iDir(#iSouth)\v=1 
iDir(#iWest)\xo=-1 : iDir(#iWest)\yo=0 : iDir(#iWest)\v=2
iDir(#iSouthWest)\xo=-1 : iDir(#iSouthWest)\yo=1 : iDir(#iSouthWest)\v=16
iDir(#iSouthEast)\xo=1 : iDir(#iSouthEast)\yo=1 : iDir(#iSouthEast)\v=32
iDir(#iNorthWest)\xo=-1 : iDir(#iNorthWest)\yo=-1 : iDir(#iNorthWest)\v=64 
iDir(#iNorthEast)\xo=1 : iDir(#iNorthEast)\yo=-1 : iDir(#iNorthEast)\v=128
iDir$(#iNorth)="North" ; these are not required - but useful when debugging
iDir$(#iWest)="West"
iDir$(#iEast)="East"
iDir$(#iSouth)="South"
iDir$(#iSouthWest)="SouthWest"
iDir$(#iSouthEast)="SouthEast"
iDir$(#iNorthWest)="NorthWest"
iDir$(#iNorthEast)="NorthEast"
Comfort
User
User
Posts: 22
Joined: Thu Jul 05, 2018 11:52 pm

Re: any pathfinding algorytm?

Post by Comfort »

Here is the code. I have changed the way you stored the map and added procedures to make it clearer.

Right clicking sets the fromPoint and left clicking the toPoint.

I have also added a MapSize constant.

Code: Select all

EnableExplicit

#MapSize = 32
CompilerSelect #MapSize
  CompilerCase 16
    #cellsize = 32
  CompilerCase 32
    #cellSize = 16
  CompilerCase 64
    #cellSize = 8
  CompilerDefault
    #cellSize = 4
CompilerEndSelect

;Structure MAPy
;  MAPx.b[#MapSize]
;'EndStructure

Global Dim MAPArry(#MapSize,#MapSize)

Structure MAPPoint
  MAPPointX.b
  MAPPointY.b
EndStructure

Global fromPoint.MAPPoint, toPoint.MAPPoint
fromPoint\MAPPointX = -1 : toPoint\MAPPointX = -1

Enumeration
  #Window  
  #MainCanvas
EndEnumeration
;-Start of search code
#iDir_South = 1
#iDir_West = 2
#iDir_East = 4
#iDir_North = 8
#iDir_SouthWest = 16
#iDir_SouthEast = 32
#iDir_NorthWest = 64
#iDir_NorthEast = 128

Structure iDir
  xo.b
  yo.b
  ;v.a  ; available directions from this cell
EndStructure

Global Dim iDir.iDir(7)
;Global Dim iDir$(7)

Enumeration
  #iNorth    
  #iWest
  #iEast
  #iSouth
  #iSouthWest
  #iSouthEast
  #iNorthWest
  #iNorthEast
EndEnumeration

iDir(#iNorth)\xo=0      : iDir(#iNorth)\yo=-1     ;: iDir(#iNorth)\v=8 
iDir(#iEast)\xo=1       : iDir(#iEast)\yo=0       ;: iDir(#iEast)\v=4 
iDir(#iSouth)\xo=0      : iDir(#iSouth)\yo=1      ;: iDir(#iSouth)\v=1 
iDir(#iWest)\xo=-1      : iDir(#iWest)\yo=0       ;: iDir(#iWest)\v=2
iDir(#iSouthWest)\xo=-1 : iDir(#iSouthWest)\yo=1  ;: iDir(#iSouthWest)\v=16
iDir(#iSouthEast)\xo=1  : iDir(#iSouthEast)\yo=1  ;: iDir(#iSouthEast)\v=32
iDir(#iNorthWest)\xo=-1 : iDir(#iNorthWest)\yo=-1 ;: iDir(#iNorthWest)\v=64 
iDir(#iNorthEast)\xo=1  : iDir(#iNorthEast)\yo=-1 ;: iDir(#iNorthEast)\v=128

;iDir$(#iNorth)="North" ; these are not required - but useful when debugging
;iDir$(#iWest)="West"
;iDir$(#iEast)="East"
;iDir$(#iSouth)="South"
;iDir$(#iSouthWest)="SouthWest"
;iDir$(#iSouthEast)="SouthEast"
;iDir$(#iNorthWest)="NorthWest"
;iDir$(#iNorthEast)="NorthEast"

Structure microCellDetail
  Parent_x.a
  Parent_y.a
  Depth.a     ; maximum depth restricted to 255 - this could be increased by combining depth/visited into word. - visited then being the top bit.
  Visited.b
EndStructure

Procedure FindPath(DiagonalMovement = #False, earlyExit = #False)
  Protected NbDirections, iDir, foundIt, itX, itY, depth
  Protected cx, cy, nx, ny
  Protected *thisCell.microCellDetail, *currentCell.MAPPoint, *NextCell.microCellDetail
  Protected NewList Queue.MAPPoint()
  Protected Dim microCellDetail.microCellDetail(#MapSize,#MapSize)  ; This could be allocated outside procedure and cleared on each test.
  
  NbDirections = 3 ; check only - N W E S - Depending how direction constants have neen set
  If DiagonalMovement
    NbDirections = 7 ; checks all - N W E S SW SE NW NE
  EndIf
  
  AddElement(Queue())                                                       ; add start location to search queue
  Queue()\MAPPointX = fromPoint\MAPPointX
  Queue()\MAPPointY = fromPoint\MAPPointY
  ;Debug "from "+fromPoint\MAPPointX+","+fromPoint\MAPPointY+"  to "+toPoint\MAPPointX+","+toPoint\MAPPointY
  ;- *** BFS algorithm ***
  While FirstElement(Queue())                                               ; loop until each cell in queue has been examined        
    cx = Queue()\MAPPointX : cy = Queue()\MAPPointY                         ; get first cell in queue
    DeleteElement(Queue())                                                  ; don't need it - remove from list
        
    ;     If StartDrawing(CanvasOutput(#MainCanvas))
    ;       Box(cx*#cellSize, cy*#cellSize, #cellSize, #cellSize, #Red)     
    ;       StopDrawing()
    ;     EndIf
    depth+1
    
    For iDir = 0 To NbDirections
      nx = cx + iDir(iDir)\xo : ny = cy + iDir(iDir)\yo           ; get neighbour location
      If nx>=0 And ny>=0 And nx<#MapSize And ny<#MapSize          ; process only if in bounds
        *NextCell = @microCellDetail(nx, ny)
        
       
        If *NextCell\Visited = #False
          If MAPArry(nx, ny) <> 1 
            If iDir > 3 
              If MAPArry(nx,cy) = 1 Or MAPArry(cx,ny) = 1         ; don't add cell if cutting corners not allowed
                Continue
              EndIf 
            EndIf
            LastElement(Queue()) : AddElement(Queue())
            Queue()\MAPPointX =  nx : Queue()\MAPPointy =  ny
            
            *NextCell\Parent_x = cx :  *NextCell\Parent_y = cy
            *NextCell\Depth = depth : *NextCell\Visited = #True
            If nx = toPoint\MAPPointX And ny = toPoint\MAPPointY      ;  check If something 
              foundIt = #True
              itX = nx : itY = ny                                     ; this could be anything and stored in a list before all cells examined
              If EarlyExit : Break 2 : EndIf                          ; keep filling CellDetail Array or if EarlyExit = #True - we are done
            EndIf
          EndIf
        EndIf
      EndIf
    Next 
  Wend
  ;---->> PATH FOUND <<---
  If foundIt
    Protected *cell.microCellDetail = @microCellDetail(itX, itY)
    Repeat
      nx = *cell\Parent_x : ny = *cell\Parent_y 
      MAPArry(nx, ny) = -3
      ;Debug ""+nx+","+ny
      *cell = @microCellDetail(nx, ny)
    Until nx = fromPoint\MAPPointX And ny = fromPoint\MAPPointY           
  EndIf
  
EndProcedure
;-End of search code

Procedure.a SetRedMark(x, y)
  
  Protected ret.a
  
  If MAPArry(x, y) = 0
    MAPArry(x, y) = 1
    ret = 1
  EndIf
  
  ProcedureReturn ret
  
EndProcedure

Procedure SetRandomBlocks()
  Protected ret.a, i.w, x.a, y.a
  
  For i = 1 To #MapSize*#MapSize/5
    ret = 0
    Repeat
      x = Random(#MapSize-1, 0)
      y = Random(#MapSize-1, 0)
      ret = SetRedMark(x, y)
    Until ret = 1
  Next

EndProcedure

Procedure PaintCanvas()
  Protected color.l, x.a, y.a
  
  If fromPoint\MAPPointX <> -1 And toPoint\MAPPointX <> -1 ; both points set.        
    FindPath( #True, #True)
  EndIf
  
  If StartDrawing(CanvasOutput(#MainCanvas))
    
    For y = 0 To #MapSize-1
      For x = 0 To #MapSize-1
        Select MAPArry(x, y)
          Case 0
            color = RGB(100, 200, 100)
          Case 1
            color = RGB(200, 100, 100)
          Case -1
            color = RGB(50, 50, 200)
          Case -2
            color = RGB(100, 100, 200)
          Case -3 
            color = RGB(150, 150, 200)
        EndSelect
        Box(x*#cellSize, y*#cellSize, #cellSize, #cellSize, color)
      Next
    Next
    
    StopDrawing()
  EndIf
  
EndProcedure

Procedure ClearPath()
  Protected x, y
  
  For y = 0 To #MapSize-1
    For x = 0 To #MapSize-1
      If MAPArry(x, y) = -3 
        MAPArry(x, y) = 0
      EndIf
    Next
  Next

EndProcedure

Procedure SetToPoint(x,y)

  If MAPArry(x, y) = 0                   
    If toPoint\MAPPointX <> -1
      MAPArry(toPoint\MAPPointX, ToPoint\MAPPointY) = 0
    EndIf                   
    MAPArry(x, y) = -1
    toPoint\MAPPointX = x : toPoint\MAPPointY = y
    ClearPath()     
    PaintCanvas()
  EndIf

EndProcedure

Procedure SetFromPoint(x,y)
  
  If MAPArry(x, y) = 0                   
    If fromPoint\MAPPointX <> -1 
      MAPArry(fromPoint\MAPPointX, fromPoint\MAPPointY) = 0
    EndIf                   
    MAPArry(x, y) = -2
    fromPoint\MAPPointX = x : fromPoint\MAPPointY = y
    ClearPath()   
    PaintCanvas()
  EndIf
  
EndProcedure

Procedure ToggleWallBlock(x,y)
  
  If MAPArry(x, y) = -3
    MAPArry(x, y) = 0
  endif
  
  If MAPArry(x, y) >= 0
    MAPArry(x, y) ! 1
    ClearPath()
    PaintCanvas()  
  EndIf
  
EndProcedure

If OpenWindow(#Window, 100, 100, 532, 532, "", #PB_Window_MinimizeGadget | #PB_Window_ScreenCentered)
  
  CanvasGadget(#MainCanvas, 10, 10, 512, 512)
  
  SetRandomBlocks()
  PaintCanvas()
  
  Repeat
    Select WaitWindowEvent()
        
      Case #PB_Event_Gadget
        
        Select EventGadget()
            
          Case #MainCanvas
            Select EventType() 
              Case #PB_EventType_LeftClick
                SetToPoint(GetGadgetAttribute(#MainCanvas, #PB_Canvas_MouseX)/#cellSize,GetGadgetAttribute(#MainCanvas, #PB_Canvas_MouseY)/#cellSize)               
              Case #PB_EventType_RightClick
                SetFromPoint(GetGadgetAttribute(#MainCanvas, #PB_Canvas_MouseX)/#cellSize,GetGadgetAttribute(#MainCanvas, #PB_Canvas_MouseY)/#cellSize)                                             
              Case #PB_EventType_MiddleButtonUp
                ToggleWallBlock(GetGadgetAttribute(#MainCanvas, #PB_Canvas_MouseX)/#cellSize,GetGadgetAttribute(#MainCanvas, #PB_Canvas_MouseY)/#cellSize)               
                
            EndSelect
            
        EndSelect
        
      Case #PB_Event_CloseWindow
        Break
        
    EndSelect
  ForEver
  
EndIf

End
Last edited by Comfort on Tue Jul 06, 2021 4:29 am, edited 2 times in total.
Comfort
User
User
Posts: 22
Joined: Thu Jul 05, 2018 11:52 pm

Re: any pathfinding algorytm?

Post by Comfort »

There are two errors in the above code.

The wall toggle procedure not allowing a wall block on a path cell and looks like FindPath is cutting corners.
Comfort
User
User
Posts: 22
Joined: Thu Jul 05, 2018 11:52 pm

Re: any pathfinding algorytm?

Post by Comfort »

Should now be working.

The dimensions of the canvas and window have been increased.
SeregaZ
Enthusiast
Enthusiast
Posts: 617
Joined: Fri Feb 20, 2009 9:24 am
Location: Almaty (Kazakhstan. not Borat, but Triple G)
Contact:

Re: any pathfinding algorytm?

Post by SeregaZ »

didnt see that "cutting corners" code before... it will cut 90 degree turn? sometimes it shows like this:

Image


but still main question is: how many memory it will eat? what if path will be very long and what if it will be a few different units? i dont know sure but i think we have 68k memory for whole game. and from that memory only small part can be used. dont know sure size, but it is very small...
Comfort
User
User
Posts: 22
Joined: Thu Jul 05, 2018 11:52 pm

Re: any pathfinding algorytm?

Post by Comfort »

Remark the Continue statement in the corner cutting test to show the problems without it.

Yes the array is hungry, 65k bytes at 128*128... maybe it could be reduced if you store just a single byte as a direction indicator, reversed, which would also serve as the Visited marker.. 65k to 16k.
User avatar
Caronte3D
Addict
Addict
Posts: 1025
Joined: Fri Jan 22, 2016 5:33 pm
Location: Some Universe

Re: any pathfinding algorytm?

Post by Caronte3D »

Comfort wrote: Mon Jul 05, 2021 1:44 pm https://www.redblobgames.com/pathfindin ... ation.html

Breadth First Search should be enough.
Awesome web, thanks for sharing it :wink:
Post Reply