Mark Sachs (ksleet) wrote,
Mark Sachs

  • Mood:
  • Music:

I was assured there would be no math!

Soooo, I haven't said much about the vector engine the last few days because I had to go into the guts of the thing and rethink how I was modeling the map.

This is more or less where we left off, with the ability to construct a map of rectangular rooms and branching, bending corridors. I decided I wanted to allow corridors to connect to rooms they happened to newly overlap. In order to do this, I'd have to detect the overlap, then clip the corridor against the room it touched. It turned out that this got very, very complicated, and had a lot of special cases. This is because internally, I was special-casing the four directions that rooms could extend in (+X, -X, +Y, -Y). This led to a nightmare of intricate switch statements, code duplication, and hard-to-trace faults. Clearly I Was Doing It Wrong.

I reconsidered for a while. Now obviously, the Right Way -- and I'd known this from the start -- is to represent rooms as arbitrary convex polygons, and when I want to extend a corridor, pick a side, compute the normal to extend it along, and boom, it's done. But I didn't want to do it that way because... well, I thought about it, and realized I was just being a big baby and didn't want to deal with polygons because polygons are complicated, waaah! How could I calculate where two polygons overlap, to join rooms and corridors? Worse yet, a corridor can bend all over the place, making it a complicated concave polygon. How do I represent that at all...?

I quite suddenly realized that these are the same problem. A concave polygon can be represented as a group of adjoining convex polygons, so if you figure out how to slice up convex polygons so they join together smoothly you can make the concave polygon. It is in fact exactly the same problem as trying to clip convex polygons against each other to make rooms and corridors join. Solving one problem solves the other. Now, we all know that breaking down a concave polygon into convex polygons is of course super-hard -- but how about building up a concave polygon from convex polygons I already have? Which just so happens to be the situation I'm in?

It turns out this is easy, and I'm rather proud for working it out all by myself. Start with one convex polygon. Take another one that's overlapping. Find the two points where the sides of the polygons intersect: there will always be just two, except for certain degenerate cases I'm handwaving away right now. This forms a new edge, which I'm calling the internal edge. Clip away the parts of the two polygons that extend across the edge, and now you have two modified polygons that join up perfectly along the internal edge to make a single concave polygon. Done!

It's more complicated than that, of course -- I had to take a few swings at the clipping logic before I came up with an order of operations that worked, and there was a lot of mathematical infrastructure that was missing from the engine. Nonetheless, I got it working, at least for my test case:

The two polygons have been intersected and clipped. The yellow line represents the internal edge I mentioned above.

As one might imagine this opens the door to an awful lot of interesting stuff... but I'll save it for a time when I've actually, well, done a little more of it.
Tags: nagawrimo
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.