I’ve been rewriting the collision detection system for the last few weeks.  I have looked at several different collision detection algorithms over the years but the one that I keep coming back to is in a paper by Kasper Fauerby at peroxide.dk called “Improved Collision detection and Response.”  The primary reason I kept going back to that one is that it included information on the response step, not just how to detect collisions.  Unfortunately, it’s a little tough to follow in places and his code listings are in C++, so taking those and converting them to Javascript has been tricky.  After several attempts with varying degrees of success, I think I finally have it working.  I have a test scene with a sphere that just moves around the x-z plane.  I placed a few primitives (boxes and spheres) and a more complicated object modeled in Blender into the scene.  Without gravity it appears to be working perfectly right now.  The algorithm handles multiple objects close together and non-convex objects as well.  I only have a few objects in the scene but I don’t see a significant impact on performance so far.

This is very, very exciting as is but there are several things I need to implement or improve:

• Code refactoring
  • Up to this point I’ve been trying to transcribe the paper’s C++ straight into Javascript just to keep things simple.  There are some C++ conventions that just don’t make sense in Javascript (like reference variables) so I would like to rewrite the whole thing.
• Gravity
  • The Fauerby paper actually includes some information on how to implement this, so hopefully it will be easy.
• Broad phase collision detection
  • The current implementation runs the rather expensive collision detection algorithm on every object in the scene on every frame.  This is fine for a very limited number of objects but I need to implement a broad phase that can quickly eliminate objects that are far away and thus cannot collide with the player.  THREE automatically generates an axis aligned bounding box (AABB) for every object in a scene, so checking against those is likely the way to go.
• Spatial partitioning
  • In addition to a broad phase, I would like to use something like an octree to further optimize the collision detection system.  There are lots of good articles on this concept, but I probably won’t implement this immediately.

There are other things to do but these are the big ones.  I’ll probably spend the next several days rewriting the code, then stick in a broad phase check, then put the code into the game.  After that I’ll work on gravity, and save octrees for another day.

Overall I’m very excited because a reliable collision detection and response system will allow me to make a basic world that feels interactive.  I can then build off that by adding more “game” type features.

Undoubtedly the biggest frustration I’ve had working with THREE.js is loading and animating objects modeled in Blender.  The tools just aren’t very polished yet and it drives me crazy that so many things work so well but that process is basically broken.  I’ve noticed on my older development machine that the created SkinnedMesh objects work differently than on my (somewhat) more powerful machine.  Specifically, I get this weird jittering action on loaded gLTF objects whenever the object is any distance at all from the origin.  This is a known issue in THREE.js and has to do with matrix transformations being performed in world space instead of local space, but I’ve looked at the code and I get lost immediately.  I just don’t understand the animation system as a whole well enough to contribute anything of value.  It doesn’t happen on every machine, which makes it all the more frustrating to troubleshoot and makes me wonder what else behaves differently on different platforms.  One of the primary advantages of using a browser and WebGL is (I thought) consistency across platforms.  It’s still open as a bug in THREE.js, so I’m hopeful that it will get fixed one day, but for now I will just see weird jittery animations sometimes because it isn’t worth the time to try and find a workaround right now.

My next step is to do a little painting of the Penrith terrain, just so it looks a little nicer.  Then I’m going to tackle collision detection again.  That’s always been a big hangup for me but if this project is ever going to get off the ground I absolutely must have a reliable way for players to collide with and react to objects in the world.

My new machine isn’t here yet.  I’m expecting it Saturday.  Still, I’ve been diving back into the codebase the last few days and continuing the reorganization project.  I’m now back to basic “walk around the map” functionality.  No collision detection, other than not falling through the terrain, but you can zoom the camera in and out.  I’ve also been working on some of the substance of the game since I really need to know what I’m building at this point, so that’s been helpful.  Penrith will still be the game’s starting area, but I have the first region semi-mapped out and a general scale for the whole game.  Lyridia is going to be a big place.  Or, at least it can be a big place.  The island is about 10,000 km².  That’s roughly the size of Jamaica.  Of course none of it will actually exist until I make it, but that’s the plan for now.

I’ve ordered the components for a new computer to use for game development.  I have been working on an old machine that was generally good enough, but I was just getting tired of it.  I ordered everything around a week ago and I’m still waiting on a few things to show up.  Once everything is here and the new machine is built I’ll dive back into development on the game.  I’ve been a little lazy/distracted the last few weeks but I’m definitely planning to pick back up soon.

I was able to implement the ability to save heightmaps and colormaps in the new world editor pretty quickly.  This is just a quick draw in the editor, so it’s definitely not a finished product and it doesn’t even look exactly like the game because it’s rendered by the editor, but check it out:

You can see here that I was able to draw some green for grass, put in a very basic path, and then put some snow on those little mountains in the background to the left.  You can also see the weird orange color I used as a base and didn’t draw over in the background to the right.  I’m really excited about this because I can now easily make terrains that are interesting and colorful, and that should allow me to really start fleshing out the world a little better.  Without a tool to mock things up, it’s sometimes hard to even imagine how the world will work, but now I can make assets for the world then just place them in an area and tweak both the asset and the world around it.  Super exciting.

I made progress on the tools to paint colors onto the terrain tonight.  Right now you can select the terrain then press ‘p’ to enter paint mode, then use a color picker to select the color you want to paint, then just left click and drag the mouse to paint wherever you like.  It really works quite well.  You can pick as many colors as you want and the editor stays interactive, although I did discover that if you make the selection circle very large it bogs down quite a bit.  That’s not really a problem, and could probably be optimized in the future if there’s ever a reason to do so.  You can’t save the color map for now, but that should be easy to implement.  I would like to add some simple convenience features soon.  For instance, I would like a toggle that allows you to paint with each face randomly different from the picked color by a very small amount.  That way when I paint, for instance, a large expanse of grass, each triangle should be a slightly different shade of green and I think that will make it more interesting.  Also, it would be nice to be able to temporarily hide the non-terrain features on the map, like buildings and trees.  It’s just easier to paint terrain without stuff in the way.  There are probably other features I will think of later, but for now I’m just super excited to have a toolset that is really coming along.  Once I can save the color map, I’ll really be in business.

I’ve been rewriting the editor but also adding in new features and the most exciting thing so far is what I’m calling a color map.  This is an image that defines the color of each individual triangle on a piece of terrain in the world.  Right now the editor will load in a color map and color the terrain appropriately, but I have to use an image editing tool like GIMP to actually create the image.  The next step is to add in some terrain painting tools so that I can change the color of the terrain right in the editor, then just save it.  This is really fantastic because it maintains the flat-shaded, low polygon look, but allows me to make terrains that are very varied in terms of color.  I can make paths, snowy peaks, beaches, meadows, etc. without textures.  The color map images are very small.  The world terrain consists of right triangles.  The short sides of those triangles are 8 meters long.  So, a 1,024 m x 1,024 m chunk of terrain consists of 256 x 128 triangles.  (Think about it.  Each row of squares in the terrain will have two triangles per square, but there are sill only 128 columns.)  Each triangle needs just one pixel to store the color of the whole thing, so my test color map is 256 pixels x 128 pixels and right now is less than 18KB as a .png file.  That size will probably grow as I add more variation to the map, but in any case we’re looking at some pretty tiny files to produce a (hopefully) interesting looking world.

I had created a decent amount of content in a wiki some time back but at some point I removed the wiki.  I reinstalled today, and fortunately it looks like I was able to recover all of the content saved in the database.  This doesn’t include any images, but that’s ok.  There weren’t many anyway.  The wiki looks like garbage right now, but I think that’s an important resource to have for me because creating a world is a complicated task and putting everything into a wiki as I’m making it helps me stay organized, and also gives users a peek at what the world will entail eventually, plus it could be a resource once the game is actually playable.  The wiki is publicly viewable, but you can’t edit anything right now.  That will probably change eventually, but it works this way for now.

I’ve slacked off the last few weeks as far as development goes but I got back into it tonight and made some good progress.  The world editor needed to be rewritten from the ground up and I’m still in the middle of that.  Even though that’s not done, the rewrite has already provided some better organization so I was able to add in a few small upgrades during the process.  Specifically, when you move an asset around in the world now there is no need to pick an axis along which to move.  Just right click on an object then move the mouse around and the object moves like you would expect it, regardless of how the camera is oriented.  This is a major improvement because moving trees and such before was a pretty big pain.  Also, when you move an object it automatically stays on the ground.  You can then specifically move it along the Y axis if you need to, but generally most things are going to be on (or near) the ground.

Tomorrow I’ll continue cleaning up and reorganizing the world editor but the next major improvement I need to add is a simple terrain painting tool.  That will actually be really fun because once that’s done I should be able to make some content that’s actually worth seeing.

I’ve been messing with the terrain in Lyridia recently because it needs work.  After some general indecision I decided it would be best if I could set the color of each face individually, that way I can add some painting tools to the world editor and just paint in paths or grassy patches or snow or beaches or whatever.  As a step toward that I needed to just figure out how to set the color of each face, and what better way than with a different random color assigned to each face!

This obviously looks a little crazy but I kind of like it.  I could see a part of the world where the terrain looks something like this all the time.  Maybe in a truly chaotic place, or maybe this is how you see the world if your character eats a hallucinogenic berry.  Lots of options.  The main point, however, is that setting each face’s color programmatically is totally possible.  That’s good because this way I can keep the low-poly style, but still add in some details to keep the terrain from just being a green blob.

Update:

I have also tried shading the terrain with vertex colors instead of face colors.  The neat thing about this approach is that WebGL blends the colors between the vertices so that if I want to draw some snow on a mountain, I can take the length of a triangle to transition from gray to white.  Or if I want to draw a path then the sides of the path can fade from brown to green.  This might take away from the low-poly look, or it might enhance it.  I won’t really know until I get some actual painting capabilities built, so my next task is to rebuild the world editor.