LoveAStar: A* Search in Lua/Love

[MarekkPie]

I'd still like to see a few test runs from different map designs, because all that stuff is theoretical at the moment. But, yeah, you should be able to just go to the GitHub page and give it a go.

[Lap]

I'm always looking for different, improved pathfinding implementations. I'm currently using the following for basic A*Star.

Code: Select all

---AStar pathfinding implentation
--@author DecoDaMan

local ipairs = ipairs
local pairs = pairs
local table = table
local math = math
local print = print
local unpack = unpack

astar = {}

---table.call
--@param t
--@param ...
function table.call(t, ...)
	if type(t) == "function" then return t(...) end
	for k,v in pairs(t) do
		if not v(...) then
			return false
		end
	end
	return true
end

---table.multiplier
--@param t
--@param num
--@param ...
function table.multiplier_call(t, num, ...)
	if type(t) == "function" then return t(...) end
	for k,v in pairs(t) do
		num = num * v(num, ...)
		if num < 0 or num >= math.huge then break end
	end
	return math.max(num, 0)
end
local object_meta = {}

---astar.Create
--@param starting_node
--@param target_node
--@param neighbour_iterator
--@param walkable_checks
--@param heuristic
--@param ...
function astar.Create(starting_node, target_node, neighbour_iterator, walkable_checks, heuristic, conditionals, args)
	return {
		node_status = {
			[starting_node] = { -- 1) Add the starting node to the open list
				list = false, -- true = on the closed list, false = on the open list
				parent = nil,
				f = 0, -- g+h
				g = 0, -- length of path from starting node to current node (current.g = parent.g + heuristic(parent, curent))
				h = heuristic(starting_node, target_node, args), -- estimated distance to target node
				c = 1,
			}
		},
		starting_node = starting_node,
		target_node = target_node,
		neighbour_iterator = neighbour_iterator,
		walkable_checks = walkable_checks,
		heuristic = heuristic,
		conditionals = conditionals or {},
		args = args
	}
end

---astar.Step
--@param object
function astar.Step(object) -- 2) Repeat the following:
	local lowest_f_score, current_node, current_status = math.huge, nil, nil
	for open_node, status in pairs(object.node_status) do -- a) Look for the lowest F cost node on the open list...
		if not status.list and status.f < lowest_f_score then
			current_node = open_node -- ... We refer to this as the current node.
			lowest_f_score = status.f
			current_status = status
		end
	end
	if current_node then
		if current_node == object.target_node then -- (If this node is the target node, stop and loop backwards from the target node via parent links to the source node...
			local path, pathi, pathn = {current_node}, 1, current_node
			while path[pathi] do
				pathi = pathi + 1
				pathn = object.node_status[pathn].parent
				path[pathi] = pathn
			end
			return true, true, path, node_status -- ...This is your path! :D )
		end
		current_status.list = true -- b) Switch it to the closed list
		local neighbour_status
		for _, neighbour_node in ipairs(object.neighbour_iterator(current_node, current_status, object.args)) do -- c) For each of the nodes linked to this node:
			neighbour_status = object.node_status[neighbour_node]
			if not neighbour_status then -- () If it isn't on the open list,...
				local walkcheck = table.call(object.walkable_checks, current_node, neighbour_node, object.startinging_node, object.target_node, object.heuristic, object.args)
				if walkcheck ~= false then -- ...and it's walkable...
					neighbour_status = {
						list = false, -- ...add it to the open list...
						parent = current_node, -- ...Make the current node the parent of this node...
						-- ...Record the..
						--g = current_status.g + object.heuristic(current_node, neighbour_node, unpack(object.args)) -- ...G cost...
						g = current_status.g + walkcheck -- ...G cost...
								* table.multiplier_call(object.conditionals, 1, current_node, neighbour_node, object.starting_node, object.target_node, object.heuristic, object.args), -- ...additional costs...
						h = object.heuristic(current_node, object.target_node, object.args), -- ...H cost...
					}
					neighbour_status.f = neighbour_status.g + neighbour_status.h  -- ...and the F cost.
					object.node_status[neighbour_node] = neighbour_status
				end
			else 
			local walkcheck = table.call(object.walkable_checks, current_node, neighbour_node, object.startinging_node, object.target_node, object.heuristic, object.args) 
				if not neighbour_status.list -- () If it is on the open list already,...
				 and walkcheck ~= false  -- ...and it's walkable...
				 and object.node_status[neighbour_status.parent].g > current_status.g -- ...check to see if this path to that node is better from the current node, using G cost as the measure...
				then
					-- ..A lower G cost means that this is a better path. If so...
					neighbour_status.parent = current_node -- ...change the parent of the node to the current node...
					--neighbour_status.g = current_status.g + object.heuristic(current_node, neighbour_node, unpack(object.args)) -- ...G cost...
					neighbour_status.g = current_status.g + walkcheck -- ...G cost...
						* table.multiplier_call(object.conditionals, 1, current_node, neighbour_node, starting_node, target_node, heuristic,object.args) -- ...additional costs...
					neighbour_status.f = neighbour_status.g + neighbour_status.h -- ... and the F cost.
				end
			end
		end
	else -- (If the openlist is empty, and you haven't found the target node...
		return true, false, {start_node}, node_status -- ...there is no path! D: )
	end
	return false
end

---astar.CalculatePath
--@param starting_node
--@param target_node
--@param neighbour_iterator
--@param walkable_checks
--@param heuristic
--@param ...
function astar.CalculatePath(starting_node, target_node, neighbour_iterator, walkable_checks, heuristic, conditionals, args)
	local object = astar.Create(starting_node, target_node, neighbour_iterator, walkable_checks, heuristic, conditionals, args)
	local finished, found, path, statuses
	while not finished do
		finished, found, path, statuses = astar.Step(object)
	end
	return found, path, statuses
end

With a quick look does anything jump out at anyone as being inferior/superior to this implementation?

[MarekkPie]

This is just a quick look (since I'm in class), but it looks like you put all the nodes (closed and open) into one list and loop over that. Nodes on the closed will never been needed again until a path is found. It looks like you "prune" it by changing its boolean value of "list," but even with something that small, you still have to poke at those dead nodes when you are looking for your next best f score.

The other thing would be to use a binary heap for your open node list. Binary heaps care little about their order, other than that each pair of child nodes is less than (or greater than for a maximal open list) its parent. That way, you don't even have to loop through your open list, you just take the top most node, and the binary heap updates itself to bubble up the next best f score.

There might be more, but like I said, I'm in class.

EDIT: (It looks like you may have changed this method after you mention it in the starting_node comments, but you've got functions with TONS of parameters, so its a bit hard to tell what's going on. I'll leave this warning in just in case you are doing it this way.)

I just noticed an issue. Right now, it seems that you are calculating your g score by adding the parent's g score to the heuristic score. The heuristic score measures the distance from any node to the exit, not to its neighbors. This is one of the things that separates A* from Dijkstra's. The g score should be the total distance traveled by the algorithm to that node (using the best path).

Another thing you could do to improve it is by instead of doing a walkable check (which I assume is checking for walls/bodies of water/etc.) inside the algorithm, when you create a node, only link to neighbors that are walkable. This would also remove a few unnecessary checks that probably add up in the long run.

Overall, I'd say there's a lot of computations being done inside the algorithm that could (and probably should for efficiency) be done outside. A* (by itself) mainly deals with navigating around static objects, so needing to calculate distances and neighbors aren't really necessary during real time. I fixed this by finding the neighbors, the absolute distance (g score) and the heuristic distance (h score) all during the initial creation of the path map (the full list on non-wall nodes in the 2D, or maybe even 3D, game map). That way, instead of having to constantly recalculate information that (probably) hasn't changed, you do this once per deformation (a wall goes away or gets added).

It does leave that end of the implementation up to the user of my A*, but I included (what I think) are some pretty nice instructions and a helper node constructor that will throw an error if the nodes were constructed incorrectly.

[Jasoco]

This shouldn't happen.

[MarekkPie]

viewtopic.php?f=5&t=7174&start=30#p46554

Not everyone agrees. Pure A* doesn't assess the size of an object, so in this case, there is nothing stopping it. That's why I didn't ignore this case in my demo. There is nothing stopping you from pruning those neighbors when you make your flattenMap function. I gave a simple example of one inside the code, and some instructions on how to make it in instructions.txt. It's nothing major, just at the beginning of a level, loop through the level and make an array of nodes (provided by a constructor in the astar.lua file) with appropriate information. I don't think you'll find an abstract A* (like mine) that is going to be "plug and play."

For how to get rid of this situation, when you are finding your neighbor nodes, look at the nodes orthogonal to you. If it is a wall, remove all the nodes on that side from your neighbors.

Code: Select all

OOO   O = empty
XNO   X = wall
OXO < N = currently checked node
^

The row/column with the arrows will be removed from the neighbor list on the currently checked node.

[Jasoco]

No. It shouldn't happen. That's not an opening. It's two corners of walls touching too close for anything to fit through. Therefore the thing traveling won't be going through it.

Who doesn't agree? I need names and addresses.

Can you fix it for little old me? For old times sake? Remember the good times we shared?
[INSERT MEMORY MONTAGE HERE SET TO SARA BAREILLES "GRAVITY"]

[bartbes]

Except the A* algorithm doesn't know they are walls, just nodes.
I assume every node has a list of neighbours, meaning that if the diagonally 'connected' tiles aren't in that list this shouldn't be happening. (I personally frown upon diagonal movement anyway.)

[kikito]

This shouldn't happen.

That is a common question in roguelikes that allow for diagonal movement. Some of them allow that, others don't.

The ones that allow it have a standard explanation: all walls have round corners. A regular monster/player would be able to "squeeze" between them. Like this:

roguelike.png (18.72 KiB) Viewed 5806 times

[coffee]

This shouldn't happen.

That is a common question in roguelikes that allow for diagonal movement. Some of them allow that, others don't.
The ones that allow it have a standard explanation: all walls have round corners. A regular monster/player would be able to "squeeze" between them. Like this:

Yes it is. If you were a player, could you go between those walls?

Hmmm, actually some (probably a lot) roguelikes would let you pass.

I already stated that some posts ago. As kikito says it's really very very very (add more very's) common in roguelikes. So I and thousands of other rogue players are sending you our addresses now Jasoco.

The most right correct in this kind of engine is have some switch that enable/desables that "permissive" diagonals. In my rpg/rogue I'm doing atm I actually also let do this diagonal moves. I also understand that Jasoco says that souldn't happen but also always map representations differ so in one game wall "holes" can be larguer than in anothers.

[MarekkPie]

For a less game-specific answer (along the lines of bartbes):



This is all A* sees. It doesn't look at the actual geometry of any given map; it only knows its neighbors (the other nodes it is connected to) and the distance to each of them. This is why I require a custom flattenMap(), because if I made A* do this for you, not only would it be much slower (you can see from your SS that my flattenMap takes a while), it would make it less abstract, since there is little possibility I could account for all the possible maps.

I assume you've got everything already in a square-based grid, so all you are looking for is pruning those unique situations? I explained in my first reply how to do it, but I suppose I could whip something up.

Your game also has doors, which I'm not certain how you'd want the pathfinding to handle. Unless you say otherwise, I am going to assume the enemies can open the doors themselves, and it is instant, which essentially means the doors only exist as a visual barrier. Then I can just write flattenMap so that it ignores doors.