Page 3 of 4
Re: LuAstar, a simple A* pathfinding class
Posted: Thu Oct 20, 2011 2:20 pm
by Kadoba
Jasoco wrote:I'm interested in implementing this class/library/whatever into some games. It works pretty well. But I don't like how it handles diagonal movement where it cuts corners.
I think I got this working for you.
Go to line 80 in Astar.lua and replace the following:
Code: Select all
local left,right = false,false
if not self.diagonalMove then -- Diagonal Moves, optional!
left = (y==self.currentNode.y-1) and ((x==self.currentNode.x-1) or (x==self.currentNode.x+1))
right = (y==self.currentNode.y+1) and ((x==self.currentNode.x-1) or (x==self.currentNode.x+1))
end
if not left and not right then
with this:
Code: Select all
local stop = false
if self.diagonalMove then -- Skip if this is a diagonal node but is blocked by an adjacent node.
local xdiff, ydiff = x - self.currentNode.x, y - self.currentNode.y
if math.abs(xdiff) == 1 and math.abs(ydiff) == 1 then
if not self:isWalkable(Node(self.currentNode.x, self.currentNode.y+ydiff)) then stop = true end
if not self:isWalkable(Node(self.currentNode.x+xdiff, self.currentNode.y)) then stop = true end
end
else -- Diagonal Moves, optional!
stop = (y==self.currentNode.y-1) and ((x==self.currentNode.x-1) or (x==self.currentNode.x+1))
stop = stop or ( (y==self.currentNode.y+1) and ((x==self.currentNode.x-1) or (x==self.currentNode.x+1)) )
end
if not stop then
That should work. If not then I can post the altered .love
Re: LuAstar, a simple A* pathfinding class
Posted: Thu Oct 20, 2011 11:37 pm
by Jasoco
Can you post it? For some reason the one I have doesn't have that section of code...
Re: LuAstar, a simple A* pathfinding class
Posted: Fri Oct 21, 2011 1:48 pm
by Kadoba
Sure thing.
Re: LuAstar, a simple A* pathfinding class
Posted: Fri Oct 21, 2011 5:16 pm
by Jasoco
Kadoba wrote:Sure thing.
Works great! Thanks!
Re: LuAstar, a simple A* pathfinding class
Posted: Mon Dec 12, 2011 7:35 am
by Jasoco
Bumping because I now have a problem.
I started implementing this into a project I am working on and discovered a problem with how the map grid in the Astar library vs. how I store map grids in all my projects.
Seem in Astar, grids are expected to be stored as Y first then X. In that you go for y, for x. But I have always stored mine as X then Y with for x, for y. Now, I don't want to have to change how I do my thing, but this kind of messes things up. Because I like to refer to my grid tiles as grid[x][y] not grid[y][x].
Is it possible to flip this around? Or get a different library?
Re: LuAstar, a simple A* pathfinding class
Posted: Mon Dec 12, 2011 7:51 am
by Robin
A* is pretty abstract, so x or y shouldn't matter. You can probably use it the way you want to use it.
Re: LuAstar, a simple A* pathfinding class
Posted: Mon Dec 12, 2011 8:23 am
by Jasoco
Robin wrote:A* is pretty abstract, so x or y shouldn't matter. You can probably use it the way you want to use it.
The problem is when you initialize it, you pass a grid. My grids go [x][y]. But LuaStar errors out unless I pass it a grid with [y][x] formatting. I'd like to modify it so that it expects x, y instead of y, x.
Also, it seems LuaStar is a bit slow. I have a grid of 38x23 and it sometimes takes upwards of .5 seconds to calculate a path. Is it possible to use threading or some other method to have it calculate the path in the background so it doesn't pause the rest of my program? Somehow have it calculate the paths parallel to the rest of the game. I was hoping to use it for AI in a simulation game with little people who need to wander around from destination to destination, but it will be quite a problem when every single person is pausing the program every time they try to calculate their path.
Re: LuAstar, a simple A* pathfinding class
Posted: Mon Dec 12, 2011 9:11 am
by Robin
Hm, neither of those should happen in a proper implementation of A*.
Re: LuAstar, a simple A* pathfinding class
Posted: Mon Dec 12, 2011 9:35 am
by Jasoco
See for yourself...
LuaStar library is unmodified except for a console print to show the time it takes to calculate. Run with Console. Should run fine in 0.7 and 0.8 both.
Re: LuAstar, a simple A* pathfinding class
Posted: Mon Dec 12, 2011 11:23 am
by coffee
When I saw some time ago this demo I thought this was amazing. But since there wasn't very instructions about it and I didn't any real test yet I had some doubts about future using it. In theory and looking how the engine interface, as Jasoco noted could be some problems to adapt it for our own engines without changing the library itself.
For example, I have multiple layers on my project, if I wanted to use it how I made the Astar check and account both layers for obstacles at same "run"?
Also, since it's a library could be a little more flexible. Not my case but probably not all people use or needs a single walk value/variable like the one set by Astar:setObstValue but instead inverse checking letting player to walk only in one or two tile values (and negate walk in all other map tiles). So couldn't otherwise user say the value(s) which permits walking?
