Top-Down RTS Game Engine in Vanilla JS
Pretend it's the 1960's. On the surface, the United States and the Soviets are locked in a space race to be the first to the moon. But, secretly they've both already established bases in space. You're a commander with a secret space force waging war throughout the solar system.
That's the world of Battlezone, an Activision game I grew up playing.
Battlezone was a rare breed of game which was both an FPS:
and at the same time an RTS:
(Quick note: The methods here come from my personal research into building a game engine. My background is in software engineering but not in game development. These solutions and implementations are not necessarily correct or optimal.)
Movement & collision detection
Starting from my working game loop (which was already capable of rendering shapes), the first step in this project was to make it possible to move entities around. Instead of WASD translating to North/South/East/West on the canvas, those commands would now be relative to the entity being "driven".
To begin understanding how to check for collisions between objects, I added a basic radius check. If the distance between two objects is less than the sum of their radii, then their bounding circles must be overlapping.
It isn't perfect but it does allow me to stress test the number of comparisons relative to the number of entities.
But this just terminates after the entities collide. We need to have the objects react to the collision in a useful way and keep the game going.
By using a basic elastic collision we can have our driven entity bounce off with equal force to the impact.
Increasing the number of entities, however, results in an increase in the number of collision checks. You can imagine that each entity is a vertex on a complete graph, and each collision check is an edge.
(n(n-1)) / 2 collision checks for
n entities. This is fine for a small game, but if we had 1000 entities then we'd need 499,500 collision checks. That's a lot of computation to perform every 60th of a second. Maybe we can find techniques to reduce the number of checks performed.
A quadtree is a data structure that allows us to subdivide the canvas into four quadrants, and then subdivide those quadrants further as needed.
With regards to collision detections, we can use a quadtree to reduce the number of comparisons being done. Simply put, if two entities aren't in the same quadrant, they can't possibly be colliding, and we don't need to compare them.
This allows us to add more concurrent entities to the game.
This still works when we turn the collision behavior back on for every object.
Even when adding the elastic bouncing resolution back in.
From Cartesian to vectors
The prior demos all used independent variables for the X and Y velocity for each object. This was rooted in the legacy of the game engine which only worked in Up/Down/Left/Right movements.
Unfortunately that results in some ugly functions responsible for determining how much to modify each of those velocities after each collision.
A better solution is to use vectors to indicate the motion of each object. Here we specify an angle (theta) and velocity (magnitude). We're still using two variables, but now we can use basic vector addition to compute the results of collisions and accelerations.
Better collision detection
Now this engine has the ability to track and draw hundreds of entities at the same time. But recall that we are still using a primitive collision detection: The radius check.
It's time to update the code to actually check if two rotated rectangles are touching. This would be a simple AABB overlap checking algorithm, if we didn't have to handle rotations. Because we are allowing rotations, we can instead check if the line segments that make up the borders of each rectangle are intersecting.
The downside to this is that we would now have to run several calculations to check each of the sides of every pair. To avoid that we can create a hierarchy of checks.
- Start with entities in the same quadrant.
- Check if their bounding circles overlap (quick).
- If so, check if any their edge lines intersect (less quick).
Looking at gray boxes sliding around is fun and all, but a space race RTS game needs some sprites. I first experimented with adding sprites in my RPG game engine and it was time to add some here.
Dynamic viewport & tracking
Everything up to this point has occurred within the same 800 by 600 pixel canvas. Not exactly the largest game world...
To make a world worth exploring this engine would either need a much larger canvas, or the ability to scroll around and see different parts of the map. I chose the latter.
With some updates to the size of the world and logic to offset where the objects are rendered, we can extend the game beyond the borders of the canvas.
With this change, we're wasting time and resources if we render objects that aren't within the viewport. One additional change was needed to update the rendering logic so that only visible objects are drawn.
Trying to improve collision resolution
I'm beginning to understand some of the challenges in a 2D physics engine. One of which is that resolving collisions can be difficult.
I haven't drawn attention to it, but in the prior examples it was sometimes possible to get entities stuck inside each other. To fix that the code was updated to push entities completely outside of each other before giving them their elastic bounce.
Guns, sounds, and destruction
Finally, it's time to start making this feel more like a game.
What's a tank game without cannons, explosions, and some destruction?
My work on this so far has been enlightening, challenging, and extremely rewarding. I've implemented quadtrees, collision detection, viewports, and a lot more. The next step is the hardest: Coming up with things to do in the game.
Emulating Battlezone has given me direction up to this point, but I don't want to remake the same missions and the same story. I decided to take a break from this project at this point to research mechanics and stories that I think are worth pursuing.
I'm sure I'll revisit this someday soon. Until then, farewell!