'$include:'CONSTANTS_Color.BI'
_TITLE "Pathfinder v1.0 for QB64v1.3" ' done 2019-12-17 to 2019-12-18
' by Myself (Karsten Maske)
'
' ESC to exit program
' any other key restarts with creating a new random map
'
CONST MAPWIDTH
= 100 ' 100 on 800 * 600 => 8 pixel width CONST MAPHEIGHT
= 100 ' 100 on 800 * 600 => 6 pixel height CONST SQUAREWIDTH
= SW
/ MAPWIDTH
CONST SQUAREHEIGHT
= SH
/ MAPHEIGHT
CONST COST
= 1 ' move cost from one square to another; horizontal/vertical = diagonal CONST YOUSHALLNOTPASS
= 32000 ' !! signed integer, stay within positive values
id
AS INTEGER ' calculated as y * MAPWIDTH + x
DIM SHARED Nodes
(0 TO (MAXY
- MINY
) * MAPWIDTH
+ (MAXX
- MINX
)) AS typeNode
' #############################################################################################################
' <- Definitions
' -> Initialization
' #############################################################################################################
bPathFound = 0
bNoPathFound = 0
startX = 6
startY = MAPHEIGHT - 6
endX = MAPWIDTH - 6
endY = 6
InitNodes
InitMap
SetWall
INT(MAPWIDTH
/ 2), INT(MAPHEIGHT
/ 4), INT(MAPWIDTH
/ 2) + 1, MAPHEIGHT
- 5 SetWall
INT(MAPWIDTH
/ 2) + 1, MAPHEIGHT
- 6, INT(MAPWIDTH
/ 3), MAPHEIGHT
- 7 RandomBlock
PaintMap
ShowCrow
endID = GetIdFromXY(endX, endY)
id = GetIdFromXY(startX, startY)
startID = id
Nodes(id).x = startX
Nodes(id).y = startY
Nodes(id).id = id
Nodes
(id
).f
= SQR(((startX
- endX
) ^ 2) + ((startY
- endY
) ^ 2)) ' only h(x) Nodes(id).p = 0
Nodes(id).oo = 1 ' put on open list
Nodes(id).oc = 0
' #############################################################################################################
' <- Initialization
' -> Main
' #############################################################################################################
GetNeighbours
ShowPath
' #############################################################################################################
' <- Main
' -> helper
' #############################################################################################################
GetIdFromXY = (y - MINY) * MAPWIDTH + (x - MINX)
' #############################################################################################################
' <- helper
' -> pathfinding SUBs
' #############################################################################################################
ooid = GetMinFromOpenList
IF ooid
= 0 THEN ' nothing on open list bNoPathFound = 1
x1 = Nodes(ooid).x
y1 = Nodes(ooid).y
PaintBlock ooid, GOLD
id = GetIdFromXY(x, y)
IF Nodes
(id
).oc
= 0 THEN ' not yet on closed list PaintBlock id, AQUA
f
= Nodes
(ooid
).f
+ Map
(x
, y
) + SQR(((x
- endX
) ^ 2) + ((y
- endY
) ^ 2)) IF Nodes
(id
).oo
THEN ' is on open list Nodes(id).p = Nodes(ooid).id
Nodes(id).f = f
ELSE ' not yet on open list Nodes(id).f = f
Nodes(id).p = Nodes(ooid).id
Nodes(id).oo = 1 ' put on open list
PaintBlock id, DARKORANGE
Nodes(id).p = Nodes(ooid).id
bPathFound = 1
PaintBlock id, GRAY
Nodes(ooid).oc = 1
Nodes(ooid).oo = 0
PaintBlock ooid, BLACK 'SILVER
minf = 99999.9
id = 0
FOR i
= 0 TO MAXX
* MAXY
- 1 minf = Nodes(i).f
id = i
GetMinFromOpenList = id
id = GetIdFromXY(x, y)
Nodes(id).id = id
Nodes(id).x = x
Nodes(id).y = y
Nodes(id).f = 0
Nodes(id).p = 0
Nodes(id).oo = 0
Nodes(id).oc = 0
' #############################################################################################################
' <- pathfinding SUBs
' -> map related non graphical Subs
' #############################################################################################################
y1 = (y - MINY) * SQUAREHEIGHT
y2 = y1 + SQUAREHEIGHT - 1
Map(x, y) = 1
x1 = (x - MINX) * SQUAREWIDTH
x2 = x1 + SQUAREWIDTH - 1
SUB SetWall
(x1
, y1
, x2
, y2
)
x = x1
x1 = x2
x2 = x
y = y1
y1 = y2
y2 = y
Map(x, y) = YOUSHALLNOTPASS
x1
= INT(RND * (MAPWIDTH
- n
- 2)) + 1 x2 = x1 + n - 1
y1
= INT(RND * (MAPHEIGHT
- n
- 2)) + 1 y2 = y1 + n - 1
SetWall x1, y1, x2, y2
' #############################################################################################################
' <- map related non graphical Subs
' -> map related graphical Subs
' #############################################################################################################
y1 = (y - MINY) * SQUAREHEIGHT
y2 = y1 + SQUAREHEIGHT - 1
x1 = (x - MINX) * SQUAREWIDTH
x2 = x1 + SQUAREWIDTH - 1
IF Map
(x
, y
) < YOUSHALLNOTPASS
THEN col = FERN
col = BLACK
LINE (x1
, y1
)-(x2
, y2
), col
, BF
LINE (x1
, y1
)-(x2
, y2
), BLACK
, B
PlaceStartEnd startX, startY, MAROON
PlaceStartEnd endX, endY, LAWNGREEN
x1 = (x - MINX) * SQUAREWIDTH
x2 = x1 + SQUAREWIDTH - 1
y1 = (y - MINY) * SQUAREHEIGHT
y2 = y1 + SQUAREHEIGHT - 1
LINE (x1
, y1
)-(x2
, y2
), col
, BF
LINE ((startX
- MINX
) * SQUAREWIDTH
, (startY
- MINY
) * SQUAREHEIGHT
)-((endX
- MINX
) * SQUAREWIDTH
, (endY
- MINY
) * SQUAREHEIGHT
), WHITE
PaintMap
zid = GetIdFromXY(startX, startY)
id = GetIdFromXY(endX, endY)
x = Nodes(Nodes(id).p).x
y = Nodes(Nodes(id).p).y
y1 = (y - MINY) * SQUAREHEIGHT
y2 = y1 + SQUAREHEIGHT - 1
x1 = (x - MINX) * SQUAREWIDTH
x2 = x1 + SQUAREWIDTH - 1
LINE (x1
, y1
)-(x2
, y2
), CORNFLOWERBLUE
, BF
id = Nodes(id).p
PlaceStartEnd startX, startY, MAROON
PlaceStartEnd endX, endY, LAWNGREEN
x = Nodes(id).x
y = Nodes(id).y
y1 = (y - MINY) * SQUAREHEIGHT
y2 = y1 + SQUAREHEIGHT - 1
x1 = (x - MINX) * SQUAREWIDTH
x2 = x1 + SQUAREWIDTH - 1
LINE (x1
, y1
)-(x2
, y2
), col
, BF