chutes_ladders.cpp

//http://codereview.stackexchange.com/questions/132587/sketch-of-chutes-and-ladders-game
#include <iostream>
#include <iomanip>
#include <vector>
#include <random>
#include <algorithm>
#include <array>
#include <vector>
#include <utility>
#include <cmath>
#include <sstream>
#include <SFML/Graphics.hpp>

# define M_PIl          3.141592653589793238462643383279502884L /* pi */

constexpr int boxcount{100};

template <typename T>
std::string to_string(const T& n)
{
    std::ostringstream oss ;
    oss << n ;
    return oss.str() ;
}

std::mt19937 gen(std::random_device{}());

/*
 * populate the chutes and ladders vectors (which should already have nonzero size)
 * with random values such that sum(chutes)-sum(ladders) == target.
 */
void makeDeltaValues(std::vector<int> &chutes, std::vector<int> &ladders, int target =50)
{
    std::weibull_distribution<> d{2.0, 20};
    auto badvalue = [](int a){ return (a<2) || (a>boxcount*2/3);};
    auto next([&](){ int m; do { m=std::round(d(gen))+2; } while(badvalue(m)); return m;});

    do
    {
        std::generate(ladders.begin(), ladders.end(), next);
        std::generate(chutes.begin(), chutes.end(), next);
        int lsum = std::accumulate(ladders.begin(), ladders.end(), 0);
        int csum = std::accumulate(chutes.begin(), chutes.end(), 0);
        // lsum must always be smaller or equal
        if (lsum > csum)
        {
            std::swap(csum, lsum);
            std::swap(chutes, ladders);
        }
        int delta = target - csum+lsum;
        // need to add delta distributed over chutes
        for (auto &v : chutes)
        {
            if (!badvalue(v+delta))
            {
                v += delta;
                delta = 0;
            }
        }
        // force remainder into first element (usually zero)
        chutes.front() += delta;
    } while (badvalue(chutes.front()));
}
/*
 * Creates a vector of start/end pairs within the range (1, boxcount-1] using
 * the makeDeltaValues() call above.  Note that for a boxcount of 100,
 * starting or ending values of 1 or of 100 are not allowed, but all values
 * between those are allowed.
 */
std::vector<std::pair<int, int>> createLinks()
{
    std::vector<int> ladders(9);
    std::vector<int> chutes(9);
    std::vector<std::pair<int, int>> links;
    links.reserve(ladders.size() + chutes.size());

    makeDeltaValues(chutes, ladders);

    for (auto item : ladders)
    {
        links.emplace_back(0, item);
    }
    for (auto item : chutes)
    {
        links.emplace_back(0, -item);
    }
    /* We now have the lengths of the various links, but
     * still need to translate those into starting and
     * ending locations.
     *
     * The method here is simple: we choose a random location
     * for the start and make sure that both start and end
     * are clear.  If they aren't we keep guessing random
     * locations until we find a clear pair.  This is guaranteed
     * to work eventually.
     */

    std::uniform_int_distribution<int> d{1, boxcount-1};
    std::array<bool, boxcount> used;
    int start;
    int end;
    for (auto &p : links)
    {
        do
        {
            start = d(gen);
            end = p.second + start;
        } while (end > boxcount-1 || end < 2 || used[start] || used[end]);
        p.first = start;
        p.second = end;
        used[start] = used[end] = true;
    }
    return links;
}

/*
 * A connector is an arrow shape that is drawn from point a to point b.
 */
class Connector : public sf::Drawable, public sf::Transformable
{
public:
    Connector(const sf::Vector2f &a, const sf::Vector2f &b, const sf::Vector2f &tileSize, const sf::Color &color)
        : arrow{sf::TrianglesStrip, 7}
    {
        auto c = b - a;
        auto width = std::min(tileSize.x, tileSize.y)/4;
        auto len = std::hypot(c.x, c.y);
        arrow[0].position = {2*width, 0};
        arrow[1].position = {1*width, 0};
        arrow[2].position = {2*width, len - 2*width};
        arrow[3].position = {1*width, len - 2*width};
        arrow[4].position = {1.5f*width, len};  // arrow point
        arrow[5].position = {0*width, len - 2*width};
        arrow[6].position = {3*width, len - 2*width};
        for (unsigned i = 0; i < arrow.getVertexCount(); ++i)
        {
            arrow[i].color = color;
        }
        setOrigin(1.5f*width, 0);
        setPosition(a);
        rotate(atan2f(c.y, c.x)*180/M_PIl - 90);
    }
private:
    virtual void draw(sf::RenderTarget& target, sf::RenderStates states) const
    {
        states.transform *= getTransform();
        target.draw(arrow, states);
    }
    sf::VertexArray arrow;
};

/*
 * About numbering: The numbering is a bit unusual for computer programs.
 * For example a 4 (width) x 3 (height) grid would be numbered like this:
 *
 *    9  10  11  12
 *    8   7   6   5
 *    1   2   3   4
 *
 * Overlaying row and column numbering onto this we have
 *
 *        0   1   2   3  <-- column
 *     +---------------
 *   0 |  9  10  11  12
 *   1 |  8   7   6   5
 *   2 |  1   2   3   4
 *   ^
 *   |
 *  row
 *
 * So to find the row coordinate from the square number, we can use this:
 *
 *    unsigned row = height - 1 - (square - 1) / width;
 *
 * Getting the column is a bit trickier since the direction of numbering alternates
 * for each row, but if we get the row first, it can be done like this:
 *
 *    unsigned col = (height - row) & 1 ? (square - 1) % width : width - 1 - (square - 1) % width;
 *
 */
class Grid : public sf::Drawable, public sf::Transformable
{
public:
    bool load(unsigned width, unsigned height, unsigned across, unsigned down, const std::vector<std::pair<int, int>> &transits)
    {
        if(transits.empty())
        {
            std::cout << "transits doesn't initilized\n";
            return false;
        }
        m_down = down;
        m_across = across;
        m_tileSize = {width/static_cast<float>(m_across), height/static_cast<float>(m_down)};
        m_vertices.setPrimitiveType(sf::Lines);
        m_vertices.resize((m_across + m_down + 2) * 2);
        // make vertical lines
        for (unsigned i = 0; i <= m_across; ++i)
        {
            sf::Vertex* line = &m_vertices[i * 2];
            line[0].position = {i * m_tileSize.x, 0};
            line[1].position = {i * m_tileSize.x, m_down * m_tileSize.y};
            line[0].color = line[1].color = sf::Color::Black;
        }
        // make horizontal lines
        for (unsigned i = 0; i <= m_down; ++i)
        {
            sf::Vertex* line = &m_vertices[(i + m_across + 1) * 2];
            line[0].position = {0, i * m_tileSize.y};
            line[1].position = {m_across * m_tileSize.x, i * m_tileSize.y};
            line[0].color = line[1].color = sf::Color::Black;
        }
        // load a font
        if(!m_font.loadFromFile("Media/arial.ttf"))
        {
            std::cout << "can't load font\n";
            return false;
        }
        // label each square
        for (unsigned i = 1; i < 1 + m_across * m_down; ++i)
        {
            unsigned row = m_down - 1 - (i - 1) / m_across;
            unsigned col = (m_down - row) & 1 ? (i - 1) % m_across : m_across - 1 - (i - 1) % m_across;
            // Create a text
            m_text.emplace_back(to_string(i), m_font, 20);
            auto& text = m_text.back();
            const auto box = text.getLocalBounds();
            const sf::Vector2f padding = {(m_tileSize.x - box.width) /3.f, (m_tileSize.y - box.height) / 3.f};
            text.setPosition(col * m_tileSize.x + padding.x, row * m_tileSize.y + padding.y);
            text.setColor(sf::Color::Blue);
        }
        const static auto comp = [this](const std::pair<int, int>& p){return makeLine(p.first, p.second);};
        m_line.reserve(std::distance(transits.begin(), transits.end()));
        std::transform(transits.begin(), transits.end(), std::back_inserter(m_line), comp);
        return !m_line.empty();
    }
private:
    sf::Vector2i indexOf(unsigned square) const
    {
        unsigned row = m_down - 1 - (square - 1) / m_across;
        unsigned col = (m_down - row) & 1 ? (square - 1) % m_across : m_across - 1 - (square - 1) % m_across;
        return sf::Vector2i(col, row);
    }
    sf::Vector2f centerOf(unsigned square) const
    {
        auto box = indexOf(square);
        return sf::Vector2f(m_tileSize.x * (0.5 + box.x), m_tileSize.y * (0.5 + box.y));
    }
    Connector makeLine(unsigned start, unsigned finish) const
    {
        const sf::Color &color = finish > start ? sf::Color::Green : sf::Color::Red;
        Connector rect(centerOf(start), centerOf(finish), m_tileSize, color);
        return rect;
    }

    virtual void draw(sf::RenderTarget& target, sf::RenderStates states) const
    {
        states.transform *= getTransform();
        target.draw(m_vertices, states);
        for (const auto &t : m_text)
        {
            target.draw(t, states);
        }
        for (const auto &va : m_line)
        {
            target.draw(va, states);
        }
    }
    unsigned m_down;
    unsigned m_across;
    sf::Vector2f m_tileSize;
    sf::VertexArray m_vertices;
    sf::Font m_font;
    std::vector<sf::Text> m_text;
    std::vector<Connector> m_line;
};


int main()
{
    sf::RenderWindow window(sf::VideoMode(600, 600), "Chutes and Ladders");

    const auto& defaultView = window.getDefaultView();
    const sf::Vector2f gridSize(400, 400);
    const sf::Vector2f blockSize(10, 10);
    sf::View view((defaultView.getCenter() + gridSize / 4.f ) / 2.f , defaultView.getSize());
    window.setView(view);

    Grid grid;
    if (!grid.load(gridSize.x, gridSize.y, blockSize.x, blockSize.y, createLinks()))
        return -1;

    while (window.isOpen())
    {
        sf::Event event;
        while (window.pollEvent(event))
        {
            if (event.type == sf::Event::Closed)
                window.close();
        }

        window.clear(sf::Color::White);
        window.draw(grid);
        window.display();
    }
}

chutes_ladders1.cpp

#include <iostream>
#include <iomanip>
#include <vector>
#include <random>
#include <algorithm>
#include <array>
#include <utility>
#include <string>
#include <cmath>
#include <SFML/Graphics.hpp>

# define M_PIl          3.141592653589793238462643383279502884L /* pi */

constexpr int boxcount{100};

template <typename T>
std::string to_string(const T& n)
{
    std::ostringstream oss ;
    oss << n ;
    return oss.str() ;
}

void makeDeltaValues(std::vector<int> &chutes, std::vector<int> &ladders)
{
    std::mt19937 gen(std::random_device{}());
    std::weibull_distribution<> d{4.0,20.0};
    auto badvalue = [](int a){ return (a < 2) || (a > boxcount * 2 / 3);};
    auto next([&](){ int m; do { m = d(gen) + 2; } while(badvalue(m)); return m;});
    std::generate(ladders.begin(), ladders.end(), next);
    std::generate(chutes.begin(), chutes.end(), next);
}

std::vector<std::pair<int, int>> createLinks()
{
    std::vector<int> ladders(9);
    std::vector<int> chutes(9);
    std::vector<std::pair<int, int>> links;
    links.reserve(ladders.size() + chutes.size());

    makeDeltaValues(chutes, ladders);
    for (auto item : ladders) {
        links.emplace_back(0, item);
    }
    for (auto item : chutes) {
        links.emplace_back(0, -item);
    }
    /* We now have the lengths of the various links, but
     * still need to translate those into starting and
     * ending locations.
     *
     * The method here is simple: we choose a random location
     * for the start and make sure that both start and end
     * are clear.  If they aren't we keep guessing random
     * locations until we find a clear pair.  This is guaranteed
     * to work eventually.
     */

    std::mt19937 gen(std::random_device{}());
    std::uniform_int_distribution<int> d{2, boxcount-1};
    std::array<bool, boxcount> used{};
    int start;
    int end;
    for (auto &p : links)
    {
        do
        {
            start = d(gen);
            end = p.second + start;
        } while (end > boxcount-1 || end < 2 || used[start] || used[end]);
        p.first = start;
        p.second = end;
        used[start] = used[end] = true;
    }
    return links;
}

/*
 * A connector is an arrow shape that is drawn from point a to point b.
 */
class Connector : public sf::Drawable, public sf::Transformable
{
public:
    Connector(const sf::Vector2f &a, const sf::Vector2f &b, const sf::Vector2f &tileSize, const sf::Color &color)
        : arrow{sf::TrianglesStrip, 7}
    {
        const float scale = 4.f;
        const auto c = b - a;
        const auto width = std::min(tileSize.x, tileSize.y)/scale;
        const auto len = std::hypot(c.x, c.y);
        arrow[0].position = {2*width, 0};
        arrow[1].position = {1*width, 0};
        arrow[2].position = {2*width, len - 2*width};
        arrow[3].position = {1*width, len - 2*width};
        arrow[4].position = {1.5f*width, len};  // arrow point
        arrow[5].position = {0*width, len - 2*width};
        arrow[6].position = {3*width, len - 2*width};
        for (unsigned i = 0; i < arrow.getVertexCount(); ++i)
        {
            arrow[i].color = color;
        }
        setOrigin(1.5f*width, 0);
        setPosition(a);
        rotate(atan2f(c.y, c.x)*180/M_PIl - 90);
    }
private:
    virtual void draw(sf::RenderTarget& target, sf::RenderStates states) const
    {
        states.transform *= getTransform();
        target.draw(arrow, states);
    }
    sf::VertexArray arrow;
};

/*
 * About numbering: The numbering is a bit unusual for computer programs.
 * For example a 4 (width) x 3 (height) grid would be numbered like this:
 *
 *    9  10  11  12
 *    8   7   6   5
 *    1   2   3   4
 *
 * Overlaying row and column numbering onto this we have
 *
 *        0   1   2   3  <-- column
 *     +---------------
 *   0 |  9  10  11  12
 *   1 |  8   7   6   5
 *   2 |  1   2   3   4
 *   ^
 *   |
 *  row
 *
 * So to find the row coordinate from the square number, we can use this:
 *
 *    unsigned row = height - 1 - (square - 1) / width;
 *
 * Getting the column is a bit trickier since the direction of numbering alternates
 * for each row, but if we get the row first, it can be done like this:
 *
 *    unsigned col = (height - row) & 1 ? (square - 1) % width : width - 1 - (square - 1) % width;
 *
 */
class Grid : public sf::Drawable, public sf::Transformable
{
public:
    bool load(unsigned width, unsigned height, unsigned across, unsigned down, const std::vector<std::pair<int, int>> &transits)
    {
        if(transits.empty())
        {
            std::cout << "transits doesn't initilized\n";
            return false;
        }
        m_down = down;
        m_across = across;
        m_tileSize = {width/static_cast<float>(m_across), height/static_cast<float>(m_down)};
        m_vertices.setPrimitiveType(sf::Lines);
        m_vertices.resize((m_across + m_down + 2) * 2);
        // make vertical lines
        for (unsigned i = 0; i <= m_across; ++i)
        {
            sf::Vertex* line = &m_vertices[i * 2];
            line[0].position = {i * m_tileSize.x, 0};
            line[1].position = {i * m_tileSize.x, m_down * m_tileSize.y};
            line[0].color = line[1].color = sf::Color::Black;
        }
        // make horizontal lines
        for (unsigned i = 0; i <= m_down; ++i)
        {
            sf::Vertex* line = &m_vertices[(i + m_across + 1) * 2];
            line[0].position = {0, i * m_tileSize.y};
            line[1].position = {m_across * m_tileSize.x, i * m_tileSize.y};
            line[0].color = line[1].color = sf::Color::Black;
        }
        // load a font
        if(!m_font.loadFromFile("Media/arial.ttf"))
        {
            std::cout << "can't load font\n";
            return false;
        }
        // label each square
        for (unsigned i = 1; i < 1 + m_across * m_down; ++i)
        {
            unsigned row = m_down - 1 - (i - 1) / m_across;
            unsigned col = (m_down - row) & 1 ? (i - 1) % m_across : m_across - 1 - (i - 1) % m_across;
            // Create a text
            m_text.emplace_back(to_string(i), m_font, 20);
            auto& text = m_text.back();
            const auto box = text.getLocalBounds();
            const sf::Vector2f padding = {(m_tileSize.x - box.width) /3.f, (m_tileSize.y - box.height) / 3.f};
            text.setPosition(col * m_tileSize.x + padding.x, row * m_tileSize.y + padding.y);
            text.setColor(sf::Color::Blue);
        }
        const auto comp = [this](const std::pair<int, int>& p){return makeLine(p.first, p.second);};
        m_line.reserve(std::distance(transits.begin(), transits.end()));
        std::transform(transits.begin(), transits.end(), std::back_inserter(m_line), comp);
        return !m_line.empty();
    }
private:
    sf::Vector2i indexOf(unsigned square) const {
        const auto row = m_down - 1 - (square - 1) / m_across;
        const auto col = (m_down - row) & 1 ? (square - 1) % m_across : m_across - 1 - (square - 1) % m_across;
        return sf::Vector2i(col, row);
    }
    sf::Vector2f centerOf(unsigned square) const {
        auto box = indexOf(square);
        return sf::Vector2f(m_tileSize.x * (0.5 + box.x), m_tileSize.y * (0.5 + box.y));
    }
    Connector makeLine(unsigned start, unsigned finish) const {
        const auto &color = finish > start ? sf::Color::Green : sf::Color::Red;
        return {centerOf(start), centerOf(finish), m_tileSize, color};
    }

    virtual void draw(sf::RenderTarget& target, sf::RenderStates states) const
    {
        states.transform *= getTransform();
        target.draw(m_vertices, states);
        for (const auto &t : m_text) {
            target.draw(t, states);
        }
        for (const auto &va : m_line) {
            target.draw(va, states);
        }
    }
    unsigned m_down;
    unsigned m_across;
    sf::Vector2f m_tileSize;
    sf::VertexArray m_vertices;
    sf::Font m_font;
    std::vector<sf::Text> m_text;
    std::vector<Connector> m_line;
};


int main()
{
    sf::RenderWindow window(sf::VideoMode(600, 600), "Chutes and Ladders");

    const auto& defaultView = window.getDefaultView();
    const sf::Vector2f gridSize(400, 400);
    const sf::Vector2f blockSize(10, 10);
    sf::View view((defaultView.getCenter() + gridSize / 4.f ) / 2.f , defaultView.getSize());
    window.setView(view);

    Grid grid;
    if (!grid.load(gridSize.x, gridSize.y, blockSize.x, blockSize.y, createLinks()))
        return -1;

    while (window.isOpen())
    {
        sf::Event event;
        while (window.pollEvent(event))
        {
            if (event.type == sf::Event::Closed)
                window.close();
        }

        window.clear(sf::Color::White);
        window.draw(grid);
        window.display();
    }
}