Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Generating polygonal maps

em2em2
edited September 2017 in General Posts: 194

image

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.

Comments

  • dave1707dave1707 Mod
    Posts: 8,464

    @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.
  • em2em2
    edited September 2017 Posts: 194

    @UberGoober smart answer. I'll try it out...

  • em2em2
    edited September 2017 Posts: 194

    168_FD4_A3_D2_AE_4500_8589_057480941_DC3
    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...

  • em2em2
    edited September 2017 Posts: 194
  • em2em2
    Posts: 194

    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.
  • dave1707dave1707 Mod
    Posts: 8,464

    @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.

  • em2em2
    edited September 2017 Posts: 194

    @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?
  • em2em2
    Posts: 194

    @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.
  • em2em2
    edited September 2017 Posts: 194

    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

  • dave1707dave1707 Mod
    edited September 2017 Posts: 8,464

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

  • em2em2
    Posts: 194

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

  • em2em2
    Posts: 194

    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

  • em2em2
    Posts: 194

    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!

  • em2em2
    edited September 2017 Posts: 194

    Getting kind of off-topic now... maybe I should change the title? Anyway, @UberGoober I had already made all the changes you suggested, before you posted them, but only now have I come around to posting the extremely messy code (run the installer again).
    I don't know if I should use sprites. Triangles are so minimalistic and sleek. I've tried making games with sprites on top of triangular bodies, but they just don't feel right.

  • em2em2
    Posts: 194

    There are some little goodies snuck into the new code (as a game). See if you can find them! Beware: on older devices, loading may take a very long time.

  • Wow it's cooler and cooler. To be fair you didn't make all the changes I suggested, because you didn't overlay a spaceship from the asset packs onto the triangle, but I think you probably made the right choice there!

    I love the Mario coin sound when the loader finishes. Has it always been there? This was the first time I heard it. It's great.

    And the little enemies are great too!

Sign In or Register to comment.