A Star

Posted by Justin Lillico on Mon 27 May 2019

Image credit

Why A Star?

So for game development, we were in a situation where we had a player that you could swap for any one of three characters. These characters needed to follow along behind the main character.

At first, I thought I could do something simple like…

if(player.x > character.x) character.x++
if(player.x < character.x) character.x--

This is obviously a simplification but it illustrates the general idea. So then jumping becomes an issue. Say we have a hole in the ground in front of the player. The player jumps over it, leaving the following character in an existential crisis about how to overcome the dilemma before it.

You could have the player object leave some kind of marker indicating a jump needed to be performed here and there are indeed some pathfinding systems that work this way. Donkey Kong on the Super Nintendo did something like this with its character following.

This was not an option so much for us, however, as we planned to be able to use this same algorithm to have enemies find their way around complex maps.

After a considerable amount of research, we settled on the A Star algorithm. This algorithm basically finds the shortest available route between two points in a grid of nodes.

What are we working with here?

As you may remember from my previous post, I use a little piece of software called GameMaker Studio 2. It works pretty well and I have spent many hours coding in its GML language so I am aware mostly of its strengths and weaknesses.

GMS2 has this concept of objects in it which is great. You can create objects and within each one is housed all of its code that is ran for every loop of the game. Objects can also inherit from each other just like any other object-oriented language.

// Player object

// Basic movement.
speed = 10;
movement = keyboard_check(vk_right) - keyboard_check(vk_left); //Checks return boolean 0 or 1
x += movement * speed;

The above code here runs inside of the player objects step event. This runs every frame. This will either move the player forward or backward or not at all depending on what is pressed. Super easy right?

But at what cost…

The main cost is not being able to define your own classes. Building custom data structures can be a real pain. I read somewhere (sorry, i cant remember where) that the creators tacked on some functions that build pseudo-data structures after GameMaker became popular as it was originally intended as a simple learning language. Things like lists, maps (aka dictionaries), grids (dynamic 2d arrays), stacks, queues etc. were implemented. For the most part, these are sufficient to build some cool stuff.

But I want to build a network of nodes that I can store my own custom properties:

node = {
        "x" : [],
        "y" : [],
        neighbours : [
                {"relationship_type" : "", "node" : node}

These are just a few of the properties I need to store.

A Star gets a little complicated.

A star is pretty hectic.

It basically goes through a set of nodes and checks the distance from the origin in node hopes and the Manhatten distance to the destination while noting a whole bunch of information on the way. Once it arrives at the end, it goes back through the nodes it found and from this data deduces the shortest path.

So what we had to do first was create a grid that divided the whole playable gaming area up into squares. Then we had to write some fairly complicated code to determine which of these squares was actually traversable.

It doesn't end there. We next needed to calculate the relationship between all these nodes based on the rules of the system. How high can you jump? How fast can you walk? This took a special amount of time to deduce.

Once we had all of that, we could plug in our A Star and it would give us a path. We simply tell a sprite to follow the coordinates it output and bam! You have a working AI traversal system.

What I've learned

Unfortunately, as I had no access to custom classes, I was forced to use a horrible mish-mash of maps and grids to store this data. This caused an unnecessary gap between my mind as a developer and what the computer is actually doing as a lot of this code is incomprehensible without a few hours to recap and some decent documentation.

Basically, GMS2 may be more limited than I had initially anticipated.

I do love it for its simplicity but it is exactly that which causes these kind of problems. I'd imagine had I had the ability to make classes, I would have created node and path classes; each with some super awesome methods and properties to make this puzzle far better abstracted.

In future, we may consider using Unity.

What now?

One thing this experience makes me want to do is record a video tutorial on how to set A Star up in GMS2 as we put a lot of effort into it and resources were limited for us. I may post a link to that in here in the coming months. Finding the time could be difficult but I really would like to do it.

At this stage, we are going to put this project on hold and make a smaller title using GMS2. I think this is a good decision for the immediate future for us.