[Archive] Adventures in pathfinding (and more!)

Editor’s Note: This was originally posted on one of my shared blogs I made with one of my friends on 8 January 2017 that you can find here. I unfortunately lost the source code for this, which is a shame since it was stored alongside a few other potential future blog posts at the time, that never panned out, and I was quite proud of this project at the time (I remember implementing a virtual camera with zooming that I was proud of, I was really happy with the pixel art I made, and it was my first time working with “Blobs” in javascript that used to generate a text file full of debug info for my troubleshooting).

I remember shortly after this, since I started a gamedev club with my friend (We had a gamejam at one point, and I still have the “Tank” game I made that was pretty fun, maybe I’ll do an introspective blog post of it in the future), I found out about unity’s navmesh and realised what I was doing here is very inefficient, because here I’m counting all pixels in the map as a “Node” to be used in the pathfinding algorithm, when what I should have done is placed a node at key points (intersections, etc.) instead, which would have been far more efficient. I remember spending a lot of time on this bug, where the “ghost” would keep trying to move right, but it would still be slightly below the wall which is blocking it, so it couldn’t get through, which was probably a symptom of not using a navmesh…

Ah, and I almost forgot about Tiled! That was a nice level editor. That reminds me of a time I was watching a youtube video of someone having their level editor being MS Paint, and their game would parse the image and use it as the level (e.g: Maybe it was a platformer and a certain colour is the floor, another colour is an obstacle, etc.), which I thought was really cool and wanted to make a project with that idea, which I unfortunately never got to.

Looking at my to-do list, I realised I haven’t done any projects with pathfinding yet. “Whelp, I better get to it then”.

Although my original goal was to create a Pacman clone, I find the code too bloated to work with. More on this later in the article.

This article was aimed to non coders but it slowly turned into something a bit more complex….Just ignore the parts you don’t understand. I try to use as much non confusing terminology as possible.

Also keep in mind I wrote this around midnight while I was very sleep deprived. And apparently blogspot hates me because it keeps glitching out on me.

What is Pathfinding?

“Pathfinding…is the plotting, by a computer application, of the shortest route between two points.” - Wikipedia.

It is typically used in video games to find the points an enemy would need to move to get to the player (i.e: Pacman). Here, the two ‘points’ are x and y coordinates. Pathfinding itself however is not bound to 2d Cartesian planes. For example, it could be bound to a 3d space to find the route from one point in 3d space and another. Another example, which is what is typically used in 3d video games, is to create a navigation mesh, or navmesh, a polygon where each edge is connected to another navmesh.

Algorithms

There are plenty of pathfinding algorithms out there, Djikstra’s algorithm, A algorithm, Breadth first search, etc.**
I will be concentrating on Breadth first search, Greedy Best first search, and A.

The reason why is because I find the level of difficulty in implementing those to be in ascending order, so I could code the former and add on to it for the next algorithm.

Coding language

Now was the time to decide what language to use. I considered C++, Python and Javascript with HTML5 to work with. Each had their pros and cons.

C++

Pros:

I am familiar with the language.

Cons:

Bad for quick prototyping, making small changes (which would be inevitable seeing as this is my first time implementing pathfinding algorithm) would require long compilation times.

Python

Pros:

Good for quick prototyping, because it is an interpreted language.

Cons:
I personally don’t like Python.


And so I decided to go with Javascript, or more specifically, ECMAScript6, because I wanted to have classes and OOP capabilities. At the time it seemed like a good idea…..

Tile Editor

So I needed somewhere to design the level maze.
Now obviously I am too lazy to write my own tile editor, so I went with Tiled. Search it up, I don’t want to link to it. It exported to a JSON file which played nicely with the Javascript code.

How it works

First off, the Breadth first search algorithm. What this basically does it is to “visit” to all directly adjacent nodes from the destination goal, and repeat the process for every adjacent node until it reaches the goal.  From there, it backtracks to get the route. Think of it like you want it to traverse as evenly as possible in all directions. You never wander too far off in one direction, each step you take, you  go back and go one step forward in all the other directions.

What is a node you ask? Well in this case, it’s just the position in the game. The x and y coordinate combined.


Pseudocode

BFS
Args: Destination position, Current position
Nodes.push(x);

FORx inadjacent(Current)
      x->parent = Current
      BFS(Destination, x)

After a few iterations, it would look something like this (the white square is the enemy and I am the red square) 

 Funny how it looks like a ship, right?

Greedy Best first search

GBFS
Args: Destination position, Current position
FOR x in adjacent(current position)
       x->parent = current
      x->score   =  distance(Destination,x)
      GBFS(Destination position, Nodes.GetLowestScore())

So it favours the one which, according to the distance function, is the closest path. This sometimes leads to false alarms though, because you may traverse so far near to the destination only to find it is blocked.

A*
Args: Destination position, Current position
FOR x in adjacent(current position)
       x->parent = current
      x->score   =  distance(Destination,x) + x->parent->score
      GBFS(Destination position, Nodes.GetLowestScore())
 
A* uses the distance from the starting point in addition to the distance to the destination .

Both A* and Greedy Best first search worked the same in my level….

Here is a random screenshot of me trying to find a bug

What is happening is that my code “visits” every adjacent node, assigns a parent, and repeats itself with the next node. A nice way I found out for debugging was to use a “Blob”, which is something like an internal file, to gather the debugging information,set the MIME type to a text file, and use it to create a blob:// url, which would make a downloadable text file. Otherwise I would have to keep going to the Inspect Element console to check for debugging info, which was very inconvenient.

Other Stuff

Views

This was also my first time implementing “View"s, allowing me to zoom in/out as well as to “follow”
the player. Surprisingly, it was not that difficult. I had a ProjectionScale multiply every speed variable and size variables, and as for the Viewport, I simply added two variables, scrollx and scrolly, to determine where in the screen to go to.

Here’s a screenshot of a bug I thought was interesting early on in the development.

Code maintainability

I’m sure it’s more of my less than impressive coding skills at fault, but I found difficulty in maintaining the code. In javascript, there are no “private” fields for classes (there are techniques to simulate this however, but I didn’t implement that) making everything very cluttered.

Oh? There’s something wrong with my m_collisionRect, let me add breakpoints to every place that is modified in Player.js.

“Two hours of debugging later..”

Oh! so I actually modified Player’s collision rect in the GameplayScene file instead as a quick fix! Well… That’s two hours of my life I’m never getting back.

In addition to that, being a C++ kinda guy, I felt very uncomfortable doing what I assume is copying everything whenever I pass it to a function instead of being able to pass it as a reference. I even miss having pointers!

In future, if I were to use Javascript for HTML5 games, I would firstly go to a good site to re-learn Javascript. Then I would ignore everything OOP and simply use vanilla Javascript, perhaps with the Phaser library. (Google it, I don’t want to link.)

5 Steps to Polishing it

At some point in the future, I would polish up the code and then turn it into a real pacman game. Turning it into a real pacman game shouldn’t be too difficult, just add the pellets and more ghosts enemies. Interestingly, the ghosts in the original Pacman had very specific characteristics. The red one would follow you directly behind, the pink one would try to cut off your paths by going in front of you. The orange one is stupid and moves randomly. Finally, the blue one would alternate between the other three. On top of all this, the ghosts would periodically all at the same time move to the four corners of the game.

Back to my tech demo thing,

First off, adding title screens and pause menus. This gives the first impression on the player instead of just launching them into a game.

Second, Animation, animation, animation. Moving objects are aesthetically pleasing for our eyes. Having a mostly stationary game like mine leads to boring visuals.

Third, Bright colours! Same idea as above. Makes it nicer to look at.

Fourth, smaller levels! While the one I did was okay for testing the pathfinding algorithm, smaller, nicely designed levels gives it a more “compact” feel as well as reducing the player’s concentration on unnecessary lengths of tiles. This also everything to be a bit bigger, which is good because you don’t have to squint your eyes.

Fifth, Music and SFX! An often underappreciated trait. The music needs to follow the mood of the game, and not be too short and repetitive. Appropriate sound effects are also very powerful in being more immersive. This is, besides the graphics, the main way of “rewarding”  the player for doing such actions such as collecting a pellet or defeating a ghost. The sound (and flashy colours) is what makes the experience all the more addictive!

Conclusion

Well, I can conclude I am very bad at coding efficiently and completing goals. My time management also needs improving, there was a time I forgot all about this project and only continued on it yesterday. But the important thing is I learned how to implement pathfinding algorithms and can concentrate more on the code design patterns next time instead of “quickly prototyping” the algorithm and making a mess of the code in the progress due to me having “temporary quick fixes” which then escalates to the universe blowing up. Okay, maybe not the universe, but the code base will definitely be messed up and if I didn’t use a repository, I could lose weeks worth of code.

Also it’s very important now I can brag tell people I know how pathfinding algorithms work and go into detail of the inner workings.