A Traveling Salesman Problem Example

Let’s say that you are trying to solve the traveling salesman problem. Let us compare two particular approaches: Random and Greedy. We will use a small subset of New York cities (NYC, Rochester, Albany, Syracuse).

Random Algorithm:

1. Pick a random starting city from (NYC, Rochester, Albany, Syracuse).
Let us start with Rochester
Chosen Cities = (Rochester)

2. Pick a random unchosen city from `(NYC, Albany, Syracuse)`
  Let us pick NYC (that’s 333 miles)
Chosen Cities = (Rochester, NYC)

2. Pick a random unchosen city from (Albany, Syracuse)
  Let us pick Syracuse (that’s 247 miles)
  Chosen Cities = (Rochester, NYC, Syracuse)

2. Pick a random unchosen city from (Albany)
  Let us pick Albany (that’s 145 miles)
  Chosen Cities = (Rochester, NYC, Syracuse, Albany)

Note: Albany back to Rochester is 226 miles.

3. There are no more cities and the route takes (333 + 247 + 145 + 226) = 951 miles

Greedy Algorithm:

1. Pick a random starting city from (NYC, Rochester, Albany, Syracuse).
  Let us start with Rochester again.
  Chosen Cities = (Rochester)

2. Pick closest unchosen city from (NYC, Albany, Syracuse)
  Syracuse is 87 miles away
  Chosen Cities = (Rochester, Syracuse)

2. Pick closest unchosen city from (NYC, Albany)
  Albany is 145 miles away
  Chosen Cities = (Rochester, Syracuse, Albany)

2. Pick closest unchosen city from (NYC)
  NYC is 156 miles away
  Chosen Cities = (Rochester, Syracuse, Albany, NYC)

Note: NYC back to Rochester is 333 miles.

3. There are no more cities and the route takes (87 + 145 + 156 + 333) = 721 miles

Using an Entity Component System with Python and SQLite3

In the last blog post, I introduced entity component systems with some C++ template code to help out with safe typecasting. In this blog post, I want to share my experiment using Python and SQLite3 to implement the database structure I read about in Adam Martins’ blog.

I have not had the opportunity to test out the performance of using SQLite3, but the Python language makes it really easy to experiment and since I use Pythonista on iOS, it can be played around with on the road, during an errand, etc. So in this post, I will focus more on creating a simple system and the appropriate SQL queries. The other program I use is called DB Browser for SQLite which is handy for building your database and doing some maintenance.

My focus is on small games right now, so SQLite3 is a good choice since I can embed it in my programs. If I need something beefier, then there are other choices like PostgreSQL or MySQL.

To initialize SQLite with Python, you can start out with the following code:

import sqlite3

conn=sqlite3.connect(":memory:")
if not conn:
    print('oh no!')
c=conn.cursor()

We can use the execute function on the resulting c object to execute SQL statements. For example:

c.execute('CREATE TABLE entities (entityID integer primary key, desc text)')

To create a table for the entities, we use the CREATE TABLE query.

CREATE TABLE entities (
    entityID  INT PRIMARY KEY,
    entityDoc TEXT)

The components table is similar:

CREATE TABLE components (
    componentID    INT PRIMARY KEY,
    componentName  TEXT
    componentDoc   TEXT
    componentTable TEXT)

And the entity component data table is:

CREATE TABLE entityComponents (
    entityID    INT,
    componentID INT,
    rowID       INT)

The example source code can be found on PasteBin at https://pastebin.com/ruTeQqYE. However, what I want to talk about is the INNER JOIN that is used to combine the entityComponents table to the actual data rows. While you should do some research on JOINS, the short story is that if you have a foreign key on the left table and a primary key on the right table, you can use the following query:

SELECT * FROM (TblA LEFT JOIN TblB ON TblA.FK=TblB.ID)

The ON keyword sets the requirements for the JOIN otherwise you get every row on the left hand side and each row is matched up with every row on the right. This is a quadratic increase in size which is something you definitely do not want. So if you wanted to do a LEFT JOIN with three tables, then you could use a query like:

SELECT * FROM (((entityComponents LEFT JOIN entities ON entities.entityID=entityComponents.entityID) LEFT JOIN components ON entityComponents.componentID=components.componentID) LEFT JOIN positions ON entityComponents.rowID=positions.rowID)

If you take a look at this query, note that that the parentheses are used to accommodate the three LEFT JOINs. These are very useful in getting these queries to work correctly.

OK, post is getting a little long, but this brings me back to my original point. I do not know the efficiency of using a database when utilizing queries like this. I have no doubt that there is a lot of usefulness here for loading and saving data. But for real-time performance, that needs some experimentation and testing across several platforms with varying compute capabilities.

Entity Component Systems

This past week, I have been focused on learning about entity component systems, or ECS. This is an interesting idea that brings in ideas from the relational database field. It started getting popular in the early 2000s with a talk at Game Developer Conference by Scott Bilas. As they were initially difficult for me to find, I have included a copy below. The blog that I really learned a lot from was Adam Martin’s five part series (especially post 5). The short short version is that instead of trying to code or encapsulate game objects as object-oriented classes, keep the logic and the data separate.

Now, this idea has not been foreign to me. When I started programming in BASIC, Pascal, Assembly, and C (those were my first languages), the procedural and modular programming approaches were the easiest to teach and learn. Object-Oriented Programming was interesting to me, but as a teen it was a little strange. Today, if I can think of a HAS-A relationship or an IS-A relationship, then I find it easier to decide whether to be more data-oriented or object-oriented. But procedural programming and having sub-modules process entire lists of structs kind of faded into the background when OOP was being touted as the best way to do anything. As a young person learning, you tend to hop on what seems industry standard and then go overboard before you learn to start balancing all the techniques together.

Still, the OOP influence on my game programming has had a long lasting impact. It’s the go to tool for starting a new project, but I have had difficulties wrapping my brain around why it feels clumsy to solve problems like game logic. So, having caught a couple of data-driven talks in the last year including CppCon14’s Data-Oriented Design by Mike Acton, I have been refreshing myself on other related techniques. It was a little disheartening then to see a talk from 2002 and compare the results from my own small games with the AAA games of today. But that’s not how I roll, my philosophy is that when you have failed and/or lost time, just try again and make it better the next time.

So what are entity component systems? The main idea is that you maintain a list of entities. An entity is an integer which uniquely identifies it in the database. In database lingo, this is a primary key. The second list (or table) is the list of components. Each component has a unique integer id, its official name, a description, and the name of the table that stores its information. An example of a component would be (1, “POSITION_COMPONENT”, “The position of an entity”, “positions”). The positions table is going to contain a primary key, x, y, and z coordinates. You could think of this as an array of a fixed arrays with 3 components.

Now we need to connect the component, the entity, and the row together. So we add another table entityComponentData with three columns of information: entity id, component id, and the id of the row containing the data. Now this is beyond the scope of this blog post right now, but you would use the power of the INNER JOIN to connect all the tables together.

In an object-oriented language like C++, we can make this whole thing a little simpler. We could define a struct for the position data. The components and entities can use a variety of data structures. For instance, we can use a std::unordered_map — which is a hash table — to store the list of components and then a nested unordered map to store the link from the entities to the components. Another approach is to maintain a set of arrays that we resize. It’s more of an approach of managing this data. Consider the following C++ snippet which shows how you would retrieve the data for a particular component.

struct Component {};

class EntityComponentSystem {
  unordered_sat<int> entities;
  unordered_map<int, unordered_map<int, Component*>> ecs;
  Component* getEntityComponent(int entityID, int componentID) {
    if (!ecs.count(componentID)) return nullptr;
    if (!entities.count(entityID)) return nullptr;
    return ecs[componentID][entityID];
  }
};

I had some success using a static member variable which stores the componentID and then use a template function which automatically casts to the right component subclass.

enum class ComponentType {
  Derived;
};

struct DerivedComponent : public Component {
  static const ComponentType ctype;
};
ComponentType DerivedComponent::ctype = ComponentType::Derived;

class EntityComponentSystems {
  template <typename T>
  T* getEntityComponent(int entityID) {
    if (!components.count(T::ctype)) return nullptr;
    if (!entities.count(entityID)) return nullptr;
    return (T*)entityComponents[T::ctype][entityID];
  }
};

With this method, you can write statically typed code that ensures your entity component system is returning the right class. I did not use smart pointers here for sake of brevity, but you could totally use something like that to make the memory management a little more automatic.

Until next time, I will be playing around with the idea of an ECS and try to think of other things that I could use it alongside with.

Working with Vulkan

So, work on Fluxions 4.0 has begun. I started out by digging into Kristian Høgsberg Kristensens’ vkCube source code. I think he did a good job laying out all the essential pieces. Vulkan like OpenGL is a C library at heart. Instead of many state calls, you need to fill in data structures with all the important information. Unfortunately, the anonymous initializer lists that C uses are not compatible with C++, so instead I used that as an opportunity to go into the vulkan_core.h header file and see what these structs do.

One key piece of information is that you need to set all the non-essential parameters of every struct to zero or you likely will cause a crash. One method is to call memset to set the entire struct to 0, which I did initially, but I think the better way is to simply initialize all the members directly. And I won’t feel that I’m adding unnecessary calls to It helps with the learning process and since the whole process of programming with Vulkan is a bit verbose anyways, not a big deal. Another option that I considered was to encapsulate every Vulkan struct as a C++ class. But there is a substantial work cost involved given the vast number of different structures in the Vulkan library.

To initialize the Vulkan library, I use SDL 2.0 to create the window, initialize OS-dependent extensions, and create a surface to render to. Ultimately, this initialization takes about 500 lines of code. I need to add the ability to create a depth-stencil buffer in addition to the color buffer, but I do not think this will take too much effort. The functionality for initialization is going to located in the VulkanContext class. The main idea is to have code that looks like:

bool MyApp::init() {
  if (!context.init())
    return false;
}

void MyApp::render() {
  context.beginFrame();
  // render objects
  context.presentFrame();
}

The next concept to finalize is the render config. The render config is a thing I started in my WebGL LibXOR game engine. The idea matches the idea of the graphics pipeline in Vulkan. Of course, I was inspired by early talks about the architectures of Mantle, Direct3D, and Vulkan in hopes that I would be ready for it when I was ready to begin work with Vulkan. This has turned out to be a good strategy. While not finished, I hope to make the following code idea to be viable:

void MyApp::render() {
  context.beginFrame()
  if (config.use()) {
    config.setLights(lights)
    config.setMaterial(material)
    config.useTransformation(transformation)
    config.useTextures(textures)
    config.draw(geometry)
    config.restore()
  }
  context.endFrame()
}

Before I go down that road, I need to identify the material, geometry, and scene graph methodologies I want to use. The first is to use the Alias/Wavefront OBJ/MTL format which is great for static geometry. The second is to investigate the Autodesk (Filmbox) FBX format which supports animation. The third is to investigate Alembic which is an animation format for preserving animation. Lastly, I have taken a look at glTF which has a nice subset of features including animation. It may be worth my time to simply develop tools to convert these into a simpler system useful for direct upload in GPU buffers. I have played around with extending the Alias/Wavefront text file format and had good results in the past. I may keep that work and see what FBX or glTF ideas might be useful.

This last point is important because when you want to focus on physically-based rendering, you do not want to get too bogged down into a complex animation system. I do want to be able to tell animated stories with my graphics engine. But I have to balance it with the needs of the other components to my graphics engine.

So, the next work I need to do is to encapsulate the following ideas in Vulkan. How do I upload a texture map, create separate uniform buffer objects, and separate interleaved vertex array objects? Currently, I am working on abstracting the VkMemory and VkBuffer objects to make this process easier. Ultimately, I am working towards a smallish demo on using the new Ray Tracing features. Until then, Adios!

Fluxions Engine 3.0: The History of a Research Graphics Engine

The first graphics engine I wrote was in the late 1990s which I originally named KA3D — short for Kick-Ass 3D. But, I couldn’t commit to this name because it had a slight hint of profanity which I am generally uncomfortable with. So I changed it to Fluxions after the Method of Fluxions which Isaac Newton invented. The name was cool and it had the allure of mystery. I found an old version of my website, though mostly non-working, which was cached in October 1999.

https://web.archive.org/web/19991007002444/http://skyscraper.fortunecity.com/altavista/565/

The first engine was short-lived and it was completely software-based using scan-line rendering and blended lightmaps and color look-up tables. It was written for MS-DOS using the DJGPP port of GNU C++ compilers. Then I discovered the Allegro library.

Fluxions / KA3D 1.0 for MS-DOS

The Allegro engine was a game engine that was fairly easy to get into. It had graphical user interfaces and extensions for 3D graphics. I was also getting into Linux at the time and I was first learning about the Mesa library for rendering with OpenGL. And then I was lucky to get a hold of Riva TNT2 card which had OpenGL graphics drivers to use at school.

So I began writing the second version of Fluxions using OpenGL 1.1. I used this for a game I was working on called Outpost Wars. I remember there was an online contest for 3D demos, so I submitted the following demo. You could walk around this strange sculpture featuring rotating rings kinda like the ones from Superman.

Fluxions 2.0: GL Land demo

I followed the extension scene around OpenGL until at least version 1.5. This was especially useful for doing bump mapping and other related techniques. I started working on an outer space network game with some friends from work. Unfortunately, we were not able to complete it, but I still look fondly back on that work. I was very pleased with some graphical user interface work I programmed and utilizing bump mapping and lightmapping. But programmable shaders were becoming interesting and so it was time for the longest-running Fluxions 3.0 graphics engine.

Fluxions 2.0 — The unpublished BattleLine game

When I began working on programmable graphics, the 3D engine has taken a number of turns before it gets to its final form. But basically, it served as the basis of my Master’s and Ph.D. research. My first trip to SIGGRAPH in 2012 really brought me up to speed on many of the latest and greatest pushes into physically based rendering. You can see some of the improvements in the remaining two images.

Fluxions 3.0 earlier results

So, I think it’s probably time that I put Fluxions 3.0 to bed. It needs a few last remaining touches, but the next version will switch to the Vulkan graphics library and make use of real-time path tracing. I will work on moving some of my earlier research work on local dynamic radiance maps, spherical harmonic lights, and scalable SH harmonics. Farewell Fluxions 3.0, and good tidings to the new Fluxions 4.0 engine.

Fluxions 3.0 later results

FreeBSD Part 4

Today, I am getting my development environment all set up. I wanted to use VS Code, but it wasn’t in the pkg system for 12.1. So I tried to use the ports system, however, the 49GB slice I have for my /usr folder was filling up — fast. OK, so instead I decided to see if I could update where I’m getting the software. So I changed from release_0 to latest inside my /usr/local/etc/pkg/repos/FreeBSD.conf. This file does not exist initially, so you have to create it. Afterward, I type in the following and I’m able to install newer software!

FreeBSD: {
  url: "pkg+http://pkg.FreeBSD.org/${ABI}/latest"
}

FreeBSD Part 3: Boot Loading

So one of my laptops is a ThinkPad Yoga that I use Windows 10, Fedora, and FreeBSD. The adventure was figuring out how to get FreeBSD to boot. I am using GRUB2 from my Fedora installation to chainload the bootloader. To do that, I had to add the following entry to the /etc/grub.d/40_custom file.

menuentry "FreeBSD" {
    insmod part_gpt
    insmod fat
    set root=(hd0,gpt8)
    chainloader /efi/boot/bootx64.efi
}

After that I ran grub2-mkconfig -o /boot/efi/EFI/fedora/grub.cfg to update my current GRUB2 configuration. And the result was that it worked! I have an entry to boot into FreeBSD now. This took several hours to figure out. I am posting to help some other soul in my situation. Now on to install Gnome Desktop, Chromium, and Xorg.

Pushdown Automata

A pushdown automaton (PDA) is a state machine with a stack. They can either be deterministic or nondeterministic. Mathematically, they are weird to look at. It is better to be deterministic rather than nondeterministic because you control what your application will do even if you do not know the exact order of user input. They can be used to handle numerous game development tasks like handling the game loop.

The formal definition is that a PDA is a 7-tuple M = ( Q, \Sigma, \Gamma, \delta, q_0, Z, F ). This is behavior and data wrapped into one. Let’s make this usable. Q is the set of states you can be in. It needs to be finite. Then you have an input alphabet \Sigma which essentially is player input. Next we have the stack alphabet \Gamma which are the items we can put on the stack.

For convenience sake, we are going to use ALLCAPS for symbols on the stack, CamelCase for states, and quoted characters (such as “Escape” or “q”) for input.

The function \delta defines which state we can transition to given the current top of the stack. This is the transition relation. For example, if INIT is currently the top item on the stack, we shouldn’t move around in states that are reserved for GAMEWON. This kind of formalism helps our PDA to be deterministic. More specifically, the transition relation requires five pieces of information (p, a, A, q, \alpha) which we will discuss shortly.

The Z is the initial stack symbol that the stack is initialized to when started. And F is the set of accepting states. For instance, perhaps we only want to transition when a key is pressed down, but not when a key is released. Often a double circle is used to mark these states.

Let’s return to the transition relation \delta which contains (p, a, A, q, \alpha). This means that we are allowed to transition from state p to state q when the input a is received and while A is the topmost stack symbol, pop the topmost stack symbol and replace it with \alpha.

If we were using a regular state machine, then we might have the player in the GamePlaying state and when the user inputs “Escape” (to pause the game), we might transition to the GamePaused state and wait until “Escape” is pressed again before transitioning back to the GamePlaying state. This is trivial, but if we then decide to add a settings menu that is accessible from the pause menu or from the game, this is going to cause a mess of if-else statements because the way to code this is:

// Init code
int gameState = GamePlaying;

// Game loop
if (gameState == GamePlaying) {
  if (keys[ESCAPE]) {
    keys[ESCAPE] = 0;
    gameState = GamePaused;
    return;
  }
  if (keys[F2]) {
    keys[F2] = 0;
    gameState = GameSettingsMenu;
    return;
  }
}
else if (gameState == GamePaused) {
  if (keys[ESCAPE]) {
    keys[ESCAPE] = 0;
    gameState = GamePlaying;
    return;
  }  
  if (keys[F2]) {
    keys[F2] = 0;
    gameState = GameSettingsMenu;
    return;
  }
}
else if (gameState == GameSettingsMenu) {
  if (keys[ESCAPE]) {
    keys[ESCAPE] = 0;
    gameState = GamePlaying; // What about pause?
    return;
}

So the problem is very clear, we have no way to remember where we currently are. We have to either duplicate the Settings menu as GamePlayingSettingsMenu and GamePausedSettingsMenu or we have to keep track of extra state. With the PDA, we can remember where we are by pushing/popping the current state. Consider the following code:

// Init code
vector<int> gameModes;
gameModes.push(GamePlaying)

// Game loop
if (gameModes.back() == GamePlaying) {
  if (keys[ESCAPE]) {
    keys[ESCAPE] = 0;
    gameModes.push_back(GamePaused);
    return;
  }
}
else if (gameModes.back() == GamePaused) {
  if (keys[ESCAPE]) {
    keys[ESCAPE] = 0;
    gameModes.pop_back();
    return;
  }
  if (keys[F2]) {
    keys[F2] = 0;
    gameModes.push_back(GameSettings);
    return;
  }
}
else if (gameModes.back() == GameSettings) {
  if (keys[ESCAPE]) {
    keys[ESCAPE] = 0;
    // now we go back to where we were
    gameModes.pop_back();
  }
}

This new PDA behavior is far easier to maintain than the previous if-else statement process. The previous Finite State Automaton (FSA) previously had no method of remembering where we were. Hence, if you pressed “ESCAPE” in the settings menu, you would go back to the game even if the game was previously paused. You would have to have a non-deterministic algorithm otherwise. The PDA makes this process deterministic, which we previously mentioned is the ideal case–you always know what your application will do.

So, one modification I like to use is to couple the stack with a main symbol, a secondary symbol, and a pop time. The main symbol is used to control the main logic of the game, the secondary symbol is used as a PDA. I can then pop the main symbol and all the PDA used for the secondary state will go away. The pop time is used to automatically pop a symbol off the stack after a certain period of time. The following pseudocode is then possible:

struct GameState {
  std::string gamemodule;
  std::string alt;
  double popTime;
}
vector<GameState> gameStates;

void init() {
  gameStates.push({"MAINMENU", "", 0});           // When play game is pressed, these next
                                                  // items are popped at 1 second intervals
  gameStates.push({"SHOWCOUNTDOWN", "THREE", currentTime + 1});
  gameStates.push({"SHOWCOUNTDOWN", "TWO", currentTime + 2});
  gameStates.push({"SHOWCOUNTDOWN", "ONE", currentTime + 3});
  gameStates.push({"SHOWCOUNTDOWN", "GO!", currentTime + 4});
  gameStates.push({"MAINGAME", "", 0});
}

void gameloop() {
  if (gameStates.empty()) return;
  GameState &top = gameStates.back();
  if (currentTime > top.popTime) {
    gameStates.pop();
    return;
  }
  if (top.gamemodule == "MAINMENU") {
    // if PlayButton pressed
    gameStates.pop_back();
    return;
  }
  if (top.gamemodule == "SHOWCOUNTDOWN") {
    // do nothing, display() will draw "ONE", "TWO", "THREE", or "GO!"
    return;
  }
  if (top.gamemodule == "MAINGAME") {
    // handle in game logic
    return;
  }
}

void display() {
  // Approach here could iterate through gameStates and render items back to front
}

Stock Market Game

From the book “Announcing Computer Games for Business, School and Home” by J. Victor Nahigian and William S. Hodges, this post is about two interesting games: Star Trek and Stock Market. There are many good games in this book, but I’ve chosen these two because they are interesting to me today. In the past, I have written these two programs out on the Commodore VIC-20. They are simplifications on previous games, but when you have very limited memory (5KB and 16KB), you have to cut features.

Stock (Market)

The object of this game is to make more money than the opponent (computer). The mechanism for this game is rolling two dice representing shares “A” and “B”. The first die allows you to buy “B” shares and the second allows you to buy “A” shares. The amount of shares is the value on each die. Selling works the same way. There is a 5% brokerage fee on each transaction. At this point, I’m wondering how much the brokerage earns?

The second mechanism is adjusting the price of the stock. This appears completely made up. You can use your turn to raise the price of a stock “A” by “B” dollars or lowering a “B” stock by “A” dollars.

Overall the program is about 2 pages of BASIC code. So the challenge would be to convert it to C++ or use JavaScript and my LibXOR library. I would rather experiment with C++ for the core mechanic and then convert it later if it still remains interesting.

Star Trek

This program is also two pages of BASIC code, but it feels more dense than STOCK. This game reminds me of an RPG or Pokemon battle. You have the U.S.S. Enterprise and a Klingon ship each facing a different angle. You have to figure out the appropriate angle to fire at the opposing ship. You are given the option to fire phasers, fire photon torpedos, print a status report, change movement, or self destruct.

I’m reading the source code and this game is more involved to describe than the STOCK game, so I will delay that until I have experimented with writing this game out. I am thinking this could be fun to expand by allowing several ships, real-time flight, or several star systems. For now, I will also try my hand at doing this in C++.

Gamedev This Year

Furtual Rabbit was my first game in a year. It was revealing how out of practice I had gotten. It might be time to start doing more One Hour Game Jams. On the other hand, I got a lot of experience with computer graphics and simulation techniques which was my main focus during the academic year.

So what will I focus on this coming year? On the top of the backlog is getting some graphics research written up and sent to journals. Next up is improving my LibXOR library for #GameDev so that I can prepare for a 7DRL. And one last goal for good measure is creating a real-time ray tracer to go with my Unicornfish network rendering concept. For this blog post, I will talk about the latter two in a bit more detail.

The 7 Day Roguelike Challenge (7DRL.com) happens in early March. Roguelikes are inspired by the game Rogue. They often feature some combination of turn-based gameplay, grid-based environments, permadeath, and procedurally generated levels. What would mine look like? Topologically speaking, I want a procedurally generated overworld and fairly shallow levels with keyed off areas. I have some concepts in my head how they might play out, but I need to work on some prototypes first.

And finally, graphics wise I want to experiment with Realtime Ray Tracing and to that extent, I want to integrate it with my network rendering API Unicornfish. This means that I need to start decoupling it from the Fluxions Library. There is a lot of work to be done in that department, so I will need to spend some time charting out how the library works. There are a lot of TODOs on the current backlog, so this coming year will be quite busy, but perhaps I can drive two publications out of all that work.