Launch!

CS488 F2011 A5 – WebGL Strategy RPG Engine

Originally published December 5, 2011. Last edited September 16, 2015 (adapted for this website's layout).

Topics/Keywords

  • Texture mapping
  • Texture atlas
  • Bump mapping
  • Procedural terrain
  • Water reflections
  • Camera on spline
  • Phong shading/lighting model
  • WebGL
  • OpenGL ES 2.0
  • Pathfinding
  • Perlin noise
  • Procedural content
  • Context-free trees

Contents

Introduction

For the final project of CS488 offered by the University of Waterloo, the students are instructed to set 10 computer graphics related objectives they need to achieve. The instructor and TAs review this objective list and interact with the students to determine if it is sufficiently difficult enough to implement. I'll discuss the objectives I chose here, those I accomplished, those I could not, and those I chose not to implement and why.

To the reader: I do aim for correctness, but unfortunately cannot guarantee it. If you'd like to e-mail me at ar.cameron@gmail.com I'd be glad to respond to any concerns regarding accuracy.

Initial Vision

You can view my proposal here. For purposes of this report, I'll focus on those objectives I did accomplish, as well as provide some discussion as to how those I did not implement might be attained.

The inspiration for this style of game were others like Final Fantasy Tactics, Ogre Tactics, and Disgaea. Please see those games for the type of gameplay I anticipated this engine being useful for.

However, I wanted to somehow bring something of my own to this genre. Many of these games would seem to suffer from needing to have maps completely designed by humans. I figured that it would be nice to allow the developer to perhaps offload some of this work to random noise, perhaps tweaking the random terrain. It was my hope that intriguing and believable landscapes could be created with very little or no modeling hours.

I also wanted this engine to be playable on just about any computer without the need to install or update. To me, WebGL seemed perfect for this: as long as the user has a browser that supports the technology, and adoption of such browsers will only increase going into the future, then it should be very easy to extend this project to be a playable game.

I also wanted to explore real-time rendering techniques and interactive modes by making an entirely GPU shader driven project. I had heard great things about what they could be used to accomplish and have definitely come to respect their

Since the environment is WebGL, the focus then is (hopefully) doing things in a smart way to provide interactive framerates in this reduced environment. There is a constant struggle, as many allowed OpenGL features are not available in the current WebGL context. Of note, Texture Arrays, and even GL_QUADS were unavailable to me.

Finally, I initially started this in C++. I quickly became frustrated with the lack of easy anonymous functions and re-compiling. JavaScript, while perhaps hundreds of times slower, allowed me to develop this prototype as quickly as I did.

User Manual

Running the application

  1. Simplest: visit this page while running the latest Chrome or Firefox
  2. Via local files: it would be nice to download all the files and just double-click the index.html and have it run, no? However, due to browser security policy CORS, this isn't possible without doing something else.
    • Either start up a local proxy or local web server to host the files, and work through that
    • Or: Find out how to disable web security for your browser of choice. In Chrome, this is "--disable-web-security" flag provided to the executable.
    Without doing at least one of those things, you will be unable to see textures.

Using the application

  • Q, E keys will rotate the camera about the various corners of the game. You may want to wait for one rotation to finish before pressing it again!
  • W, A, S, D keys will move the camera in space
  • Mouse towards top/bottom of game area will change camera elevation
  • Mouse towards left/right of game area will rotate camera
  • Mouse wheel scroll will zoom in/out
  • When the game is active, and the menu is up, you can select Move/Attack/etc. However, only Move works. Press Enter to being picking your move, then use the arrow keys to select a destination, and enter to finalize your move.

Technical Outline

Bump Mapping

Terrain bump mapping is accomplished by consulting 2 near neighbours for the corresponding fragment. These differentials are then used, with a scaling factor, to perturb the surface normal in tangent-bitangent space. This process occurs in the fragment program.

Water bump mapping is accomplished via Phong normal interpolation. This process occurs in the vertex program. The tangent-bitangent space is not necessary as the water is planar, so the normal is purely modified and then interpolated for fragment processing.

Texturing

Terrain texture is consulted by means of a texture atlas. I would have liked to use a Texture Array or even a 3D Texture, but these features were unavailable in this GL context. Depending on an attribute signaling which type of block it is, the texture UV coordinates are altered to index into the correct texture. Texture atlasing was a major pain for me, so you can still see some colour bleeding due to the texture interpolation mode.

Sprite texturing is a straight-forward case of consulting a texture. Nothing special is happening here, except alpha blending to hide the rectangularity of the sprite. I would have also liked to use atlases here and animate the sprites, but there was not enough time.

To perform water displacement, I consult 2 textures, the gradients and the permutations of Perlin's improved noise in the vertex program. This is a parallel-processing port of his normal algorithm that allows me to calculate the noise in real-time. I've ripped the basic technology from my earlier work at http://anthonycameron.com/lab#perlinshader

These same gradient/permutation textures may be used in other places, for example, to add some more fine detail in the texture/normals of the waves. Or, it could be used as a basis for more procedural textures.

Procedural terrain modeling via combinations of noise and blending functions

3D improved Perlin noise and a blending function are combined to produce what resembles a terrain. The noise is continuous, so it must be discretized. The discretized results are stored in a look-up table (LUT), of resolution^3 size, where resolution is developer specifiable. This LUT is consulted for tessellation of terrain. A clever algorithm is employed to minimize the hidden surfaces that effectively result as we carve out the landscape in discretized chunks.

Camera animation on splines

2 Catmull-Rom splines are created. The first, position, is just simply a linear interpolator, so I'm not sure why I even used a spline. I suppose the motivation is to allow for changing it to something else in the future. The second spline, velocity, modulates the evaluation of the first, and the end result is a camera that moves somewhat more fluidly than pure linear interpolation. To note: my splines are limited to just 4 control points.

AI pathing

You can see the pathing system at work with the 2 characters on the game board when you select the MOVE option.

When the game starts, it consults the LUT of the terrain to determine which positions are "standable". A position is standable if it is air and below it is ground. More complex rules would allow for checks to character height – perhaps another constraint would be to make sure there is n blocks of headroom for the character to occupy.

The result is a map in [x,z] of same dimensions as the [x,y,z] LUT of the terrain. In each square is an array of >=0 possible y-values that a character might occupy. I call this map the pseudo-heightmap.

To path find, a feeler is sent out from character position [a,b,c] to the 4 immediately adjacent game tiles. Each feeler might add >1 path segment to the currently generated path, for example, if there are >1 possible standable spots for that particular [x,z] point. The process repeats recursively from the newly added segments.

A segment is only added to the path under some specific stipulations. First, it must not already exist in the path as a shorter path. Secondly, it must be within the character's jump height. There are some other stipulations, but please refer to game.js if you're curious.

The recursion halts after a maximum number of "steps" has occurred, here referred to as the character.MOVE_DISTANCE.

This pathing system guarantees that, between 2 squares that are game-legal for a character, the character will generate the shortest path.

I've used the splines I created for the camera system to animate the position of the moving character. I put a slight bias on the first and last control point, depending on the relative heights of where he is going to and coming from, so as to give the appearance of him jumping.

Reflections on water surfaces

The terrain is flipped about the plane that represents the water. Then, it is translated by the world-height of the water plane. It is rendered to an off-screen render buffer of 512x512. The same viewport dimensions are used.

This off-screen render buffer is then consulted as a texture in the water fragment shader. The texture coordinates are calculated in screenspace: as gl_FragCoord.x / 1024.0 and gl_FragCoord.y / 1024.0. I'm not certain why 1024 seemed to provide the best results, because I would have thought dividing by the context viewport dimensions would yield UV in [0..1]. I have a hypothesis that it may be related to 1024 being a factor of 2 more than the render target resolution, namely 512x512.

The texture coordinates are then altered by the interpolated water normal. This allows the reflected scene to appear to warp and bend, which we expect to see when we look at turbulent water. The water is then shaded as per Phong shading.

I'm pretty sure the water reflections are highly hackish, but they produced somewhat compelling results.

Trees

I wanted to create some kind of context-free tree. I didn't actually go about created a grammar or anything of the sort. I just defined a few simple rules. I will now describe these rules to you, because I feel that is the best way to explain these trees.

A root segment is created with a defined number of iterations. Some simple rules are used to recursively generate the rest of the segments. In my demonstration, all segments are the same length.

The branching recursion terminates if the max iterations has been reached. N branches are added. N is calculated randomly, but is biased by the lifetime of the tree. For instance, as the iteration count increases, the maximum possible value of N decreases. For each new branch, 2 random rotations are applied to the up vector [0,1,0] to produce something like a conical distribution. The extent of these rotations can be controlled on a per-axis basis. The new segment is produced, with starting point equal to the ending point of the previous segment. The new segment's ending point is determined by this randomly rotated vector.

If you remove the randomness, it easily creates a fractal tree. If you remove the conical distribution and reduce the extent of the rotation, it easily creates a fractal fern.

The tree branches are rendered with colours determined by their segment iteration. The higher the iteration, the more the channel green contributes to the colour.

Bugs / Caveats / Cautions

If anything breaks or stops working, just try to refresh (F5) the page.

I'd give the program some time to appear to finish "working" after the execution of the significant animations. Namely, these are the Q,E keys (rotation about spline) and the character MOVE option. This is because JavaScript doesn't really support any kind of threaded model, and instead events are queued in what I would call a ridiculous way: they're all queued at once, but with different timeouts. Queueing up more before the first queue has finished is probably what breaks it.

Moving with W,A,S,D and then attempting to rotate (in any capacity) will seem to be / is buggy. I'm not happy with the behaviour.

Point sprite characters: If you zoom in too much, they will become very small. They should be a constant size, but this is surprisingly harder than I thought it'd be. At least they stop growing after a certain point when zooming out!

Texture atlasing with OpenGL2.0 is a pain. If I used the nearest neighbour texture filtering, you would not see those lines that appear on the terrain where one texture bleeds into the next. However, it also looks more like crap. Texture Arrays are not supported, and texture atlasing, I have concluded, is the work of a demon.

Future Work

  • Networking could very easily be achieved by using the browser's suite of networking tools to provide for saved game storage and multiplayer.
  • HTML5 Local Storage might be used to store the results of any significant computations, such as the look-up tables used by the noise or current game state.
  • Application source update delivery would be trivial by simply changing the pages involved.
  • The scope of the project should be kept 'rather light' so as to avoid horrendous situations like repeatedly transmitting complex meshes over HTML.
  • Use a spline with convex-hull property for camera animation and character movement
  • For the reflection map, reject those items that are below the water surface. This would probably be best accomplished through creation of a new shader, and this new shader could have intensive features like bump-mapping disabled.
  • Tessellate the trees, perhaps sampling 1 circle randomly and using that as a piecewise approximation to a cylinder. Use this circle as the top and bottom face for each of the segments.

Code Map

Third-party code

jQuery: Was very useful in the UI related aspects, binding events to keydown, mouseenter, click, and so on.

jquery.mousewheel: Another library that might not provide complete support for all browsers. I suppose mouse scrolling is something that isn't very well supported by the browsers?

gl-matrix-1.1.js: Basically, the JS port of the algebra library. I did not want to port the entire algebra library if it already existed.

Scene

scene.js: A skeleton for a scene.

small_grassy_game.js, big_terrain.js: The content of these files are executed depending on which option you select in the select box. These are probably what you might want to play with.

Application relevant

perlin.js: CPU implementation of improved Perlin noise. Consulted in the LUT generation phase of terrain. This is a port of Ken Perlin's original code that I did a while back.

*.js: All other files have descriptive names of the feature sets they implement. Please see the files themselves for more documentation.

References & Acknowledgements

The following were of use to me in the implementation of this project. I'd like to thank these authors for their great work, and apologize to anyone I forgot to mention here; I've probably forgot many in my haste.

Papers

  • Blinn, J F. (1978). Simulation of wrinkled surfaces. ACM SIGGRAPH Computer Graphics, 12(3).
  • Gustavson, S. (2005, March 22). Simplex noise demystified.
  • Vlachos, A. Isidoro, J. Oat, C. Rippling Reflective and Refractive Water. ATI Research.

Web References