Adventures in pathfinding (and more!)

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);

FOR x in adjacent(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.