So, Ruth and I just got back from Iowa.  We got to see the Iowa State Fair, which was pretty cool, and to see lots of corn and soybean farms.  I learned a lot about farming, probably the most significant part of which is the fact that the romanticized notion of a farm house in the middle of a field of corn is more or less bunk.  There are such farmhouses, but the vast majority of farms appear to be just 80 acres of corn with no buildings on them at all, and then the big harvesters come around in the fall and pick up the whole field in a few hours and then move on the the next one.

Besides being oppressively hot and humid, they also have mosquitoes in quantities I’d prefer not to imagine.  However, even though I got bit several times, I didn’t get itchy at all.  I don’t know if I lucked out there, or if there is a different species of mosquito there then I’m used to, but it worked out this time I suppose.

On the plane ride back, I did manage to get out about 13 pages of notes about Feralor and I’m going to start implementing some of those today – I’m quite excited.  I purchased to books: AI for Game Developers and Physics for Game Developers. Both books were quite helpful in sparking some ideas for me and I recommend them for anyone starting out in game development.

So the next big challenge for me is going to be the JavaScript user interface. I want it to be fluid and user-friendly, and one of the features I’d like it to have is the ability for a user to click a tile and have the UI automatically move their character to the new tile, avoiding any obstacles along the way. I Googled a lot of different search phrases to find what I’m looking for, but every time I searched for anything with the word “routing” I kept getting lots of stuff about network routing and even GPS routing, but not game player routing.

So I e-mailed a CS professor at UCSC and asked him for advice and he gave me the magic keyword: pathfinding.

So I Googled around for JavaScript implementations of pathfinding algorithms, and I found a really good example:

http://www.briangrinstead.com/blog/asta … javascript

I’ll have to modify the algorithm to take into account things like cost-per-tile (where steep ascents cost more than level movement does, for example) but more or less this is exactly the algorithm I need. Woot.

So, part of the Perlin noise algorithm is a “random noise generator”, which actually isn’t random at all but instead behaves more like a hash function. I’ve looked at several different functions to fill this need. The one that is used in the Perlin reference code isn’t particularly random from what I can tell and I’ve seen some not-so-good things about it. I tried using SHA1, which produced beautifully random terrain, but was very CPU intensive. I looked at the FNV hash but had some trouble porting it to JavaScript. I looked at MD5, MD4, CRC32 and several others and they all had a shortcoming or two.

Then I stumbled onto Paul Hsieh’s Hash page. As it turns out, this may be the perfect hash algorithm for me. It’s fast, efficient, and produces a 32-bit number rather than a 160-bit hash, as in the case of SHA1. And it turns out that it wasn’t all that hard to port to JavaScript:

// A JavaScript implementation of Paul Hsieh's Hash
// http://www.azillionmonkeys.com/qed/hash.html

// Remember that JavaScript doesn't have unsigned data types, so this function
// will return a negative integer 50% of the time, but the bitwise
// representation of the hash will still be correct.

function hsieh_get16bits(data) {
  data = String(data);
  return (data.charCodeAt(1) << 8) + data.charCodeAt(0);
}

function hsieh_hash(data) {
  var len = data.length;
  var hash = len;
  var tmp = 0;
  var rem = 0;

  if (len == 0) {
    return 0;
  }

  rem = len & 3;
  len >>>= 2;

  for (; len > 0; len--) {
    hash += hsieh_get16bits(data);
    tmp = (hsieh_get16bits(data.substr(2)) << 11) ^ hash;
    hash = (hash << 16) ^ tmp;
    data = data.substr(4);
    hash += hash >>> 11;
  }

  switch (rem) {
    case 3:
      hash += hsieh_get16bits(data);
      hash ^= hash << 16;
      hash ^= data.charCodeAt(2) << 18;
      hash += hash >>> 11;
      break;
    case 2:
      hash += hsieh_get16bits(data);
      hash ^= hash << 11;
      hash += hash >>> 17;
      break;
    case 1:
      hash += data.charCodeAt(1);
      hash ^= hash << 10;
      hash += hash >>> 1;
  }

  hash ^= hash << 3;
  hash += hash >>> 5;
  hash ^= hash << 4;
  hash += hash >>> 17;
  hash ^= hash << 25;
  hash += hash >>> 6;

  return hash;
}

So now I’m off to port this to PHP as well (which should be no problem) and then generate some terrain maps based on this new algorithm and see how it does. I’m very optimistic right now.

Feralor has several non-game-play elements that are necessary (or in some cases just nice-to-have) for the game to be successful. Some of these I have created to solve what I perceive as problems with other games. For example, the encyclopedia exists so that players have a definitive source for information about all game items, locations and concepts. By having this information listed directly on the Feralor web site, we eliminate the need to external game Wikis, and we also reduce the risk of players going to third party sites that might have malicious code designed to gain access to the player’s Feralor account.

Things like registration and avatar management also happens outside the game play engine. My reasoning for that is that those things generally happen infrequently and we don’t need to introduce additional complication to the already-complicated JavaScript game engine.

Note: This was previously posted in the Feralor Development forum before that was all rolled into the WordPress blog, which is why this appears to be incomplete.

My initial thoughts on the user interface was there there would be two maps: the interactive map that lets you pan and zoom to get a high-level overview of the world, and the “play”, which would be effectively a fully zoomed-in map that would let you interact with the environment. As time went on, it became apparent that there really was no difference between these two maps, and I decided to just combine them into one map.

From a player perspective, when you first connect to the game and select an avatar to play, you will be given a map that is all the way zoomed in on the avatar you’ve selected. Depending on your screen size, you might be able to see perhaps 20 meters in each direction. You would then be able to click map tiles and interact with the game; a left click would move your character to the tile you’ve selected, and a right click would bring up a context menu that would let you interact with the tile (for example, by building a structure or harvesting a resource).

In addition to the map itself, I am envisioning a slide-out interface on the right side of the screen. When you move your mouse to the right border of the browser, an interface will appear that will let you perform other actions, such as chatting with friends, browsing your inventory, setting options and using the encyclopedia, as well as functional stuff like logging out.

I have explored the use of the HTML5 CANVAS element and I think for now at least I’m going to not use it. For one thing, it’s not universally supported yet and one of the primary motivators of Feralor was to create something that would work in all browsers. Another problem with it is that it’s not a terribly efficient way to handle graphics – it’s actually much more efficient to use a bunch of DIV elements put together like puzzle pieces.

I also explored the use of SVG to handle graphics and I think I will stay away from that for now too, as SVG support is not universal and more importantly it is implemented very differently (in some browsers, it’s an OBJECT, and in others it’s an IMG).

I will be staying away from the AUDIO and VIDEO tags for the same reason, which implies that for now there will not be any soundtrack for the game. That’s probably OK anyhow as I am not a musician and don’t have the bandwidth to deal with setting up that infrastructure for now anyhow. It’s more important for me to concentrate on the core components of the game like game play and user interface, and then we can add other elements like sound and video later.

Note: This was originally posted in the Feralor Development forum before that was all rolled into the WordPress blog.

Perlin Noise was developed by Ken Perlin and is used extensively throughout Feralor. More information on Perlin Noise in general can be found at:

http://en.wikipedia.org/wiki/Perlin_noise

In Feralor, Perlin Noise is used to generate lots of things, including:

- Terrain
- Resource Nodes
- Difficulty Levels
- Weather

By using Perlin Noise, we can have an infinite world with minimal storage requirements on the server and also allow much of the processing to be offloaded onto the client’s browser.

One challenge related to Perlin noise has been the need to build two separate yet identical versions of Perlin libraries: one in PHP (for the server) and one in JavaScript (for the client). Perlin Noise makes use of a “random noise function”, which is actually less of a random number generator and more of a hash function – for any given input, it needs to produce the same output. JavaScript does not provide an unsigned integer data type (or any strong data types at all, for that matter) which makes bit-wise operations hard to implement, and as it turns out most hash functions are dependent on bit-wise operations. Of course, PHP does not provide strong data types either, but it seems that PHP’s default is to treat integers as unsigned whereas JavaScript seems to treat them as signed by default.

One option I have not year explored is to use string representations of numbers (in PHP, using the dechex function, and in JavaScript using the value.toString(16) function) to effectively mask the effect of signed integers, but I have not implemented this yet and I have a sneaking suspicion that the resulting code won’t be quite as fast.

Another task that needs to be dealt with is selecting which hash function to use. Initially, I wrote some code that used an SHA1 hash which produced beautifully random-looking Perlin noise. However, SHA1 is not a lightweight function and the JavaScript implementation I found is probably too slow for actual game play. Other random number generators that I found in articles related to Perlin noise produced visually-apparent artifacts (like straight lines in the noise) that are undesirable. More recently, I have come across a hash function from Paul Hsieh that appears promising:

http://www.azillionmonkeys.com/qed/hash.html

But, at present, I have not attempted to implement this in JavaScript and PHP.

For my own reference as much as everyone else’s, here are some other pages with good information about Perlin Noise:

http://mrl.nyu.edu/~perlin/noise/
http://freespace.virgin.net/hugo.elias/ … perlin.htm
http://dev.horemag.net/2008/03/02/perli … or-in-php/

Note: This post was originally posted under “Technical Details” on the main feralor.com web site. I moved it here so that I could keep a coherent repository of all information related to the game but not directly part of the game experience in one place.

The original motivation behind Feralor was to create a fun MMORPG that was platform-agnostic, unlike almost all other MMORPGs out there that utilize a proprietary client which usually only works on Windows and Macintosh computers. By using only standards-based web technologies, I am opening my game up for the whole world to play from virtually any computer connected to the Internet without the need to install any client software or browser plug-ins.

Some would argue that I could us something like Java or even Flash to accomplish more or less the same thing. However, one of my design goals here is to sharpen my HTML/CSS/JavaScript skills as these are directly relevant to my day job. Also, I like the web as a content delivery mechanism and I don’t like Java or Flash (in part because they don’t run well on my FreeBSD workstations, and also because they’re essentially closed technologies, as opposed to open-source standards like HTML, CSS and JavaScript). Also, my game should run on hand held devices, whereas Flash and Java are generally not available there.

The game makes extensive use of Perlin Noise, I’m not sure if the implementation of Perlin Noise that I am using is faithful to the original design, but it is lightweight and functional and fixes one of the most significant problems that I originally ran in to when designing the game: storage. On even a moderately sized map of 10,000 meters by 10,000 meters with a 1 meter resolution, you would need something on the order of 100,000,000 rows of database storage at something on the order of a few hundred bytes each, making the storage requirement for the map alone on the order of a double-digit number of gigabytes. It also fixes the second larges problem that I ran in to originally: not only did I have to store that much data somewhere, but I had to be able to retrieve it in a sub-second amount of time at least once every five or ten seconds for each concurrent client connected to the system. So, if 100 people are playing concurrently, I’d have to retrieve a few hundred out of 100,000,000 rows of data 100 times every five seconds or so. From a computational expense standpoint, using procedural terrain generation is far more efficient. Plus, it has the added benefit of making the world infinite in size.