converting Tetriminos into polygons (or tracing a poly shape around square tiles)

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
Post Reply
DarkShroom
Citizen
Posts: 86
Joined: Mon Jul 17, 2017 2:07 pm

converting Tetriminos into polygons (or tracing a poly shape around square tiles)

Post by DarkShroom »

Hi forum

Now it seems a weird request, i don't really have the requirement for just the Tetris shapes, i could most likely just draw them.

What i want to do is draw in tiled, for my framework, floodfill like tiles (to figure the ones to be joined), join them as one big polygon, and then texture them.


There's a couple of reasons. Optimisation, but also being able to walk along a surface without getting stuck in the gaps.


I have no idea where to begin when describing such an algorithm? Does anyone have any ideas. So far I have got a cool library for performing boolean operations on polygon shapes but it doesn't really work when the shapes do not overlap.

I need something specific to converting a grid.


Can anyone point me in the right direction? I appreciate it might not exist in lua code, but any code would likely do for porting.



EDIT, one lead:
https://stackoverflow.com/questions/127 ... d-polygons
DarkShroom
Citizen
Posts: 86
Joined: Mon Jul 17, 2017 2:07 pm

Re: converting Tetriminos into polygons (or tracing a poly shape around square tiles)

Post by DarkShroom »

well after much deliberation i am fairly certain my answer is some variation or usage of the "marching squares" algorithm

so i am trying to convert this to lua:
https://en.wikipedia.org/wiki/Marching_ ... _algorithm

so i have so far managed to get to the bit of creating the same as part of what i have found on wiki:

Code: Select all

local function marchingSquares(map) 
    
    local width = #map[1]
    local height = #map
    
    local ret = {} --build a new map
    
    for y = 1, height - 1 do
        
        local ret_row = {}
        
        for x = 1, width - 1 do
            
            local mval = 0
            
            --matches the same lookup table here
            --https://en.wikipedia.org/wiki/Marching_squares#Basic_algorithm
            if map[y][x] == 0 then
                mval = mval + 8
            end
            if map[y][x + 1] == 0 then
                mval = mval + 4
            end
            if map[y + 1][x] == 0 then
                mval = mval + 1
            end
            if map[y + 1][x + 1] == 0 then
                mval = mval + 2
            end
            
            table.insert(ret_row, mval)
            
        end
        
        table.insert(ret, ret_row)
    end

    return ret
end

local test_map = {
    {0, 0, 0, 0, 0}, 
    {0, 1, 1, 1, 0}, 
    {0, 1, 1, 1, 0}, 
    {0, 1, 1, 1, 0}, 
    {0, 0, 0, 0, 0}, 
}

for y, row in ipairs(marchingSquares(test_map)) do
    print(inspect(row)) --please note i tend to use the "inspect" lua package
end
i have to admit, my brain now hurts a bit, clearly yeah maybe this works, it is used for "edge detection"... but what i still have is the map that is one smaller in width and height than the original... i have to use "linear interpolation"??

does anyone have any ideas of how i can use this to map out the coordinates of the edges? i dunno if i should run off to stackoverflow here maybe, as perhaps i know we where a bit outside of the scope of the love 2d engine itself

anyway, this would be useful, because for my engine i can just draw a load of squares in tiled, and then turn them into a big polygon

edit: oh also this might be useful to people making those sort of tile maps where you get nice boundaries around rivers and stuff, like where the water meets the edge, perhaps also making pixel perfect collision polygons (although it might be wasteful with certain complex sprite shapes)

edit2: well i might be getting there, i dunno perhaps i turn that lookup table into like a load of 2D coordinates, figure out which ones meet or something (maybe my code will not support the square maps with the holes
User avatar
ivan
Party member
Posts: 1911
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: converting Tetriminos into polygons (or tracing a poly shape around square tiles)

Post by ivan »

First of all, why do you need to represent tetrominoes as individual polygons?
Marching squares along with triangulation is certainly NOT the most "optimal" approach.
In fact, it will make the problem much harder for you.
Note that your code doesn't actually "march" or trace around the contours.
You don't need mval for each cell, only the ones that are "in your path".
For a real, robust solution, you're going to deal with "open" contours and other tricky stuff like holes in polygons.
I can tell you right now, there are better/simpler ways to handle tetrominoes.

For example, you can hard-code these by hand:
local t = { 0,0, 3,0, 3,1, 2,1, 2,2, 1,2, 1,1, 0,1 }
Another option is to draw each tetromino as a series of rectangles.
The simplest approach of all is to use images.
DarkShroom
Citizen
Posts: 86
Joined: Mon Jul 17, 2017 2:07 pm

Re: converting Tetriminos into polygons (or tracing a poly shape around square tiles)

Post by DarkShroom »

well thanks for the reply, i perhaps mistakenly said tetrimos to make the problem more simple to explain... as yeah i know i could have just collected all the tetrimos

i am basically trying to turn groups of squares, that are like tetrimos into a polygon, so i can trace the edge of a square drawn map

i may have an unoptimal solution, but i can't find a better one


so far, it's long winded but i have create a new lookup table with the help of python, i think i will collect all matching marching squares cases:

poly_coors_lookup = {}
poly_coors_lookup[1] = {{0,0},{1,0},{0,1}} --an "L" shape
poly_coors_lookup[2] = {{0,0},{1,0},{1,1}}
poly_coors_lookup[3] = {{0,0},{1,0}} --a straight edge
poly_coors_lookup[4] = {{0,0},{1,1},{0,1}}
poly_coors_lookup[6] = {{0,0},{1,1}}
poly_coors_lookup[8] = {{1,0},{1,1},{0,1}}
poly_coors_lookup[9] = {{1,0},{0,1}}
poly_coors_lookup[12] = {{1,1},{0,1}}

(i eliminate corner cases where there was one coordinate and also all filled and all empty)

this follows wikipedias ODD choice of which corner is which https://en.wikipedia.org/wiki/Marching_ ... orithm.svg
see where it says 8-4-1-2 in the square, i choose there way so i can use that diagram

I am planning to collect all them cases, then check through all the coors and find if any of them would join end to end (likely having to flip the tables round possibly)

I appreciate this all seems a bit crazy, but i cannot find anything else, i might just ignore holes anyway.... sorry for saying tetrimos i did say in the post it was an example



so to summarise, in the end i want to draw square maps in tiled, and trace the boundaries to make giant polygons out of them... the second usage MAY be, to create collision polygons out of sprites on the fly.... yes i think it might be slow, and cannot happen mid game...
furthermore, yes i am not sure why i am so obsessed with this problem, but it seems it can be done and the marching squares knowledge has amused me

edit: my lookup table i think is wrong, but i will find the issue (it is generated anyway)

edit2: i think i understand your advice (following the edge), i might try a different approach, well at least i learnt something, i think, i'll try all avenues i may as well now
User avatar
ivan
Party member
Posts: 1911
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: converting Tetriminos into polygons (or tracing a poly shape around square tiles)

Post by ivan »

DarkShroom wrote: Wed Nov 29, 2017 3:52 pmso to summarise, in the end i want to draw square maps in tiled, and trace the boundaries to make giant polygons out of them... the second usage MAY be, to create collision polygons out of sprites on the fly.... yes i think it might be slow, and cannot happen mid game...
The problem in my opinion is that you are working with a tile-based map.
Trying to handle the collisions of a tile based map using polygons generated via marching squares is a nightmare.
Just use edge shapes for each cell on the map.
There are 16 different edge types based on the 8 adjacent tiles.
It's simple, clean and will allow you to load the map in chunks.
DarkShroom wrote: Wed Nov 29, 2017 3:52 pmfurthermore, yes i am not sure why i am so obsessed with this problem, but it seems it can be done and the marching squares knowledge has amused me
Marching squares is cool, especially when used in the right context (ie heightmaps).
I have played around with the marching squares algorithm in the past too.
Last edited by ivan on Wed Dec 15, 2021 11:32 am, edited 1 time in total.
DarkShroom
Citizen
Posts: 86
Joined: Mon Jul 17, 2017 2:07 pm

Re: converting Tetriminos into polygons (or tracing a poly shape around square tiles)

Post by DarkShroom »

@ivan

hi thanks, yes i did have a complete rethink, you where right about marching squares being wrong

in the end i checked each filled square for N E S W if that was a empty tile, if so, i stored the line itself as coordinates. I collected all these edge lines and then joined them all together when the end of one matches the start of another

i think there may even be a slightly quicker way concerning tracing the perimeter but this works :) (no holes yet)

i enjoyed marching squares mind, it's defiantly useful to me for something else
Post Reply

Who is online

Users browsing this forum: Google [Bot] and 33 guests