Archived Chaos

[archivedchaosblog]

Migration – COMPLETE!

I have finished migrating all the stuff from my old blog. Hopefully if I ever have to do this again it will be less painful / I can just reference this blog as a subdomain – old.archivedchaos.com or something. ENJOY!

[archivedchaosblog]

Collision Handling: My battle with Mathematics, Logic and Implementation (2013)

In my second year at University (2011) studying Computer Science, I decided I’d start making a game. I’ve always intended to get into game design/development so I figured now that I was actually learning to program, I should put these skills into practice. Here is the very first screenshot I took of it:

Even at this point it was already clear that collision handling was relevant. I actually wrote some code for this to allow the player to move and jump around on this rectangle. However, the difference between handling the collisions of a player with a fully-developed level and one constant sized rectangle is colossal. 

At first, Collision Handling and Collision Detection don’t seem like different things. I know certainly going into this project that my own reasoning was that as long as the player and everything in the level was represented by a rectangle, it should be fairly trivial to detect when these shapes are intersecting, especially when the engine I was using (as well as Java itself) featured a Rectangle.intersects() method for my convenience.

That’s the trap.

It’s not until you sit down to actually develop this interaction that you have the fatal conversation with yourself: “Okay, so if the rectangles intersect then… they should… actually, I don’t know what they should do.” It’s that moment you learn the difference between Collision Detection and Collision Handling. 

Collision Detection, for the most part, is a simple calculation, even for complex shapes in multiple dimensions; it’s the Handling part that’s tricky. If two shapes are intersecting or are about to intersect, what steps do you take to make them 

No-longer intersect?

Produce a satisfactory outcome for future interactions?

Allow me to briefly cover how this problem is generally handled most of the time. Observe the following diagram:

Rectangle A is attempting to move along the vector represented by the red arrow. If it does move to this position, it will intersect Shape B:

This collision has been detected, now to handle it. Traditionally, this will be handled in one of a few similar ways:

1.) "Rewind”

A2 is the result of handling the collision. In this method the shape is moved backward along it’s movement vector to a point where it no longer intersects. This has the problem of “freezing” the object upon collision. The only way for A to move at all is for it to move away from B, it can’t slide along the side of it. In this instance, if A were a player object and B were a wall, attempting to move Diagonally Up/Left would result in no movement. This type of solution is rarely ideal.

2.) “Fastest Escape”

In method 2, the result A2 is found by computing the smallest distance required to leave the intersecting shape. In this case, A2 is found by moving A to the bottom edge of B. This, for the most part, solves the problem of getting stuck against an object, as it allows Shape A to slide along Shape B in an attempt to move Diagonally Up/Left. You can see that if Shape A persisted in this direction its result would be movement directly to the left (the upwards movement would be cancelled), until it cleared Shape B. Despite these solutions’ popularity, they are fundamentally flawed. Observe the following:

In this instance Shape A is moving VERY fast. So fast, in fact, the system will not detect any collision before or after movement. At neither of these points in time is A intersecting B, thus, these shapes did not collide. Systems that use this methodology suffer from the limitation of being unable to handle fast-moving objects. To counteract this, many Systems run these physics calculations on a separate timer, often much faster than the actual graphics or logic ticks. In our latest example this would result in Shape A’s intersection with B being calculated at multiple points along its vector which, in this case, would probably detect and correctly solve the collision. If your Engine needs to support very fast objects, you increase the rate of this tick to make for more accurate collisions, at the cost of extra processor utilisation. If you are unlucky enough to be working in an environment that cannot facilitate this behaviour (by being either underpowered or limited technologically - working in a single-threaded environment, for example) then you cannot overcome this problem. Many years ago I asked a professional game developer how one may get around this problem. He told me that it could be solved using vector arithmetic. This makes sense, as vectors are continuous, not discrete, so theoretically one could use them to solve these collisions absolutely. As I was in my second year at university and had, at the time, already taken 2 or 3 mathematics papers featuring vectors, and their surrounding arithmetic, I figured I understood the mathematics enough to work out how to do this. I spent a long time thinking of different ways to achieve it; some ideas good, some bad. Eventually, the idea of how it would work formed in my head, as follows:

By testing for an intersection between A’s movement vector and each face of B, I could detect what face these shapes were going to collide along. I could then scale A’s movement vector appropriately to simulate a “collide-then-slide” result. It looks a bit counter-intuitive in this diagram as the result A2 isn’t actually touching any shapes. You have to remember that, in this instance, A’s movement vector is HUGE. If this were a game, A would be moving many times it’s own size per frame, which is a very high speed. This interaction represents, in-between frames, A colliding with B, then sliding off its bottom edge. 

However, I immediately started to run into problems, mostly in the form of counter-examples breaking my logic. For starters, where does A’s movement vector even project from? It’s clear in this case that it should come from the top left corner, but if it were travelling Up-Right, the result would not be accurate. I decided this vector should project from all vertices in the shape, since you can’t really collide edge-to-edge, right? If two shapes are colliding at least one of them has to be Vertex-to-edge. Wrong. I quickly thought of this counter-example:

If Shape A were significantly bigger than B, it could move straight past it without any of its vertices ever colliding with an edge on B. I toyed around with projecting A’s movement vector backwards from B, but eventually realised that I needed to project both ways in order to guarantee a detection:

Now the system would be able to detect any collision between any shape, and I should point out that at this point I was still working with Polygons, not just Axis-Aligned Rectangles. Eventually the vector projection onto arbitrary edges made things too complex, and I had to settle on the restriction of purely using Axis-Aligned Rectangles. I may make a post solely on AABBs and their use in physics simulations at some point. 

Now the system was doing really great, but I was still running into a few issues, mainly corner cases (literally). I was having troubles dealing with corner-to-corner collisions. This was a problem that stumped me for months, and caused me to restart my thought process from the beginning a couple of times. Every time I hoped to simplify the system so that I needn’t deal with problems caused by the corners, but every time they would show up and start causing problems anyway.

The first problem seems trivial, but it becomes important:

What happens in this case? It is indeterminate which faces of B A is colliding with, but I didn’t want to make allowances in my algorithm for this specific case. I wanted it to be treated like every other collision – ultimately it didn’t matter which side it went along, I was happy just as long as it went along one of the sides.

In comes the trouble:

In this instance, all vertices in the system that return a collision will return a collision at length 0. However, we still have one that we want to pick as the “correct” result. The corner-to-corner collision at the top may pick the wrong side (as I had previously determined I didn’t care which side was picked in a corner-to-corner collision, just as long as a side was picked). In this scenario, the top-left corner of A and the top-right corner of B are colliding with each other (corner-to-corner collision), and the bottom-left corner of A is colliding with B’s right side. This is the telling factor; we want to make sure we only pick the result of a Corner-to-Corner collision if we have no other choice. So, in the algorithm, whenever a corner-to-corner collision occurs, we flag it as a “Corner” collision and add it to the results pool. When the results are sorted for choosing at the end of calculating, we look for the shortest non-corner collision; if no results are non-corner, then we just take the shortest in the list.

Now the system was doing great, it could handle collisions between any 2 objects in a stable manner, but in implementation a problem quickly arose. Say Shape A is travelling like this, into 2 shapes:

2 intersections are detected. It’s clear that the intersection with shape B is the shortest, so the algorithm picks that face to “slide” along. However, this produces an erroneous result:

Result A2 has slid along the right face of Shape B after computing a collision, but is now intersecting with Shape C. We can’t take the result from Shape C either, since that would result in a collision with Shape B. The solution? Good old fashioned recursion. We re-call the whole algorithm again but this time, instead of making the request with the original request vector, we give it the result of the collision with B, like so:

Since this result has been calculated from a collision with Shape B, we can be sure that any subsequent result of this vector will NOT intersect Shape B. This request does not intersect Shape B, so our intersection with Shape C is our only result, producing the following:

Which is the result we want, representing a collision with both shapes. This recursion stops when the requested vector is equal in length to the result vector (i.e. if we run this calculation one more time and no further collisions are detected).

That’s the algorithm in its entirety. It’s not a lot of code once it’s all worked out, but it’s taken me a long time to work out. I did originally do research into some pre-existing algorithms but never felt comfortable with them, and I didn’t feel like I truly understood them. This has been a great learning experience for me. It’s an algorithm I see myself using for all my 2D collision handling needs.

If you have any questions about this algorithm or would like to see some code implementations of it feel free to comment about it or message me. Although please note I wrote this post in 2013 😂

[archivedchaosblog]

Terrain Generation in Unity3D (2014)

Since terrain generation was still my most successful program to date and it’s something I’ve inherently studied in-depth now, I decided that it would make a solid project for Unity, too.

I found a Noise library (implementing new and improved Simplex noise, also by Ken Perlin) written in C# and away I went.

It was a bit of a learning curve for me because I had no idea how Unity handled anything, especially Meshes or MeshFilters. Eventually I got it worked out and produced the screenshot above.

I had to actually port across one of the algorithms (”RidgedMulti” libnoise implementation) to C# to create the mountain-like shapes.

I decided to round the final output to discrete series, creating contours in the generation. It looked quite boring and smooth without, so I left it in for a while (it looked like Minecraft).

Thankfully Unity made lighting and shading a total breeze beyond the technical generation itself.

Next thing I wanted to learn more about was shaders. First one I ever “wrote” (basing my code off someone else’s) was a textured and lit mesh. Also note the mixing of two textures to the height of the terrain, this was all accomplished with a shader.

I had never written or even looked at a shader before, and Unity handles Shaders in a bit of a unique way, so getting this to work was a bit of an iterative process. Eventually I got it to blend two textures based on the alpha of a vertex. Setting the alpha of the vertices was trivial in the terrain generation, I just had to divide the height by the max height (i.e. convert it to a percentage) and then set the alpha of that vertex when I was creating it.

After getting the textures to play nicely I decided I should work on the terrain generation some more. I took out the Minecraft-esque contouring and added another fine, erratic, layer of noise to the entire algorithm and scaled it by the vertex’s alpha, so that higher-up (rocky) areas are more rough and better match their material.

I was developing this over a day and screenshotting pretty frequently which is why I have this project documented in such finely-detailed increments.

In this, latest, version of the Unity Terrain Generation project I changed the rocky texture to actually be stone/rock (instead of dirt) and added a SkyBox to the scene, changing the light colours/angles to match. I eventually ended up texturing the box shadow caster in the middle to be a Space Odyssey joke. 

[archivedchaosblog]

Getting Real – Unity3D (2014)

In 2014 I was occasionally attending a Game Developers meetup that was held each Month. From what I saw there, and from the multitude of job openings I’d looked at in Game Development, Unity3D was far more industry-standard than I had realised.

I’d been aware of Unity for some time but never personally used it, so I decided I should learn something about it.

This was the first thing I made in Unity. You could control the tall box with the mouse + WASD, and it changed colour once per second. Clicking with the mouse created a physics box with a random colour. You can shove the boxes around with your “character”.

Obligatory shadows + lighting because with Unity it was just drag and drop.

[archivedchaosblog]

DeltaTime in Love2D (2013)

On the second day of my project-week I decided to make some kind of 2d-platformer, with no real goal in mind. Spent a little while making a really retro background (drawn with a laptop nuben…), and managed to implement quite a nice player movement interface.

The reason this project never got very far was because I thought it was time I learned to use deltaTime in graphics applications properly, so my games can lag without slowing down. I took the frame limit off this game, and implemented the use of DT terribly :D But it worked.

The side effect was all I had to do was bind up/down to a scalar that multiplied DT and it would slow-down/speed-up time in the game. It was pretty awesome 😀

[archivedchaosblog]

AI Simulation (2013)

While I was on a break in Wellington one year, I decided to start spamming Love2D programs for the fun of it. Kind of like a speed challenge; it gets you motivated, feeling creative and makes for good programming practice. I made one program a day for a few days (the intention was to do it for a week); the last one actually resulting in a pretty promising game concept that I should post about on here some time (and is the reason I did not continue writing a project per day in that week).

Anyway, here is the first program I made. It’s some kind of AI Simulator. It’s in the style of Rock-Paper-Scissors. I wanted to create a system where AI would be constantly interacting with one-another forever, but was unable to create a system without a point of equilibrium.

It is basically like “this colour hates this colour hates this colour …”. Red shapes are being chased (running away from something chasing it), shapes with a Yellow highlight are chasing (following a red shape). A clear example of this is the Green Triangle chasing the Blue Triangle at the top.

Clicking anywhere creates a pile of random shapes. It’s interesting to see it evolve but it reaches racial supremacy pretty fast, wherein one colour has too many members to be overthrown as the “dominant” colour.

[archivedchaosblog]

Physics Implementation (2013)

Love2D, of course.

I was at a friend’s house and we were both poking Love2D. I decided to just make your standard Bouncing Balls program (The “Hello World” of 2D Graphics) for fun. After I did that, I added gravity to the balls. My friend then challenged me (read: I challenged myself) to make the balls collide with one another.

Since they were exclusively circles I figured this couldn’t be too hard. I poked around with it for about a day and managed to get it working pretty nicely. It had some bugs but it was quite impressive for a hand-coded physics implementation.

After finishing that I thought “Where do I go now?”. The only solution was “more complexity”. So I reprogrammed the physics to attract balls to the centre of the screen; it was mildly interesting, but nothing more than a change in the direction of the force of gravity.

My final challenge was to create a static “planet”-like circle in the middle, and have the balls bounce off this, a-la Mario Galaxy. It was tricky working with a static object exerting a force on the other bodies, but I got it to work eventually. It even simulated Orbits mildly well.

It’s always been a goal of mine to hand-code a physics engine so it felt good achieve this.

[archivedchaosblog]

FEZ Cube Language Translator (2013)

I picked up FEZ in early 2013 and absolutely loved it.

I loved the puzzle-solving aspect to it and decided to translate some of the Cube-Language text around the game.

I worked out the mapping to the English alphabet and thought it would a good idea to create a program to easily translate between Cube Langauge and English.

I very-nearly finished this program but I ran into some problems with wrapping the English text… I would like to see this finished some day even though the game is years old now, just because it was so polished / functional / nearly complete.

Also written in Love2D

[archivedchaosblog]

“Tasty Fungal Fun” (2013)

I never gave this project a proper title so I just referred to it as TFF – “Tasty Fungal Fun”; I got it off the side of a Grow-Your-Own mushrooms box.

This project was part of my Love2D crusade. I had an idea for some kind of microorganism/cell type game but was having trouble finding inspiration for it. In a move towards finding inspiration I decided to just draft out a kind of cell-evolution simulator program.

Clicking anywhere in the game area creates a seed, all seeds are the same but grow over time and will spawn children seeds around them that are slightly deviated in colour. This evolves over time as colour deviations are propagated through generations and colour strains start to form.

A cell can only spawn on an uninhabited (i.e. white) area, so eventually, the cells start to starve and die off, producing new cultures.

This is the same run of the game posted in the first screenshot but left to "grow” for a few minutes. You can see some new strains starting to evolve, the dark purple in the bottom corner and the cyan-blue next to it

It’s really great to watch it evolve over time.

[archivedchaosblog]

Intro to Love2D - Tower Defense 2.0 (2013)

A long time ago I read somewhere that Garry Newman (creator of Garry’s Mod) had used/admired a game engine called Love2D.

Love2D is for 2D game development running the programming langauge LUA.

I didn’t look into Love2D until a few years after I had first seen it recommended on Garry’s forums but one day I decided I should try it.

I immediately fell in “love” with it, and LUA. It was so simple to create really great, impressive projects.

This is one of the first projects I started in Love2D, I thought it was fitting to redo my original Tower Defense Game, but properly. This is as far as I’ve gotten with it, but it’s technically impressive. The towers are rendered on a Sprite Batch (i.e. FAST!) and have dynamic depth-ordering, something that plagued my original game.

Here you can see my krab-bot being obscured by a hastily-drawn tower because he is behind it.

[archivedchaosblog]

Terrain Generation and Perlin Noise (2013)

After I created the Minecraft Clone, I posted the 3 images shown in my previous post to Reddit’s /r/gaming subreddit. It made it to the front page and I got a lot of great feedback from people. People seemed genuinely grateful that I advertised the project as a "clone” of Minecraft, and I got a lot of questions about how I had written the program, how to program graphics etc.

After explaining how my crappy terrain-generation algorithms worked, a few people suggested using something called “Perlin Noise”, a technique developed by Ken Perlin to mathematically derive smooth, gradual “random” values from N-dimensional inputs, frequently used in procedural Terrain Generation!

I looked into it and found a library for Java. I soon integrated it with LWJGL and had it generating heightmaps for planes and colour gradients. Sampling the colour gradients I could set the colour on each vertex and render wild, realistic-ish landscapes. By the time i was done with this program, I had it flying over an infinitely generating terrain in real-time! It was beautiful 😌

[archivedchaosblog]

Minecraft Clone (2013)

After a long while using LWJGL as an interface for OpenGL I decided to start using the library properly and make something better than anything I’d done before.

I decided the ultimate project in LWJGL was Minecraft, seeing as Minecraft itself was written on LWJGL. I spent a few days getting the project to this point and I learnt a lot from it.

The terrain was a fixed size and used completely made-up algorithms for generation. I think they looked pretty good for being based on nothing.

This program ran pretty poorly, really. Through making it, though, I learnt a lot about optimising a renderer. I learnt about Occlusion Culling, drawlists and spent a lot of time squeezing every piece of performance out of it. Eventually I got it to run okay-ish, it even ran poorly on my crappy laptop.

It made me really appreciate how fast Minecraft is, even though it’s often slated as being slow because it’s written in Java.

Another view of the generated landscape. Of course, the landscape was different every time you ran the program.

The textures I used were just some generic textures I had lying around for games and such. Fun Fact: Neither of these textures were technically organic, the green was something like a tarpaulin sheet over a crate, and the grey was a metal cube texture.

[archivedchaosblog]

AI Program (2012)

This was an attempt I made to write an AI you could talk to. It was for a game idea I had where you talked to an AI which slowly divulged a creepy story. I think it worked pretty well, but it took a lot of development (I wrote an entire Visual C# editor just for the purpose of creating AI databases) to make it anywhere near believable.

It worked well because it was designed to tell a story, so the AI didn’t have to be able to respond to any garbage you typed, it encouraged you to stay “on-topic”.

[archivedchaosblog]

Pony Quest - A 2D Platformer (2012)

Pony Quest is a 2D platformer game project that I was working on for a few years starting while I was at University. I spent so much time on it because, well, when I started I knew nothing about anything. The whole project was rewritten twice to incorporate improving design foundations.

This screenshot in particular is very important to me; it demonstrates a stable object collision system I designed and implemented. It took me at least six months (on-and-off) to work out all the bugs in the system. I have a write up about it I will be posting here soon after I’ve finished making all these project posts. This picture took a lot of work to get and I’ve never been more proud of a duller picture. 

Early on in development I started co-developing a level-designer for the game. It worked pretty well, allowing you to design and export your own maps for use in the game.

The editor is written entirely in pure Java, which is quite an achievement if you’ve ever written GUIs using Java. It also implemented some kind of custom renderer to run the preview Panel which was displaying the game, or at least something that looked like it.

[archivedchaosblog]

Learning OpenGL (2012)

In University I took a paper on Computer Graphics which covered OpenGL as well as some 2D image filtering concepts. After I finished the paper I started to prod OpenGL in my own time.

This is the first test I ran. I did it in LWJGL which is a Gaming Library for Java that exposes OpenGL’s raw functions pretty directly. I made it generate the top layer of the HSL colour space.

Since I had already studied OpenGL in a basic form I was able to pick it up pretty fast. For my second project I implemented Shadow Volumes. They sucked! (a volume per object, which meant overlaid shadows. I tried for a long time to render them as one but I never figured it out…) but it was very satisfying to create such a basic building block of computer graphics by hand.

This was a while after the other two OpenGL tests. I decided to revisit something I’d tried to do a long time ago in a language called DarkBasic, in which I created a pile of randomly scaled buildings across a plane to create “random cities”.

The main difference for this project, obviously, was that I would be doing all the graphical programming myself. This was also the first time I had implemented a WASD-type flying camera in OpenGL which was tricky to think about at first.

I then enhanced the project, adding lighting to the scene, a “skybox” and miscellaneous detail objects scattered across the ground. It ran pretty poorly, there were no performance tweaks, it straight up rendered the entire scene all the time, haha 😬

The last thing I did to this project was turn it into an realtime-strategy type thing because, well, why not? I added a cursor (which is kind of hard to see in the picture but it’s near the center), which was a hand-drawn polygon (i.e. I typed the coordinates into the code myself) that mapped to the mouse position. This was my first time rendering 2D graphics at the same time as 3D Graphics.

I also took out the WASD flying camera and replaced it with a traditional RTS mouse-scroll movement 👍

[archivedchaosblog]

Minecraft DerpyBot (2011)

A while ago now I wrote a mod for Minecraft that added a “Bot” to the server to perform admin duties. This was mainly because I felt Minecraft’s multiplayer lacked a few features, so I decided to add them myself. Her name was Derpy and she could do all sorts of things like store teleport locations and preserve your inventory when you died (which was not a feature at the time).

My most proud feature on Derpy was her interface with CleverBot, which allowed players to chat with her. In the photo above she is singing the Team Rocket theme song with us, she was a lot of fun.

She could also be mean.

[archivedchaosblog]

Tower Defense (2010)

In Compsci 101 I wrote a Tower Defense game for my final assignment. It was written (terribly) in Java and featured infinite levels of increasing difficulty, it was quite fun! Albeit hard.

Harder monsters (circles) had more evil looking colours. Towers could be upgraded in terms of range, damage, projectiles per shot and rate of fire. There were two types of tower. A standard projectile-type tower and an area-of-effect one, which did less damage, in an area, obviously.

Still the only game I’ve ever “finished” 👾