Page 1 of 1
Multiple Recursion
Posted: Tue Sep 11, 2012 2:11 am
by 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!
Re: Multiple Recursion
Posted: Tue Sep 11, 2012 1:58 pm
by Kadoba
It looks correct at a glance. Can you post a .love?
Re: Multiple Recursion
Posted: Tue Sep 11, 2012 2:21 pm
by 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.
Re: Multiple Recursion
Posted: Tue Sep 11, 2012 5:49 pm
by 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.
Re: Multiple Recursion
Posted: Tue Sep 11, 2012 6:11 pm
by Robin
Inny wrote: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
Re: Multiple Recursion
Posted: Tue Sep 11, 2012 9:03 pm
by allanws
Thanks for the answers!
vrld wrote: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?
Kadoba wrote:It looks correct at a glance. Can you post a .love?
Sure thing.
source.love - 239.3 Kb
Cheers!
Re: Multiple Recursion
Posted: Tue Sep 11, 2012 9:45 pm
by 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
Lua Manual wrote:
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.
Re: Multiple Recursion
Posted: Wed Sep 12, 2012 12:54 am
by allanws
vrld wrote: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
Lua Manual wrote:
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!