Multiple Recursion

[allanws]

Hello everyone,

I am working on a project for my A.I. class and I have encountered a problem (which I recall having a few years ago on another project).
I don't know if this is a Lua or LOVE problem (most probably lua), you guys might be able to help...

I have the following local function:

Code: Select all

local function expand(tile)		
		
		-- Caso o tile for loja...
		if tile.type ~= 'o' and tile.type ~= 'x' then
		
			shops[tile.type] = shops[tile.type] + 1
		
		elseif tile.type == 'x' then
		
			return
		
		end
		
		tile.walkedOn = true
		
		-- Table de tiles adjacentes
		local adjTiles = {
			self:getTile(tile.x + 1, tile.y),
			self:getTile(tile.x - 1, tile.y),
			self:getTile(tile.x, tile.y + 1),
			self:getTile(tile.x, tile.y - 1)
		}
		
		-- Para cada tile (se existir e ainda não passou) expandir recursivamente
		for i,v in ipairs(adjTiles) do
		
			if v ~= nil and not v.walkedOn then				
				
				expand(v)	
				
			end
		
		end	

		return	
	
	end

As you can see, I have a recursive call inside a loop for each adjacent tile to the current one.
What happens is that it doesn't fully expand all tiles, the ones on the left and right hand side of my map (x = 1 and x = MAPSIZE) don't expand.

I tried changing the order of the tiles in "adjTiles" and that seems to change everything:
If I put "self:getTile(tile.x, tile.y - 1)" as first index, the right- and left-most tiles expand, but the top ones (y = 1) don't.
That happens with every permutation of adjTiles, some tiles don't expand.

A pic:



Thanks in advance!

[Kadoba]

It looks correct at a glance. Can you post a .love?

[vrld]

Wild guess, but you exit before setting tile.walkedOn to true if tile.type equals 'x'. Moving 'tile.walkedOn = true' to the start of the function might fix your problem.

[Inny]

Lua's order of operations is a little strange, this might be a case where you're being bit by it on this line: if v ~= nil and not v.walkedOn then

If I'm not mistaken, lua is interpreting it like so: if v ~= (nil and not v.walkedOn) then which is probably incorrect. Try putting explicit parenthesis.

Also see: http://www.lua.org/manual/5.1/manual.html#2.5.6

Edit: I am mistaken, I read the chart backwards, the and operator goes _after_ the ~= and not operators.

[Robin]

If I'm not mistaken, lua is interpreting it like so: if v ~= (nil and not v.walkedOn) then

Nonsense. Both not and ~= have higher precedence than and.

if v ~= nil and not v.walkedOn then parses as if (v ~= nil) and (not v.walkedOn) then

[allanws]

Thanks for the answers!

Wild guess, but you exit before setting tile.walkedOn to true if tile.type equals 'x'. Moving 'tile.walkedOn = true' to the start of the function might fix your problem.

I've changed my function a bit to avoid this from happening. Now, a tile with type == 'x' doesn't even expand.

Code: Select all

local function expand(tile)		
		
		-- Caso o tile for loja...
		if tile.type ~= 'o' then
		
			shops[tile.type] = shops[tile.type] + 1		
		
		end
		
		tile.walkedOn = true
		
		-- Table de tiles adjacentes
		local adjTiles = {
			self:getTile(tile.x + 1, tile.y),
			self:getTile(tile.x - 1, tile.y),
			self:getTile(tile.x, tile.y + 1),
			self:getTile(tile.x, tile.y - 1)
		}
		
		-- Para cada tile (se existir e ainda não passou) expandir recursivamente
		for i,v in ipairs(adjTiles) do
		
			if v ~= nil and not v.walkedOn and v.type ~= 'x' then				
				
				print("Expanding: " .. v.x .. " " .. v.y)
				expand(v)	
				
			end
		
		end	

		return	
	
	end

Same thing happens though...
The main problem I'm having is debugging this. If I could debug it, I'm sure I'd find a solution, but how can I in LOVE?

It looks correct at a glance. Can you post a .love?

Sure thing.
source.love - 239.3 Kb

Cheers!

[vrld]

Here's the problem:

Code: Select all

      local adjTiles = {
         self:getTile(tile.x + 1, tile.y),
         self:getTile(tile.x - 1, tile.y),
         self:getTile(tile.x, tile.y + 1),
         self:getTile(tile.x, tile.y - 1)
      }

      for i,v in ipairs(adjTiles) do

Hint:

ipairs(t)
Returns three values: an iterator function, the table t, and 0, so that the construction

for i,v in ipairs(t) do body end
will iterate over the pairs (1,t[1]), (2,t[2]), ···, up to the first integer key absent from the table.

[allanws]

Here's the problem:

Code: Select all

      local adjTiles = {
         self:getTile(tile.x + 1, tile.y),
         self:getTile(tile.x - 1, tile.y),
         self:getTile(tile.x, tile.y + 1),
         self:getTile(tile.x, tile.y - 1)
      }

      for i,v in ipairs(adjTiles) do

Hint:

ipairs(t)
Returns three values: an iterator function, the table t, and 0, so that the construction

for i,v in ipairs(t) do body end
will iterate over the pairs (1,t[1]), (2,t[2]), ···, up to the first integer key absent from the table.

Changed to pairs() and worked! Thanks so much vrld!
Although I'm still not quite sure I understand why ipairs doesn't work in this case... Doesn't it iterate over ALL values returning index and value?
I didn't understand the last statement "up to the first integer key absent from the table".

EDIT: Also, +1 karma
EDIT2: Scratch out that last paragraph, I understand now!