Category Archives: Programming

Building a better pathfinder

A while back I was working on a project called “Meander”. It was to be a 2D point-and-click adventure game, and later, a versatile engine for my personal use. One of the things I was most proud of was its pathfinding algorithm. It was my single greatest accomplishment, and even though it had its fair share of problems and design shortcomings, it did its job.

Looking back on the code now, I can see that it’s a huge mess. The code for accessing a given node in the grid is convoluted and only works with specific parameters, and there are many places where I iterate through the entire grid just to check if a single node is valid. I’ve thought about refactoring it lots of times, but the problems are rooted deeply in the design.

Over the past nine days I’ve been teaching myself HaXe. I’m a big believer in learning languages by using them, so I took the opportunity to write an experimental game framework called Astral for HTML5, Neko and Flash Player; three of HaXe’s compiler targets. One of the classes I wanted to implement was a pathfinder that met a few specific requirements:

  • Operated with any dimensions. Meander’s pathfinder only worked with a grid 40 * 30 nodes.
  • Be completely standalone. Meander’s pathfinder had a renderer built in, and returned destinations by pixel.
  • Be fast. No matter how poorly optimized Meander’s pathfinder was, it was written in C++, which is orders of magnitude faster than any of the languages I target with Astral.

Here’s how it went down.

Algorithm structure

An A* or Dijkstra pathfinder is really not a very complicated algorithm. The process is explained here, which was invaluable during my first implementation. The basic idea is to simulate a flood of water from node to node until the end node is reached, then follow it backwards to find the path. Essentially, the flow looks like this:

  • Check if the start node is the same as the destination node. If it is, the path is already solved.
  • Check if both the start and end nodes are in valid positions on the grid. If not, the path can never be solved.
  • Create a new grid to keep track of nodes that have been flooded.
  • Add the start node to the flooded grid. Each time you add a node to the flooded list, keep track of how far many iterations you’ve gone through and set a “cost” variable in that node.
  • Add the start node to a “parent” list.
  • Until the flood reaches the end node, do the following:
    • For each node in the parent list, do the following:
      • Check in each direction around the node to see if the node there is a valid move.
        • If it is, check to see if it has been flooded yet.
          • If it has, ignore it.
          • If it hasn’t, add it to a “next-parents” list, and add it to the flooded list.
    • If the next-parents list is empty, there are no more valid moves and the path cannot be solved.
    • Otherwise, set the next-parents list as the parent list.
  • If the flood reaches the end node,  do the following:
    • Create a FILO stack or queue to use as the path.
    • Add the end node to the path.
    • Until the start node is added to the path, do the following:
      • Check in each orthogonal direction around the node at the front of the path to see if the node there has been flooded.
        • If it has, check to see if its cost is less than the front node’s cost
          • If it is, add it to the path and return to the beginning of the loop, skipping the next step.
      • (Optional) Check in each diagonal direction around the node at the front of the path to see if the node there has been flooded.
        • If it has, check to see if its cost is less than the front node’s cost
          • If it is, add it to the path and return to the beginning of the loop.

That’s all there is to it.

So, how’d I do?

  • I tested the grid with a number of different size configurations, and all of them worked without a problem. Since this was a concern coming into the project, I was able to plan ahead and make sure nothing was hard-coded in.
  • There isn’t one line of code in the whole pathfinding system that deals with any sort of graphics device.
  • Obviously it’s not a good idea to run this solver every frame, but the speed at which it calculates a path surprised me. It’ll never beat a pure C implementation, but for most purposes it should be more than adequate.

Don’t take my word for it though, the source is all available over at the Bitbucket project.

Actionscript — likes and dislikes

 

I’ve been using Actionscript 3 as part of my game programming class for almost a month now. Coming from a C++ background, there were a lot of things I didn’t like about it the first day. Some of those things I’ve grown to like; others…not so much.

 

Things I like about Actionscript:

The import system

In AS3, libraries are built on the “one class, one file” paradigm. Each class must reside by itself in a file with the same name as the class. At first I thought that this was just a needless imposition; coming from C++ where every class can be in one file, it seemed silly to me that a language would restrict the freedom of the programmer in that way. As it turns out, this is possibly the thing I like best about the language.

AS3 classes are organized in “packages”, in a similar way that C++ uses namespaces. A package is a folder that contains class files, and is usually named according to Java naming conventions; for example since my website is www.jacobalbano.com, my classes are in the folder hierachy com/jacobalbano/, resulting in the package com.jacobalbano.

The beauty of this system is that the source is always exactly where you expect it to be, as opposed to in C+, where hunting down a class definition in a source tree can be a pain. Additionally, there is no concept of definition and implementation, since each class is contained in its own file.

Getters and Setters

In C++ classes, modifying or accessing private member variables requires two functions, usually defined as SetVariable() and GetVariable(). Actionscript streamlines this pattern with getter and setter functions, which take this form:

This allows access to the private variable _ID like this:

The beauty of this system is that it allows the convenience of a public variable without the problem that setting a variable is often not enough. For example, to start an animation with a class in C++, you’d have to use the following style:

The PlayAnimation() function in the above case might stop the current animation and start the one specified in the function’s parameters. In Actionscript, the procedure would be the same, but the interface is different:

In this case, the setter function would perform the same actions as PlayAnimation(), but in a cleaner way, in my opinion.
In addition, member variables can be made read-only or write-only by eliminating one of the functions.

Super() and function overrides

When extending a class, functions of the base class can be overridden with a function implemented in the derived class. In addition, the base functions can be accessed with the super keyword. For example:

The base function update() is overridden by the derived class, but it is preserved so we can still access it.

Function pointers

I’ve tended to shy away from using function pointers in C++, even going as far as to embed a Lua interpreter to bind actions to a GUI. Actionscript makes it easy to store and use function pointers with the Function type.

 

Things I dislike about Actionscript:

Syntax

This is a big one. Actionscript’s syntax (and that of any other ECMAscript-derived language) is close enough to C that I didn’t have a hard time picking it up, but some of the changes are clumsy. I would say the biggest offender is variable declaration.

This introduces another gripe I have…

Actionscript is a GC language.

I know it isn’t cool to manage memory yourself anymore, but I like the control it gives me over the program. Actionscript is very picky about what may and may not be deleted.

Actionscript doesn’t have Enums

Enums are a fundamental part of my programming workflow. I can’t think why they wouldn’t exist within the language, but they don’t.

Actionscript has limited support for class templates

The only class that has template support is the Vector class, and templates aren’t exposed for implementation into custom classes. I managed to fake it a bit, but it’s far from preferable.

Actionscript is platform-specific

I wouldn’t even consider learning a language if it didn’t run on Linux. Fortunately, Actionscript can be developed, compiled and run on Windows, Mac and Linux natively. In this case I refer to the fact that Actionscript only really runs on the Flash or Air VMs, one of which has been discontinued on Linux, and neither of which has particularly good performance.

Actionscript allows developers to be lazy

The Flex compiler won’t complain if you miss a semicolon. Forgot to define a return type for a function? Don’t worry, the compiler doesn’t care. I compile my C++ with every possible warning enabled, so this is another thing that bothers me a lot.

Actionscript doesn’t support overloading

In Actionscript you can only have one function per function name, even if the parameters are different between declarations. This means that you can only have one type of constructor, which gets awkward. In addition, operator overloading is not allowed, so if you want to trace your custom class you’re out of luck.

 

There’s a lot to like about Actionscript, but it has its fair share of ugly features and anti-features. If not for Flashpunk and FlashDevelop I would have given up on it by now. Ironically, Flashpunk is the best framework I’ve ever used, period, and Flashdevelop is the best IDE I’ve ever used, period. At least they make the language bearable while I have to use it.

Implementing std::pair in Actionscript

This post is pretty out of date, and I wouldn’t use the same solution today. I’m leaving it here for posterity, but don’t consider it some kind of expert advice.

One of the things that bothers me about Actionscript is the lack of templates. The Vector class is their only appearance, and since Adobe hasn’t seen fit to open up the feature for general use it looks like that won’t be changing anytime soon. I’m not very good at using templates in my own C++ classes, but I certainly like to use them as part of the STL.

This week I needed a function to return two values at once. “No problem,” thought I. “I’ll just use a std::pair to store both.” A few seconds later I realized that I was still thinking in C++, so I went around searching for a comparable class in Actionscript, only to find that none existed. This was not to be borne.

Therefore I present a class I wrote to fill the gap. It’s compiler safe and mirrors the design of std::pair as much as possible.

Example usage:

I haven’t done a huge amount of testing, but I’m happy with how it works so far. As usual it’s open-source to do with what you want. The repository is here.

grue

GruePunk

One of my two assignments for the first week of my game development class was to create a “Choose your own adventure” game. The result was GruePunk, a first-person adventure based on Zork (playable version here). I’ve been trying to figure out an elegant way of embedding the .swf in my website but I can’t seem to make it work and look right at the same time, so you’ll just have to grab the file from the Bitbucket link.

I’d literally never touched a line of ActionScript in my life until three days before starting the project. The week it took me to finish it was exhilarating, if only for the pace I put myself through. While there are many things about ActionScript that differ from C++ in a good way (function pointers in particular are a thing of beauty), there are many that I dislike, and quite a few that had me hung up for hours until I figured out what was wrong. Still, the fact that I learned an entire new language in a week is something that still makes me all kinds of happy.

What are you waiting for? Go get the source or play the game!

Should have seen that one coming

Well, as happens most times when I think I’ve got it all down, further investigation reveals quite the opposite. Long story short, my camera doesn’t work in all cases. Long story long, keep reading.

To determine the furthest distance between focus points (the 2d positional vectors that my camera must keep in view at all times) I was using std::max_element and std::min_element, like so:

where FocusPoints is a container of const references to 2d vectors, and Vec2Predicate is a function pointer for sorting the container by. This is where I made my fatal mistake.

How do you determine whether one point on a Cartesian grid is greater or lesser than another? As far as I know, you can’t. You can tell which is greater on an axis, but that’s it. My function Vec2Predicate compared two vectors on the x axis only. At first it seemed to work fine, but I ran into problems when the focus points were aligned with each-other on Y. As best as I can figure, min_element and max_element were returning the same element. Thus, the distance between the two points was always zero, and the camera never zoomed out. This resulted in actors getting awkwardly close to the edges and, in some cases, going off screen while the camera did nothing.

For obvious reasons, I’ve decided to do away with the entire system involving distance between points and instead use bounding circles. Here’s my plan for the new implementation:

Each frame, loop through the list of focus points
Find which Cartesian quadrant each point lies in
Test a point three meters towards each of the two nearest walls
If either point is off screen, break the loop and zoom out
If the loop finishes without any test points extending past the bounds of the screen, zoom the view in.

I’m really hoping it’ll work…I’ve spent far too much time on this facet of the engine and I’m longing to move onto something else.

Building an intelligent camera

My graph system is working nicely with multiple resolutions, but I realized while working on it that I’ve essentially locked myself into having every scene the same size. While not necessarily a problem, from a design standpoint it really isn’t conducive to the type of levels I want to implement. Of course, allowing scenes to exist that are larger than the size of the screen introduces several new problems, namely:

  • The camera needs to keep all actors in view at all times
  • Additional detail will be needed to surround the accessible area

That doesn’t seem too hard, right?

Hah!

Easy stuff first: The camera is going to need to center itself between all points I tell it to focus on. All I have to do is get the average value of all positions. Fortunately this actually happened exactly as I thought it would.

Now on to zooming. Essentially, I check distance between the two focus point furthest from each other. If it’s over a certain length, zoom out. If it’s under, zoom in. Stop zooming in once the view is a certain width, so it doesn’t zoom in to eternity.

Seems simple enough, right? That’s what happens when I write up a blog post after the fact. I really should start writing these while I’m in the thick of things…

Resolution independence

Planning posts are all well and good, but what happens when you end up going in an entirely different direction?

I ended up creating a new class, MN::Window, that inherits from sf::RenderWindow but adds some useful members to determine resolution and pixel scale ratio.

Now, when I’m constructing the pathing graph, each cell is WindowWidth/20 by WindowHeight/15. I still have a 20×15 grid and an array of Vector2fs, but they’re static to save on memory. I can also access grid locations from anywhere in the program, so all objects in the world will use graph indices for positional values from now on.

Previously I had been developing Meander to run in a window at 800×600. Besides the issue with hard-coded window dimensions, it also created the problem that resizing it larger (to, say, 1920×1080) stretched the images out from a 4:3 ratio to 16:9. And no, they’re not the same. To fix this, I started targeting a 16:9 resolution by default. But what happens when I want the display to be smaller? I added a few members to MN::Window that help me solve this problem.

To display correctly on a lower resolution, all the sprites on the screen need to be scaled by a factor of WindowDimensions/OriginalDimensions. For example, a transition from 1920×1080 to 1366×768 works out to this:

 

I’m no good at math. I may seem like it sometimes, but it’s all an act, I assure you. I don’t know if the scale ratio for any resolution of 16:9 will result in x === y. But just to be sure I’m going to leave both equations in.

This tells us that each sprite needs to display on the screen at 0.7 of its actual height and width. My sprite manager can take care of that each time the resolution changes.

Whew! Got that checked off the list. I made myself promise I wouldn’t play any video games until I’d finished. Time for a rest. :D