Author: Travis Adsitt

Has my ego inflated in the last couple of weeks from programming in C++? Maybe, maybe not… All I know is that C++ is leagues faster than Python. Don’t believe me? Well, I am glad you are here! This week, we will be converting a Python program I wrote and documented here to its C++ counterpart.

At the end of this post, I hope to have concrete evidence of just how much faster C++ can be! Let’s dive in!

Measurement

First, we must take measurements on the portion of code we will be converting. If you haven’t read the original article here, I recommend you give it a peek. Here’s a snippet of how the original program generates mazes:

for i in range(args.num_to_generate):
    maze = WordMaze(args.word, args.grid_width, args.grid_height, args.pixel_width, args.pixel_height, args=args)
    maze.save_image(args.filename.split(".")[0] + "_" + str(i) + ".png")

We will be timing the maze generation and the image storage. To do this, we will utilize the following generator function for a set of input values:

def test_maze_inputs():
    words = ["Hello", "Random", "Testing", "Maze", "Generation"]
    grid_widths = [(20, 20), (40, 40), (80, 80), (160, 160)]

    for word in words:
        for width in grid_widths:
            yield argparse.Namespace(word=word, grid_width=width[0], grid_height=width[1], pixel_width=20, pixel_height=20)

We will be building mazes at the sizes of 20 x 20, 40 x 40, 80 x 80, and 160 x 160. These will be pixel sizes 400 x 400, 800 x 800, 1600 x 1600, and 3200 x 3200, respectively. The values chosen are arbitrary and all runs will be done on the same system.

Below is the timing test run code:

if __name__ == "__main__":
    # args, _ = parseargs()
    maze_generation_times = []
    image_save_times = []
    for test_input in test_maze_inputs():
        print(f"Testing Inputs: {test_input}")

        # Time Maze Generation
        start_time = time.perf_counter()
        maze = WordMaze(test_input.word, test_input.grid_width, test_input.grid_height, test_input.pixel_width, test_input.pixel_height)
        stop_time = time.perf_counter()
        total_time = stop_time - start_time
        maze_generation_times.append(total_time)

        # Time Maze Saving
        start_time = time.perf_counter()
        maze.save_image("maze.png")
        stop_time = time.perf_counter()
        total_time = stop_time - start_time
        image_save_times.append(total_time)
    # Print our table
    print("CSV:\n")
    header_printed = False
    
    for ti, test_input in enumerate(test_maze_inputs()):
        if not header_printed:
            for key in test_input.__dict__:
                print(key, end=",")
            print("Generation Time,Image Save Time,")
            header_printed = True
        
        for key in test_input.__dict__:
            print(test_input.__dict__[key], end=",")
        print(f"{maze_generation_times[ti]},{image_save_times[ti]},")

It will print out a nice CSV-style output for us to curate in Excel:

All right, we have our times to beat! Let’s convert some code!

C++ FTW… Maybe

To make this as fair as possible, I will do my best not to adjust the design of the program. I will simply translate it to C++ and run the same benchmarks.

One does not simply translate from Python to C++

Basically Anyone (except Travis)

Here I am a week later, literally. I have a functioning C++ program that generates the same output you would expect to see from the Python script in my previous post.

Oh boy, it even looks like it has a memory leak! Let’s go ahead and try to fix that up really quickly….

DONE! My brain is fried. I am going to simply let the results speak for themselves:

Python vs C++ Results

Python and C++ clearly diverge even at the first data point. On the bar graph, you can see the stark differences by maze size. For the largest maze size in this test (3200 x 3200 pixels), Python was about 4 times slower than C++!

On the scatter plot, you can see the time differences plotted out by actual square pixels. The linear fits of the data are pretty good, with R-squared values slightly exceeding 0.99. The linear fit equations could be useful for estimating time values for other maze sizes that we did not test.

The desired maze size (in square pixels) would be substituted for the ‘x,’ and solving for the ‘y’ would result in a time estimate. You can see that the slope (time divided by square pixels) of the Python algorithm is steeper than C++, further showcasing C++’s efficiency.

Conclusion

This was an excellent learning experience for me. In the process of rewriting my code, I got a close-up look at various inconsistencies and poor algorithmic choices that came along with my first implementation.

I have yet to fix these things, as it was important to me to have an apples-to-apples comparison between the two codebases. If you compare the GitHub repositories (Python vs C++), you will find there are very few design differences between the two.

Thank you for reading this week!

-Travis

This week, I am exploring a simple application that simulates tree propagation using SFML and C++. Join me as I build a 2-D forest with a keyboard!

This is the first of a series of posts I am releasing about software simulations in C++ using SFML. My work on simulations is an ever-growing exploration and has only recently taken a turn into the land of C++.

The Basics (Dynamic SFML graphics)

I have a background in C, but up until now, my acumen in C’s object-oriented relative (C++) has been limited to “Hello World.” So, I was quite nervous to translate my usual techniques for Object Oriented Programming (OOP) in Python to my new adventures in C++.

I started off by setting up my environment to be able to compile and link against the SFML library (you can read more details here).

With the environment ready, I worked on drawing to the screen. I created a program which randomly spawns yellow dots (“people”) with an area that slowly spawns green dots (“forest”):

This is a pretty basic start, but I felt good about being able to draw something. Each of these dots represents an object, and some objects inherit from a parent. Thus, I developed basic building blocks for a more complex simulation.

Problem

There was only one problem with the above simulation: Let’s just say…it really leaves a lot to the imagination. Actually, maybe that’s what this should be about…exercising your imagination. It sure would make a programmer’s job a lot easier…

Grids… Structure… Yeah!

I created a simple 2-D array of pointers of type ‘GridCell’. To make things easy, any object that exists in the grid must inherit from it.

Simulation Objects (with Delegated SFML Drawing)

There are three simulation objects:

• SeedCell (Introduced in tag v0.2)
• LeafCell (Introduced in tag v0.1)
• TrunkCell (Introduced in tag v0.1)

Progressive Overview

Everything starts from a seed. The SeedCell has a chance of “becoming” a TrunkCell. A TrunkCell, once fully matured, will grow LeafCells in its four compass directions.

I decided to allow the LeafCells to propagate a little further than a single grid block away from the TrunkCell before dropping more SeedCells.

GridCell

Remember, everything has to inherit from the GridCell class if it wants to exist in our grid.

class GridCell : public Cell{
    protected:
    sf::RectangleShape shape;
    uint32_t tick_born;
    int grid_height, grid_width;
    public:
    GridCell(sf::Vector2f pos, sf::RenderWindow *window, uint32_t tick_born): Cell(pos, window), grid_height(config::grid_edge_size), grid_width(config::grid_edge_size), tick_born(tick_born){}

    sf::Vector2f get_pos_in_direction(Directions in_direction){
        if (in_direction == all){
            return sf::Vector2f(-1,-1);
        }

        if (in_direction == north){
            return sf::Vector2f(pos.x, (pos.y > 0) ? (pos.y - 1) : grid_height - 1);
        }
        if (in_direction == east){
            return sf::Vector2f((pos.x + 1) < grid_width ? pos.x + 1 : 0, pos.y);
        }
        if (in_direction == south){
            return sf::Vector2f(pos.x, (pos.y + 1) < grid_height ? pos.y + 1: 0);
        }
        if (in_direction == west){
            return sf::Vector2f((pos.x > 0) ? (pos.x - 1) : grid_width - 1, pos.y);
        }
    }
    virtual void step(GridCell **N, GridCell **E, GridCell **S, GridCell **W, int current_tick){
        // Take actions here
    }
    virtual void draw(){
        // Draw Here
    }
};

You might notice this also inherits from a Cell class. This simple class is actually an artifact of an earlier experiment. Eventually, I will find time to join these objects together again, but at the time of this publishing they are still [sadly] separate.

In the chunk of code above, notice the step function’s signature. When the world ticks forward in time, it hands all game objects a pointer to the pointer of the object that may (or may not) exist in all of its immediate compass neighbors.

As we will see in the TrunkCell, this is useful for the technique I used to propagate objects on the grid.

SeedCell

This simple little object brings so much more if it is chosen to sprout! Below is all it takes to be a ‘seed’ in the simulation.

class SeedCell: public GridCell{
    public:
    using GridCell::GridCell;
};

This is the only object that is manipulated by the grid. It must be controlled this way because of the inheritance structure.

TrunkCell

If the SeedCell ‘transforms,’ it becomes a TrunkCell which matures over time. By ‘transform,’ I mean that if the grid randomly generates a boolean value of True, then the program deletes the ‘seed’ object and replaces it with a TrunkCell.

class TrunkCell: public GridCell{
    float density = 0;
    float current_maturity = 0;
    float total_time_alive = 0;
    int maturity_time = 10;
    int current_season = 0;
    int past_season = 0;
    int season_allowable_new_growth = 1;
    public:
    using GridCell::GridCell;
    void draw(){
        float x_offset = (area.x - (area.x * density)) / 2;
        float y_offset = (area.y - (area.y * density)) / 2;


        shape.setPosition(sf::Vector2f((pos.x * area.x) + x_offset, (pos.y * area.y) + y_offset));
        shape.setSize(area * density);
        shape.setFillColor(sf::Color(0x96, 0x4B, 0));
        window->draw(shape);
    }
    void step(GridCell **N, GridCell **E, GridCell **S, GridCell **W, int current_tick){
        if (density >= 1){
            if(!*N){
                *N = new LeafCell(get_pos_in_direction(north), window, 3, &season_allowable_new_growth, current_tick);
            }
            if(!*E){
                *E = new LeafCell(get_pos_in_direction(east), window, 3, &season_allowable_new_growth, current_tick);
            }
            if(!*S){
                *S = new LeafCell(get_pos_in_direction(south), window, 3, &season_allowable_new_growth, current_tick);
            }
            if(!*W){
                *W = new LeafCell(get_pos_in_direction(west), window, 3, &season_allowable_new_growth, current_tick);
            }
        }
        if (density < 1){
            density = ((float) current_tick - tick_born) / maturity_time;
        }else{
            density = 1;
        }

        current_season = (current_tick - tick_born) / maturity_time;

        if (current_season != past_season){
            season_allowable_new_growth = 1;
            past_season = current_season;
        }
    }
};

When the TrunkCell reaches full maturity, it spawns LeafCells at each compass direction around itself, if the positions in the grid are empty. To do this, it sets the pointer reference to a new object that is spawned into the grid. This only works because of the assumption that the propagation is happening in a single execution thread.

LeafCell

The LeafCells have a propagation-level counter and an integer pointer assigned by the originating TrunkCell. The propagation-level counter tracks the distance from the originating TrunkCell.

class LeafCell: public GridCell{
    float density = 0;

    int current_life_cycle = 0;

    int total_life_cycle = 10;
    int ripe_time = 2;
    int old_time = 6;
    int *new_growth_count;
    int propagation_level;

    sf::Color fill;
    sf::Color ripe;
    sf::Color old;
    public:
    LeafCell(sf::Vector2f pos, sf::RenderWindow *window, int propogation_level, int *new_growth_count, uint32_t tick_born) : GridCell(pos, window, tick_born), ripe(0, 255, 0), old(218, 165, 32), propagation_level(propogation_level), new_growth_count(new_growth_count){
        shape.setPosition(sf::Vector2f(pos.x * area.x, pos.y * area.y));
        shape.setSize(area);
    }
    void draw(){
        shape.setFillColor(fill);
        window->draw(shape);
    }
    void propagate_leaves(GridCell **N, GridCell **E, GridCell **S, GridCell **W, int current_tick){
        if((*N) && (*E) && (*S) && (*W)) return;
        if (propagation_level <= 0) return;

        bool prop_n = get_rand_bool(0.25);
        bool prop_e = get_rand_bool(0.25);
        bool prop_s = get_rand_bool(0.25);
        bool prop_w = get_rand_bool(0.25);

        if(!(*N) && *new_growth_count > 0 && prop_n) {
            *N = new LeafCell(get_pos_in_direction(north), window, propagation_level - 1, new_growth_count, current_tick);
            (*new_growth_count)--;
        }
        if(!(*E) && *new_growth_count > 0 && prop_e) {
            *E = new LeafCell(get_pos_in_direction(east), window, propagation_level - 1, new_growth_count, current_tick);
            (*new_growth_count)--;
        }
        if(!(*S) && *new_growth_count > 0 && prop_s){
            *S = new LeafCell(get_pos_in_direction(south), window, propagation_level - 1, new_growth_count, current_tick);
            (*new_growth_count)--;
        } 
        if(!(*W) && *new_growth_count > 0 && prop_w) {
            *W = new LeafCell(get_pos_in_direction(west), window, propagation_level - 1, new_growth_count, current_tick);
            (*new_growth_count)--;
        }
    }

    void propagate_seed(GridCell **N, GridCell **E, GridCell **S, GridCell **W, int current_tick){
        if((*N) && (*E) && (*S) && (*W)) return;
        if (propagation_level > 0) return;

        bool prop_n = get_rand_bool(0.01);
        bool prop_e = get_rand_bool(0.01);
        bool prop_s = get_rand_bool(0.01);
        bool prop_w = get_rand_bool(0.01);

        if(!(*N) && *new_growth_count > 0 && prop_n) {
            *N = new SeedCell(get_pos_in_direction(north), window, current_tick);
            (*new_growth_count)--;
        }
        if(!(*E) && *new_growth_count > 0 && prop_e) {
            *E = new SeedCell(get_pos_in_direction(north), window, current_tick);
            (*new_growth_count)--;
        }
        if(!(*S) && *new_growth_count > 0 && prop_s){
            *S = new SeedCell(get_pos_in_direction(north), window, current_tick);
            (*new_growth_count)--;
        } 
        if(!(*W) && *new_growth_count > 0 && prop_w) {
            *W = new SeedCell(get_pos_in_direction(north), window, current_tick);
            (*new_growth_count)--;
        }
    }

    void step(GridCell **N, GridCell **E, GridCell **S, GridCell **W, int current_tick){
        current_life_cycle = (current_tick - tick_born) % total_life_cycle;

        if(current_life_cycle <= ripe_time){
            if (current_life_cycle == 0 && (current_tick - tick_born) > 0){
                propagate_leaves(N, E, S, W, current_tick);
                propagate_seed(N, E, S, W, current_tick);
            }
            density = current_life_cycle / (float) ripe_time;
            fill = ripe;
        }else if (current_life_cycle > ripe_time && current_life_cycle <= old_time){
            int total_steps = old_time - ripe_time;
            int current_step = current_life_cycle - ripe_time;

            fill.r = ripe.r + (current_step * ((old.r - ripe.r) / total_steps));
            fill.g = ripe.g + (current_step * ((old.g - ripe.g) / total_steps));
            fill.b = ripe.b + (current_step * ((old.b - ripe.b) / total_steps));
        }else {
            fill = old;
            density = ((float) total_life_cycle - current_life_cycle) / (total_life_cycle - old_time);
        }
        
        if(density > 1){
            density = 1;
        }
        fill.a = 255 * density;
    }
};

As a secondary constraint, there is a ‘season_allowable_new_growth’ integer pointer to slow the propagation of LeafCells. This pointer is controlled by the TrunkCell to allow only a certain number of LeafCells to be spawned each season.

Once the propagation-level value reaches zero, a LeafCell will randomly drop SeedCells in the empty compass directions around itself.

Current State

You can check out the simulation’s behavior in its current form in the following YouTube demo:

The repository is currently at tag v0.3 at the time of publishing. If you want to recreate this for yourself, feel free to clone and check out that tag!

Thank you for reading 🙂 If you have any feedback or suggestions, please comment below!

Kivy plots for a simulation of populations, moving trends, and financial flows.

This week, I wanted to explore a non-zero-sum, agent-based simulation with political platforms and town populations. Given a set of towns with unique political platforms and individuals with political preferences who vote and can move, do we ever see a situation where all individuals are happy?

This is a highly simplistic model that does not conclusively show that free markets are non-zero-sum. Also, I’m definitely not a economics major!

Travis

Hurry! My Time is Limited!

If you are in a hurry, here’s the break-down:

• Metric choice matters when inspecting a market to find causation.
• Money is a ‘grease’ for personal-value-based choice.
• I still love simulations!!!

Metric Choice Matters in the Simulation

While building this simulation, I had the opportunity to install metric collection for a variety of components involved in town voting, market transactions, and population movement. This was required for some debugging to understand why things might not be going as expected. In some cases, it was because my intuition was off. Other times, it was a legitimate bug in my code.

There are definitely people left ‘unhappy’ in this model. Optimization occurs when everyone settles where they are happiest (or the least unhappy).

In this case, each person ends up in a place that for them isn’t worth leave, but they may still be unhappy with their town’s politics. In other words, if there were a town with politics which aligned better with their values, they would move but no such town exists.

Money is the Grease

For me, this project really solidified a different thought process regarding money. I have always seen money as something I must attain from a corporation in order to purchase goods for myself and my family. Building this model has shown me that there is another way of viewing money. Values come first and money is simply a grease to help you attain those values.

Watching this message unfold in the simulation, I realized that I sometimes lack true value. The space is filled with meaningless material purchases. Given a strong enough set of values, you can produce goods which others value. Then, you can’t help but attain money, which incidentally helps you pursue the principles you cherish most.

This thought introduces a question for me. What happens when your values tightly align with the values of the people around you? What can be achieved in such an environment?

I Still Love Writing Simulations

I will be honest…most of the programs I write are not contrived at the outset. In fact, I often almost quit working on them out of embarrassment that there isn’t a clear reason to build. The question, ‘What are you going to get from this?’ creeps in every time. However, after building it, I always have new ‘A-ha!’ moments that feel inherently meaningful. This time was no exception.

Enough of that though! Let’s dig into the specifics of this simulation!

Person/Town Breakdown

Person in the Simulation

Political Preference

In our model, a person has a political ‘base’ preference represented by a binary number. Each bit is a political issue that they either agree with (1) or don’t agree with (0). In addition to this ‘base’ preference, each person is assigned a random ‘Hardheadedness’ value. ‘Hardheadedness’ represents the total number of political preference bits that a person must match with a town’s political preference bits before they cross the happy-unhappy threshold. These ‘Hard Preference Bits’ are selected and set at random during initialization.

In the example above, you can see a person with a ‘Hardheadedness’ score of 3. You can also see their ‘Base Preference Bits,’ and the randomly-selected ‘Hard Preference Bits.’

Happiness Calculation

A person’s happiness is calculated by comparing the political climate (the town’s current political platform), bit by bit, to the person’s base political preference (‘Base Preference Bits’).

If one bit of the town’s political platform aligns with a person’s base preference bit, that 1:1 match adds one to their happiness score. On the other hand, if the town’s political platform bit does not align with the person’s base preference bit, it will only subtract from happiness if this same bit is True (1) for one of their ‘Hard Preference Bits.’ If ‘Hard Preference Bit’ is False (0) for this platform bit, the individual does not care about the mismatch. Let’s look at our example again:

Those ‘Hard Preference Bits’ are reflected here in the ‘Base Preference Bits’ as the underlined bits. The underlined bits are the only bits that can affect the happiness score in a negative way if they don’t align with their town’s political platform.

Happiness is capped at the total number of bits in the platform. In this case, a max happiness would be 8. If a person is basically happy, their happiness starts at the platform bit count. Otherwise, it starts at 0.

Deciding to move

A comparison between a person’s happiness and their randomly assigned happiness threshold decides whether they move or stay. The program randomly generates this value between 0.4 and 0.6. Next, the program compares a happiness decimal to this random threshold. The happiness decimal is the happiness score (a sum of 1-8, described in the “Happiness Calculation” section) divided by the number of total happiness bits (which is currently 8 total bits). This division produces a decimal between 0-1. If our happiness decimal is greater than the random threshold between 0.4 and 0.6, the person stays in their current town. Otherwise, if the decimal is less than the threshold, then the person wants to move.

Let’s say the person desires to move. Now they must visit all other towns to see which make them happiest. In some cases, even if they wish to move, they are still happiest where they are. So, they stay!

Remember, just because the person wants to move doesn’t mean they can. A secondary barrier becomes important: Money! There is a cost to moving. A person can only move if they can pay the price. We will explore this later in the explanation of the Town object.

Town in the Simulation

High-Level

A town is responsible for:

• Conducting votes on the current political platform.
• Tracking the population’s seniority hierarchy.
• Keeping the town bank, taxing, and paying people.

Conducting Votes

When the program conducts a vote, it iterates all persons in the towns population to add or subtract a value for each bit in the political platform (see the explanation of a person’s political preference in the sections entitled “Political Preference” and “Happiness Calculation”). The majority vote count result for a political platform bit (positive or negative) sets the same bit in the town’s platform to 0 or 1.

Tracking Seniority

At instantiation, the original persons in a population of a town receive randomly assigned seniority values between 0 and 1. This value represents the amount of time a person has spent in a specific town. For each step of the world, a person’s seniority factors into their wealth. As time passes, the seniority value increases slowly.

Keeping the bank

A town starts off with a specific amount of money in its bank. The bank slowly distributes money to its population based on seniority. A town also uses taxes and utility costs to keep money liquid and cyclic.

The program calculates taxes by multiplying a person’s annual income times the town’s income tax rate (a flat tax). It likewise calculates utility costs by finding the product of the average wealth of the town and a flat tax rate, then by multiplying this product by the individual’s seniority score. The idea is that if you lived here longer, you should pay more. Perhaps I should invert this idea…I’m still not quite sure (let me know your thoughts in the comments below if you think this is fair/unfair!).

The World

The ‘world’ is at the highest level. It is the overarching scheduler for towns and people. Its two chief responsibilities are:

• Managing the market for moving (including money transfers).
• Directing town voting cadence.

Managing a Market in the Simulation

A supply- and demand-model tracks the market for moving. The calculation for demand takes the number of people who want to move to the town and subtracts that value from the number of people who want to move out. The program divides this result by the total number of people moving to obtain a ‘cost adjustment’ value from a ‘base moving cost.’ This model considers supply infinite, as the towns do not have a population cap.

Voting Cadence

Every town votes at the same periodic time. The program checks this against each step of the world. The newly voted-in platform may cause some persons to move. This new paradigm may also make people who just moved into a new town unhappy.

Dynamic Interface Orientation

1. Plot 1 – Each town’s current population
2. Plot 2 – Total persons moved at each time step
3. Plot 3 – Total persons desiring to move
4. Plot 4 – Total wealth of each town
5. Plot 5 – Current cost to move to each town (Note: 50 = the ‘floor’ to this cost)

Observations

1. Here, there are two towns that are valued higher than the other towns at the start. In other words, more people want to move in than want to move out.
2. When people start moving, the populations of their former towns drop and the population of their new town increases.
3. Here, wealth is tightly coupled with incoming populations as they bring money with them.
4. Finally, there is a steady decline of people wanting to move when they can either afford to move or demand falls to a level where the cost is affordable.

Conclusion

It was super fun to write this simulation! This exercise developed into something more than just a technical exercise. I learned some economic and behavioral concepts regarding personal values and monetary impact.

I hope you enjoyed this week’s post. Thank you for reading it! Feel free to leave a comment correcting me. As mentioned earlier, I am not an economist :). If you want to see the code that drove this post, you can find it here on my GitHub (warning, it’s a bit messy).

If you’d like to check out some of my previous work on simulations, then please go to these posts:

• Making a Balanced Simulation
• Making a Balanced Simulation #2
• Kivy, One of the Best and Powerful GUI Creators

To check out the Python GUI platform I used for the plots in this article, please check out Kivy here.

Merry Christmas and Happy New Year!