Making an RTS Game - Part 3

NOTE: This article was ported from tumblr

Hello ! Here I am once again to talk about my game. This time, less things done overall however some interesting topics I will talk about. This part will be dedicated to the movement of the units on the map.

1. “Optimizations” on procedural generation

But first, updates about terrain generation!

This is not really an optimization, but in order to generate the whole map, I had to cut the mesh in several small pieces, more commonly called chunks. Indeed, I learned the hard way (by smashing my head for 1 hour before getting the answer) that the number of vertices for each mesh in Unity is limited to 65535 (vertices). Let’s do a quick calculation: If I generate a 100x100 tile map, then there will be 10.000 total tiles on the map. With 4 vertices per tile, this gives us 4 * 10.000 = 40.000, so far so good. However, if I generate a map of 150x150 tiles, we have 4 * (150 * 150) = 4 * 22.500 = 90.000 vertices! And so, here is the problem. Once identified, I could start working on the “chunking system” a.k.a. creating several small meshes of a certain size (for example, a chunk of 10 tiles each) and placing them in the right place. So each chunk is only 10104 = 400 vertices.

Everything worked the first time as you can see…

But I finally got everything working after a few (long) hours of work. Here is the initial result:

And the updated version with much nicer colors (and addition of sand tiles, a pain in the ass, also) :

The next thing to do to further optimize it is to do m u l t i t h r e a d i n g, but that will be for later.

2. A* Pathfinding Algorithm

As I can’t use Unity’s native NavMesh system since I generate the world procedurally (or I would have to do more research about it), I needed a way to move my units on the map while avoiding obstacles. The solution is simple: the A* Pathfinding algorithm. I’m not going to talk about it in detail, because people much smarter than me are already doing it: watch this Code Monkey video.

It’s a bit complicated to see but you can see the green line that corresponds to the path the entity will take.

And here, a small clip to see everything in action.

3. Path smoothing with Chaikin’s Algorithm

NOTE: Links are dead :(

At this point, the unit can move on a path to the chosen destination but the path is rather… linear. I wanted to find a way to round out the path. So I inadvertently (or by a divine message) discovered a site that showed me the Chaikin algorithm. A little more research and I was able to find another site that detailed how the algorithm works. With that, I was able to implement it and round the sharp turns along the way.

As you can see, the path is much smoother, as the algorithm adds extra points to round everything out.

4. Unit Formation

And finally, I started implementing what we call unit formations. This is simply placing the units in a certain way, more generally in a grid. For this, I was once again able to rely on an amazing tutorial from Tarodev that explains how to implement this concept.

I slightly modified the code to allow the addition of an offset, which allows me to move the center of the formation to the mouse position. As you can see below, the units move to a selected point in the formation.

Thinking about it, I don’t really like this system and it doesn’t look very organic, and I’m thinking of changing to a simpler system where the units move to a random point within a radius of the chosen point, which will allow me to take advantage of the implementation of the Poisson Disk Sampling algorithm I coded (copied) earlier for an old project (damn, it takes a lot of algorithms to make a game…).

I’m also thinking of trying to implement the concept of boids to make the movement of units even more unique, as well as avoiding unintended collisions between them. But I’m going to focus on the essentials first, and the next step will be to implement the first bit of gameplay: harvesting resources.

If you want some info between these posts, I recommend you to follow me on Mastodon, Bluesky and even Twitter/X (as long as the latter exists) where I post from time to time what I’m doing. Again, since I don’t have access to my computer during the week, progress will be slow but I’ll do my best to propose things as time goes by.

On that note, see you next time! ~ Luckius 🌼💀