LuAstar, a simple A* pathfinding class

[Kadoba]

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

[Jasoco]

Can you post it? For some reason the one I have doesn't have that section of code...

[Kadoba]

Sure thing.

[Jasoco]

Sure thing.

Works great! Thanks!

[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?

[Robin]

A* is pretty abstract, so x or y shouldn't matter. You can probably use it the way you want to use it.

[Jasoco]

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.

[Robin]

Hm, neither of those should happen in a proper implementation of A*.

[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.

LuaStar Test.love

(5.2 KiB) Downloaded 145 times

[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?