A Star
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.
I know what you're thinking... Clearly, I should also be learning how to use software like Adobe Illustrator and not rely so heavily on MS Paint. But hey, I know it and have been using it for years, seems to do most things I need it to!
So this week I have been getting well stuck into developing this website. They gave me the task of creating a method of arranging thumbnails by date, views and type. This proved to be just the level of challenge I needed.
After sitting in front of my computer for nearly two days researching the things I could do using the JQuery library and vanilla JavaScript, I built a few functions to take care of the job.
php echo "var js_views_dates = [";
for ($i = 0; $i < sizeof($articles_info); $i++) {
echo " [ " . $articles_info[$i][6] . ", " . strtotime($articles_info[$i][7]) . "] ,";
}
echo "];";
?
First, I converted the existing array containing the views and dates I needed to know into a JavaScript array. I found a few ways to do this but they were all to complex for me at this level so I came up with this method on my own. Basically just writes the JS on the fly by echoing strings. Pretty simple, but effective.
I won't bore you with the event listeners. I used Jquery for those. Let's skip to the functions I called AFTER the document was ready...
//Get the elements.
parent = document.getElementById("article_box").children;
//Here, we combine the object in its original form along with the views and date gathered from the php.
//0 : views
//1 : dates
for (var i = 0; i < js_views_dates.length; i++){
js_article_info[i] = [parent[i], js_views_dates[i][0], js_views_dates[i][1]];
}
//This preserves the original order of the articles
original_order = js_article_info.slice();
So here I get the elements, attach them to the views and dates I got before and save the list as it currently is. I use this when the user chooses to reset from custom arrangements.
function setupOrder(original_array, order_by, high_low){
//This is a sort function that arranges the array by the first dimention, in numeric lowest to highest order
original_array.sort(function(a, b){
if (a[order_by] === b[order_by]) {
return 0;
} else {
return (a[order_by] < b[order_by]) ? -1 : 1;
}
});
if(high_low){
original_array.reverse();
}
So I learned what the sort() function did and how to get it to do my bidding. I feel like this is a function I may end up taking advantage of a lot. This is called when the user chooses the arrangement they want. It sets the order of the list based on an integer value representing their choice.
function updateArticles(order){
//This while loop simply removes the contents of the parent div by ID.
while (document.getElementById("article_box").hasChildNodes()) {
document.getElementById("article_box").removeChild(document.getElementById("article_box").lastChild);
}
//This for loop appends the objects from start to finish of the new array.
for (var i = 0; i < order.length; i++){
document.getElementById("article_box").appendChild(order[i][0]);
}
}
Finally, this function is called after setupOrder() to update the elements on the page based on the new information.
Once I had these functions built, the rest of the logic was only a line or two in the event listeners. I feel like it was efficient, although I'm sure there are many other methods and this is far from the most efficient.