Need A* Help

[ArchAngel075]

perhaps if you retry the implementation of that then i can take a chance to see what i can do?
I do know i had to do some magic in STI to make the library behave correctly(involving adding 2 to the tile cords(x and y) in valid_node_check() function but returning path was -2)

[zorfmorf]

I took a look at that astar library and plugged it into your project. I tried to change as little as possible but removed most code in pathfind.lua as it wasn't needed anymore.

If you rightclick somewhere, a path from the player position to the clicked position is calculated and saved in the global "path". If a path exists, the path is drawn.



Next step would be for the player to move if a path exists. That is quite easy. If the global variable "path" is not nil, move the player to the first entry in "path". If you reached it, remove that first entry. If "path" is empty, set it to nil as you've reached your target.

Edit: I'd advise you to look at the changes I've made (mostly pathfind.lua). Rewrite/change it as necessary and ask questions if something confuses you. The biggest change I had to make: the library wants a one-dimensional list of tables where every table has an x and y value. Therefore I changed the two-dimensional node array to be one dimensional.

[Roland_Yonaba]

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.

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.

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.

• Inny's Astar
• MarekkPie's loveAstar, with binary heaps
• Bartoleo's MRPAS+Length of sight+Astar
• Kikito's Pulsar
• Taehl's TLPath
• LuAstar and Jumper (I wrote them)

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.

[zorfmorf]

Wow this is a great post!

You'd be well advised to read and follow Roland_Yonaba's post, it is really well written and in the long run it always pays off to understand something instead of just using it. In fact, the astar library that was posted and that I added to your project is NOT perfect in this case. Why? When searching for neighboring nodes it looks through all nodes and considers all nodes as neighbours that have a specific characteristic (in your case that are very close). However because you are using a grid you already know all neighbors and could skip this step entirely. If you had a very large grid (e.g. 10000x10000 squares) this could lead to your game freezing for a short time until the path finding is complete. A custom astar implementation could therefore still be of use depending on your needs.

@Roland_Yonaba: Sorry for stealing your thunder! Your post is much more useful than mine, props for taking the time. I don't know if this sounds creepy but I'm a big fan of your work!

[davisdude]

I don't know if this sounds creepy but I'm a big fan of your work!

Isn't everybody?

[Roland_Yonaba]

Sorry for stealing your thunder! Your post is much more useful than mine, props for taking the time. I don't know if this sounds creepy but I'm a big fan of your work!

Oh, don't be. Your post was as constructive as mine, since you have taken a bit of your time to help someone. Props to you as well.

@Davisdude: Much thanks for the kind words.
Löve is in the air.

[Zilarrezko]

Wowy!

This is probably going to take a week maybe for me to look at as this week Im graduating and it takes at leasy 3 or 4 read overs to understand what's going on.

but let me touch on a couple things

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.

I actually fixed it. It was just one thing that had to do with a setFont function I believe. I got it to work eventually but I think I didn't want to take a reverse engineer it because the pathfinding was kinda weird. It didn't look like it took the shortest path, it kinda looked like... hold on...

https://imgflip.com/gif/947xu

that... hopefully that shows up. never used that thing before.

Here are my initial assumptions. Your game world is a flat 2-dimensional map. It cas be represented with a 2D table of integers.

yeah... I work with my artist, and together we both don't make anything really. I'm more productive though, I'm on here trying to learn every type of thing I can (shaders, pathfinding, status bars and the like.). And first we were doing a game with 2D tiles, where the player moves independently of the tiles. Then he wanted to do isometric, so I said alright, then I made a little happy Isometric grid. Kinda like diablo 1? yet the player still moves independent of the tiles. Now He want to do a platformer because he said isometric drawing was too hard. Now I'm thinkin, that Conventional A* isn't going to cut it and I've pretty much rushed this A* learning for nothing .

As for the code and stuff I've read through it. and I'd need more time to fully understand it, I just don't have the time right now, but I'll be coming back to it asap. Either soon, or after I graduate.

[ArchAngel075]

It is taking the shortest path afaik, as it does not do diagonal movement, only horizontal and vertical.

-My guess-

[Zilarrezko]

Walked it through my head and it seems that as weird as it sounds. Without diagonal movement. That going up then over is just the same as up and over sequentially. Just as the same as rise over run is equal to the straight line of a linear regression.

Just doesn't look natural when it goes up then over opposed to up and over sequentially.

[Roland_Yonaba]

The Great ArchAngel is totally right. In this case, it means only orthogonal moves are allowed. No diagonals.
If you got such results using Jumper, then you just needed to use pathfinder:setMode.