Making a Game Engine from scratch

[h3]Venerable Knights,[/h3][p][/p][p]When riding through Frontier Valley in search for adventure and glory, you travel across a dynamic world that goes through constant change. You will see the sun setting in the distance, trees swaying in the wind, and snowflakes painting the land white. When moving around, your path will be set up automatically to lead around obstacles in an efficient way.[/p][p]Those features, and many more, are driven by the custom engine developed for Knights of Frontier Valley. To stay with above examples: the time when the sun should be setting is managed by the "Time Manager", a component that controls and keeps track of game time and ambient light. Precipitation and trees swaying in the wind rely on the "Weather Manager", and snowflakes are drawn by the map renderer using particle effects. Characters moving across the map use the custom Pathfinder algorithm.[/p][p]If you are interested in how some of those things work and why I chose to write my own engine in the first place, you came to the right place!
[/p][p]There is also a video where I talk about the engine:[dynamiclink][/dynamiclink][/p][p][/p][p]Tthe sun sets in the Valley[/p][p][/p][h3]Motivation[/h3][p][/p][p]Let's start with the "Why". Creating a game engine from scratch for a game like this is a massive project. Engine features include rendering an isometric view (2.5D), sophisticated memory management, procedural generation of different types of maps, complex character behavior and interactions, persistence (save/load), both realtime and turn-based mechanics, custom pathfinding, and much more. You can expect work in the order of years.[/p][p]Since there are mature game engines out there to choose from, some available for free, why would anyone go through such an effort? It is about the goals you are trying to accomplish.[/p][p][/p][p]When I started working on the game in 2016 my role models were early industry pioneers like Richard Garriott, Sid Meier, and Peter Molyneux who made their first games in the golden age of RPGs in the '80s and '90s. They didn't use third-party engines back then, and as I saw it, walking in their footsteps meant learning how to make a game from the ground up. Building my game on top of someone else's code base that I didn't fully understand and couldn't fully adjust to realize my vision was not something I was interested in. Also, I thought it would be fun (most of the time, it is).[/p][p]While Knights of Frontier Valley was my first game, I looked back on a Software Engineering career spanning two decades, working on software for desktop, web, embedded systems, and mobile devices. Some of my past projects in Silicon Valley included GPS software, early iPhones and the original iPad, and the Infotainment and Autopilot systems in Tesla cars.[/p][p]So there was a programming background, but developing games is a very distinct field and I had a lot to learn. I had a busy day job when I started the game, so any work on it could only happen evenings and weekends. After about three months, I had a prototype of a basic game loop where a character could walk across a map and do some simple interactions. While this prototype worked, I realized that the current approach would never produce a game with interesting visuals. The technologies I had used just were not meant for making games, so I threw everything away and started over - this time utilizing libGDX, an open-source Java framework that simplifies OpenGL rendering and some other gaming-related functions. I chose Java as the language and OpenGL for rendering as those technologies had been used in other successful games, including Minecraft and RuneScape, and I was familiar with the language.[/p][p]Now I was on the right path, and over the following years, the game and its engine would continue to grow.[/p][p][/p][p][/p][p]The world map: early prototype vs today[/p][p][/p][p]Making the engine from scratch took around five years of part-time work, and if someone was to ask me whether they should do it for their own game, I would say this: it is not for everyone. I would not recommend it to someone new to programming. But even for experienced developers, the advantages of full code-control, ease of mind regarding possible royalties, added learning effects, and the great feeling of accomplishment must be weighed against years of work without income and a good amount of frustration. If you do not know whether you should do it, you probably should not. The will to finish what you started has to be strong, young Padawan, or else you risk putting a lot of time into something that you might eventually abandon.[/p][p][/p][h3]Engine basics[/h3][p][/p][p]But what exactly is the "game engine"? You might get different answers depending on who you ask, but in my case, I consider the engine to be all parts of the software that do not deal with the logic or appearance of a specific game. It is core functionality, separated out, so it can be used for other games as well, if they are of the same type.[/p][p]Two things about software design: first, to make code readable, maintainable, and reuseable, functionality should be encapsulated. That means that separate parts of the code base should not contain logic for different features. And second, behavior and visualization should always be separate. [/p][p]Following those two principles, my custom engine was designed to consist of several modules, each handling a particular game functionality. At runtime, those modules are used as needed, controlled by one core component that holds it all together: the main game loop. [/p][p]The main loop is a function that runs many times per second. Each run, the entire game world gets updated and a frame is rendered that shows the world in its most up-to-date form on the screen. Ideally, the main loop runs at least 60 times per second (= 60 FPS) - this number has to do with legacy monitor hardware, which was refreshing up to 60 times per second (= 60 Hertz). Today the number is often higher, usually 144 Hz.[/p][p]If your system isn't powerful enough to produce 60 FPS (the bottleneck is usually the GPU), you might notice lags and choppy animations. But with Knights of Frontier Valley, you don't have to worry about your video card: graphics are mostly pre-rendered, so the GPU can basically take a vacation while the game is running. On my old laptop I do not see any lag even when the game is running on integrated graphics.[/p][p][/p][p]All parts of my engine include:[/p]

[p]Main loop[/p]
[p]State machine[/p]
[p]Memory Management[/p]
[p]Persistence Handler[/p]
[p]Renderers for the map and entities[/p]
[p]Video playback system[/p]
[p]Sound output[/p]
[p]Mouse/keyboard Input handling[/p]
[p]Networking features[/p]
[p]Game time management[/p]
[p]Pathfinding[/p]
[p]Map Models[/p]
[p]Weather Model[/p]
[p]Character Model and character action queues[/p]
[p]Character Travel Module[/p]

[p][/p][p]Not part of the engine are:[/p]

[p]Anything story related and quests[/p]
[p]Graphical assets, music, and sfx[/p]
[p]The UI[/p]
[p]Procedural map builder logic[/p]
[p]Game-specific characters, objects, and items[/p]
[p]NPC behavior[/p]
[p]Anything game-specific including character creation, combat workflow, special effects (like magic), custom shaders, mini-games, and much more[/p]

[p]I'll go into more detail on two of the engine modules: the character model (and the related action queues), and the component that controls traveling NPCs, the character travel module. If you'd like to know more, there are also dev logs about pathfinding and rendering on the game's website.[/p][p][/p][h3]Character Model and Action Queues[/h3][p][/p][p]The character model is a software container that holds all characters that currently might need to act - those characters must be loaded in memory to update their behavior. It includes all those that are on the same map as the PC, as well as some others that might need to act for other reasons: faction leaders, traveling characters (more on that later), and important quest characters. When the PC is in a city, the character model contains hundreds of NPCs - many of them in buildings, others walking around outside.[/p][p]The game world is populated with many more characters than those that are in the character model at any given time, but since most of them are on different maps (= not visible to the player) and do not have any reason why they might need to act, there is no point in keeping them in memory and wasting CPU cycles on keeping them updated. Those "dormant" characters are stored in the database and will be loaded into the character model when the need arises.[/p][p]When the PC moves to a different map, the character model decides which characters need to be added to it (and which ones can be kicked out), and then performs the necessary steps. Newly added characters then go through a function where their last stored state gets evaluated - if their position and activity is no longer fitting to their current behavior cycle (work, sleep, leisure, etc), they will be teleported to the right spot on the map and start an appropriate activity.[/p][p]Internally, the character model does not keep track of individual characters but of "character groups". Every character, even when acting all alone (including the PC), is always part of a group, possibly with only one member. If there are several group members, they always remain on the same map and move in formation, following a designated group leader. If a group member dies, his corpse is moved to a new single-member group. If the group leader dies, a new one is determined, going by power and rank.[/p][p]When group characters need to be able to act individually (= not move in formation), such as during tactical combat, the group temporarily splits up, and each character gets their own single-member group. After combat ends, surviving NPCs re-join their old groups or form new ones.[/p][p][/p][p]Listing the characters on the current city map that are outside buildings in developer mode[/p][p][/p][p]Now that you know which characters are kept in the model and are able to act, let's take a look at what "acting" means in the context of the engine.[/p][p]Each character has an "action queue", which is a list of actions the character will execute in order. Such actions include things like "move along a path", "interact with an object", "talk", "attack", "play music", "read from a scroll", etc, or even just "wait".[/p][p]When a character isn't already busy performing an action, the topmost one is taken off the queue and gets started. Only if the queue is empty, the character is truly idle.[/p][p]The queue might contain many actions, and some of them could split into several new ones when their execution starts. It is a complex system where every possible character action needs to be pre-defined and clear about when it is completed. There are currently 36 different types of actions, some representing sets of several sub-actions. One action is called "custom action" and can basically do anything, so there literally are no limits to what characters can do in the game.[/p][p]If something unforeseeable happens while an NPC is working off their queue (like the PC attacking them), the queue gets cleared and the behavior is re-evaluated, spawning new actions on the queue in response.[/p][p]When the game is saved, action queues also get saved and will be restored upon loading, so all characters continue right where they left off.[/p][p][/p][p]A character's action queue can be printed on the screen in developer mode. In this example, the PC will walk towards the noblewoman, then turn towards her, then stop his walking motion, and finally interact with her using interaction type "Communicate"[/p][p][/p][h3]Character Travel Module[/h3][p][/p][p]NPCs in the character model may travel from any point in the world to any other point in realtime at any moment, even across maps that are currently not loaded in memory. The engine's "character travel module" will reliably determine all actions needed for the trip and put them on the group leader's action queue. If, for example, a character was to travel from the attic of his house to the cellar of another house in a different city, the following actions would need to be taken:[/p]

[p]Start the appropriate move animation (walk, run, or fly...in other scenarios maybe also ride or swim)[/p]
[p]Walk towards the stairs leading down[/p]
[p]Take the stairs from level to level until arriving at the building's entrance level[/p]
[p]Walk to the entrance door[/p]
[p]Interact with the door to exit the building[/p]
[p]Walk to a point where the town can be exited[/p]
[p]Exit the town[/p]
[p]Walk across the world to the destination city's entrance[/p]
[p]Enter the city[/p]
[p]From the entrance, go through city quarters as needed to get to the one with the destination house[/p]
[p]Go to the entrance of the house[/p]
[p]Interact with the door to enter the building[/p]
[p]Take the stairs down until arriving at the destination cellar level[/p]
[p]Go to the destination position in the cellar[/p]

[p]Those actions will be executed one by one, but pre-calculating the full list of required actions before the trip is not optimal. Something unexpected could happen along the way which might force the character to re-evaluate their behavior: a critical door could be locked, or the character could just get too tired to proceed. And of course, traveling between towns is not without danger in the Valley. The character really doesn't know what will happen on the trip, so the engine only calculates one step at a time from above list. When arriving at a waypoint, the situation gets re-assessed (taking the character's new environment into account) before calculating the next step on the trip, if nothing else of higher priority turns up.[/p][p]Making the decision on how to proceed at each waypoint rather than in advance makes the system very robust and avoids calculating actions that might have to be discarded. It also spreads out the computational effort, which is a good thing when many characters travel at the same time.[/p][p]Traveling characters remain in the character model even if they leave the PC's map, so they can continue acting until they arrive at their final destination. Now, while the character is on the PC's map, any obstacle on the path is in memory and known, and can be routed around using the Pathfinder component. But if the character has left to a different map, how does the system know how to route around obstacles there, and determine how long it will take, if that map is not in memory?[/p][p]I solved this problem by adding the concept of "off-map routing", a system that uses average travel times when moving a certain distance across different types of maps. I determined those average travel times by doing a large number of routes on each type of map. That means that when an NPC leaves the PC's map and disappears from view, and then the PC follows him a bit later, the player will find the NPC just at the right spot where he should be at that time.[/p][p]It is an approximation, not a real caclulation, and it is a bit of "faking" this part of the trip. But it works pretty well and players will never know that parts of the route were fake, MUHAHAHAHA. Ok, well, YOU do know it now - consider it your reward for reading all the way to the end. Your attention span is admirable and you probably have what it takes to write your own game engine.[/p][p][/p][p]Until next time,[/p][p]Martin[/p][p][/p]