Need A* Help
Forum rules
Before you make a thread asking for help, read this.
Before you make a thread asking for help, read this.
 ArchAngel075
 Party member
 Posts: 311
 Joined: Mon Jun 24, 2013 5:16 am
Re: Need A* Help
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)
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)
Re: Need A* Help
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 onedimensional list of tables where every table has an x and y value. Therefore I changed the twodimensional node array to be one dimensional.
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 onedimensional list of tables where every table has an x and y value. Therefore I changed the twodimensional node array to be one dimensional.
 Attachments

 workspace_with_astar.zip
 (5.8 KiB) Downloaded 87 times
 Roland_Yonaba
 Inner party member
 Posts: 1560
 Joined: Tue Jun 21, 2011 6:08 pm
 Location: Ouagadougou (Burkina Faso)
 Contact:
Re: Need A* Help
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.
Here are a lot of nice implementations. You can learn a lot from the code.
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 errorprone. 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 2dimensional 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 fcosts.
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.
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.
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:
This game map is 5tiles wide and 3tiles 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 indepth 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:
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 :
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.
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 indepth set of notes concerning heuristics and how they affet pathfinding.
Here are two examples of distance heuristic :
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 ?
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:
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 endlocations, plus a fifth optional boolean argument, to specify if we can diagonal moves or not.
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.
You can reconstruct this very path using the following (it has to be defined before pathfinding.findPath, of course, since the latter uses it) :
For now on, you should have a 100% working Astar implementation. Here is an example of how you should use it:
Output:
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.
Brace yourself. This is going to be long.
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: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.
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.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
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)
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 errorprone. 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 2dimensional 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 fcosts.
Code: Select all
local function createNode(x, y)
return { x = x, y = y, h = 0, g = 0, f = 0 }
end
Code: Select all
local pathfinding = {}
pathfinding.mapData = {}  This will hold the game map.
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
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},
}
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
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}
}
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
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
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 = {}
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
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 fcost 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 fcost
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
Code: Select all
local function backtrace(node)
local path = {}
repeat
table.insert(path, 1, node)
node = node.parent
until not node
return path
end
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
Let us make a quick change to the gameMap and include diagonal neighbors in the search this time:1 1
2 1
3 1
4 1
5 1
5 2
5 3
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
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.1 1
2 1
3 2
4 3
5 3
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.
Last edited by Roland_Yonaba on Mon May 26, 2014 2:47 pm, edited 1 time in total.
Re: Need A* Help
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!
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!
Re: Need A* Help
Isn't everybody?zorfmorf wrote:I don't know if this sounds creepy but I'm a big fan of your work!
GitHub  MLib  Math and shape intersections library  Walt  Animation library  Brady  Camera library with parallax scrolling  Vimlovedocs  Help files and syntax coloring for Vim
 Roland_Yonaba
 Inner party member
 Posts: 1560
 Joined: Tue Jun 21, 2011 6:08 pm
 Location: Ouagadougou (Burkina Faso)
 Contact:
Re: Need A* Help
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.zorfmorf wrote: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: Much thanks for the kind words.
Löve is in the air.
 Zilarrezko
 Party member
 Posts: 345
 Joined: Mon Dec 10, 2012 5:50 am
 Location: Oregon
Re: Need A* Help
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
https://imgflip.com/gif/947xu
that... hopefully that shows up. never used that thing before.
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.
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
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...Roland_Yonaba wrote: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.
https://imgflip.com/gif/947xu
that... hopefully that shows up. never used that thing before.
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 .Roland_Yonaba wrote:Here are my initial assumptions. Your game world is a flat 2dimensional map. It cas be represented with a 2D table of integers.
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
 Party member
 Posts: 311
 Joined: Mon Jun 24, 2013 5:16 am
Re: Need A* Help
It is taking the shortest path afaik, as it does not do diagonal movement, only horizontal and vertical.
My guess
My guess
 Zilarrezko
 Party member
 Posts: 345
 Joined: Mon Dec 10, 2012 5:50 am
 Location: Oregon
Re: Need A* Help
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.
Just doesn't look natural when it goes up then over opposed to up and over sequentially.
 Roland_Yonaba
 Inner party member
 Posts: 1560
 Joined: Tue Jun 21, 2011 6:08 pm
 Location: Ouagadougou (Burkina Faso)
 Contact:
Re: Need A* Help
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.
If you got such results using Jumper, then you just needed to use pathfinder:setMode.
Who is online
Users browsing this forum: No registered users and 11 guests