EDIT: As I was writing this, some great people (Zorfmorf) provided help. Anyway, just for the sake of information, I will add my two cents.
Brace yourself. This is going to be long.
Zilarrezko wrote:I think you were the one that actually made an a star and jump point search on love, tried to run it but it was outdated.
Can you please elaborate a bit more on this ? I'd love to provide a fix if there is something wrong about that. Actually, have you tried to use the
latest version available ? Have you taken a look at the
documentation ? The
README ? Was the
example of code given wrong ? Let me know please.
Zilarrezko wrote:
Are you suggesting I look for one on the forum? As I tried and only found your stuff I believe. I tried to find something working, but I haven't had any luck
Well, I was not mentionning especially this forum. But hey, only on this forum, there are tons of interesting stuff, as far as I could find.
Here are a lot of nice implementations. You can learn a lot from the code.
I took a look at your code, and I think there are a lot of things that goes wrong, mostly because you are trying to adapt a library to your situation, without having a real understanding on how pathfinding works. My advise is...choose. Either use a library, or implement your own Astar. I will give you some pointers, and even some code for the latter. Then, it is up to you to decide if you want to rely on a library or keep going with your own Astar.
You are free to use the code I am giving below, it is totally free, but I wrote it from scratch, so it might not be error-prone. You are supposed to
get the logic,
organize it at your will (you might have to split it up into smaller files/modules) and implement it on your own. Plus, it
doesn't fit straight into your game, but the relevant modifications are straightforward to implement, I believe.
So, shall we proceed ?
Here are my initial assumptions. Your game world is a flat 2-dimensional map. It cas be represented with a 2D table of integers.
So, let us focus, for now, on Astar pathfinding. We will just consider this very algorithm. I assume you read some papers on it, and you have a general understanding on how the algorithm works (if not, as I am not going to cover it right here,
please go back to some
reading). Then, how do you implement it ?
First of all, let us model a Node. The Node structure will keep some information about the coordinates of every single node on the game map. Those information are generally the coordinates of the node itself, in tile units (x, y) and the different costs that the algorithm evaluates: g-, h- and f-costs.
Code: Select all
local function createNode(x, y)
return { x = x, y = y, h = 0, g = 0, f = 0 }
end
Then, we can already write down the general layout of our pathfinding module. I am not going to use an OOP style (as it is not relevant here), but you are free to modify it.
Code: Select all
local pathfinding = {}
pathfinding.mapData = {} -- This will hold the game map.
Then we can define an initialization function, that should be called once, and only once. It will create some static information, the node data for every single node on the map. As the number of nodes will not change (the map dimensions are supposed to be constant), there is no need to call this function multiple times, or it will be a memory and speed overkill.
Code: Select all
function pathfinding.initMap(gameMap)
local w, h = #gameMap[1], #gameMap -- gameMap width and height dimensions
pathfinding.map = gameMap
for y = 1, h do pathfinding.mapData[y] = {}
for x = 1, w do
pathfinding.mapData[y][x] = createNode(x,y)
end
end
end
Notice this function receives as argument a
gameMap. This is a 2D representation of the game world, and it contains integers. The purpose of such a map is to let the pathfinfind algorithm know if a node can be traversed (walkable) or should not be crossed (obstacle). Commonly, the number "zero" is used to represent walkable nodes. Any other value will represent an unwalkable tile.
Here is an example of gameMap:
Code: Select all
local gameMap = {
{0,0,0,0,0},
{0,1,2,2,2},
{0,0,0,0,0},
}
This game map is 5-tiles wide and 3-tiles high. Value 0 stands for free tiles, and other values (1's and 2's) represent obstacles, nodes that cannot be crossed. In case you need more information on this, i would suggest taking a look at
Kikito's tile tutorial, which covers in-depth the topic of representing 2D maps, with nice illustrations.
Also, notice another implementation detail. The
pathfinding.initMap function creates a variable
pathfinding.map which is just an internal reference to the
gameMap, to be use later to access to
gameMap contents easily. Second, it also create a variable
pathfinding.mapData which is also a 2D table, but only contains the node data for pathfinding.
What is interesting in this scheme is you can have dynamic maps. In case you want to change a tile behavior, at runtime, just edit the corresponding value in
gameMap. It won't affect information inside
pathfinding.mapData since this only contains node data for pathfinding. And since
pathfinding.map is a shortcut reference to
gameMap, the algorithm will be aware of this change.
Then, if we want to check if a node is free (i.e, walkable), we can use this:
Code: Select all
function pathfinding.isWalkable(x, y)
return pathfinding.map[y] and pathfinding.map[y][x] == 0
end
Next, we need a way to get the
neighbors (often called
successors) of a given node. We just have to notice that neighbors of a node are just the nodes that surrounds him. On a grid, it is very easy to get them, as there are at most 8 neighbors : 4 of them are positionned orthonally : north (up), south (below), west (left), east (right). The other 4 neighbors are adjacent, i.e, in diagonal. So let us define some direction vectors to get them in a clean manner :
Code: Select all
-- Direction vectors for orthogonal neighbors
local orthogonalVectors = {
{x = 0, y = -1},
{x = -1, y = 0},
{x = 1, y = 0},
{x = 0, y = 1},
}
-- Direction vectors for diagonal neighbors
local diagonalVectors = {
{x = -1, y = -1},
{x = 1, y = -1},
{x = -1, y = 1},
{x = 1, y = 1}
}
Then, the following function will return an array list of neighbors for a given node. The boolean optional argument
diagonal will specify if we want to include diagonal neighbors. In case we set it to
false, diagonal neigbors will be discarded, and then we will have paths consisting of only horizontal/vertical moves.
Code: Select all
-- This returns the appropriate nodeData struct:
function pathfinding.getNode(x, y)
return pathfinding.mapData[y] and pathfinding.mapData[y][x]
end
-- Returns an array of neighbors of node n
function pathfinding.getNeighbors(n, diagonal)
local neighbors = {}
for _, axis in ipairs(orthogonalVectors) do
local x, y = n.x + axis.x, n.y + axis.y
if pathfinding.isWalkable(x, y) then -- Only include the orthogonal neighbor if it is walkable
table.insert(neighbors, pathfinding.getNode(x, y))
end
end
if diagonal then
for _, axis in ipairs(diagonalVectors) do
local x, y = n.x + axis.x, n.y + axis.y
if pathfinding.isWalkable(x, y) then -- Only include the diagonal neighbor if it is walkable
table.insert(neighbors, pathfinding.getNode(x, y))
end
end
end
return neighbors
end
What do we need else ? Some heuristic, to evaluate the distance between two nodes. Depending on the desired results, you can use manhattan (which is quite common) or euclidian. Amit Patel provided a very in-depth set of
notes concerning heuristics and how they affet pathfinding.
Here are two examples of distance heuristic :
Code: Select all
local function manhattan(nodeA, nodeB)
local dx, dy = nodeA.x - nodeB.x, nodeA.y - nodeB.y
return math.abs(dx) + math.abs(dy)
end
local function euclidian(nodeA, nodeB)
local dx, dy = nodeA.x - nodeB.x, nodeA.y - nodeB.y
return math.sqrt(math.abs(dx*dx) + math.abs(dy*dy))
end
In the following, I will assume that the variable
pathfinding.heuristic will refer to either
manhattan or
euclidian function.
Depending on what you have chosen.
From now on, we have almost everything we need to write our pathfinding core. Before that, let us define more variables, shall we ?
Code: Select all
pathfinding.openList = {}
pathfinding.visited = {}
The table
pathfinding.visited will keep track of node whose data were modified during a search. For such nodes, we need to reset their data back to the initial values before performing another search, or it will lead to unexpected behaviors.
So here is the function we will use for that purpose:
Code: Select all
local function resetForNextSearch(pathfinding)
for node in pairs(pathfinding.visited) do
node.parent, node.opened, node.closed = nil, nil, nil -- erases some temporary properties added during the search
node.f, node.g, node.h = 0, 0, 0 -- resets all the costs back to zero
end
pathfinding.openList = {} -- clears the openList
pathfinding.visited = {} -- clears the visited nodes list
end
Added to that, we will only use an
.openList. We do not need to manage a
closedList. Instead, we will write some temporary properties inside each node data (
.opened, .closed, .parent) to keep things simple. Let us take a look at the core function, the one that deals with pathfinding. It is a direct translation of the pathfinding algorithm pseudocode. It expects four arguments, being the coordinates of the start and end-locations, plus a fifth optional boolean argument, to specify if we can diagonal moves or not.
Code: Select all
function pathfinding.findPath(startX, startY, goalX, goalY, diagonal)
local startNode = pathfinding.getNode(startX, startY) -- get the startNode data
local goalNode = pathfinding.getNode(goalX, goalY) -- get the startNode data
assert(startNode, ('Invalid coordinates for startNode: (%d, %d)'):format(startX, startY))
assert(goalNode, ('Invalid coordinates for goalNode: (%d, %d)'):format(goalX, goalY))
resetForNextSearch(pathfinding) -- clears node data, explained before
-- pushes the start node to the openList
startNode.g = 0
startNode.h = pathfinding.heuristic(startNode, goalNode)
startNode.f = startNode.g + startNode.h
table.insert(pathfinding.openList, startNode)
pathfinding.visited[startNode] = true -- adds the startNode to the list of visited nodes.
while #pathfinding.openList ~= 0 do -- while there are still some nodes in the openList
-- We pops the node at the head of the list, it should be the lowest f-cost node normally
local node = pathfinding.openList[1]
table.remove(pathfinding.openList, 1)
-- if this node is the goal, we stop and backtrace to get the path
if node == goalNode then return backtrace(node) end
-- if not, we move it to the closed list, and we examine its neigbors.
node.closed = true
local neighbors = pathfinding.getNeighbors(node, diagonal) -- we can add an extra argument here if we need diagonals, see before.
for _, neighbor in ipairs(neighbors) do
if not neighbor.closed then -- if the neighbor was not examined before, try to see if it can lead to a better path
local tentative_g = node.g + pathfinding.heuristic(node, neighbor)
if not neighbor.opened or tentative_g < neighbor.g then -- If so, set the actual node as the parent of the neighbor, and update data
neighbor.parent = node
neighbor.g = tentative_g
neighbor.h = pathfinding.heuristic(neighbor, goalNode)
neighbor.f = neighbor.g + neighbor.h
pathfinding.visited[neighbor] = true -- add the neighbor to the list of visited node, since its data were mdified
if not neighbor.opened then -- push the neighbor to the openList as it was not already there
neighbor.opened = true
table.insert(pathfinding.openList, neighbor)
end
-- since we made some edits to the node data, we need to sort the openList by f-cost
table.sort(pathfinding.openList, function(nodeA, nodeB) return nodeA.f < nodeB.f end)
end
end
end
end
end
And well, that's it.
Ah, I must add something, about
backtracking. In case a path is found, the
pathfinding.findPath function should return the path.
Code: Select all
-- if this node is the goal, we stop and backtrace to get the path
if node == goalNode then return backtrace(node) end
You can reconstruct this very path using the following (it has to be defined before
pathfinding.findPath, of course, since the latter uses it) :
Code: Select all
local function backtrace(node)
local path = {}
repeat
table.insert(path, 1, node)
node = node.parent
until not node
return path
end
For now on, you should have a 100% working Astar implementation. Here is an example of how you should use it:
Code: Select all
-- The game map
local gameMap = {
{0,0,0,0,0},
{0,1,2,1,0},
{0,0,0,0,0},
}
-- create pathfinding map data
pathfinding.initMap(gameMap)
local path = pathfinding.findPath(1,1, 5,3) -- Looks for path from node(1,1) to node(5,3) without diagonals.
-- if found, then print the steps along the path
if path then
for k, node in ipairs(path) do print(node.x, node.y) end
end
Output:
1 1
2 1
3 1
4 1
5 1
5 2
5 3
Let us make a quick change to the
gameMap and
include diagonal neighbors in the search this time:
Code: Select all
-- replace the 2 with a 0, tile(x=3,y=2) is now walkable
gameMap[2][3] = 0
local path = pathfinding.findPath(1,1, 5,3,true) -- Looks for path from node(1,1) to node(5,3) with diagonals.
-- if found, then print the steps along the path
if path then
for k, node in ipairs(path) do print(node.x, node.y) end
end
1 1
2 1
3 2
4 3
5 3
So you now have all the details you need to write your own Astar. Besides this, you will have to take care on the logic to draw your 2D map, translate the world pixels to tile units, write th logic to move entities along a path etc. But all of this are really straightforward. I will highly recommend, in case you really want to write it on your own, to start a new blank project, implement Astar, get it to work before trying to add this in your actual project. It'll help tremendously.
And of course, in case there is
anything that remains unclear (my english is not that fine), let me know so that I can provide more details.
.