I'm trying to detect all regions of a tiled map, and store them in a table.
I found example of a "paint"-like flood fill, and tried to use that. Its working if map table is small 512x512 for example.
But if i chose map size 1024x1024 for example, i get stack overflow.
Code: Select all
function M:grid_get(x,y) return self.map[x][y].type end
function M:set(x,y,v) self.map[x][y].type = v end
function M:collect_regions(x,y,v)
local region = {}
region.type = self:grid_get(x,y)
if self:grid_get(x,y) == v then return end
local oldv = self:grid_get(x,y)
local qx = {x}
local qy = {y}
local left = 0
local right = 1
local function enqueue(x,y)
right = right + 1
qx[right], qy[right] = x, y
end
while left < right do
left = left + 1
x, y = qx[left], qy[left]
if x >= 1 and y >= 1 and x <= self.map_width and y <= self.map_width then
if self:grid_get(x, y) == oldv then
local r = {x=x,y=y}
table.insert(region,r)
self:set(x, y, v)
self.map[x][y].looked = true
enqueue(x+1, y)
enqueue(x-1, y)
enqueue(x, y+1)
enqueue(x, y-1)
end
end
end
table.insert(regions, region)
local t = self:get_next()
if t ~= nil then
self:collect_regions(t.x,t.y,_)
end
end
function M:get_next()
local x = self.prevx or 1
local y = self.prevy or 1
local max_x = self.map_width
local max_y = self.map_width
repeat
y = y+1
if y > max_y then
y = 1
x = x+1
end
if x > max_x then
return
end
until self.map[x][y].looked == false
self.prevx, self.prevy = x,y
local t = {x=x,y=y}
return t
end
