'TODO: BUGS
' (no known bugs but this is just a prototype)
'TODO: OPTIMISATIONS
'* Bi-directional search
'* Cancel all rays on route to a just met ray
'* optimize rayMovementDistance value (base this on previous results)
'* do not init rays to already reached points
'* do not init rays to points 2 or more away in a direct up/down/left/right direction
'* Use activeRayIdList (WIP)
'TODO: FEATURES
'* 3D layers
wall = 1
map(x, y) = wall
'Used during path finding
granularity = 6
locationsWidth = mapWidth / granularity
locationsHeight = mapHeight / granularity
REDIM SHARED locations
(locationsWidth
, locationsHeight
) AS location
FOR x
= 0 TO locationsWidth
FOR y
= 0 TO locationsHeight
locations(x, y).x = x * (mapWidth / locationsWidth)
locations(x, y).y = y * (mapHeight / locationsHeight)
PSET (locations
(x
, y
).x
, locations
(x
, y
).y
), _RGB(255, 255, 255)
finalConnectionId = -1
maxConnectionDistance = 4
'build connections
FOR y
= 0 TO locationsHeight
FOR x
= 0 TO locationsWidth
lastConnection = -1
FOR y2
= y
- maxConnectionDistance
TO y
+ maxConnectionDistance
FOR x2
= x
- maxConnectionDistance
TO x
+ maxConnectionDistance
'Test: an entity walking from point1 in the direction of point 2 will arrive at point 2 without encountering any obstructions
'Note: this part of the code is a mess because I coded it in the quickest way I could think of, it would be replaced with real code for walking the character and detecting if point 2 is actually reached
xx1 = locations(x, y).x
yy1 = locations(x, y).y
xx2 = locations(x2, y2).x
yy2 = locations(x2, y2).y
steps = granularity * 2
dx = (xx2 - xx1) / steps
dy = (yy2 - yy1) / steps
blocked = 0
xx1i = xx1
yy1i = yy1
xx1 = xx1 + dx
yy1 = yy1 + dy
LINE (locations
(x
, y
).x
, locations
(x
, y
).y
)-(xx2
, yy2
), _RGBA(128, 128, 128, 32) finalConnectionId = finalConnectionId + 1
c = finalConnectionId
locations(x, y).firstConnectionId = c
connections(lastConnection).nextConnectionId = c
lastConnection = c
connections(c).destLocationX = x2
connections(c).destLocationY = y2
connections
(c
).distanceCost
= CLNG(SQR((xx2
- xx1
) * (xx2
- xx1
) + (yy2
- yy1
) * (yy2
- yy1
)) * 10) 'distance cost should be calculated by movement test above
'test walkability
'destLocationX AS LONG
'destLocationY AS LONG
lastRayId = -1
lastActiveRayIdListId = -1
lastActiveRayIdListFreeId = -1
startX = 5
startY = 20
endX = 76
endY = 55
'add rays
x = startX
y = startY
parentRayId = 0
c = locations(x, y).firstConnectionId
lastRayId = lastRayId + 1
r = lastRayId
lastActiveRayIdListId = lastActiveRayIdListId + 1
activeRayIdList(lastActiveRayIdListId) = r
rays(r).parentRayId = parentRayId
rays(r).connectionId = c
rays(r).distanceRemaining = connections(c).distanceCost
c = connections(c).nextConnectionId
finished = 0
finished = 1
rayAdvancementDistance = 1
lastRayIdCached = lastRayId
FOR r
= 0 TO lastRayIdCached
IF rays
(r
).distanceRemaining
> 0 THEN finished = 0
rays(r).distanceRemaining = rays(r).distanceRemaining - rayAdvancementDistance
' PRINT rays(r).distanceRemaining
IF rays
(r
).distanceRemaining
<= 0 THEN ' END
'a ray reached a destination
c = rays(r).connectionId
x = connections(c).destLocationX
y = connections(c).destLocationY
IF locations
(x
, y
).reached
= 0 THEN PSET (locations
(x
, y
).x
, locations
(x
, y
).y
), _RGB(255, 255, 0) locations(x, y).reached = 1
CIRCLE (locations
(x
, y
).x
, locations
(x
, y
).y
), 10, _RGB(255, 255, 0) 'perform trace-back to build path
'a ray reached a destination
c = rays(r).connectionId
x = connections(c).destLocationX
y = connections(c).destLocationY
CIRCLE (locations
(x
, y
).x
, locations
(x
, y
).y
), 10, _RGB(255, 255, 0)
r = rays(r).parentRayId
'add new rays
parentRayId = r
c2 = locations(x, y).firstConnectionId
lastRayId = lastRayId + 1
r2 = lastRayId
lastActiveRayIdListId = lastActiveRayIdListId + 1
activeRayIdList(lastActiveRayIdListId) = r
rays(r2).parentRayId = parentRayId
rays(r2).connectionId = c2
rays(r2).distanceRemaining = connections(c2).distanceCost
c2 = connections(c2).nextConnectionId
