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;
};```

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.

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.

RPG Slots Progress – Cocos2d Review

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* ReelSprite::create(const std::string& filename, std::vector<int> _cells)
{
ReelSprite* mainSprite = new ReelSprite();

mainSprite->init(filename);
mainSprite->autorelease(); // <-- ADD TO AUTORELEASE POOL
mainSprite->cells = _cells;

return mainSprite;
}```

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.