Most things have been done a few times over on these forums
You can also look through the older DBpro snippets / 20 line challenges etc, most of it is easily convertable / improvable by AGK.
Here is an A* I did in DBpro, it is quite short and would be very easy to convert. It does need optimization for larger maps / paths.
drop an image on the .exe and it will pick two random points to pathfind between. It expects no larger than 1024 x 1024
`setup app
randomize timer()
set display mode 1024, 1024, 32
set window on
`load and process heightmap image data
load image cl$(), 1, 1
paste image 1, 0, 0
sync
sync
imgX = image width(1) - 1
imgY = image height(1) - 1
dim HMdata(imgX, imgY)
for x = 0 to imgX
for y = 0 to imgY
HMdata(x, y) = rgbr(point(x, y))
next y
next x
`set up pathfinding
HEIGHT_MOD = 9 `applies cost modifier to prefer not going uphill
startX = rnd(imgX)
startY = rnd(imgY)
targetX = rnd(imgX)
targetY = rnd(imgY)
`below is the A* implementation
open to write 1, "log.txt"
type nodeData
x as integer
y as integer
f as float
g as integer
h as integer
p as integer
endtype
dim NodesOpen() as nodeData
dim NodesClosed() as nodeData
`close start node
array insert at bottom NodesOpen()
NodesOpen().x = startX
NodesOpen().y = startY
NodesOpen().p = -1
targetFound = 0
while targetFound = 0
`get lowest f cost node from open -> active node is always index 0 in open list
sort array NodesOpen(), 3
write string 1, "Open Nodes:"
for oi = 0 to array count(NodesOpen())
write string 1, str$(NodesOpen(oi).x) + "," + str$(NodesOpen(oi).y) + " f: " + str$(NodesOpen(oi).f)
next oi
`set active node to closed
array insert at bottom NodesClosed()
NodesClosed().x = NodesOpen(0).x
NodesClosed().y = NodesOpen(0).y
NodesClosed().f = NodesOpen(0).f
NodesClosed().g = NodesOpen(0).g
NodesClosed().h = NodesOpen(0).h
NodesClosed().p = NodesOpen(0).p
tParent = array count(NodesClosed())
array delete element NodesOpen(), 0
dot NodesClosed().x, NodesClosed().y, rgb(0, 0, 255)
write string 1, ">> active node is " + str$(NodesClosed().x) + "," + str$(NodesClosed().y) + " moved to closed"
write string 1, "Remaining Open Nodes:"
for oi = 0 to array count(NodesOpen())
write string 1, str$(NodesOpen(oi).x) + "," + str$(NodesOpen(oi).y) + " f: " + str$(NodesOpen(oi).f)
next oi
`get all nodes surrounding active node
for lookX = 0 to 2
for lookY = 0 to 2
`ensure that look ahead is within bounds
if (NodesClosed().x + lookX - 1) > 0 and (NodesClosed().x + lookX - 1) < imgX and (NodesClosed().y + lookY - 1) > 0 and (NodesClosed().y + lookY - 1) < imgY
`check if new node is on closed list
write string 1, " check if " + str$(NodesClosed().x + lookX - 1) +","+ str$(NodesClosed().y + lookY - 1) + " is closed"
if nodeNotClosed(NodesClosed().x + lookX - 1, NodesClosed().y + lookY - 1)
write string 1, " node is not closed"
`check if new node is passable
`check if new node is already on open list
openNodeID = nodeIsOpen(NodesClosed().x + lookX - 1, NodesClosed().y + lookY - 1)
if openNodeID > -1
write string 1, " node is already open -> try to update"
`node is open, check if this path is better
`get old g
oldG = NodesOpen(openNodeID).g
`calc new g
if abs(lookX - 1) = abs(lookY - 1)
`diag
newG = NodesClosed(tParent).g + 14
else
`ortho
newG = NodesClosed(tParent).g + 10
endif
`modify g by height variance
newG = newG + (HMdata(NodesOpen(openNodeID).x, NodesOpen(openNodeID).y) - HMdata(NodesClosed(tParent).x, NodesClosed(tParent).y)) * HEIGHT_MOD
if newG < oldG
write string 1, " new G is better ?" + str$(newG) + " < " + str$(oldG)
`set new parent
NodesOpen(openNodeID).g = newG
NodesOpen(openNodeID).f = newG + NodesOpen(openNodeID).h
NodesOpen(openNodeID).p = tParent
else
write string 1, " new G is worse ?" + str$(newG) + " < " + str$(oldG)
endif
else
write string 1, " node is not open -> add to open"
`add to open list
array insert at bottom NodesOpen()
NodesOpen().x = NodesClosed().x + lookX - 1
NodesOpen().y = NodesClosed().y + lookY - 1
NodesOpen().p = tParent
dot NodesOpen().x, NodesOpen().y, rgb(0, 255, 0)
`calc g
if abs(lookX - 1) = abs(lookY - 1)
`diag
NodesOpen().g = NodesClosed(tParent).g + 14
else
`ortho
NodesOpen().g = NodesClosed(tParent).g + 10
endif
`modify g by height variance
NodesOpen().g = NodesOpen().g + (HMdata(NodesOpen().x, NodesOpen().y) - HMdata(NodesClosed(tParent).x, NodesClosed(tParent).y)) * HEIGHT_MOD
`calc h
NodesOpen().h = (abs(NodesOpen().x - targetX) + abs(NodesOpen().y - targetY)) * 10
`calc f
NodesOpen().f = NodesOpen().g + NodesOpen().h
`check if added node is target node
if NodesOpen().x = targetX and NodesOpen().y = targetY
targetFound = 1
exit
endif
endif
else
write string 1, " node is closed"
endif
endif
next y
if targetFound = 1 then exit
next x
endwhile
write string 1, "Path Found:"
dim NodePath() as nodeData
array insert at bottom NodePath()
NodePath().x = targetX
NodePath().y = targetY
NodePath().p = NodesOpen(array count(NodesOpen())).p
sourceFound = 0
while sourceFound = 0
i = NodePath(array count(NodePath())).p
write string 1, "checking closed nodes for current path node parent: " + str$(NodesClosed(i).p) + ":" + str$(NodePath(array count(NodePath())).p)
if NodesClosed(i).p = -1
sourceFound = 1
exit
else
array insert at bottom NodePath()
NodePath().x = NodesClosed(i).x
NodePath().y = NodesClosed(i).y
NodePath().p = NodesClosed(i).p
endif
endwhile
array index to bottom NodePath()
while array index valid(NodePath())
dot NodePath().x, NodePath().y, rgb(255, 0, 0)
write string 1, str$(NodePath().x) + "," + str$(NodePath().y)
previous array index NodePath()
endwhile
write string 1, "Closed Nodes:"
array index to top NodesClosed()
while array index valid(NodesClosed())
write string 1, str$(NodesClosed().x) + "," + str$(NodesClosed().y) + "p: " + str$(NodesClosed().p) + " f: " + str$(NodesClosed().f) + " g: "+ str$(NodesClosed().g) + " h: " + str$(NodesClosed().h)
next array index NodesClosed()
endwhile
write string 1, "Open Nodes:"
array index to top NodesOpen()
while array index valid(NodesOpen())
write string 1, str$(NodesOpen().x) + "," + str$(NodesOpen().y) + "p: " + str$(NodesOpen().p) + " f: " + str$(NodesOpen().f) + " g: "+ str$(NodesOpen().g) + " h: " + str$(NodesOpen().h)
next array index NodesOpen()
endwhile
`just display the results
do
loop
end
function nodeNotClosed(tX, tY)
for i = 0 to array count(NodesClosed())
if NodesClosed(i).x = tX
if NodesClosed(i).y = tY
exitfunction 0
endif
endif
next i
endfunction 1
function nodeIsOpen(tX, tY)
tID = -1
for i = 0 to array count(NodesOpen())
if NodesOpen(i).x = tX
if NodesOpen(i).y = tY
tID = i
exitfunction tID
endif
endif
next i
endfunction tID
http://games.joshkirklin.com/sulium
A single player RPG featuring a branching, player driven storyline of meaningful choices and multiple endings alongside challenging active combat and intelligent AI.
