12
\$\begingroup\$

The classic Chutes and Ladders game has a grid of 100 squares with various "chutes" (which send a player backwards) and "ladders" (which promote a player forward). The goal here was to randomly create a series of these chutes and ladders such that the net effect is that there are 50 more squares that may be lost than gained. I had considered finishing this off to a complete and playable game, but it doesn't seem to be a sufficiently interesting game to warrant the small additional effort.

Here's a screenshot of the result:

Chutes and Ladders screenshot[1]

distrib.cpp

#include <iostream>
#include <iomanip>
#include <vector>
#include <random>
#include <algorithm>
#include <array>
#include "distrib.h"

int makeDeltaValues(std::vector<int> &chutes, std::vector<int> &ladders, int target) 
{
    std::random_device rd;
    std::mt19937 gen(rd());
    std::weibull_distribution<> d{2.0, 20};
    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;}};
    int iterations = 0;
    do {
        ++iterations;
        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()));
    return iterations;
}

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(std::pair<int, int>{0, item});
    }
    for (auto item : chutes) {
        links.emplace_back(std::pair<int, int>{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;
}

distrib.h

#ifndef DISTRIB_H
#define DISTRIB_H
#include <iostream>
#include <vector>
#include <utility>

constexpr int boxcount{100};

/*
 * populate the chutes and ladders vectors (which should already have nonzero size)
 * with random values such that sum(chutes)-sum(ladders) == target.
 */
int makeDeltaValues(std::vector<int> &chutes, std::vector<int> &ladders, int target=50);

/*
 * 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();

#endif // DISTRIB_H

main.cpp

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <utility>
#include <cmath>
#include <SFML/Graphics.hpp>
#include "distrib.h"

# define M_PIl          3.141592653589793238462643383279502884L /* pi */

/*
 * 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::sqrt(c.x * c.x + c.y * c.y);
        arrow[0].position = sf::Vector2f(2*width, 0);
        arrow[1].position = sf::Vector2f(1*width, 0);
        arrow[2].position = sf::Vector2f(2*width, len - 2*width);
        arrow[3].position = sf::Vector2f(1*width, len - 2*width);
        arrow[4].position = sf::Vector2f(1.5*width, len);  // arrow point
        arrow[5].position = sf::Vector2f(0*width, len - 2*width);
        arrow[6].position = sf::Vector2f(3*width, len - 2*width);
        for (int i = 0; i < 7; ++i) {
            arrow[i].color = color;
        }
        setOrigin(sf::Vector2f(1.5*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();
        states.texture = NULL;
        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) {
        m_down = down;
        m_across = across;
        m_tileSize = sf::Vector2f(width/m_across, height/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 = sf::Vector2f(i * m_tileSize.x, 0);
            line[1].position = sf::Vector2f(i * m_tileSize.x, m_down * m_tileSize.y);
            line[0].color = sf::Color::Black;
            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 = sf::Vector2f(0, i * m_tileSize.y);
            line[1].position = sf::Vector2f(m_across * m_tileSize.x, i * m_tileSize.y);
            line[0].color = sf::Color::Black;
            line[1].color = sf::Color::Black;
        }
        // load a font
        m_font.loadFromFile("times.ttf");
        // 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
            sf::Text t = sf::Text(std::to_string(i), m_font);
            t.setCharacterSize(20);
            sf::FloatRect box = t.getLocalBounds();
            t.setPosition(col * m_tileSize.x + (m_tileSize.x - box.width)/2, row * m_tileSize.y);
            t.setColor(sf::Color::Blue);
            m_text.emplace_back(t);
        }
        for (unsigned i=0; i < transits.size(); ++i) {
            m_line.push_back(makeLine(transits[i].first, transits[i].second));
        }
        return true;
    }
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");
    sf::Event event;
    sf::View view;
    view.reset(sf::FloatRect(-20, -20, 600, 600));
    window.setView(view);

    Grid grid;
    if (!grid.load(400, 400, 10, 10, createLinks()))
        return -1;

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

        window.clear(sf::Color::White);
        window.draw(grid);
        window.display();
    }
}
\$\endgroup\$
  • \$\begingroup\$ Awesome, I like the image rather than just coordinate pairs! \$\endgroup\$ – Raystafarian Jun 22 '16 at 17:27
5
\$\begingroup\$
  1. I'm a little bothered by the piecemeal conversion from rectangular to polar coordinates. I think I'd rather wrap them up into a little neater package:

    std::pair<float, float> r2p(float cx, float cy) {
        auto len = std::sqrt(cx * cx + cy * cy);
        auto angle = atan2(cy, cx)*180/M_PIl - 90;
        return {len, angle};
    }
    

    It's open to some argument that it would be better still to define a polar_coordinate class (and probably a rectangular coordinate class as well), with each providing a constructor from the other (or a conversion operator to the other) so the compiler can help a little bit in enforcing type safety.

  2. You've used copy initialization syntax a few places for no particularly good reason I can see. For example:

    sf::Text t = sf::Text(std::to_string(i), m_font);
    

    I'd generally prefer something like:

    sf::Text t {std::to_string(i), m_font};
    

    Depending on the overloaded ctors sf::Text provides, this can change the meaning though. If you run into that, I'd use auto instead:

    auto t = sf::Text(std::to_string(i), m_font);
    
  3. You've defined Grid::indexOf, and Grid::centerOf, but in Grid::load, you duplicate the logic of indexOf exactly, and could probably use centerOf to simplify the logic for setting the text location as well (although this isn't quite as precise of duplication).

\$\endgroup\$

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.