5
\$\begingroup\$

This is code from a grappling hook implementation. This is specifically code that, after a block is detected between two way points, it tries to find a path around.

This particular piece of the function considers the blocks that are in the way and decides which corners are appropriate to wrap around.

The point will always be on the edge. If it's not the very first (anchor) point, it will always be on a corner. So if the problem block is our block we just choose the two closest corners. Otherwise we need to look at this diagram.

Example

In the picture the block at 3 o'clock corresponds with case 1, at 1:30 is case 3, 12 o'clock is case 2, and 10:30 is case 4. 9 o'clock is a special case, when the point and the block share an orthogonal edge, it should use the far point instead of the near point.

Here's my code, problem is a Vec2I which is a std::array<int, 2> with several convenience functions. origin is a GrapplingHookPathPoint which is a struct defined as:

struct GrapplingHookPathPoint {
  GrapplingHookPathPoint() : anchorPoint(Vec2F::filled(nan<float>())), anchorBroken(), endpoint() {}
  GrapplingHookPathPoint(Vec2I anchoredBlock, Vec2F anchorPoint, bool anchorBroken, bool endpoint)
      : anchoredBlock(anchoredBlock), anchorPoint(anchorPoint), anchorBroken(anchorBroken), endpoint(endpoint) {}
  Vec2I anchoredBlock;
  Vec2F anchorPoint;
  bool anchorBroken;
  bool endpoint;
  bool operator==(GrapplingHookPathPoint const& rhs) const;
};

Vec2F is std::array<float, 2>, RectF is a Rectangle class

if (dest.endpoint && RectF::withSize(Vec2F(problem), {1, 1}).contains(dest.anchorPoint))
  continue;

if (origin.anchoredBlock == problem) {
  Logger::debug("door 0\n");
  if (origin.anchorPoint[0] == origin.anchoredBlock[0] &&
      origin.anchorPoint[1] == origin.anchoredBlock[1]) { // bottom - left corner
    Logger::debug("subdoor -3\n");
    corners.append({problem, Vec2F(problem) + Vec2F{1, 0}, false, false});
    corners.append({problem, Vec2F(problem) + Vec2F{0, 1}, false, false});

  } else if (origin.anchorPoint[0]     == origin.anchoredBlock[0] &&
             origin.anchorPoint[1] - 1 == origin.anchoredBlock[1]) { // top - left corner
    Logger::debug("subdoor -2\n");
    corners.append({problem, Vec2F(problem) + Vec2F{1, 1}, false, false});
    corners.append({problem, Vec2F(problem), false, false});

  } else if (origin.anchorPoint[0] - 1 == origin.anchoredBlock[0] &&
             origin.anchorPoint[1]     == origin.anchoredBlock[1]) { // bottom - right corner
    Logger::debug("subdoor -1\n");
    corners.append({problem, Vec2F(problem) + Vec2F{1, 1}, false, false});
    corners.append({problem, Vec2F(problem), false, false});

  } else if (origin.anchorPoint[0] - 1 == origin.anchoredBlock[0] &&
             origin.anchorPoint[1] - 1 == origin.anchoredBlock[1]) { // top - right corner
    Logger::debug("subdoor 0\n");
    corners.append({problem, Vec2F(problem) + Vec2F{1, 0}, false, false});
    corners.append({problem, Vec2F(problem) + Vec2F{0, 1}, false, false});

  } else if (origin.anchorPoint[0] == origin.anchoredBlock[0]) { // on the left
    Logger::debug("subdoor 1\n");
    corners.append({problem, Vec2F(problem), false, false});
    corners.append({problem, Vec2F(problem) + Vec2F{0, 1}, false, false});

  } else if (origin.anchorPoint[0] - 1 == origin.anchoredBlock[0]) { // on the right
    Logger::debug("subdoor 2\n");
    corners.append({problem, Vec2F(problem) + Vec2F{1, 0}, false, false});
    corners.append({problem, Vec2F(problem) + Vec2F{1, 1}, false, false});

  } else if (origin.anchorPoint[1] == origin.anchoredBlock[1]) { // on the bottom
    Logger::debug("subdoor 3\n");
    corners.append({problem, Vec2F(problem), false, false});
    corners.append({problem, Vec2F(problem) + Vec2F{1, 0}, false, false});

  } else if (origin.anchorPoint[1] - 1 == origin.anchoredBlock[1]) { // on the top
    Logger::debug("subdoor 4\n");
    corners.append({problem, Vec2F(problem) + Vec2F{0, 1}, false, false});
    corners.append({problem, Vec2F(problem) + Vec2F{1, 1}, false, false});

  } else {
    // we can't route around this block we're inside of it, this shouldn't happen!
    starAssert(false);
  }

  // Decide which two corners we're considering
  // two cases, either we consider two adjacent corners
  // or two opposite corners.
  // Adjacent corners happen when origin and the problem tile
  // are nearly orthagonal to each other.
  } else if (origin.anchoredBlock[0] == problem[0] &&
             origin.anchorPoint[0] != origin.anchoredBlock[0] &&
             origin.anchorPoint[0] != origin.anchoredBlock[0] + 1) {
    Logger::debug("door 1\n");
    corners = List<GrapplingHookPathPoint>(2, {problem, Vec2F(problem), false, false});

    if (origin.anchorPoint[1] > problem[1])
      corners[0].anchorPoint += Vec2F(0, 1);

    corners[1].anchorPoint = corners[0].anchorPoint + Vec2F(1, 0);

  } else if (origin.anchoredBlock[1] == problem[1] &&
             origin.anchorPoint[1] != origin.anchoredBlock[1] &&
             origin.anchorPoint[1] != origin.anchoredBlock[1] + 1) {
    Logger::debug("door 2\n");
    corners = List<GrapplingHookPathPoint>(2, {problem, Vec2F(problem), false, false});
    if (origin.anchorPoint[0] > problem[0])
      corners[0].anchorPoint += Vec2F(1, 0);

    corners[1].anchorPoint = corners[0].anchorPoint + Vec2F(0, 1);

  } else if (((origin.anchoredBlock[0] > problem[0]) ==
              (origin.anchoredBlock[1] > problem[1]) &&
               origin.anchoredBlock[0] != problem[0] &&
               origin.anchoredBlock[1] != problem[1]) ||
              ((origin.anchorPoint[0] == origin.anchoredBlock[0] + 1 &&
                origin.anchoredBlock[0] == problem[0] &&
                origin.anchoredBlock[1] > problem[1]) ||
               (origin.anchorPoint[1] == origin.anchoredBlock[1] + 1 &&
                origin.anchoredBlock[1] == problem[1] &&
                origin.anchoredBlock[0] > problem[0]))) { // Positive Slope
    Logger::debug("door 3\n");
    corners = {{problem, Vec2F(problem) + Vec2F(1, 0), false, false}, {problem, Vec2F(problem) + Vec2F(0, 1), false, false}};

  } else {
    Logger::debug("door 4\n");
    corners = {{problem, Vec2F(problem), false, false}, {problem, Vec2F(problem) + Vec2F(1, 1), false, false}};

  }

This seems needlessly complex, especially the condition for "door 3" and some of the repeated logic.

Can you help me pare this down into something easier to understand and more readable?

\$\endgroup\$
3
  • \$\begingroup\$ I must confess that I don't really understand the problem nor the drawing but my feeling is that you might want to have a look at en.wikipedia.org/wiki/Convex_hull_algorithms. \$\endgroup\$ – SylvainD Sep 20 '13 at 19:47
  • \$\begingroup\$ The current question title, which states your concerns about the code, is too general to be useful here. Please edit to the site standard, which is for the title to simply state the task accomplished by the code. Please see How to get the best value out of Code Review: Asking Questions for guidance on writing good question titles. \$\endgroup\$ – Toby Speight Sep 11 '18 at 13:58
  • \$\begingroup\$ This question is older than the first revision of your guide, and has had no activity since being fully asked and fully answered 5 years ago. I'm not going to bother. You're welcome to perform the edit to your heart's content, or find four other people to close this question for being too unclear. Thanks. \$\endgroup\$ – OmnipotentEntity Sep 13 '18 at 3:54
3
\$\begingroup\$

I can't follow your code at all, mainly because I don't understand your terminology. What'a a GrapplingHookPathPoint? anchoredBlock? anchorPoint? problem?

Anyway, I'll describe how I would approach the problem instead.

Let's assume that all coordinates are expressed relative to the desired origin point. If not, make it so.

Then, for each square (which I'll call a Block), sort the four vertices according to their angle if they were expressed in polar coordinates. The first and last vertex after sorting are the ones you are looking for. One advantage of this solution over yours is that the squares do not have to be rotationally aligned with the x and y axes. The main benefit is that there are many fewer cases to be covered — the computer, rather than the programmer, does the hard work.

I'd like to avoid having to call atan2(), both because trigonometric functions are computationally intensive and because arctangents fail at 90°. Instead of sorting by the angle, I can just sort by the cosine of the angle, as long as all of the points are on the same side of the X-axis. (The cosine of the angle can be calculated using the rule AB = |A| |B| cos θ .) If a square straddles the X-axis, I can try using the Y-axis instead. If a square straddles both the X- and the Y-axis, then it must contain the origin, which is an error.

Tested using clang++ -std=c++11 -g -o cr31597 cr31597.cpp and on ideone.

#include <algorithm>    // for std::sort
#include <iostream>
#include <vector>
#include <math.h>       // for sqrt

//////////////////////////////////////////////////////////////////////

class Vec2F {
  public:
    float x, y;
    static const Vec2F ORIGIN, I, J;

    Vec2F() : x(0), y(0) {}
    Vec2F(float x, float y) : x(x), y(y) {}
    Vec2F(const Vec2F &other) : x(other.x), y(other.y) {}
    Vec2F &operator=(const Vec2F &other) {
        if (this != &other) {
            x = other.x;
            y = other.y;
        }
        return *this;
    }
    bool operator==(const Vec2F &other) const {
        return x == other.x && y == other.y;
    }
    const Vec2F operator+(const Vec2F &other) const {
        return Vec2F(x + other.x, y + other.y);
    }
    Vec2F operator-() const {
        return Vec2F(-x, -y);
    }
    Vec2F operator-(const Vec2F &other) const {
        return *this + -other;
    }
    Vec2F operator*(float scale) const {
        return Vec2F(scale * x, scale * y);
    }
    float cross(const Vec2F &other) const {
        return x * other.y - y * other.x;
    }
    float dot(const Vec2F &other) const {
        return x * other.x + y * other.y;
    }
    float magnitude() const {
        return sqrt(x * x + y * y);
    }
    float sinOfAngleRelTo(const Vec2F &ref) const {
        return ref.cross(*this) / ref.magnitude() / this->magnitude();
    }
    float cosOfAngleRelTo(const Vec2F &ref) const {
        return ref.dot(*this) / ref.magnitude() / this->magnitude();
    }
    friend std::ostream &operator<<(std::ostream &out, const Vec2F &v) {
        return out << '(' << v.x << ", " << v.y << ')';
    }
};

const Vec2F Vec2F::ORIGIN(0, 0),
            Vec2F::I(1, 0),
            Vec2F::J(0, 1);

//////////////////////////////////////////////////////////////////////

class Block {
  public:
    const std::vector<Vec2F> vertices;

    // Block is specified by its southwest corner
    Block(const Vec2F &sw) {
        Vec2F v[] = {
            sw + Vec2F::J,      sw + Vec2F(1, 1),
            sw,                 sw + Vec2F::I,
        };
        const_cast<std::vector<Vec2F>& >(vertices) =
            std::vector<Vec2F>(v, v + sizeof(v) / sizeof(Vec2F));
    }
    Block(const Block &other) : vertices(other.vertices) {}
    friend std::ostream &operator<<(std::ostream &out, const Block &b) {
        return out << "Block<" << b.vertices[2] << " - " << b.vertices[1]
                   << " centered at "
                   << b.vertices[2] + (b.vertices[1] - b.vertices[2]) * 0.5
                   << '>';
    }
  private:
    Block &operator=(const Block &other);
};

//////////////////////////////////////////////////////////////////////

// Comparator for Vec2F to be used to sort points by how much their angle
// deviates from a reference vector
class AxisComparator {
  public:
    static const AxisComparator HORIZ, VERT;
    const Vec2F ref;

    AxisComparator(const Vec2F &ref) : ref(ref) {}

    // Returns true if a should be ordered before b
    bool operator()(const Vec2F &a, const Vec2F &b) const {
        float cosAngleA = a.cosOfAngleRelTo(ref);
        float cosAngleB = b.cosOfAngleRelTo(ref);
        if (cosAngleA == cosAngleB) {
            // Same angle; the longer vector is considered more extreme.
            return cosAngleA < 0 ? a.magnitude() > b.magnitude()
                                 : a.magnitude() < b.magnitude();
        } else {
            return cosAngleA < cosAngleB;
        }
    }

    // Returns true if at least some pair of vectors are on opposite sides of
    // ref, or if at least one of them is aligned with ref
    bool straddles(const std::vector<Vec2F> &vv) const {
        int side = 0;
        for (auto i = vv.begin(); i != vv.end(); ++i) {
            float sinAngle = (*i).sinOfAngleRelTo(ref);
            if (sinAngle == 0.0) {                          // aligned with ref
                return true;
            } else if (side == 0) {                         // 1st time through
                side = (sinAngle < 0) ? -1 : +1;
            } else if (side == +1 && sinAngle < 0.0) {      // wrong side
                return true;
            } else if (side == -1 && sinAngle > 0.0) {      // wrong side
                return true;
            }
        }
        return false;
    }
};

const AxisComparator AxisComparator::HORIZ(Vec2F::I),
                     AxisComparator::VERT(Vec2F::J);

//////////////////////////////////////////////////////////////////////

class Grapple {
  public:
    const Block block;
  private:
    std::vector<Vec2F> vertices;
    const Vec2F *v1, *v2;

  public:
    Grapple(const Block &b) : block(b), vertices(b.vertices) {
        if (!AxisComparator::HORIZ.straddles(vertices)) {
            std::sort(vertices.begin(), vertices.end(), AxisComparator::HORIZ);
            v1 = &vertices.front();
            v2 = &vertices.back();
        } else if (!AxisComparator::VERT.straddles(vertices)) {
            std::sort(vertices.begin(), vertices.end(), AxisComparator::VERT);
            v1 = &vertices.front();
            v2 = &vertices.back();
            return;
        } else {
            v1 = v2 = NULL;
        }
    }
    bool possible() const {
        return v1 && v2;
    }
    const Vec2F &vertex1() const {
        return *v1;
    }
    const Vec2F &vertex2() const {
        return *v2;
    }
};

//////////////////////////////////////////////////////////////////////

int main() {
    Vec2F tests[] = {
        Vec2F(-3.0, -1.0),      // < 9 o'clock
        Vec2F(-3.5, +2.5),      // 10:30
        Vec2F(-0.5, +4.0),      // 12 o'clock
        Vec2F(+2.5, +2.5),      // 1:30
        Vec2F(+4.0, -0.5),      // 3 o'clock
        Vec2F(-0.5, -0.5),      // centered at origin
        Vec2F(+0.0, -0.0),      // corner at origin
    };
    for (int i = 0; i < sizeof(tests) / sizeof(tests[0]); ++i) {
        Block b(tests[i]);
        Grapple g(b);
        if (g.possible()) {
            std::cout << "Grappling vertices for " << g.block << ": " << g.vertex1() << " and " << g.vertex2() << std::endl;
        } else {
            std::cout << g.block << " contains the origin!" << std::endl;
        }
    }
    return 0;
}
\$\endgroup\$
1
  • \$\begingroup\$ I eventually used something different. But this helped me substantially. Thank you very much. :) \$\endgroup\$ – OmnipotentEntity Sep 25 '13 at 7:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.