Dragging Roads

I’m currently working on a game prototype (using C++ and SFML) that involves, among other things, dragging roads on a tilemap. I had a very specific behavior in mind for dragging, which took some work to get right. I’m going to document my results here.

# Plumbing

Before we can even start to worry about how the dragging works, we have to implement a dragging action. SFML exposes events for the mouse being clicked, released, and moved — these form the basis of our action.

//... Inside main loop

sf::Event event;
while (window.pollEvent(event))
{
    switch(event.type)
    {
    //... Other event handling
    case sf::Event::MouseButtonPressed:
        // Map global pixel location to a location relative to the window.
        sf::Vector2f clickPos = window.mapPixelToCoords(
            sf::Vector2i(event.mouseButton.x, event.mouseButton.y)
            m_map->getView());

        // Map this relative pixel location to a specfic tile.
        sf::Vector2i tilePos = m_map->mapPixelToTile(clickPos);

        // Tell the current tool where to start a drag.
        m_currentTool->startDrag(tilePos);
        break;
    case sf::Event::MouseButtonReleased:
        // End the active drag.
        m_currentTool->endDrag();
        break;
    case sf::Event::MouseMoved:
        sf::Vector2f mousePos = window.mapPixelToCoords(
            sf::Vector2i(event.mouseMove.x, event.mouseMove.y)
            m_map->getView());

        sf::Vector2i tilePos = m_map->mapPixelToTile(mousePos);

        // Update the current position of the drag.
        m_currentTool->updateDrag(tilePos);
        break;
    }
}

//...

This is all fairly straightforward: map the mouse coordinates to a particular tile and pass off to the Tool class. We now have the groundwork in place:

class Tool
{
private:
    bool isDragging;
    sf::Vector2i m_dragStart;
    sf::Vector2i m_dragCurrent;
    std::vector<sf::Vector2i> m_tiles;

    void updatePath();  // <-- The magic happens here.

public:
    void startDrag(const sf::Vector2i& pos)
    {
        if (m_isDragging) return;

        m_isDragging = true;
        m_tiles.push_back(pos);
        m_dragStart = pos;
        m_dragCurrent = pos;
    }
    void updateDrag(const sf::Vector2i& pos)
    {
        if (!m_isDragging) return;

        m_dragCurrent = pos;
        updatePath();
    }
    void endDrag()
    {
        if (!m_isDragging) return;
        m_tiles.clear();
    }
};

# The Algorithm

Our goal is to produce a list of tile coordinates that connect m_dragStart and m_dragCurrent. We want a linear path, with an optional dogleg, i.e.:

* * * * * *
          * *
            * *
              * *

Finally, if there is a diagonal segment, we want the tip to “rotate” as we extend the drag:

* * *
    * *
      *
    |
    v
* * *
    * *
      * *
    |
    v
* * *
    * *
      * *
        *

The first draft of the algorithm succeeds at everything except rotating:

void Tool::updatePath()
{
    // Clear output vector.
    m_tiles.clear();

    sf::Vector2i curr = m_dragStart;

     while (curr != m_dragCurrent) {
        m_tiles.push_back(curr);

        // Signed deltas
        const int dx = curr.x - m_dragCurr.x;
        const int dy = curr.y - m_dragCurr.y;

        if (abs(dx) > abs(dy)) {
            curr.x -= 1 * sign(dx);
        }
        else {
            curr.y -= 1 * sign(dy);
        }

    }

    m_tiles.push_back(curr);
}

(The sign function simply maps negative numbers to -1, positive numbers to 1, and 0 to 0.)

This is a very simple algorithm, but it doesn’t handle the diagonals exactly the way we’d like. The “rotation” of the diagonal end is determined by what branch is run when abs(dx) == abs(dy) — here, it’s the vertical shift, and as such the diagonal always ends with a vertical shift. This causes a “wiggling” motion when dragging diagonally, as the entire diagonal segment shifts back and forth to compensate. Not ideal.

The key is that as we extend either the vertical or horizontal delta for the entire path, we want the diagonal end to switch rotations. This leads to the following:

void Tool::updatePath()
{
    // Clear output vector.
    m_tiles.clear();

    sf::Vector2i curr = m_dragStart;

    // Manhattan distance from m_dragStart to m_dragCurrent.
    const int dist = abs(m_dragStart.y - m_dragCurrent.y) +
                     abs(m_dragStart.x - m_dragCurrent.x);
    const bool odd = dist % 2 != 0;

    while (curr != m_dragCurrent) {
        m_tiles.push_back(curr);

        // Signed deltas
        const int dx = curr.x - m_dragCurr.x;
        const int dy = curr.y - m_dragCurr.y;

        if (abs(dx) > abs(dy)) {
            curr.x -= sign(dx);
        }
        else if (abs(dx) < abs(dy)) {
            curr.y -= sign(dy);
        }
        else {
            if (odd) {
                curr.x -= sign(dx);
            }
            else {
                curr.y -= sign(dy);
            }
        }
    }

    m_tiles.push_back(curr);
}

In this modified version, we take the Manhattan distance between start and current tiles. Then, if this number is odd, we shift horizontally when the deltas are equivalent, and if it’s even we shift vertically. Which rotation is used for odd/even is arbitrary, it only matters that they are different. Now, as we drag along the diagonal, the rotation of the end tile changes as the mouse crosses the tile boundaries, preserving our previous path and eliminating the “wiggle”.

Advertisements