How to check if Lua table contains coordinates?

Question

I'm trying to implement a simple pathfinding system that works with open and closed lists. I'm having trouble with the closed list. How can I check if the closed list already contains the coordinates?

closed[current] = true

local neighbors = getNeighbors(current[1], current[2]) -- get neighbors for the current node
for k, v in ipairs(neighbors) do -- iterate through each neighbor
  if not closed[v] then
    table.insert(open, v)
  end
end

getNeighbours returns every neighbour tile of a tile(x,y) in the form of coordinates(x,y). How can I check if the closed table already contains these coordinates?

Answer 1

Hashing the whole table

With Lua, the key (hash) of the table can be almost everything, EVEN a table with 2 values.

Assuming current[1] and current[2] represents, respectively, the coordinates x and y, you can just check closed[current]. See the example below:

local coordinates = {
  {1.3,5},
  {2.2,3.4},
  {3,6.8}
}
local closed = {} --Empty closed list
local current = coordinates[1]  --{1.3,5}
print(closed[current]) --Not visited = nil
closed[current] = true --Marking as visited
print(closed[current]) --visited = true
print(coordinates[2]) --Not visited = nil

When you check if closed[current] then ..., the entry not existing is equivalent to nil, that is equivalent to false. If you explicitly want false values instead of nil you can do the initialisation of the closed list like this:

closed = {}
for i=1,#coordinates do
    closed[coordinates[i]] = false
end

Hashing the coordinate values

The only problem would happen if you are somewhere in your code copying the values of the coordinates, instead of referencing the table {x,y}. In that case you would have different tables, so the hash will give you false even when the values of the 2 tables are equal.

If that is likely to happen you will need to hash with the VALUES instead of the table. You can do this the way Egor suggested, with a single hash, of with a double hash, like this:

local function listAddPoint(list,point) --Adds point (a {x,y} table) to the list
    if not list[point[1]] then
        list[point[1]] = {}
    end
    list[point[1]][point[2]] = true
end

local function listHasPoint(list,point) --Checks if the point (a {x,y} table) is on the list
    if list[point[1]] and list[point[1]][point[2]] then
        return true
    end
    return false
end

local coordinates = {
  {1.3,5},
  {2.2,3.4},
  {3,6.8}
}
local closed = {} --Empty closed list
local current = coordinates[1]  --{1.3,5}
print(listHasPoint(closed,current)) --Not visited = false
listAddPoint(closed,current)--Marking as visited
print(listHasPoint(closed,current)) --visited = true
print(listHasPoint(closed,coordinates[2])) --Not visited = false