Posts in Category: Progression

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:

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.

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.