# A* Pathfinding In Game

I wrote a post on implementing a simple A* Pathfinding algorithm a couple months ago. When I went to add it to my game I ran into some interesting differences I wanted to write an update on.

Here is the algorithm working on my game server. Both player and NPC are red blocks. When the player is within viewable range of the NPC, the NPC will start chasing it.

The pathfinding algorithm allows the NPC to maneuver around blocked tiles.

## Coordinate to Tile Mapping

One thing I discovered while incorporating it into my game was my simple example had a 1:1 coordinates to tile ratio. Coordinates 0,0 was the first tile, and 0,1 was the second tile. When tiles were 16×16 pixels, the coordinate to index mapping broke.

To address this, I needed to pass  map width and map height in tiles, as well as the tile size so it was known when a new row started and the bounds of the map.

I did this by creating a map struct that contained the width, height, size, and pointer to the tile vector.

```struct GameMap {
GameMap() {}
GameMap(int _map_width, int _map_height, int _tile_size, std::vector<unsigned int>* _tiles) : map_width(_map_width), map_height(_map_height), tile_size(_tile_size), tiles(_tiles) {}
int map_width = 0;
int map_height = 0;
int tile_size = 0;
std::vector<unsigned int>* tiles;
};```

# Metroid: Samus Returns

Metroid II is one of the most memorable titles for me on the Gameboy. The game play, aesthetic, and soundtrack  are really good and create an immersive experience.

I remember being sucked into the alien world. The sounds and environment were strange and mysterious.

One memory that sticks with me is after defeating a metroid, sometimes the soundtrack/sound effects would change, giving the impression that my actions had somehow changed something, and adding to the suspense of what would happen next.

In all, this was a game that fully immersed me, encouraging me to explore and take my time, instead of trying to just get through each level. Investing the effort to solve puzzles was well worth it and gave a bit of an edge against the next baddie.

In 2017 Metroid: Samus Returns was released. This is a remake of Metroid II that sticks to the core of what made the classic, while bringing it up to modern times with some quality of life improvements and additional changes. It’s different, yet unmistakably Samus Returns.

# October Development Progress

This is the first of my weekly reviews. I’m starting this to help keep track of what I’m doing and and to set forward goals.

The past two weeks have been a mix of new and old projects, including business-oriented project planning web applications, a World of Warcraft data sync, and two game development projects.

## Asana Features

I use Asana to manage my teams tasks. Asana is very simple and flexible, but is missing some features we need to keep track of our sprints and better organize our tasks and Kanban board.

Sprint Reporting

One of these missing features is a burndown chart based off of effort estimation. I’ve been building out our own burndown chart in an Electron app using Google Charts to display the statistics and feeding in the task data from Asana using their API. At this time I’ve got the chart but also a break out of the effort we’ve committed and the effort we’ve knocked out.

This has already proven to be really helpful, as we now have an easy way to track our progress and see the sum of effort completed at the end of the week.

Asana Bot

Asana supports custom fields, but doesn’t allow us to make them required. Requiring the effort estimation for a new task would be ideal. In addition there are a few other events where I would want additional info provided, such as when a task is labeled as blocked, a due date is passed, or a new task is added to the sprint.

To solve these problems, I’m building out a Slack chat bot using the Botkit framework. So far I’ve been learning the ropes of what the chat bot can do and building out the groundwork.

# October Gaming Progress

Here is a quick look at the games I’ve been playing recently. I’ll try to post some updates on progress now and then.

This time around, I finished Metal Gear Solid (1998), some World of Warcraft, Destiny 2, and Diablo 3.

## Metal Gear Solid (1998)

I finally completed Metal Gear Solid after many deaths from the Metal Gear mech and the fist fight with Liquid Snake.

MGS is a game I watched being played and beaten. Though it’s been so long I could only remember pieces of it. Needing to  transform the card key between rooms was one of those pieces, though I thought it was in a different game in the series.

Finishing it myself was gratifying. There were a lot of frustrating and tiring moments. I have the Metal Gear Solid HD Collect (MGS 2, 3, Peace Walker) to finish at some point.

## World of Warcraft

I jumped on WoW and ran an instance of “The Motherlode!”, which was interesting experience with other players. I was playing with a new tank (but not new to the instance) and unfortunately I kept aggroing mobs when I chased bubbles from the Azerite armor talent Secrets of the Deep. I may need to switch that out. The dungeon map for “The Motherlode!” is pretty open with branching pathways. If you meander or lag behind, it’s easy to accidentally pull enemies. So far this is my least preferred Dungeon, strangely, this makes me want to play it more so that I will learn how to do it right. My favorite Dungeon so far is Waycrest Manor.

# 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. Add current node to closed list
4. Remove current node from open list
5. Process neighboring nodes (North, West, South, East)
1. Set current node as parent of neighbor if weight is less

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

Next we’ll go over the structures and functions involved with this algorithm. One core structure is the node.

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:

```struct Node {
int x;
int y;
int index = 0;
int distance;
bool blocked = 0;
int weight = 0;
Node *parent = NULL;
};```

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.

Grid and List Structures

Nodes are stored as pointers in a vector. The open list is implemented as a multiset with the comparison function, NodeComp, so sorting is automatically done. Lastly, the closed list is implemented as a vector of ints that stores the indexes.

```typedef std::multiset<Node*, NodeComp> NodeList; // So we don't need to type out the full definition everywhere

NodeList open_list; // Node pointers to process
std::vector<int> closed_list; // Node indices already processed
std::vector<Node*> grid; // All nodes```

# 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.

# 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):

```void attackGoblin(Monster* goblin) {
int health = goblin->getHealth();
health -= 10;
goblin->setHealth(health);
}```

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?

```(thread 1) int health = goblin->getHealth(); // getHealth returns 500
(thread 2) int health = goblin->getHealth(); // getHealth() returns 500
(thread 2) goblin->setHealth(health); // Goblin health is now 470
(thread 1) goblin->setHealth(health); // Goblin health is still 470```

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.

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).

```[xdebug]
xdebug.profiler_enable=1
xdebug.profiler_output_dir=\Users\Justin\Misc Code\Profiling\php7```

## 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

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.