Category: Creation

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!

Simulation-building is something I seem to return to over and over again. I really enjoy learning something new each time I witness how small behaviors produce emergent behavior. Graphics are an accessible way to conceptualize the complex nature of multi-variable simulations. In this article, I lay the foundation for a project I hope will serve as the first chapter for a much larger vision.

Let’s explore Kivy, a powerful Python app development library.

Spoiler alert, this has, by far, been my best experience with a Graphical User Interface (GUI) library in Python. For me, it provides the best of two worlds for building a small application for a very basic simulation:

• Layout management and simple widgets for boiler-plate application objects, like buttons and text inputs.
• Custom drawing to the widgets’ underlying canvas, allowing for custom shapes and graphics.

A Very Basic Simulation

To get a better feel for this GUI framework, I decided to implement a primitive simulation to display on my application. The rules are simple: You have people and you have food! A person (red square) has a stomach and energy. The person’s stomach is filled with food, and energy is created from the food in their stomach. Food (green square) is a stationary source for a person to fill their stomach.

People move around in search for stationary food supplies, which expends energy and in turn uses the food in their stomach. If a person’s energy and stomach level reach 0, they are no longer considered alive (blue square).

Kivy

All right, with the simulation explained, it’s time to dig into Kivy! Kivy gives you so much to play with, yet has a refreshingly minimal barrier to entry. You can add buttons, text boxes, labels, and so much more! The best part is, through the Kv Language, your GUI can function on its own without Python code driving it. There is a helpful rundown on the Kv language on Kivy’s website here.

Kv Design Language

An example of this can be found in my ‘SimulationController’ widget, defined in SimulationGUI.kv below:

<SimulationController>
    BoxLayout:
        width: root.width
        height: root.height
        orientation: "horizontal"
        BoxLayout:
            orientation: "vertical"

            Slider:
                id: grid_height
                min: 25
                max: int(root.height)
                step: 1
                orientation: "horizontal"
            Label:
                text: str(grid_height.value) + " Map Height"
            
            Slider:
                id: grid_width
                min: 25
                max: int(root.width)
                step: 1
                orientation: "horizontal"
            Label:
                text: str(grid_width.value) + " Map Width"

You can see the ‘SimulationController,’ with two nested ‘BoxLayouts.’

<SimulationController>
    BoxLayout:
        width: root.width
        height: root.height
        orientation: "horizontal"
        BoxLayout:
            orientation: "vertical"

On the outermost ‘BoxLayout,’ I define its width and height to fill the space allotted to it by the element into which it is inserted. It took me a while to wrap my head around this as I attempted bigger layouts. Also note the orientation, which describes the direction things will be stacked.

Inside the innermost ‘BoxLayout,’ you can see Slider and Label pairs:

            Slider:
                id: grid_height
                min: 25
                max: int(root.height)
                step: 1
                orientation: "horizontal"
            Label:
                text: str(grid_height.value) + " Map Height"
            
            Slider:
                id: grid_width
                min: 25
                max: int(root.width)
                step: 1
                orientation: "horizontal"
            Label:
                text: str(grid_width.value) + " Map Width"

The Slider and Label are GUI Widgets built into the Kivy library. For the Slider, I set an ID value (basically a name referenced elsewhere in the code), along with a minimum and maximum value. In the Label Widget, you can see the GUI driving itself a bit – the text of the Label is set by the value currently selected by the Slider. This might be a commonplace functionality for a GUI framework that I just haven’t discovered before, but I really like it. Everything looks a lot cleaner when simple functionalities like this are independent from the Python code.

Invoking Python code directly from this language is pretty easy, too.

        Button:
            id: start_but
            on_press: app.run_sim(root.ids.num_people.value, root.ids.num_food.value, root.ids.grid_height.value, root.ids.grid_width.value)
            text: "Start Simulation"

In the above example, you can see a direct reference to ‘app’ and a call to ‘run_sim.’ This is defined on the Python side in my ‘SimulationGUIApp’ object which inherits from the ‘App’ object from the Kivy library.

The reference to ‘run_sim’ uses information from our widget and calls the function with the values collected as parameters. Awesome!

Kivy and Python

For me, it is often difficult to understand the interface between a design language and a program language (I’m looking at you, Javascript and CSS!). Let’s cover some basics.

Make Kv Definitions Python reference-able

First thing: How do you let Kivy know you are using a Kv file? There are a few ways to do this, but the one I chose was to name the .Kv file the same thing as my app’s object name (e.g., Kv filename is ‘SimulationGUI.kv’ and my Python object is ‘SimulationGUIApp’). An important detail here is to note that my Python object name ends with ‘App,’ while the filename doesn’t.

As for the Widgets defined in the .Kv file, all we have to do to use them on the Python side is create an empty class with the same name, as shown below:

.Kv Definition

<SimulationController>
    BoxLayout:
        width: root.width
        height: root.height
        orientation: "horizontal"

Python Definition

class SimulationController(Widget):
    pass

Even though the class is empty, the layout and widgets are defined in the .Kv file and will be shown when the app loads.

Once you do that, you can add Widgets to an App, creating your interface. In the example below, class ‘MainScreen’ inherits from ‘BoxLayout’ and then adds two Widgets to itself. One of the widgets is our familiar ‘SimulationController.’ Next, a ‘MainScreen’ object is instantiated and added to the app class (‘SimulationGUIApp’) in its build method.

class SimulationViewport(Widget):
    pass

class SimulationController(Widget):
    pass
        
class MainScreen(BoxLayout):
    def __init__(self, **kwargs):
        super(MainScreen, self).__init__(**kwargs)
        self.orientation = "vertical"
        self.size_hint = (1.,1.)

        self.sim_view = SimulationViewport()
        self.sim_cont = SimulationController()

        print(self.sim_cont.ids["grid_height"].value)
        
        self.add_widget(self.sim_view)
        self.add_widget(self.sim_cont)

class SimulationGUIApp(App):
    def build(self):
        main_screen = MainScreen()

        self.sim_view = main_screen.sim_view

        return main_screen

I decided to do it this way so I could access the canvas of our ‘SimulationViewport’ for drawing people and food. Also, in the above snippet, I left in a line of code to show how you can reference the values of the Widgets contained in our Kv-defined widgets using the ‘ids’ dictionary.

A Slightly More Advanced Kivy Concept

Until now, we have focused on the basic uses of Kivy. Now, let’s dive into how to draw on Widgets so that we can see our people as they wander around our world looking for food sources.

Assumptions Kill Me

One frustrating mistake I made was when I assumed that my drawing would be relative to the corner of my Widget. In a multi-widget layout, this would mean that the position of each drawing would be local to its own widget. In reality, the drawings are positioned within the global window’s coordinate grid, regardless of widget. With this mistaken assumption, I thought that the Widgets were overlapping one another. I likely developed this intuition from HTML and CSS, where the flow layout can cause elements to exist over one another.

Finally, I realized that drawing occurs from the window’s origin. This is really simple to do, but figuring it out was difficult. Below is the code snippet that saved me, particularly the self.sim_view.pos[0] and [1].

pos_screen_x = x * block_width + self.sim_view.pos[0]
pos_screen_y = y * block_height + self.sim_view.pos[1]

Rectangle(pos=(pos_screen_x, pos_screen_y), size=(block_width, block_height))

A ‘Rectangle’ is drawn at the x, y coordinates of our Person or Food with an offset of ‘self.sim_view.pos[0]’ and ‘[1],’ which gets it to our desired spot. The challenging part, however, is that you can draw outside the widget and it will still be rendered if it is within the window’s region.

So now we are drawing in the right place, but how do we select a color?

It’s like painting

Right above the lines of code where we select the x and y coordinates, there is an if-else block where the color palette is chosen for the upcoming ‘Rectangle’ draw. This color choice selects a value between 0 and 1 for each color (Red/Green/Blue). Here, we check if our object is ‘Food’ or ‘Person.’ Then, we select red or green of varying intensity, based on energy or food levels:

if isinstance(thing, Food):
    color_strength = thing.Amount / thing.MaxAmount
    color_strength = max([color_floor, color_strength])

    Color(0.,color_strength,0.)
elif isinstance(thing, Person):
    color_strength = thing.Energy / thing.EnergyMax
    color_strength = max(color_floor, color_strength)
    if thing.alive:
        Color(color_strength,0.,0.)
    else:
        Color(0.,0.,1.)

Conclusion

This has been a wonderful learning experience for me, and I hope by posting it here it can be useful to you, too! I look forward to possibly building out the simulation and controls with more options and depth.

If you are interested in further reading on my work in the simulation building realm, check out my wandering development post here, where I attempt to build a balanced simulation of a simple model for populations and reproduction.

There is also an excellent website with many models much better than mine on a website called NetLogo. I found this gem while doing research for my simulation (I also bought a book, Complex Adaptive Systems: An Introduction to Computational Models of Social Life, to add to my collection of unread books!).

Thank you so much for sticking with me, I hope the coming week receives you well 🙂

Code

Get the code for my simulation at my GitHub.

Last week, my son Isaac was crushed by his 3rd-grade spelling test. For an 8-year-old, it can be difficult to study something that might seem opaque in its usefulness. So, with a bit of Python magic, let us engage the children in solving a spelling maze!

The idea is to accept the input of a word, then generate a maze where the path to success is made easier if you know the next letter of the word.

Just Passing Through (TL;DR)

I figured I would need the ability to 1) generate a maze, 2) find all the junction points of that maze, and 3) draw letters at the junctions which lead the player down the correct route.

I built infrastructure and foundational code to perform functions like determining block positions, drawing the maze, and cleaning up relationships between blocks. Separately, I created a Maze class, which handled the maze-generation algorithm. I treated this Maze class as a parent to the WordMaze class which handles many of the functions related to letter placement. This helped de-clutter the Maze class and extend its functionality.

At the end of my project journey, I developed the code to apply words in the maze. This part became pretty complex, as I needed many parameters to be met so that the letters would group properly and the possible “incorrect” letter junctions along the solution route would be challenging enough. There were bugs to iron out, but eventually the code worked. Even better, soon a kid will be learning his spelling list and having fun at the same time!

Staying for a While (Technical Peeps)

The code for this project can be found at my GitHub.

Infrastructure and Foundational Code

After writing a toy maze generator, it was clear that I would need to build some foundations to help reduce the top-level complexity of the maze generation code. The three main foundational classes were:

• A Map Class
• A Draw Class
• A Path Class

Foundational Code: Map Class

The map class handles the grid of blocks to represent a player’s position at any point in the maze. It performs the following functions:

• Block relationships, including entry and exit directions
• Block positions, including x-y coordinate grid

Foundational Code: Draw Class

The draw class (‘Drawable2D’ in the code) is responsible for drawing to a grid of pixels, as defined by the object itself. This is an inheritable class allowing an object to set its pixel width and height and call functions like ‘fill,’ ‘draw_portion,’ or ‘draw_edge.’

The object inheriting from this class must implement a ‘draw’ method instructing how to draw itself.

Foundational Code: Path Class

This class is responsible primarily for generating random paths using the ‘step_path’ function. By moving this logic to its own class, we radically reduce the complexity of generating the maze.

Now that we have a high level view of the classes involved, let’s get into the actual maze generation!

Maze Generation

The code is available at my GitHub, but I will include the chunks of code I am referencing as we go along. For this section we will look at the ‘generate_maze’ function in the Maze class, as shown below:

def generate_maze(self):
    # Setup our start and end blocks
    self.map_start = self.map.get_start_block()
    self.map_end = None

    # We always go from North to South
    self.map_start.entry_direction = GridDirection.North

    # Setup our temporary algorithm variable
    new_start = self.map_start 

    # Start our Algorithm
    while not self.map_end:
        # Generate random paths from our starting block
        self.generate_paths(new_start)
        
        # Get the lowest block and set an exit direction (South)
        y, lowest_block = self.get_lowest_block()
        lowest_block.exit_directions.add(GridDirection.South)

        # If we have hit the bottom of the play area make this our end block
        if y == self.map.grid_height - 1:
            self.map_end = lowest_block
        # If we haven't hit the bottom then make this our next start block for random paths
        else:
            new_start = self.map.get_block_in_direction(lowest_block, GridDirection.South)
            new_start.entry_direction = GridDirection.North

    # Draw the final maze
    self.map.draw()

Firstly, we only make Mazes that start at the top and end at the bottom. With this basic tenet, we can say that we aren’t done building the maze until we have at least one block touching the southern edge of the grid. This is why our main while loop is checking for a ‘map_end’ block. We will be iterating the algorithm steps until we see such a block.

So first we grab the map’s start block, set that as our ‘new_start’ and generate paths from it. Once we have generated the paths for ‘new_start,’ we get the lowest block explored on the grid. If this block is touching the southern edge of the grid, we are done! If it isn’t touching the southern edge, then we set the southern edge as an exit. Next, we get the block south of this block and set it as ‘new_start’ and let the algorithm run again.

Generate Paths

The ‘generate_paths’ function (code below) is a random depth-first search algorithm that will generate random exits as it goes on its current search.

def generate_paths(self, start_block: Block):
    # Setup our Algorithm temporary variables
    possible_path_starts = [start_block]

    # While we have possible path starts continue building
    while possible_path_starts:
        # Randomly choose our next path start and remove it from the list
        current_start = random.choice(possible_path_starts)
        possible_path_starts.remove(current_start)

        # If this block is already explored move on
        if current_start.explored:
            continue
        
        # Otherwise create a new path and step it until it is finished
        path = Path(self.map, current_start)
        while not path.complete:
            possible_path_starts.extend(path.step_path())

Below is a GIF of how this algorithm looks when it is running.

It will eventually produce a maze like this:

All right, so we have a maze generated! Now how do we get our word in there to guide our kid to the spelling solution?

Putting Spelling Words in the Maze

With perfect 20/20 hindsight, I probably would have included exit count in path creation when I was working on the maze generator. I hadn’t considered how to control the number of exits on the solution path until I tried applying a word to it. The problem is our solution path must have exactly the same number of junctions as there are letters in our target word. This means if we have too many junctions on our solution path, we must do something to remove them.

I had a few ideas on how to do this with simple algorithms that I thought for sure would do exactly what I wanted them to do… None of them worked for various reasons, largely due to bugs in the foundational code.

I created multiple band-aids to mitigate these problems. If the band-aids stacked too high, I would eventually sift the code down to where it belonged. However, I will warn the reader, none of the code that I submit here is pretty. This was one of those “quickly written/get the thing working!” kind of projects. Should it be deemed for long term use, I think a rewrite would be warranted and easily done. Anyway, on to the method that I chose!

Apply Word

The ‘apply_word’ method orchestrates all the steps in adding letters to our maze and is included in a child class of the Maze class called… WordMaze.

def apply_word(self):
    exit_count = len(self.word)
    solution_junctions = self.get_solution_path_junctions()
    
    if len(solution_junctions) < exit_count - 1:
        raise IndexError("Not enough exit points to write word!")
    
    # Randomly select the junctions to be used for our word path
    selected_junctions = self.select_solution_path_junctions(solution_junctions)

    # Close off and unexplore all other junctions
    self.close_all_solution_path_junctions(solution_junctions, selected_junctions)

    # Reopen paths for unexplored areas on valid routes
    self.fill_out_unexplored_areas()
    
    # Apply letters to junctions
    self.apply_letters_to_junctions()

Put simply, after we have generated a maze using our parent class, we find all junctions in the map and select ones that are located along the solution path. From this smaller set, we randomly choose the junctions we want to use for the letters of our word (this shortens the list further).

With our solution letter junctions selected, we need to get rid of all other junctions along the solution path. So, we close off their entry and “un-explore” them, meaning we reset them to the original state they held before we applied any path algorithm to them.

At this point we have a pretty boring maze, and it likely is pretty easy to distinguish which path is the right one because we “un-explored” all but the ones chosen for our letters. To increase complexity, we open the dead-ends of our selected paths, exploring them until the dead space is accessible again from the selected junction.

If this is still confusing, stick with me, we have some visual elements below that will hopefully fill any gaps of understanding. First, let’s break down the important methods included in the code block above that follow the steps I just described.

get solution path junctions

This function gets all of the junctions in the map and randomly selects ones that exist on the solution path.

select solution path junctions

Of the set of junctions that exist on the solution path, select only as many as there are letters in our target word. Do this selection at random.

close all solution path junctions

This closes all of our non-selected solution path junctions and marks the blocks in the path closed off from the solution path as not explored.

Fill out unexplored areas

Now that we have a bunch of unexplored territory, let’s re-explore it from the dead ends of the selected paths. This should make the puzzle a bit more…puzzling!

Apply Letters to junctions

Finally, let’s get some letters at the junction exits. This method will iterate all junctions, giving them each a random letter. Then, it will iterate all the solution path blocks in order, applying the correct letter of the word to each. To make things a bit more tricky in the orthogonal direction of the solution path, we put the letter that comes after the correct letter.

Below is a GIF showing the re-exploration of unexplored map area:

With re-exploration completed, we can perform letter application. Below is the result of running the following command:

python3 ./main.py --word Discover

Conclusion

Spelling is difficult for many youngsters my son’s age. I hope that doing puzzles will push it just far enough over the edge of engagement to keep him moving forward. I want to thank you for sticking with me through this post. I hope the ideas and implementation I shared were thought-provoking. If you have any thoughts inspired by this post, please feel free to leave a comment below.

Also, if there is interest, I can push a web version of this application so that you can generate spelling mazes from a webpage instead of having to run it on your local machine.

Thanks for reading!

Spelling Maze Code

The code for this project can be found at my GitHub.

My Related Work

If you find algorithms interesting and would like to read more about another project of mine, check out another interesting algorithm problem from my PaperBoy VR Game.