A Game Engine From Scratch In JavaScript Part 2 – Physics

About 1-2 weeks ago I decided to make a game engine in my spare time. The most challenging aspect so far has been the handling of physics – how objects in the game behave when they collide.

I was able to get a few collision prototypes working. Here’s what the first prototype looks like, it could handle many moving objects, but the accuracy wasn’t perfect:

View post on imgur.com

Disclaimer: I do not own the graphics depicted in this article, nor do I have permission to use them in a commercial product. The graphics were found using Google Image search, and they are being used here solely for showcasing the engine’s capabilities and progress. The tree sprites are from Here Be Monsters, and the player/wolf sprites are from Ragnarok Online.

What you’re seeing in the screen capture above is a bunch of objects (wolf sprites) being spawned with a “roam” AI package, which just makes the objects move around. This AI package idea will be expanded upon later, but it’s kind of how Skyrim AI works, mixed with Final Fantasy XII Gambits – interchangeable and override-able behavior stacks for different scenarios.

(The screen capture above doesn’t reflect 60 FPS due to gif recording at the time. It’s also a .gifv image hosted by Imgur, my apology if the buffering is choppy…)

Overall Architecture

The central piece to the engine’s architecture is the game loop. It looks something like this:

function run() {
    handleInput();
    handleAI();
    handlePhysics();
    drawBackground();
    drawEntities();
    drawWeather();
    drawUI();
    window.requestAnimationFrame(run);
}

That loop will continue running until the game stops, and its job is to update the state of the game as time progresses. I won’t go too much into the other parts here since I wanted this article to focus on the physics.

How the Physics Engine Works

The red squares in the screen capture above define the collision boundaries for each object, and the squares should never overlap. However, this algorithm had trouble achieving perfect accuracy with a large amount of moving objects, and I’ll attempt to explain why towards the end of this article.

Depth-Sort the Objects

The main loop will first sort all entities in the scene by their positions on the y axis (entity.y), putting the objects which would appear furthest from the player at the top of the sorted list to create a back-to-front draw order, ensuring that the sprites overlap correctly based on their perceived depth. This part works flawlessly.

Simulate Object Movement

Next, the engine processes all of the objects to determine their new (desired) positions. Some objects might be moving faster than others, or not at all. Some objects might collide with others due to these movements, but for now we ignore any collisions and just allow the objects to overlap. The collisions will be resolved before the scene gets drawn, as we are still processing the physics for a single frame at this point. It seems like a lot of work, but the computations are rather trivial for the CPU when compared to the canvas draw calls and work being done by the GPU, so the physics shouldn’t become a bottleneck for quite some time.

As stated earlier, the objects move around using a “roam” AI package, which just selects a new position that the object will move to, and repeat it again once the move has been fulfilled.

Partition the Space

The next step is to store all visible objects in a 2d tile array based on their positions. This is a simple spacial partitioning technique that speeds up collision detection by grouping nearby objects so they can be tested against each other instead of the whole set. It’s like a quad-tree, but computationally simpler.

Detect the Collisions

Now we have a minimal set of objects that should be tested for collisions against each other. We then walk the array of tiles, testing each tile’s objects for collisions against other objects in the tile. You might be wondering, what happens when an object partially occupies two tiles, or four tiles in the case of being on a corner? When we store the visible objects in the 2d tile array, we make sure to store the object in every tile that it intersects. This allows us to detect objects that are colliding across or being pushed across tile boundaries.

Resolve the Collisions

Once objects are found to collide, we can resolve them using the data provided by our simple collision detection algorithm which does a rectangle intersect test and provides us with a width/height that tells us how deep one object penetrates into the other when overlapping. All we do is move the offending object outside of the object it would be overlapping. We move the object “back the way it came” at a distance equal to the penetration depth, so now the objects should be touching instead of overlapping.

There are a few problems with this approach to collision resolution. By far the most common issue is that objects can pass through each other if they have a high enough movement speed where one object would pass completely over another object without intersecting it first.

The next issue is that we are treating one object as the “offender”, and this is the object which gets moved “back the way it came”. But what if both objects were moving and they are both offenders? What needs to be done differently here is move both objects back the way they came. While the first problem doesn’t really crop up in the screen capture above since the objects don’t move very fast, the second one is a major issue that is probably causing some inaccuracy. I will definitely be looking to improve this aspect of it later on.

There is a third serious issue which I haven’t mentioned, and another method worth mentioning. Consider this section incomplete.

Iterate

Up to this point we’ve basically covered a single iteration of the physics step, and we might be ready to draw the objects now. Before that though, we can actually run the physics step multiple times to account for the small changes being made by the collision resolution algorithm. By running the physics multiple times we can check for collisions a second, third or fourth time before assuming every object has been fully corrected so as not to collide with anything else. Many physics engines work this way, but I’m thinking there may be a way to avoid the iterations completely.

Unfortunately, there wasn’t much difference in the accuracy of collision detection and resolution algorithms when running 50 iterations vs 5 or 10 iterations of the physics step per frame, so I chalked it up to certain parts of the algorithms being at fault. The algorithms performed well at 2 to 10 iterations per frame, but could achieve 50 iterations per frame (!!) with 400 objects in the scene without dropping below 60 FPS on a budget computer rig. Not bad.

This was a good start, but it didn’t satisfy everything I wanted to do.

For Mass Amounts of Objects, Use Mass!

Like the prototype above, I’ve discovered that many of the existing collision detection/resolution methods described on the internet tend to break down when you introduce multiple moving objects, and games will be carefully designed around these limitations so they don’t appear, even though the limitations are there in the code. For example, most games wouldn’t have more than a few moving objects in the scene, let alone colliding with each other all at the same time. Which means the prototype shown above might already satisfy the needs of some games.

For this engine I wanted to build something flexible, and the prototypes I had tried thus far just weren’t that flexible. This meant wrapping my head around some physics concepts and I’m not very good at math, so something warned me I wouldn’t be much better at physics. Anyhow, I tried a few more prototypes and landed on an interesting side effect – the collision resolution algorithm was allowing objects to push other objects around.

I tested this a bit more and studied the code that was making it work. It turns out the code was only feasible for object-to-object collisions, but not object-to-object-to-object collisions. That’s when I had to toss out the algorithm and start over. Not to say the previous algorithms were a waste, I mean to say one must save his work, clean his slate and just start over with a clear mind. Each algorithm feeds into the next.

Eventually, I ended up with a new concept, and another prototype:

In the screen capture above, I’ve decided to give the objects a new property called mass. The tree gets a mass of 1000, the wolf a mass of 15, and the player a mass of 50. To put it simply, the wolf can’t push the player or the tree, and the player can’t push the tree but it can push the wolf.

So what happens when the player pushes the wolf against the tree? The tree should stop both the wolf and player from moving, due to its mass. We make this happen by imparting the tree’s mass to any objects touching the tree. It means the wolf inherits a mass of 1000 from the tree when touching it, which means the player should not be able to push the wolf or the tree. It also means the wolf imparts the tree’s mass onto the player.

This idea of objects having their masses imparted onto each other when touching is something I made up to get the algorithm behaving a certain way. This could also be looked at as objects having a certain resistance to forces (being pushed or pulled). It’s probably nothing close to real physics, but it could be the start of something. As Wikipedia states:

“In physics, mass is a property of a physical body which determines the strength of its mutual gravitational attraction to other bodies, its resistance to being accelerated by a force, and in the theory of relativity gives the mass–energy content of a system.”

Where To Go From Here

There’s a big problem with the last example which uses mass. When the wolf inherits the tree’s mass of 1000, it means the wolf is rooted to the tree, so it cannot be pushed away from the tree, it’s stuck there. To fix this, we could apply the mass in a certain direction only, so if the wolf is pushed away from the tree, it inherits no mass from the tree in that direction. Actually, it makes more sense if we say that the wolf inherits a resistance of 1000 mass towards the west, so we could check for this resistance before allowing the wolf to move west.

We also need to make sure that if the player (50 mass) tries to push 4 wolves (15 * 4 = 60 mass), the player should be stopped or severely slowed down by the accumulative mass of the wolves.

We could also add more modifiers for realism, such as terrain friction which could be done by setting a friction value for each tile, and the friction would work to slow down the player while attempting to push an object across the tile.

And what about effects such as gravity wells, vacuums or quicksand which pull objects with mass towards them, or magnets that attract/repel certain types of elements? These things would require a lot of special circumstances in the code, or a robust physics implementation.

History

This engine was built from scratch with Javascript and HTML5 canvas. It requires no external libraries or frameworks. It is the spiritual successor to a DirectX game engine I was building over 10 years ago which got put on the back-burner when I started learning web development. Here we are now, finally resuming that passion and life-long goal.

Related

Tags: , , , , , , , , ,

Leave a Reply

Your email address will not be published. Required fields are marked *