I'm trying to use a breadth-first search on a grid for path finding. My code works for a grid of 7x7, and just barley for 8x8, but it runs out of memory at 9x9. I was just wondering if there was a way I could do things differently to keep the memory usage down.

function grid:findpath(src,dest)

 function buildpath(node)
  local path={}
  local current=node
  while current do
   add(path,current,1)
   current=current.parent
  end
  return path
 end

 local dirs={
  {x=-1,y=0},
  {x=1,y=0},
  {x=0,y=-1},
  {x=0,y=1}
 }
 src.parent=nil
 local queue={}
 local visited={}
 for y=1,grid_size do
  local row={}
  for x=1,grid_size do
   add(row,false)
  end
  add(visited,row)
 end
 add(queue,src)
 while #queue>0 do
  local node=deli(queue,1)
  visited[node.y][node.x]=true
  if node.x==dest.x and node.y==dest.y then
   return buildpath(node)
  end
  for dir in all(dirs) do
   local new_node={
    parent=node,
    x=node.x+dir.x,
    y=node.y+dir.y
   }
   if new_node.x>0 and new_node.y>0 and new_node.x<=grid_size and new_node.y<=grid_size and visited[new_node.y][new_node.x]==false and self[new_node.y][new_node.x]==0 then
    add(queue,new_node)
   end
  end
 end
end

Thanks

did you check it produces a correct result in the first place?
9x9 is quite small, I am suspecting an infinite loop

So, this problem intrigued me enough to do some testing and working on it. However, I'm not entirely sure why the amount of memory your code uses would be a problem. I placed instances of print(stat(0)) in the most intensive parts and ran it with a 13x13 test maze. The numbers ranged from 36kB to 65kB, and ended on 35kB. For comparison, running pico-8 with just an empty _init() and an _update() containing only the reporting of memory gives 23kB. At most, your code is only using 42kB out of the available 2048kB or so. My best guess is that your memory running out is caused either by calling it a couple hundred times before the garbage collector hits or by some related process that merely makes it look like the pathfinding is the problem.

That said, if you'd like to try a lower memory version, here's one that never uses more than 1 dimension to store anything (beyond of course what is necessary to make it a drop-in replacement for your code). It runs at a straight 37kB for most of the function and then momentarily goes up to 39kB, so it maxes at about 16kB beyond what pico-8 already ends up using. The downside is the extra math needed to avoid an off-by-one bug may add considerably to the number of cycles used.

function grid:findpath(src,dest)

  function buildpath(node,parents)
    local path={}
    local current=node
    local old
    while current do
      local node_version = {
        parent=old,
        x=current%grid_size+1,
        y=flr(current/grid_size)+1
      }
      add(path, node_version, 1)
      current=parents[current]
      old=node_version
    end
    return path
  end

  local dirs = {-1,0,1,0,0,-1,0,1}

  src_node=(src.y-1)*grid_size+src.x-1
  dest_node=(dest.y-1)*grid_size+dest.x-1
  local queue={}
  local visited={}
  for i=0,grid_size*grid_size-1 do
    add(visited,false)
  end
  add(queue,src_node)
  visited[src_node]=true
  while #queue>0 do
    local node=deli(queue,1)
    if node==dest_node then
      visited[src_node] = false
      return buildpath(node,visited)
    end
    for i=1,#dirs,2 do
      local dirx = node%grid_size + dirs[i]
      local diry = flr(node/grid_size) + dirs[i+1]
      local new_node = diry*grid_size + dirx
      if dirx >= 0 and diry >= 0 and dirx < grid_size and diry < grid_size and self[diry+1][dirx+1] == 0 and not visited[new_node] then
        visited[new_node]=node
        add(queue,new_node)
      end
    end
  end
end

and how many "units" are you calculating path for?
that might better explain the OOM error!

Thanks @kimiyoribaka!
I actually used your function as a drop-in replacement, and no more out of memory problems. I had thought about doing something like this, but I didn't think it would make that much of a difference; two dimensions didn't seem like a lot.

@freds72, each unit is just a table like this:

src = {
 parent = [parent unit],
 x = number [1 to grid_size],
 y = number [1 to grid_size]
}

So, for a 9x9 grid it would only be 81 units right?

Ah, I guess it'd be good to explain why that made a difference. When you make a 2-dimensional container, every row within the container needs to be another table. When you then make every element within the container an object, that means each object and each row is another table. According to a quick google search, the normal lua implementation requires 40 bytes per table just to keep track of the table itself. Pico-8's version might be a smaller, but it's still going to use considerable memory if you make structures that nest lots of tables.

That makes sense.

Coming from other languages, it took me a while to get the hang of using tables. But then I started to appreciate how flexible they were/are, so I might be using them a little more than necessary.