# Generating polygonal maps

This picture was generated by selecting random points, creating Voronoi polygons, and filtering them with noise. My question: for physics, colliding with multiple polygons really slows down the project. Can I possibly speed up calculation time by combining adjacent polygons? The math for this is beyond me.

@em2 One way you might be able to check for collisions is to draw the edges of the polygons with a specific color and depending on the direction your primary object is moving, see if it would run into the polygons edge color. That way you’re only checking a few pixel colors instead of checking for a lot of edges.

@em2 just puzzling this out, here…

What you ultimately want to do is to create one big polygon for each self-contained area…

If you can programmatically search for a line that isn’t overlapping any other line, you can be sure the line is on the outside of a shape…
Every perimeter line will connect to two and only two other perimeter lines – meaning lines that also don’t overlap other lines…
So if you can set up logic that traces from point to point checking for lines that don’t overlap other lines, you should be able to assemble one big polygon from all the perimeter lines… right?

Not sure exactly how you do that, but it seems like something the 2D physics engine should be able to do.

@UberGoober smart answer. I’ll try it out…

Hmm…
Green edges are (supposed) outside edges—as you can see it thinks that some outer edges belong to the inside. Another problem is that it takes O(e^2) time, where e is the number of edges. I’ll post the code so you can understand.

EDIT: fixed it. Still posting the code…

Problem #2 - seperating distinct polygons

I don’t think physics can take all the outer vertices and perform collisions, can it? The encircled portion shows what I mean. I want to separate sections that are not connected to one another. The obvious, but worst solution would be the brute force method: iterating over every line and checking if it is connected to something, but a cleaner way would be faster.

What is going to be colliding with these walls? Just curious, I don’t think it matters rrgarding your question.

As far as I know, the 2D Physics engine’s collision detection has no limit on vertices it can handle.

There’s that Codea sample project that generates colliding polygons every time you tap the screen–tap a bunch of times and you quickly wind up with way more vertices than you have in the perimeters shown here, and way more collidable object to boot.

@em2 Since you can identify the outer edges, you can use the physics polygon for collision. In your above example, you would have only 8 physics polygons to check for collision which shouldn’t cause any slowdowns.

@UberGoober yes, but just passing all the outlined vertices to `physics.body` won’t work. Dozens of different `STATIC` polygons are also slow. Currently, this is just an experiment, but I plan to use this for a 2d top down space map generator.

Won’t work? What happens? You don’t need to go into the nitty gritty if you don’t want to, I can’t be sure I’ll follow it anyway.

Are you actually experiencing this slowdown or are you assuming it? @dave1707 doesn’t seem to think it would be a problem.

I’ve written an app using the same physics engine (not in Codea, in SpritrKit) and it’s a fast-paced action game that has to detect collisions between 3 or 4 moving bodies and hundreds of individual stationary bodies. I see no slowdown at all, though I am cheating a little by only using the physics engine to detect the collisions, not to handle them. I handle them myself in code. That might be an option for you too.

Wait–are you assembling the outlines into big many-sided polygons or leaving them as individual vertices?

@dave1707 I missed your post. Possibly a bug in the forums? That is exactly what I want to achieve, but currently all that is known is where the edges are, not what polygon they belong to. That’s the “Problem 2” I tried to articulate above.

@UberGoober I see. In retrospect, the slowdowns in my initial tests were caused by drawing too many lines—I will replace them with a mesh. Since multiple static bodies don’t affect performance, the edge detection now only needs to be purely aesthetic. It would be preferable to just use individual vertices and line segments, but then I would have to deal with tunneling and slow continuous physics.

Lines will be drawn with mesh, and the original polygons will serve as static physics bodies for collision detection. No more worries about separating large polygons.

When you’re talking meshes I get lost in the weeds, but as far as knowing which polygon edges belong to, that’s exactly what the collision detection does. It passes you references to the two bodies that collided along with various data about that collision. That’s why I asked if you were assembling the vertices into big polygons–if you do that then it’s trivial to determine which one has been hit.

But like I said meshes are outside my understanding, so I grant that you may be talking about a better and easier approach.

@dave1707 indeed, it does take quite a while, almost 30 seconds on my iPad air 2 with 256 polygons.

Success!
@UberGoober meshes are faster than drawing many lines. I won’t be assembling the vertices, just colliding with the original, small tiles.
https://pastebin.com/Tt33pQqk

@em2 Looks good. It takes awhile to create it if there’s a lot of polygons and sometimes it crashes.

This version uses coroutines, a loading screen, and mesh. If you look closely, you’ll see that the mesh has tiny cracks in it. It looks awful.
https://pastebin.com/CikxvzSV

New version with little spaceship. Move the slider to change direction.
Gist Link (The project is gettting long, so I’ve put it on an installer)

Love that smoke trail.

Need more space to zoom around!

For a simple embellishment you could draw one of the spaceships in the asset packs on top of your little triangle dude.

A nice mod to the slider control might be to make it control left and right rotation instead of absolute positions. Make the slider go from -1 to 1, and have its starting value be 0, and you could use it more like a steering wheel…

Cool to see this progression!