How to merge polygons for a tilemap

Sep 20, 2011 at 2:43 PM
Edited Sep 20, 2011 at 6:28 PM

Hello.

I'm currently working on a toolset for platform games, and in my tilemap editor, each tile has it own physic preset, that can be a rectangle, or a triangle, or any user made polygon.

http://img839.imageshack.us/img839/113/toolset.png 

Then, when I build the tilemap, each tile has it own polygon:

http://img835.imageshack.us/img835/8496/resultv.png 

The tilemap itself is one single body, and each tile is a fixture that is attached to that body.

 

So, there is any way that I can merge these polygon into fewer polygons? like making an union with the neighbor polygons to create one.

 

Thanks in advance.

Renan.

Sep 20, 2011 at 5:31 PM

Merge the lists of vertices and then decompose them. Use some algorithm to detect which polygons you can merge.

Sep 20, 2011 at 6:07 PM
Edited Sep 20, 2011 at 6:28 PM

Thank you for your reply.

How do I decompose the new Vertices?

I actually tried with BayazitDecomposer, but an exception is thrown.

An unhandled exception of type 'System.ArgumentOutOfRangeException' occurred in Engine.dll
Additional information: Index was out of range. Must be non-negative and less than the size of the collection.

 

I think it is because there is no guarantee that the tilemap will have every tile connected with another one.

http://imageshack.us/photo/my-images/708/testalf.png/

Sep 20, 2011 at 6:21 PM
Edited Sep 20, 2011 at 6:22 PM

What exception?

Also, if you merge polygons you'll have to "merge" textures as well, or manage them separetly. I don't think it's easy to attach several textures to a single polygon.

 

Also, an idea appeared in mi mind, why not you just make geometry and images separatedly? You know, a layer in the editor for the geometry and others for the images.

Sep 20, 2011 at 6:41 PM
Edited Sep 20, 2011 at 6:50 PM

What my editor does, is just pick points, as you click in the image, so this points works as vertices for the physic preset.

I did this way to make ths physics more automatic, since you have to create the presset for a given tile, only once, then, whenever you use that tile, the physic for it will be the same.

My editor exports something like this:

[pressets]

Presset 1: x= 0, y= 0, w= 80, h=80 (square presset)

Presset 1: x= 0, y= 0, w= 40, h=40 (half square presset)

[tiles]

Tile0 = Uses Presset 1

Tile1 = No Presset

Tile2 = Uses Presset 2

Tile3 = Uses Presset 2

 [tilemap]

Tile0, Tile0, Tile0, Tile2, Tile2

Tile3, Tile3, Tile1, Tile3, Tile2

 

Then. in my engine  I build the physic for the tilemap something like that:

foreach (Tile in tile in this.Tiles)
{
    Vertices vertices = new Vertices();
    foreach (Vector2 vector in tile.PressetVertices)
    {
        vertices.Add(new Vector2(vector.X + offsetX, vector.Y + offsetY)); // This values comes from the editor
    }  
 
    physicManager.Add(vertices, Tilemap.Body);
}

public void physicManager.Add(Vertices verts, Body body)
{
    PolygonShape shape = new PolygonShape(verts, 0.5f);
    Fixture fixture = body.CreateFixture(shape);
}

 Also the textures are totaly apart from the pressets, it have no conections with the vertices that the user created in the editor.

Sep 20, 2011 at 6:56 PM

Well, maybe you took some separated polygon, or maybe it just can't handle vertices inside the polygon you will create. I mean, if you have four little squares building one bigger square, there are 4 vertices just in the middle, and I don't know if this may be causing the problem.

Sep 20, 2011 at 7:14 PM
Edited Sep 20, 2011 at 7:28 PM

Yeah, if I add all the vertices to a single list, and try to decompose it, it generates an error, because will cause some strange situation, like the one you said.

 

I will try to simplify the problem.

I have this tilemap:

http://imageshack.us/photo/my-images/695/tilessquare.png/

 

This tilemap generate this vertices:

http://imageshack.us/f/710/verticescopy.png/

 

So my editor generates this:

Vertices:

Red: x:=0, y=80, w=80, h=80

Pink: x:=80, y=80, w=80, h=80

Blue: x:=160, y=0, w=80, h=80

In my engine I have:

Vertices redVertices = new Vertices();
redVertices.add(new Vector2(0, 80));
redVertices.add(new Vector2(80, 80));
redVertices.add(new Vector2(0, 160));
redVertices.add(new Vector2(80, 160));
These vertices will be tranformed into a shape;

PolygonShape

shape = new PolygonShape (redVertices, 0.5f);

 

And added to the tilemap body

tilemapBody.CreateFixture(shape);

 
This is done for each of the tiles.
If my tilemap has 100 tiles, I will have 100 squares, and move those square to sides.
What I want to do is, based in this squares, can I simplify it?
Like, using an algorithm and get something like this:
http://imageshack.us/photo/my-images/101/mergedo.png/
The red and the pink, where merged, because they are touching.
I know this is complex, but maybe there is something in the farseer that does this, and I dont know.
Thank you by your patience.
Sep 20, 2011 at 7:32 PM
Edited Sep 20, 2011 at 7:40 PM

Hey, I understand what you want! But I don't have an perfect answer, only things I think could work.

Ok, after this disclaimer I think you should try using this instead of what you use.

After getting all the vertices in the list try that:
List<Vertices> list = BayazitDecomposer.ConvexPartition(redVertices);        
redSquare = BodyFactory.CreateCompoundPolygon(World, list, 1f, BodyType.Static);
redSquare.Position = new Vector2(0,0);
And I don't think there is something that does this automatically. But maybe I'm wrong.


Sep 20, 2011 at 7:46 PM
Edited Sep 20, 2011 at 8:04 PM

Hey.

I did what you suggest, and when tried to decompose:

List<Vertices> list = BayazitDecomposer.ConvexPartition(AllVertices);

I got this exception:

An unhandled exception of type 'System.ArgumentOutOfRangeException' occurred in Engine.dll

Additional information: Index was out of range. Must be non-negative and less than the size of the collection.

 

Then I simplified again the tilemap, for just 2 tiles, and got this:

http://imageshack.us/photo/my-images/62/22627303.png/

 The vertices are right, but it decomposed in a strange way, and sometimes, it asserts saying that the polygon is non-convex

Thank you

Sep 20, 2011 at 8:20 PM
Edited Sep 20, 2011 at 8:23 PM

Maybe they are in the wrong order, or maybe it's just that the decomposer ONLY works with convex polygons, and fails with a simple rectangle like that. Try making a staris-like shape with squares and try to use the decomposer again to see what happens.

 

Also, I remember reading that FPE has some decomposers, try using the others.

Sep 26, 2011 at 2:52 AM

Hello Ayalaskin,

Nice tileset, looks great.  I don't have a solution but I may have some pointers or theories that may help.

What I'd try is declare another Vertices object, then take your list of Vertices generated by your tilemap and start a loop.
Within that loop do a query (by looping, selecting, or Linq) on the new Vertices object to see if the Vector2 already belongs to the new Vertices object, if it doesn't then allow it to be added.

The other problem is the winding order of the verts (I think you demonstrated that in an image above where the top left vert did not connect with the bottom left vert.
This has been a problem for me in the past but I think you might be able to Sort the Vertices object so that Farseer will connect the dots in the best order.

The above is only THEORY and could possibly be a terrible one, I hope it helps.
One of my many abandoned projects has the same problem you are mentioning, I just never got around to figuring out.  If you do get past it please share.

Best of luck,

Nick 

            

 

Oct 10, 2011 at 11:38 PM

Hello Ayalaskin,

Did you get anywhere with this?

Thanks,

Nick

Oct 11, 2011 at 5:38 PM

Hey, thank you for your answer.

I kind of give up for the moment.

I tried many thing,s and algorithms, but the disposition of the tiles are a mess, and it is hard to organize the vector.

Developer
Oct 13, 2011 at 7:26 PM

I tired a totally different approach.

Instead of trying to reduce the number of bodies by combining them I simply add and remove tiles bodies when they get close to a dynamic body. This work extremely well as I can have 5+ million static 'tiles' and hundreds of dynamic tiles with no problems. I can also add and remove tiles without any problems.

So now you say, "Sweet, but what about the edge catching problem?" and I say this -

I add an OnCollision event that is able to detect whether or not the two bodies that are colliding are a tile and dynamic and then add a tiny amount of velocity in the opposite direction of the collision normal. Once tuned, this works perfectly well and completely removes the edge catching problem.

Oct 14, 2011 at 8:19 AM

Matt, I saw your video where you implement what you are describing (the dynamic static bodies), and is completely brilliant. Do you store the "squares" on a two dimensional array? (so the array coordinates matches the dynamic bodies coordinates)

Developer
Oct 15, 2011 at 2:33 AM

@Pnikosis - I hate to give specific examples or source code because some of my GPL licensed code has been used in commercial apps without permission. I also feel like I'm giving away tech for free without any compensation. I have been coding for quite some time now and never earned a single dollar. And it sucks when someone takes the code you open sourced and makes money off it. I would consider sending you the source code for my prototype if your really interested.

In my game I have a ton of tiles (think Terraria) and I wanted real physics. So I do store my tiles in a 2D array. However, the coordinates are not matched.

Oct 15, 2011 at 10:43 PM
Edited Oct 15, 2011 at 10:44 PM

You mean creating the bodies when a dynamic object get near, and deleting them when it's far?

Cool idea. I'm not working in a 2D project by the moment, and I don't think I would be using a tile system, by it looks great and very smart.

Oct 17, 2011 at 4:06 AM

Matt, you Terraria clone vid on youtube is awesome and definitely supports your approach.  It runs smooth as glass, thanks for the nudge in a better direction.  Also sorry that people poop on your license :( 

Oct 18, 2011 at 10:10 AM
mattbettcher wrote:

@Pnikosis - I hate to give specific examples or source code because some of my GPL licensed code has been used in commercial apps without permission. I also feel like I'm giving away tech for free without any compensation. I have been coding for quite some time now and never earned a single dollar. And it sucks when someone takes the code you open sourced and makes money off it. I would consider sending you the source code for my prototype if your really interested.

In my game I have a ton of tiles (think Terraria) and I wanted real physics. So I do store my tiles in a 2D array. However, the coordinates are not matched.

 

Don't worry Matt, I wasn't asking for the code, just a quick comment on how you did it as I was quite curious about how you approached the bodies caching and the dynamic activation. Right now I'm not planning to do anything that would require this, but thanks anyway :)

Dec 28, 2011 at 4:08 PM
mattbettcher wrote:

I tired a totally different approach.

Instead of trying to reduce the number of bodies by combining them I simply add and remove tiles bodies when they get close to a dynamic body. This work extremely well as I can have 5+ million static 'tiles' and hundreds of dynamic tiles with no problems. I can also add and remove tiles without any problems.

So now you say, "Sweet, but what about the edge catching problem?" and I say this -

I add an OnCollision event that is able to detect whether or not the two bodies that are colliding are a tile and dynamic and then add a tiny amount of velocity in the opposite direction of the collision normal. Once tuned, this works perfectly well and completely removes the edge catching problem.


Thanks for a simple solution to the edge catching problem that I've been struggling with for a while. Solved my problem ;)

Mar 14, 2012 at 2:28 AM

Bringing up an old thread here but if you could pm me any source code forwhat you describe there Matt it would be really appreciated. My current game is for a uni project and my platformer is currently been plagued by the edge catching but I can't seem to do what you said to the same effect.

If not I can totally understand if not but thought I'd ask anyway!