One of the other big changes that I want to make from the standard RPG system has to do with the way character progress is handled. Leveling up is so much a part of the role-playing genre that when they other types of games started adding levels, they called them RPG elements. Many descriptions of the RPG genre actually say that the single most important aspect for a game to be considered an RPG is that is has a leveling system. There are many reasons games do this, and I plan on addressing those, but if you just want to see my proposed alternative, you can jump right to it.

People like to feel powerful. Games let us escape from our mundane world and enter another world where we can feel empowered. This has to be balanced with the difficulty of the gameplay though; a character who trounces all of his enemies from the outset gets boring very quickly. Having the characters grow in power through the game does a really good job of accomplishing this in a game where player skill is almost irrelevant. This is especially true of role-playing games, where the standard story line starts with something mundane that we can relate to, but inevitably turns into a quest to literally save the world. There are few situations that make us feel stronger than being the only person capable of saving the entire world.

Save the world? Fef! We can go all 4D on it and save time too!

There are other ways to achieve this feeling, and there are many successful games that get by with the characters ending the game with the same skills and equipment they had at the start. These types of games tend to rely on play elements that require precision from the player, and as the player gets better at performing them, the increased skill will achieve the same effect. Since the type of RPG combat I’m most interested focuses on strategy, it becomes difficult to recreate that feeling based on player skill alone. Sure a chess match between players of drastically different skill levels tend to be quick and easy for the master, but when the difference is only a matter of a few dozen hours of experience, things tend to still be evenly matched.

It takes years of practice to pull off this decisive of a victory.

One of my biggest complaints with the leveling system is that while it felt great to get more hit points and strength the first hundred or so times, after a while it all just kind of blended together. What’s the difference between having 100 hit points and 1000, when enemy damage scales the same so its always 10% of your max? Having this arms race between player and enemy stats requires meticulous balance on the part of the game designer, or the result is either the character levels being too high for an area and the game being boring because it’s too easy, or even worse, the character levels being too low, which forces the player to grind for experience just to catch up.

After killing your 500th evil bird, do you still really feel like celebrating?

The benefits of the leveling system must be pretty great, as gamers have put up with all of these drawbacks for decades just to keep them. Our urge to feel empowered by the games we play, and not just that to have it feel like we earned that power, is a strong one, and to try and take that out of a game in this genre would be foolish. I could have simply chosen to make sure I keep a close eye on balance in my game, or put in arbitrary caps and experience boosts to force the player level to be where I expected it, but my past issues with game balance have assured me that statistical balance is not easy, and without a dedicated testing group it might be downright impossible. Instead, I looked to some of the great games out there that don’t have levels to see how they solved the problem.

One of the common features of action games of the 16-bit era and modern-day FPS games is that your character seems to acquire quite the bag of tricks throughout the course of play. The characters start the game with a few basic commands; slash your sword and block, shoot your gun and jump, fire your pistol and take cover. As you play through the levels, you get new items or skills, that while not statistically better than your existing skills make certain situations, or sometimes the whole game, much easier. Super Metroid’s ice beam may not actually do more damage, but being able to immobilize your enemies absolutely trivialized a number of encounters of nightmarish difficult prior to acquiring it.

No more will you drop on my head while I run under you. Ha!

The question remains, can this style of progression work in a turn-based game? Many games give the players more skills as they progress, but most do so with statistical upgrades available to those skills as well. Sure you might get a spell that applies some status effect to your enemy, but in most games those skills have a niche use at best, and quickly fall by the wayside when a greater fireball becomes available. This leaves one final hurdle to this revision of the advancement system becoming viable, and that’s making sure the tricks that are placed in the player’s bag are actually useful.

The good old attack command. It’s all you ever really need.

In most games that have them, these utility spells rarely see use for two main reasons. The first is that in a standard enemy fight it is almost always faster to just use brute force to kill the targets as quickly as possible. Part of this is due to the nature of many random encounter fights being too simple, which I addressed in an earlier post, the other is that often times the turn spent to apply the status effect is not worth the loss in damage. What good is a 50% damage boost if the fight only lasts two rounds?

The other issue is that almost every fight that lasts more than the few rounds given to a random encounter is a boss fight, and as we all know, bosses are immune to all status effects as a general rule. There is good reason for this; boss fights are the climax points of each chapter and having them vulnerable to a skill that removes the tension from the fight break the pace of the game. If the boss has a single mechanic and the player can disable that mechanic, or use a spell to kill it outright, then something has to be done, and the easy answer is immunity. The better answer, I think, is to have better bosses who adapt, and if there is an instant death skill it should be hard enough to set up that its use becomes a strategy instead of an instant victory.

In order to eliminate the need for and possibility of level grinding, and to address any issues that may stem from such a change, I have come up with the following proposal.

1. Characters have no level. This means that a fight against a bandit at the beginning of the game has the same effective threat level at the end of the game. Your skills will let you get in more hits and evade more attacks, but the numbers will stay the same.
2. New skills are gained as the story progresses. This is how most action games handle it, and in the absence of levels it just makes sense. This would take the form of acquiring a new unique item to use or receiving special training from someone.
3. Utility skills will be useful. With the longer random fights, their utility will already be higher than usual. Since the fights are more about creating the openings, effective use of skills will always result in a shorter fight. Boss fights will not rely on a mechanic that can be shut down with a few utility skills, allowing them to be vulnerable to these skills.
4. Money is earned from story events. Since there is no incentive to grind for experience, making fights the primary means of income seems out of place. Towns will have a variety of mini-games that players can engage in to earn extra money. A coliseum will let players use combat as their mini-game of choice.
5. Training modes give passive traits and stat bonuses. These will be almost like classes, though dealing exclusively with passives. There will be a few tiers of each of these which become available as the game progresses. Once unlocked, players can activate them either by spending time playing the mini-games or paying for training.

With this setup, I believe I can achieve a good feeling of progression without the need for mindless repetition, while still providing players with a sense of accomplishment as they progress. This will eliminate the need for level grinding, and even the benefits that it usually confers that make it so useful it becomes almost mandatory. With the coliseums in each town, players will have a safe way to test their fight strategies quickly, which should eliminate any possible use the fodder encounters might provide.

As I’ve stated before, turn-based combat systems should be all about strategy. Fights should have meaning, and require thought and strategy, as opposed to simply holding down the attack button. Once we have arrived at a combat system that achieves this, we run into another problem almost immediately when we place it inside an RPG: nobody wants to fight a thousand battles that require actual thought and energy, it’s just too draining. Using myself as anecdotal evidence, I know that when presented with the choice between having random battles and not, people will often choose the latter. Random battles do serve a purpose, but I feel like we can do better. For the details of my implementation, you can skip right to them.

Other people seem to agree, there is something wrong with the random battle concept.

Having random battles serves a number of purposes; it gives a general sense of danger to the world, it gives the player obstacles to overcome outside of the story which fends off boredom, and it balances the two sides of the game so you don’t spend 90% of your time in town or walking around a map. At this point we can achieve all of those things without the downsides that normally come from having random encounters, namely the frustration of an encounter rate that is too high. Let’s start with the sense of danger these encounters can add to the world the game exists in.

This doesn’t exactly scream danger…

Games revolve around struggle; that’s what makes the medium interactive, and more engaging than, say, a book. The players gets to feel that struggle, and how engaging the gameplay is will be tied directly to how sweet success feels over that struggle. When there is no challenge presented to the player, that’s when boredom sets in. In the Cthulu Save the World, I would burn through the encounters for an area so that I could then explore freely. More often than not, I would leave chests undiscovered simply out of boredom. Walking through the maze of a dungeon on a flat map wasn’t challenging in any way, all of the threats had been eliminated and I simply rushed to the end to get to the exciting parts again. Part of this had to do with the nature of the level design, but that topic deserves its own post at a later date.

Enemy forces that pose no real threat make combat boring and leads to the “hold down ‘A'” mentality. Enemies that are significant threats that occur repeatedly make dungeons a game of chance where the win condition is “hope this monster doesn’t show up too often.” I have actually seen that phrase in countless strategy guides over the years. Some games strike a balance here by having the hard enemies occur on a trigger, with trapped chests being a popular trigger to use, and have the normal enemies be fodder for the player to kill.

Wanted: Hard-working kobolds to die at the hands of adventurers. Must be fearless in the face of a literally impossible challenge, good with kids is a plus.

So how do we create this sense of danger without it getting frustrating? There are a few options. Ambiance helps in this department, scary sounds echoing in the darkness, driving music to build tension, visual effects like people running past you or explosions tearing up the terrain, but by itself that isn’t enough. My solution to this problem is similar to my solution to randomness in combat; make it seem random without actually being random. We can add tension by having dozens of groups of enemies pursue the characters through the map. When the enemies catch up, that’s when you have a combat encounter. Audio and visual clues can help the player know where to go to avoid combat if that’s the goal, or run head-first into the fight, depending on play style.

Like this, but the enemies don’t wander or move on a set path.

Obviously, with fights that are draining both to engage in and to get into or run from, these can’t just pop up anywhere. The frequency of the fights will need to be drastically lower than in a normal system, and the times you are in a situation to potentially enter combat will need to be lowered as well. This leaves us with an interesting conundrum. If we make fights too rare the threat goes away, so how do we keep that threat alive without actually putting the player into a fight? Showing the player clues of pursuit will help keep the threat alive, as long is the threats are acted on every so often. This will hopefully cause players to feel a sense of urgency when the bushes around them start rustling, as if they stick around they will be thrown into a potentially long and difficult fight, but they might be able to outrun it before it even happens.

I neither know nor want to know what is waiting for me in there

In mulling over the concepts for a while I decided to take things back down to the roots and set out the goals I want my encounters to achieve. These are only for the encounters on the world map or in dungeons and not for the boss fights.

1. Put pressure on the players while they are exploring.
2. Give players a chance to try out their new skills or combat strategies.
3. Balance the time spent in and out of combat.

Since the combat system we have already lined out leads to longer and more involved fights, we need fewer fights to accomplish #3, so we need to ramp up the non-combat threats to the player to meet #1, and somehow still give the players a way to achieve #2 without wandering around for too long or getting in over their heads.

While not a “random” encounter, this normal wandering enemy was harder than most of the game’s bosses. This is something I want to avoid.

Here is my proposed outline of how to handle the random encounter issue. Note that unlike my two previous articles, this one is pure speculation. I have not actually put any of these into play as I’ve only done the prototype for the in-combat gameplay. I’m sure some aspects will change once I get to that point, but for now I want to put my ideas out there, as it’s important to understand the goal of the random encounters so you can see why I don’t think the heavier combat system will drag the game down.

1. Encounters are the result of the player colliding with moving entity. Other games have done this, but usually the entity movements are fixed to an area or a path. I want to have a wolf pack track the player when they enter it’s territory, and through tracking or other skills the players may notice they are being followed and can back off before the fight begins. Pursuing enemies may have a range they will follow to, but can track the player anywhere within that range.
2. The world map has a few wandering enemies with large ranges. I want my world map to be somewhat large, and I want players to feel like they can explore it without getting themselves killed in the process. The hints of threats should be enough to keep players on their toes for the most part.
3. Dungeons will have many enemies that track the player constantly. In a dungeon, the threat should be great and constant. I almost want to create the feeling of a stealth game here, but not exactly. If the player heads straight to their goal, the encounter quantity will be comparable to a normal game. If they duck into hallways to avoid encounters it will be lower, and if they go exploring it will be drastically higher. The level design will take this into consideration.
4. Large cities will have coliseums where the player can grind. I want to minimize grinding, both the need for it and the rewards for doing so, but people need a way to test out their strategies in a safe environment. By taking out the fodder encounters, I have lost this, so the coliseum gives it back. This also justifies why you might earn money for fighting a wolf. The wolf didn’t have it on him, you just won a cut of the bets against you.

That sums up the design concept for my “random” encounters. I feel like this will achieve the pacing and engagement benefits that the old systems strove for, without bogging down the players with endless, mindless battles, and without making the game feel too arduous.

Continuing in the vein of my last post on turn-based combat, I wanted to go a bit deeper into the feature that generated more questions and concerns than any of the others. I made the statement that nothing in the combat scene would be determined by a random number generator. I made this decision after playing an older RPG and losing a fight by just a few hit points. I went back and the played the fight in the exact same way and ended up winning. This got me thinking about why we use random numbers in these types of games. I want to detail some of the variables that will go into the combat system to give it more depth, but first some history. For those who only want the details, you can skip right to them.

Nothing is more frustrating than being punished for something out of your control. Over a large enough sample pool, the average may be a good experience, but too often have I been on the bad end of a particularly terrible streak of luck. When I play an action game and I miss an attack, it doesn’t quite sting as bad. Sure I missed, and it was chance that the enemy moved out of my attack area at the last second and there was nothing I could do about it, but it didn’t feel that way. I feel like I can learn from that type of failure; next time I’ll attack earlier, or get closer, or something. When I lose to a dice roll it just seems wasted, there is nothing to learn from it. It’s the same reason that slot machine mini games only hold my attention for a few seconds.

Maybe if I pull the lever harder this time…

Why then do we continue to use random numbers to augment combat? The added excitement is definitely a good thing, and when every processor cycle had five things competing for it it was the best way we could add this element. Times have changed quite a bit since then, and while a lot of the focus in the gaming world was on graphics, there has been little work toward improving the underlying systems that this random number is filling in for.

We can now see that we have an arbitrary chance to hit, and it’s really pretty.

There are a lot of factors that go into why somebody might miss an attack, or be able to dodge it. Most of the time, someone with proper training doesn’t miss an attack against a stationary target, unless they are tired or distracted. We can model those things though, tracking fatigue and storing what the character is focused on. Sounds or other factors might distract him, or his fatigue might limit his effective range. Why then are there no (or at most very few) games that take these things into account?

I think the answer to that question has a two-part answer. The first part is that players are accustomed to the random chance system. We’ve all seen it before, and for all of its flaws we as players have accepted it. If it isn’t broke, why bother fixing it? The second part is that adding a multitude of other variables for players to manage can quickly turn the game into an exercise in managing spreadsheets instead of just playing the game. Some games have done this successfully, but that tends to be the focus of the game, and the gameplay quickly becomes secondary.

Not the game I want to make or play.

After pulling apart this aspect of the standard turn-based system, I decided that it was worth trying to improve, but it had to be done right. Ideally, the player wouldn’t even notice this was all going on under the hood unless they dove into it; it would seem random to them. If the end result of the innovation is the same as the status quo, why bother then? A system like this confers a few significant benefits that are too appealing to pass up.

1. Combat is deterministic. Basically what this means is that for the same exact fight (entities, positions, equipment, etc all equal), and the same player inputs, the fight will be the exact same. This makes for easy replay systems, which can give players quick feedback on what they did wrong in a fight, or let them jump into the middle of a recorded fight to try different strategies.
   

   It’s like being able to tag-team with your past self.

2. More options for skills and effects. When your chance to block is determined by your level of focus, what direction you are facing, which hand has your shield and the direction the attack is coming from, altering any one of those things can affect it. If each of those things then affects four other things, effects will feel more natural, and the skills can have huge strategic potential just by modifying one of those behaviors.
   

   If you can’t see the points in the middle, it will seem random.

3. Higher skill ceilings. In the older rpg games there was very little inside of a fight that the player could manipulate. This meant that once you looked up the right setup for a fight, levels, gear and job settings where applicable, everyone was on the same page. Difficulty was added by way of hit points, and it could all be overcome by grinding. With a finer grain of detail, a novice can play the game through on the normal difficulty and be fine, but a better AI can challenge players to gain a deeper understanding of the system for a better on-the-fly strategy.
   

   Easy to play, hard to master. The ultimate example of a high skill ceiling.

Equipped with an understanding of the system I want to create, and the goals I want to accomplish by doing so, I have outlined the rules for creating a turn-based (sort of) combat system with no random elements. I have only implemented some of these rules so far, but I already find the combat to be much more engaging.

1. All characters are assumed to always hit. At a base level, all attacks will hit their target. There are no critical hits, and misses are assumed to be the result of the target actively dodging, blocking or parrying, or simply moving out of the way of the attack.
2. Avoidance is based on time. To avoid an attack, a character must: see it coming (in their field of view), react in time (reaction time is fast enough to do anything before the attack finishes after they notice it), have enough time left over to perform the action (dodge/parry/block time is less than the time left before the attack finishes, but after they react to it), and not be otherwise occupied (in mid swing, resting, or recovering from an action).
3. Game actions are higher-level concepts. You issue commands to engage, not attack. Some characters may have skills that let you attack with no regard for personal safety, but for the most part they will keep their target engaged but focus on survival and only attacking when they see an opportunity. This means combat will be as much about creating openings as taking advantage of them. This also means that the characters will need to work together as much as possible to do so.
4. Game actions focus on variety over power. As you progress in the game, your skills will give you more ways to manipulate the battlefield, instead of letting you dish out damage in greater numbers. A young wolf doesn’t stop being a challenge because you can kill him in one hit, rather it becomes trivial to knock it off balance and keep it that way. This isn’t directly related to not having random numbers, but since the player won’t gain a greater chance to hit as time goes on, this gives them a way to feel like they are progressing and growing more powerful.
5. All characters have a short-term energy gauge. Again, not a direct result of removing random numbers, but a necessary tool to prevent stalemates in the system. Two characters can only keep each other engaged for so long before one of them has to stop and rest to regain energy. This forces the system to create those openings and keep combat from getting stale.

These rules give us a system that hopefully gives the player greater strategic options without requiring in-depth knowledge to get started. If you get caught off-guard by an archer that your characters couldn’t see in the darkness, that’s no different to the novice player than being on the receiving end of a critical hit. As long as the actions are built properly, a novice player can just spam the engage command and the characters will handle their targets as best as they can, and will be no different than holding the ‘A’ button to spam attacks in a Final Fantasy game. Even with that style of play, at least you get the replay system.

I recently wrote a prototype for a turn-based RPG combat system, and it breaks a lot of the conventions normally associated with that genre. It’s still feels very much like a traditional eastern-style role playing game (shortened to jrpg from here on), but I tried to use modern game design concepts to extract the core of what makes that type of game fun and create something wholly new and much more engaging than what you typically see from the genre. I’m going to go into it in more depth in a moment, but first some background on why I chose to do this. If you don’t care about the background and just want to read about the system, you can just skip to it.

Many genres of game have hard-set, long-standing codified rules. Many of these rules were set when the video game industry was still in its infancy, and were created to work with or around the very limited hardware available at the time. Few genres have more of these rules than the jrpg. When you think of a jrpg there are tomes of rules that games must obey to fit this genre: turn-based combat, random encounters, item shops in towns with ever improving levels of equipment (granted, there is a large focus on story as well, but I’m going to focus on the gameplay here, since any genre of game can tell a story.) The list goes on, but most of these stem from one of two limitations.

Final Fantasy – 1987. One of the earliest and most influential titles of the genre.

The first is that a large number of the features were pulled from tabletop rpgs, which simplified things so that a person could keep track of them. Real-time combat is near-impossible to keep track of with pens and paper, so we have turns. Tracking the movement patterns of monsters and wildlife throughout the wilderness is also maddeningly complex, so we approximate the chance encounters with a dice roll.

Red deer migration patterns, and that’s just one species. Who would want to even try to keep track of that?

The second limitation was that game consoles were not capable of handling much more than a human GM was. This is where item shops with set stock and prices, world maps with players the size of cities and towns with five houses come from. It simply wasn’t feasible, or even a good use of anyone’s time to add hundreds of houses and NPCs that did nothing to advance the plot or aid the players.

Guess how many of those houses are relevant to the plot?

Conservation of detail meant that every house and NPC, every hallway in a dungeon, and every encounter in the game had to hold some significance to the plot in a very direct way. How many times are the random encounters in those games the result of some great evil causing monsters to start acting up? We’ve come a long way since that screenshot up there from 1987, and neither of these two limitations really hold any weight any more. We don’t need people to place every building or NPC any more, and there’s no reason for random encounters when computers can track the movement patterns of millions of animals.

Introversion’s city generator. This is a real thing.

I’ve deconstructed a large number of the rules of this genre recently as an exercise in design, and to me the most fundamental gameplay element of these games was turn-based combat. Stats and equipment, random encounters and dungeons are all driven forward by what invariably becomes an exercise in how fast you can tap the accept command to blaze through the combat scenes. Bosses tend to be the notable exception, but the number of hours spent mindlessly pressing that button could be much better spent doing something more meaningful and engaging. Recent entries by Zeboyd Games have moved in this direction, and it’s a fantastic way to improve the genre, but I think there is more that can still be done.

On the Rain-Slick Precipice of Darkness 4

One thing that has always bothered me about these games is that many choices aren’t meaningful when it comes to combat. If a character can equip swords, why would they ever choose daggers? In real combat, daggers are smaller and faster, and give the user more mobility, though they sacrifice range for it. Maces are much heavier and take longer to attack with, but the blunt force of the impact can be more devastating to a knight in plate armor than a slash from a sword. For balance, these weapons either all deal the same damage, or the people who use the ones with lower have some other aspect that makes them desirable. Dagger users tend to be able to steal from their enemies, for example.

One of the ways I saw to open this up was to change the concept of what a turn is. Modern day computers are no longer restricted to handling complex combat calculations by turns, many real-time role playing games have proven that. So what then is the goal of using a turn-based system over a real-time system? In my view, the two systems present largely different challenges to the player. In a real-time, or action, system, the player is tasked with not only making snap decisions, but with executing them quickly and effectively. The challenge places more emphasis on speed than strategy, with the strategy usually occurring as a separate layer of the gameplay.

Skyrim’s strategy layer

In a turn-based game, the focus is on strategy. Ancient turn-based games like Chess and Go have are great examples of the levels we can take a game to just on simply mechanics and strategy. I’m not trying to create something quite like that, but I do want each fight to feel significant. This change will affect things like how frequent fights are and the whole random encounter system, but I’m getting ahead of myself.

Here is the outline of the Interrupted Real-Time System that I developed to address these problems.

1. Turn lengths are variable – Each turn is an action, and each action has both a wind-up and recovery time, based on the action and the equipment the character is using. What this means is that a character attacking with a sword would get two turns in for each turn by a character attacking with a hammer.
2. Combat progresses in real time – An action that takes one second to complete will fire off one second of combat time after the command is given. This means that other commands might interrupt the attack, or the target might die before the attack finishes. Depending on what happens, the character will go straight into the recovery period and the players turn will come earlier than expected.
3. Combat pauses for input – While all of this plays out on the screen in real time, when the player is prompted for their next command, the action on the screen pauses. This gives some of the flexibility of real-time combat while still letting the player focus on strategy over speed.
4. Combatants move around – Not a new feature, games like chrono trigger have used this before, but in those systems it seemed more of a visual feature than a strategic one. If a character has a weapon with a greater range, they can attack from farther away. This means that a spear can keep a sword at bay with much less risk, and archers are mostly safe from melee units. The system will handle the movement to keep this from becoming a tactics game; moving into range is simply part of the attack.
5. Nothing is random – Chances to do things like dodge or land a hit will not be determined by a random number generator. The system can model a sufficient amount of data behind the scenes to allow for things to seem random, but with proper strategy a player can control them. Things like field of view and focus will determine how quickly characters react, and movement or parry speed will combine with that to decide if a hit was successful. Two characters going head to head using basic attacks will likely never actually hit each other.

With those five bullet points, I feel like I have addressed the major concerns inside of a combat scene that I brought up earlier. This gives players the flexibility to make meaningful choices regarding their equipment, and sufficient avenues to develop and execute a deep strategy based on those choices.

Pathfinding is and has always been incredibly interesting to me. From the first time I saw a unit move around an obstacle back in the late ’90s playing Starcraft, I have been awed by the ability of a computer to something more than walk a straight line to its target. Many times before had I exploited that weakness of computer-controlled enemies to my advantage, hiding from enemies behind a short wall to take a rest or lob ranged attacks while they sat there running into the wall in a hopeless attempt to get me. At the time I was amazed, I was just getting started with programming, and while I could grasp at least at the conceptual level how most of the game worked, I was positively mystified by this feat.

Obviously I have come a long way since those days, and while I wouldn’t have considered myself an expert, I felt like I could hash out at least a workable version of this concept when the need arose for a prototype I worked on recently. This was actually somewhat true in that I was able to write out some code that produced a workable path, but oh man was it slow. Not like, sit there and wait for it to finish slow, I was still measuring times in milliseconds, but running in real time was not an option. Thankfully, this wonderful internet age we live in meant that the answer of how to speed this up was out there just waiting for me to find it.

Initial searches led to the obvious choices. A* on a grid was the first algorithm I found, and while not an eye-opening revelation, they were certainly doing things in a smarter way than I was. I took to task and quickly implemented the algorithm on my little world, and while this was decidedly faster, the paths it came up with were less than desirable. Choppy, robotic movement was something I had encountered in other games, and now I fully understood why.

Source: http://commons.wikimedia.org/wiki/A*_Algorithm

This worked, and honestly for as unimportant as the paths were to the project I should have just stopped here and moved on, but that’s not how I roll. I wanted something that seemed a bit more natural, a path that I would actually walk in that situation. I wanted something more like this.

A more natural path

I did a bit of research on various methods of smoothing A* paths, and found a great article about optimizing the heuristic used to generate better paths. (http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html)

This helped, and the paths looked better, but I had two real issues with this. The first was that some of the paths still looked wrong; my entities were not tied to the grid, so it made no sense for them to walk along it’s lines. The second was that while my terrain was tied to a grid, I wasn’t exactly happy with that either, I wanted to be able to drop obstructions of arbitrary shapes and sizes at arbitrary locations. In search of a better algorithm, I came upon a nice little gem of an algorithm called Theta*.

The gist of this algorithm is that it keeps track of significant turns and casts lines between turning point nodes and the new nodes it searches. It basically then comes up with a straight of lines as possible by keeping only the nodes at the turn points. This was a bit more of an eye-opening moment to me. The answer seemed so simple and obvious I was almost annoyed with myself for not coming up with it on my own. With pride sufficiently swallowed, I set out to put it into practice.

Real people tend to walk straight to the nearest opening.

This was almost exactly what I was looking for. No more movement awkwardly restricted to only 90 or 45 degrees. This looked like what a real person might have done, given the circumstances. Theta* was a great success, but there was still a little bit of work to be done. By toying with how the entities moved, giving them a sort of inertia and not letting them snap on turns, I managed to get exactly what I was looking for.

Real people tend to round corners.

The last real issue here was that I was still tied to a grid. I will spare you the gritty details for maybe another time, but in the theta* implementation they mentioned using visibility graphs. After a bit of research on building one, I wrote up a quick algorithm to generate the graph allowing me to place my existing tiles anywhere on the map, which led to this.

Because sometimes curves just look better.

I still can’t get over how nice that all looks. I’ve seen some impressive pathfinding in 3D games, but not usually in the realm of 2D gaming. I’m excited for the natural look this will give movement in my projects, and while I realize this will likely be a feature nobody really cares all that much about, I just really couldn’t help myself.