Westward dev log #6: Networking, Pathfinding and Australia

These have been productive two weeks, with significant progress in the direction of an actual game.

Networking

My first goal was to have all the networking functionalities up and running, which is now the case. There is not much to do yet in the game, but all is in place so that whatever you do, the information is sent to the other players in real-time.

For this, I have heavily reused the networking code of Phaser Quest, which makes me glad to have spent so much time on it back then. In particular, for a game aspiring to have a huge world, it was imperative to use an AOI system. The one I designed for Phaser Quest can be applied to pretty much any game, which is very convenient. I also recycled the same update system, because it worked well, was efficient, and well structured.

Now that the networking aspects are all in place, it’ll be very easy to synchronize additional features of the game.

Pathfinding

That one was more tricky. I intend Westward to be a tiles-based game, where the player can move by clicking on his destination on the screen. His sprite is then supposed to walk towards that destination, following the shortest path and avoiding obstacles. This is called pathfinding, and is a well-known problem for which excellent libraries exists, for example Pathfinding.js in Javascript.

The problem is, the most common implementations rely on a matrix-like data structure to represent the world, the collision matrix, where each cell corresponds to a possible position in that world. The content of the cells may vary, but essentially indicates if a cell is walkable or not.

The problem is that the size of the collision matrix is directly proportional to the size of the game world, and when you want your game world to be potentially extremely big, this may not scale well. Therefore, I needed a way to reuse the nice Pathfinding.js library, but with a different underlying data-structure.

I didn’t want to have to hack through the library and refactor half of it, I wanted an elegant solution. And I got one! I discovered the obscure art of Javascript metaprogramming, which, as the text in the link indicates, “allows to intercept and define custom behavior for fundamental language operations”.

The idea is that I don’t want to have to fill a huge matrix with the objects that the library uses to compute a path. Instead, I resort to a 2D array storing only the locations of the obstacles. Since arrays are sparse in Javascript, this doesn’t take too much memory. In any case, it scales with the number of obstacles, not the area of the world, which is a huge improvement.

Then, I replace the collision matrix of PF.js by my 2D array. The problem is that the 2D array is sparse, whereas the collision matrix needs to be entirely full (even the walkable cells need to be filled with information explicitly saying these cells are walkable). As is, everything would come crashing as soon as PF.js would try to access and empty cell, as it would only find “undefined”.

That’s where metaprogramming comes into play. I use “traps” (see link above) to intercept all accesses to the collision grid, and return on the fly the proper objects that the library needs, based on whether or not the cell it tries to access contains information or not. The entire pathfinding algorithm remains exactly the same, but is lured into thinking that it’s interacting with a big fat dense matrix, when in fact it’s dealing with a slender sparse array.

In total, I only had to define the handlers to define that new interface to the collision matrix, as well as replace one single one-line method of the initial library. This makes this solution very robust, as I can update the library without breaking anything (unless there is a major change in how they represent collisions). And for a total of 25 lines of code (+ a very well made library), I achieved efficient pathfinding while getting rid of any concerns about the size of the world. (Now if a player requests a path from one corner of the world to the other, that would of course be a problem, but it’s not supposed to happen in the game and can be easily avoided by checking the player’s input.)

This was the biggest aspect of the implementation of the movement system. The rest was making sure that the player’s sprite would tween correctly along the path, using the new Phaser 3 API.

Australia

Last but not least, I also made progresses on the world-building front. In the past few weeks, I have been wondering about what should the size of the final world map be. This is an important variable, as it will have a lot of impact on many things. And I needed to decide that early, to be able to create the world at the right size. However, deep down I didn’t really want to settle on a size, I would prefer to be able to experiment at will with worlds of various scales, without having to rebuild a world each time (even though it’s already mostly automated).

In particular, coastlines are particularly affected by the scale of the game. There is a coast that goes from the north edge of the world to its south edge. Naturally, it’ll not have the same size if the world has a north-south length of 100 tiles vs 10,000 tiles. More importantly, all the variations along the coast, such as bays, peninsulas etc. have to scale accordingly; they cannot have a fixed size regardless of the scale of the world.

I found that the best way to tackle this is to represent the coastline as a SVG path, representing the trajectory of the coast in a standardized space. Then, once the scale of the world is decided, the path can be scaled accordingly in order to reproduce the exact same shape at all scales (this is why vector graphics, which rely on paths, can be scaled so well without losses or artifacts). It didn’t take too long to write some code to read a path and deploy it in the world.

In order to test the approach, I decided to create in the game a lake that would have the shape of Australia. I went on Google Maps, took a screenshot of Australia, opened it in Gimp, and exported from it a path that perfectly matches the shape of the continent. Then, I elected to create a world of 1200 x 600 tiles and to apply the path onto it. Below is a capture of the result, at a 1/40 scale in order to fit on the screen.

I’m pretty happy with it. The continent is slightly stretched, because the dimensions of my world are not proportional to the dimensions of the space in which the path was drawn. Apart from that, the result is pretty recognizable and exhibits many details of the actual coastline of Australia. All these irregularities are the important part, because they would be very time-consuming to reproduce by hand, and because they are what makes an environment more interesting in a game.

This was also the occasion to test if everything in the game does react well to relatively big maps as I keep asserting. So I proceeded to load that map in the game, and to try and make one complete tour of the lake, by clicking and walking and pathfinding, just as a player would normally do.

It took me 9 minutes of play to finish my tour of the lake, which I find relatively long. In the final game, where things would actually happen along the way (encounters with wildlife, stopping to pick up things, resting at an inn, …), this may well take 30-45min, which makes it a significant trip. Again, long distances and correspondingly long trips will be an important aspect of the game, and it seems like this could indeed be delivered.

All along the trip, the game engine smoothly loaded and discarded on the fly the relevant chunks of the map around the player, so that at any given time, only 10 chunks were displayed at the same time, out of the 1200 chunks which constitute the whole map (the map is 40 chunks wide and 30 chunks high, and a chunk is 30 tiles wide and 20 tiles high).

In addition, the pathfinding worked like a charm, correctly avoiding the water and guiding my character in his merry walk along the 5520 tiles delimiting the shape of the lake.

All this is very satisfying, and converges in the direction of having the tools to make a big world very easily, and having an engine that supports it and basically doesn’t give a damn about the size of the world, since it only works with local information. By changing two values in the world-making script, I can recreate the same lake, ten times bigger or ten times smaller, without it taking any more of my time, nor impacting the game in any way (except for the poor chap who actually has to walk around the lake).

Even better, moving to paths now make it possible to design the shape of the continent(s) of the game extremely easy. It can be done even in the simplest image editor, as long as the result can be exported as a SVG path. It is now even easier for me to draw non-random, complex coastlines, but it makes it also easy for pretty much anyone else who wants to work on the game. Anyone can make a map, and in a few clicks it can be reproduced in the game, at any scale.

What’s next

Thanks to all that, the game is now actually playable. It’s literally a walking simulator only, but that’s a start. Now that it is possible to move, dozens of different paths open for me in terms of development. I could start implementing the battle system, or introduce the first buildings, or set up interactions with the environment, etc. I actually have no fixed idea about what I’ll be working on until the next dev log; I’ll probably alternate between different branches. Hopefully the next two weeks will be as productive as the last two.

There is still no demo, because there is nothing yet to see which clearly defines the identity and gameplay of the game. As soon as it will be the case, which is approaching, it’ll be time to set up the production pipeline and share with you the first demos. In the meantime, here is a capture of my little guy making a stop during his tour of the lake. Looks like a great fishing spot.

Jerome Renaux

I'm an independent game developer, working mainly on browser-based multiplayer online game (HTML5 & Javascript). I love to discuss about all aspects of game development so don't hesitate to get in touch!

More Posts

Follow Me:
Twitter

Jerome Renaux

I'm an independent game developer, working mainly on browser-based multiplayer online game (HTML5 & Javascript). I love to discuss about all aspects of game development so don't hesitate to get in touch!