Posts By Justin Osterholt

A Simple A* Pathfinding Algorithm

Pathfinding is a fundamental tool commonly used to move characters around a map intelligently. Here I will be going over the A* algorithm written in C++.

It’s important to visualize how the pathfinding algorithms search for the most efficient path. Here is a neat demo using a JavaScript library called Pathfinding.js. By playing with Pathfinder.js, you should notice that the algorithm first tries to go straight for the end point and only when it hits a blocked node will it look for nodes that follow a less direct path.

The Algorithm

In a nutshell, the A* algorithm uses a graph of nodes that have a weight associated to them used to weigh paths from the start node to the end node.

What weight represents is arbitrary, since A* can be applied to different scenarios. For navigating through a map of squares for example, this value could be based on distance and steps taken. The algorithm processes neighboring nodes, adding all neighbors to an “open list” and then moving on to the lowest cost node in that list.

Given the open list begins with the start node (opposed to be empty), the main loop of the algorithm looks like this:

  1. Get next node from open list (now known as current node)
  2. Skip node if in closed list or out of bounds
  3. Process neighboring nodes (North, West, South, East)
    1. Set current node as parent of neighbor if weight is less
  4. Add current node to closed list
  5. Remove current node from open list

In all, the algorithm uses three lists:

  • Open List:  Keeps track of which nodes to search next and is ordered by weight
  • Closed List: Al nodes that have already been searched
  • Path: Linked list that connects the end node to the start node

To clarify on the path, there are actually multiple paths that exist because less efficient paths may be found before the most efficient path. The end node will have the final path, and that is all we care about.

Implementation

Node Structure

As mentioned before, this is implemented in C++ and the graph is comprised of nodes.

Here is the Node structure with only its members:

I use indices to keep track of nodes. This includes determining which node is the start and end, as well as which nodes have already been processed (closed list) and which nodes should be processed next (open list).

Note: The index struct member is there for convenience, so a coordinate to index lookup doesn’t need to be run every time.

The path list mentioned before is a linked list created through the parent  struct member, which points to another node.

Battle for Azeroth Pre-Patch


Being someone who wants to make games for a living, I find it disappointing how much I miss or don’t complete in the games I play. Time seems to slip away and I ask myself why I didn’t do more. One of my big goals this year and prior was to rediscover what I’m passionate about, what motivates me. Fantasy and games are two things I love.

July has been a month of reflection and trying to get back on track. Instead of talking about what and why hasn’t, I’m going to focus on what has happened and I want to happen.

Pre-patch Preparation

This month I’ve been preparing for the upcoming World of Warcraft expansion, Battle for Azeroth. This includes taking care of some things so I don’t need to backtrack (ex. flying) and achieving some things before they go away for good (ex. artifact appearance).

First I want to reflect on my thoughts and feelings on flying being gated and in-game items (gear, appearances) going away after the expansion ends. I’ll bring Diablo III into this as well, as it has gear and other goodies it rewards players when they finish season achievements.

Flying over Suramar after pathfinder achievements completed

Flying

Even though it was way late into the expansion, I was able to gain my flying in Legion, something I didn’t do in Warlords of Draenor (previous expansion) . So this was a special feat for me. It was challenging given my availability, I am balancing games with family and side-programming. This means I have to be selective about what I invest my time in and it’s possible I won’t get what I want. It also means I need to be smarter about how I do things, something I’m still learning.

Not having flying during the leveling experience definitely helps with immersion. Flying makes it easier to escape and access areas more easily, but waters down or nullifies the experience of exploring and adventuring because the danger is no longer there and discovery isn’t as much of a challenge anymore. In this way, I appreciate what current and past expansions have done when they lock down flying. It makes the danger and achievements feel that more real.

With that said, achieving flying in Legion was a challenge and I had to step away from it at some point. I found myself stuck in progressing through the main storyline because of a reputation gate and my timing was off for dungeons and raids. I tried chipping away at the rep, but at the time I still had at least three factions to gain reputation with and it felt cumbersome.

When I came back to the achievement, I had a more focused effort by only doing world quests for one faction at a time and using WoWHead to get passed the quest blocker I was running into. I also finally knuckled down and completed some quests in raids.

I’m hoping in Battle for Azeroth I will have an easier time keeping up with the rep grind, I think that’s the biggest factor that made me step away. As much of a pain it was, being challenged to get flying made the expansion better. I experienced the full content when I would have skipped out on Suramar and missed the conclusion of that questline.

Global Game Jam 2018

Global Game Jam 2018 took place at the end of January. It was hosted locally here in Sacramento at Square One Clubs. I participated as much as I could, but unfortunately I had some family obligations that prevented me from making it down to the site.

For my game, I created a first person puzzler in a 3D world. I used it as an opportunity to get more familiar with Blender and Unreal Engine. With this being a learning experience, I didn’t get as far as I would with tech I was already familiar with. Overall, it felt like a success. I am now much more comfortable making shapes and applying textures in Blender. I also learned what is lost while exporting a blender project into Unreal, such as shaders that are closely tied to the rendering engine.

Alright, so lets take a peek and go over some stuff!

My game takes place in a testing grounds with various platforms and standing orbs. In this first iteration, it takes place in space, but after building out the platforms that idea didn’t seem to pan out so well, for reasons I’ll go into shortly. The skybox texture was created using a premade texture from SpaceScape, a free tool for creating space skyboxes.

Unreal is a very powerful engine with some very useful tools in prototyping a scene. You can create shapes in the scene on the fly. Unfortunately (at least as far as I know) those custom shapes, known as brushes, are their own object type and I couldn’t find an easy way to convert them into components for reuse. I imagine it’s possible, the answer just wasn’t easily at hand. I created the octagon platforms and the orb with stand using brushes.

Level Design

The prototype was meant to contain a couple puzzle platforms where you had to touch light orbs in the right sequence in order to open the pathway to move forward.

The big lesson I learned in creating this initial level was that too much open space is a bad thing for this type of game. It can be pretty, but it becomes boring quickly because it lacks visual stimulation and removes mystery and discovery. The suspense of not knowing what’s in the next room or around the next corner is non-existent because those elements don’t exist. In addition, the lack of landscape/buildings make the story of the level sparse, which is also unappealing.

For that reason, if I work on this project again, I plan on adding buildings and short corridors that give glimpses of the outside.

Rising Steps

At the start of the level there are “rising steps” which consist of several triangular shaped steps that form a bridge. Initially all but one step are hidden from view. When the player steps on the first, the others rise sequentially to form the bridge.

First half of bridge activating

Powering the bridge was done using Blueprint visual scripting. With Blueprint, you script behavior through nodes that perform logic on other nodes (I’ll go more in depth on Blueprint scripting in a another post). The bridge is actually made up of two components; the container component that “activates” children steps once the first step has been touched and the individual step component manages behavior for each step once activated.

  • Bridge Blueprint
  • Rising Step Blueprint

The screenshots above are too small to make out details, but they should reflect how noodly chaining can get. Visual Scripting can look messy when used in this way. I would rather code out the logic, however for prototyping it is much much faster and easier to iterate through.

There is a learning curve in getting familiar with the function nodes, but at the end of the day it’s still using common concepts used in programming. It’s just a bit different and requires different thinking. The context filter the editor acts as guard rails to prevent you from adding incompatible nodes, which eases the scripting experience.

Spiral Steps

The spiraling staircase allows the player descend to higher or lower levels. The length of the staircase was a problem here and with a lack of landscape or objects to interact with, the long descent turned it into a tedious walk that didn’t give much in return. If there was something big awaiting the player at the next platform, it may have worked to emphasis the player was transitioning into something more involved, but it didn’t work for the simple platform I had there.

Another problem with the length, and given the size and shape of the steps, was the camera felt like it was jittering as the player walked down multiple steps. In the future it would be worthwhile to try either angling the steps down or creating an angular collision box over the steps that smoothed out the descent.

Modeling with Blender

On the art and modeling side, the “bridge” steps were shaped and textured in Blender, a free 3D modeling software. Blender is a powerful tool, but has a steep learning curve and many shortcuts to learn. One of the more challenging aspects of Blender that I run into is the different view modes it has. Two in particular are object mode and edit mode. The modes give you different ways to manipulate an object and the UI is contextual, changing for each mode.

Once I got used to some of the basics of Blender (which I did prior to the jam), learning to do things like change the shape, size, and texture of objects was much easier. I even managed to create a little transparent kiosk, shown in some of the screenshots.

The UV map was interesting to work with. Blender has a smart UV mapper that will break up the UV based off of the object. Blender allows you to paint on the texture from within the program, but I ended up creating the actual texture in Gimp. Gimp has a lot of strengths, but it’s UI drives me crazy, so the experience actually motivated me to finally knuckle down and purchase a Photoshop subscription.

Summary

In summary, I used the Global Game Jam as an opportunity to get more familiar with Unreal Engine, Blueprint visual scripting, and Blender. I found these tools are powerful and worth adding to my toolkit. The experience was very rewarding and I continued learning even after the jam, dabbling with rigging later on. There are A LOT of tutorials out there.

While Visual scripting and Blender have some downsides, such as visual messiness or a learning curve, they are still very powerful and useful.

Game development is about iterating through idea and learning through trial and error. It’s good to take a step outside of your comfort zone and try new things and see how it fits in your toolkit and overall vision.

 

Out of Phase: Race Conditions and Shared Mutexes

This is part of a series for the Out of Phase game project that reflects on various stages, covering pros and cons of the creative process and implementation of the game.

Last year I started porting over the backend of my game from Python to C++. The reason for this move ties into my long-term goals as a game developer. Programming a multiplayer server has been something that has intrigued me for a while. The idea of creating a virtual environment that is continuously running and allows multiple players to interact with that environment in real time is fascinating to me.

At this time, my game will only support two players, but I would like to play around with adding more.  I’m doubtful this will be a massively multiplayer game, like World of Warcraft or Elder Scrolls Online, since that would be a huge amount of effort. So maybe up to four players.

Real-time games that support multiple players typically require some special handling of synchronizing the game state as it is updated from the player’s clients. Without synchronizing, race conditions will occur which will result in erroneous and unpredictable ways.

So in this post, I’ll be covering how to avoid race conditions in C++ threads by using locks and mutexes.

Race Conditions

Let’s take a code snippet as an example (this is make believe pseudo code):

Race Condition 1

Ok. So the problem here is what happens when two players are attacking this goblin at the same time. Just because this code is wrapped in a function, doesn’t mean each block of code gets executed sequentially. It’s possible that the lines of code being run between each player may be executed in a mixed order.

Let’s assume that goblin->getHealth  and goblin->setHealth  read and write the current health value from or to memory. (But they don’t use synchronization)

Two players are attacking a goblin with 500 health. Both players inflict 30 damage at the same time. We expect the goblin’s health to drop down to 440, but instead, it only drops down to 470. What happened?

Where did the damage go? Well, it got overwritten because the instructions weren’t synchronized. Each thread keeps a separate copy of health and when the goblin’s health is changed in one of the threads, it never updates in the other.

Using SQLite in a Threaded Java App

A few months ago I decided to port my WoW data importer app from PHP to Java because the website was already built in Java. I also wanted to see if execution time could be improved in a multi-threaded app.

The PHP script stores the JSON returned from the WoW API into individual JSON files for each item. This means there are thousands of JSON cache files. There’s a second script that packs these responses into a single file, and then a third script that imports the data from the consolidated file in the second script.

The reason for this two-step process was to see the difference in time it took my script to process the individual files vs a consolidated file, as describe in my blog post on optimizing the PHP importer script.

This approach was overcomplicated and pretty inefficient. While writing the Java app, I wanted to create a cache source that didn’t require another script to pack the data, but was could be updated efficiently.

Choosing SQLite

At first, I tried Oracle BerkleyDB. Coding that up was pretty simple, and I got it working. However, I couldn’t find a good program to manage the BerkleyDB. The apps I came across either wasn’t specifically for BerkleyDBs or they required compiling, and I didn’t want to bother with that.

Since I’ve used SQLite in quite a few projects, it seemed like the next choice. While the mySQL database I’m putting the data into would have worked fine, that database could be remote, and I needed a local database to cache the API results into.

Threading Gotchas

A big challenge with SQLite is that you’re working directly with a file, and not a service like you do with mySQL. Because of this, special precautions need to be taken so that you don’t run into SQLITE_BUSY exceptions or accidentally corrupt your database by writing in two threads at once. This happened at least once while I was playing around with different configurations.

Tip #1: Share the SQLite connection between threads

Creating a shared connection should at least avoid corrupting the database. However, it’s still possible to come across the SQLITE_BUSY exception

Tip #2: Use a Lock

Sharing the connection worked very well at first. I was able to import data into a clean database without any problem. However, when the app was run again and started updated cache, I started running into SQLITE_BUSY exceptions.

Data Importer Optimizations

Nobody wants a slow application. Efficiently optimizing your application takes experience and constraint. You don’t want to prematurely optimize, but you also don’t want to code something subpar that will contribute to your technical debt and put your app in the grave early.

There is a balance that needs to be struck. Knowing when and how to optimize needs to become second nature so that it doesn’t interfere with the development workflow. Producing something so that it can be demonstrated often is more important than optimizing in many cases.

This post will cover a few optimization techniques associated to reading from files and running SQL queries. These tests are written in PHP, an interpreted language, though the techniques can be applied to other languages as well.

The Script

The program is basically a data importer. It takes item data from the World of Warcraft API and updates a mySQL database. Before this script runs, the Warcraft JSON data is saved in a single file delimited by a newline character. This single file, which acts as a cache, allows me to focus on optimizing the local operations without network overhead.

XDebug Setup

XDebug for PHP has a useful profiling feature. When profiling is enabled, XDebug will store the profiling data in the directory specified, and the file can be read with KCacheGrind (Linux) or WinCachGrind (Windows).

Optimizations and Tests

The complete dataset consists of 99,353 records. There are empty records which take up a newline, so the text file contains 127,000 lines.

Base Test

(Link)

I started off with a PHP script that was purposely designed to be slow. Each item was stored in its own cache file.

For each item:

  • Open the item specific data file
  • Check if there is JSON data (move onto next line of JSON if none)
  • Parse JSON
  • Query database for existing record
  • Execute insert if no existing record
  • Execute update if record exists

This took 2 hours and 37 mins. This is absolutely horrible. The good news is there are quite a few things that can be optimized here.

Here is one thing to keep in mind in regards to speed, the closer your data is stored to the processor, the faster it can be processed.

CPU Cache < Memory < Hard Drive < Local Daemon < Network/Internet.

RPG Slots Progress – Cocos2d Review

rpgslots

I started developing a slots game using the Cocos2d C++ SDK. Cocos2d is an opensource game development framework that support C++, Objective-C, and JavaScript. Eventually, this game will evolve into a slots RPG, like King Cashing and King Cashing 2. For now it uses a pretty generic reels and a match 3 mechanic that matches on the same row as well as cells on adjacent rows. For score, it keeps experience points, since this will transition to the RPG slots.

Source for the project can be found here. As of this writing, it’s in early development.

Like many game frameworks, Cocos2d has many helper functions that allow for quick game prototyping. Scenes are easy to construct, and assets, sprites, and audio can be added using built in Cocos2d objects. It even supports the ability to add custom shaders.

Extending Sprites

I found quickly that I needed to create custom objects that extended sprites. In this project there two classes that extend cocos2d::sprite ; the reel, and the HUD.

Grouping elements within sprites helped with organizing code and separation of concern. I did run into strange memory errors when trying to add certain objects, such as cocos2d::Label , directly to the scene while also having a pointer to it in the scene.

Autorelease

The Cocos2d C++ framework uses a smart-pointer technique to automatically destroy dynamically allocated objects when its internal reference count is 0. This relieves pressure in remembering to destroy objects and worrying about pointer ownership. Though cyclical dependencies still need to be avoided.

The built-in Cocos2d objects are automatically added to the autorelease pool, so there is no need to use the new  keyword. In my project, I have an object that extends the Cocos2d sprite. So there’s some boilerplate code that I needed to add so my object would be added to the autorelease pool.

ReelSprite::create  is a static method that follows the Cocos2d convention of constructing an object and adding it to the autorelease pool. mainSprite->autorelease()  is the line that actually adds the object to the autorelease pool, so that it does not have to be manually destroyed.

Screen View to World Coordinates

I needed a map editor with more features than what I saw included in TILED back in August, so I decided to try my own hand at creating a map editor. It’s just an interactive grid, right? Not quite. At least in the approach I took.

I started writing the tile editor with C++ and SDL. Implementing drag functionality was pretty easy since that was baked in the SDL API, however, I didn’t want to build the UI widgets from scratch. Unfortunately, the existing UIs I found weren’t compatible with SDL, so I had to pivot and use straight OpenGL and matrix math.

Because I was ditching the SDL framework, I had to implement my own drag logic, which is what I will discuss in this post.

Moving Objects with Mouse Picking

I needed the ability to select objects in 3D space, which lead me to a technique called mouse picking. This technique utilizes ray casting, which is how you detect if a line (a ray) intersects with something else.

The article “Mouse Picking with Ray Casting” by Anton Gerdelan helped explain the different planes/spaces and what they represented.

In order to move the objects in 3D space at a distance that matched the mouse movement, I had to transform the coordinates between screen and world spaces. When working with 3D coordinates, there are several spaces or planes that have their own coordinates.

A very simplified list of these spaces are:
Screen Space > Projection (Eye) Space > World Space > Model Space.

newtranspipe

Anton Gerdelan’s Mouse Picking with Ray Casting

Fully understanding the transformation formula was a challenge for me. Normalization and calculating the inverse Projection Matrix tripped me up due to a combination of confusion and erroneous input.

The Solution

Here are some code examples of the final working solution.

Initialization of Projection, View, Model

View to World Coordinate Transformation

At first this algorithm felt a bit magical to me. There were things going on I wasn’t entirely wrapping my head around, and when I stepped through the algorithm I got lost at the inverse matrix multiplication. In addition, the “Mouse Picking” article normalizes the world space values, which we don’t need.

An Introduction to React

I’ve been working with React a bit lately and wanted to document my experience and findings. Since there’s quite a few “hello world”/getting started guides out there already, I’ll provide links to those and cover key points I took away from articles and experience.

When React was announced around mid-2013, it looked like an interesting concept and seemed like it should be pretty significant considering it was being maintained by Facebook. However, it fell off my radar soon after. as It was too early to use in any of my projects. Looking at where React stands now in addition to supporting libraries, I can see  that the scene has matured and stabilized quite a bit.

What is React?

React is a JavaScript library created by Facebook that fulfills the functionality of the view in MV*C. It stands by itself and aligns with the “single responsibility” principle that is the first of the five S.O.L.I.D object-oriented programming and design principles. Other concerns such as routing, controller, and model/stores are separate patterns that exist outside of React.

Because of this separation, React can fit into other frameworks or be pieced together with other libraries to make a complete MV*C framework, such as Flux (see which Flux implementation should I use on history/development of Flux), Redux, or Cerebral.

React is designed to be scalable and fast. Some patterns like its root level event listener are intended to make React fast, and other features, such as the virtual DOM, use encapsulation to reduce or eliminate common problems with scaled web applications caused by conflicting class/ID names and DOM manipulation side effects.

Also worth noting, React was split into react-dom and  react-native to independently support browser and mobile apps. For this article, I’ll be covering what is referred to as react-dom, which is React for the browser.

Learning Curve

Working with React and its ecosystem has been interesting. Given you’re already familiar with JavaScript, React itself isn’t that difficult to comprehend. Though it does take some time to understand the concepts React is founded on and what problems it is addressing. For example, the data flow design may take some time to get used to.

The challenges with React more lie in the ecosystem, when third-party libraries and the build process come into play. However, the libraries are worth getting familiar with, and the build process should become less confusing as things settle down. For now, there are plenty of boilerplate start projects on github.

Getting Started

The first step is to take it easy and not get overwhelmed. There are a collection of technologies that make a React stack, and they don’t have to be learned at once, I recommend first focusing on React and JSX first. By understanding the core concepts and working with plain React is a good start.

React’s homepage goes over the fundamentals of building a React app from scratch without diving too far into the tool chain. A starter kit can be downloaded from their getting started guide.

Most examples require compiling the HTML like markup called JSX into JavaScript. This can be done through a browser version of the Babel library called Babel Standalone. However I’ve found this makes debugging difficult, because I can’t set accurate breakpoints. Compiling the application outside of the browser as part of the build process is recommended.

The following is a simple “Hello World” component defined with a pure function. For components that don’t hold state (covered further down), pure functions are preferred over react factories, such as React.createClass or React.createComponent.

See the Pen React Hello World by Justin Osterholt (@hattraz) on CodePen.0


Out of Phase: Genre Considerations

This is part of a series for the Out of Phase game project that reflects on various stages, covering pros and cons of the creative process and implementation of the game. The first post can be found here.

Deciding what type of game you’re creating can be difficult while the concept is in its infancy. There’s so many ideas you want to use, and many of those may conflict with each other at first, requiring some compromise in order for them to gel

In Out of Phase, there was a struggle to combine puzzle and action mechanics.I was trying to integrate elements from the two genres that I knew were successful by themselves, but incompatible with each other. To resolve this, I had to consider what experience I wanted to give the player and how the mechanics from each genre would contribute to that experience.

Some ideas I had to let go of, as they were too far from the vision, and other ideas had to be reworked to fit the core game concept. Here’s a reflection of that journey.

Puzzles

First I’ll start off with what kind of puzzler this is not, but what I originally thought it was going to be.

Some of my favorite games are point-and-click puzzlers, such as Myst or Escape the Room games such as Crimson Room. In these types of games, the player can progress at their leisure. While there may be action sequences, they usually don’t require interaction from the player, though there are some exceptions where the player must make a timed decision during the action sequence. The timing is typically pretty lax however.

Games like Myst, Crimson Room, or even The 7th Guest are what I would consider leisure puzzlers. They are typically slower paced compared to an action game and focus more on immersion and an experience. Death in these games are pretty rare, and are based off of a decision and not action, so the player is given a high level of safety while exploring the worlds. The focus of these games is on immersing the player into a fantasy world, and death or abrupt twitch mechanics tend to draw the player out.

While these games are fun, they weren’t the style I was looking for. Instead, I wanted to go with something more real time and physical, like Maniac Mansion or the more recent Ib. I wanted to give the player a different feeling of tension that they may need to react fast to avoid getting injured or killed, which deviated from leisure puzzlers.

This was a point of conflict in my early design brainstorming, because I liked the pacing and immersion of the leisure puzzlers. However, every time I tried to settle on removing action from the game, it felt incomplete. So I moved onto a different type of puzzler, one which was more physical and time sensitive.

In the first prototype I started with a very basic series of chambers and hallways that contain puzzles. This is what was implemented at the the Global Game Jam, and I had the beginnings of what was like a Portal clone, with pressure plates and objects that could be pushed onto them.

oop_barrel2

Where it differed from Portal (besides no portals!) is some objects and parts of the maps would be different between the players, in some cases requiring the players to communicate and discover the difference in order to complete the puzzle.

There would be furnished rooms with interactive objects, like a record player that would play music, light switches, and paintings. The player would need to interact with certain objects and in some cases complete a sequence in order to progress through the game.

With these ideas, this game was becoming more like Ib, where core gameplay involved adventuring through the levels and discovery. There would be some action sequences, but the player had to evade dangers, opposed to attacking those dangers.

The game concept already sounded fun, and there were so many possibilities for puzzles. Yet, there were some things that didn’t feel right. I didn’t want the player to be totally defenseless, I wanted to let them fight back. I also needed something that gave the game some replay value after the puzzles were figured out, so my focus began to shift.