UniEmblem Report

From the onset, I knew I wanted to create a turn-based strategy RPG, as homage to Fire Emblem, one of my favourite series. I created a game design document in order to fully plan out the game mechanics and design, including what classes, functions, AI behaviour and pathfinding algorithms I would need.

I knew I wanted units to have different movement types and for terrain to have different movement costs for each type, allowing for some interesting play and differences in the pathfinding. I also knew that there would be a need for behaviours for the enemy actors.

I also made a concept for a few different behaviours, describing what they would do and possible pathfinding algorithms that would work with it.

Coming into the assignment, I had already done research during the summer on how to build an actor using A* pathfinding. I built a program where white dots would find their way from the red square to a blue square, being unable to traverse through purple squares. The dots would dynamically update their path when the user spawned more purple squares. The initial version of this program used a Greedy-Best-First, but it evolved into A*.

However, the game I wanted to create was turn-based and not real time. Additionally, while the player controlled their units, I would still need to find out the range they can move to, and then the path to a particular tile in range.

I planned to use a modified version of Dijkstra’s Algorithm as a way to find out the available movement spaces, as well as the path to a certain space.

For the pathfinding algorithm, I had a class Tile to represent a square on screen, and a Grid which was a collection of Tiles. Each Tile had a reference to Terrain, which contained data about movement cost and defensive bonuses. When a Unit requested to move, it would check which tile it was located in and mark that as the current tile. From then, the algorithm would mark the current tile as closed, check the adjacent tiles, potentially add them to the queue, and would continue until no more tiles were in the queue. The function would return a vector of all the tiles, to be used in the game.

There are additional checks we would have to make, such as if a tile is currently occupied – and by whom, as allies can move through each other while enemies block movement, and the movement cost of the terrain for the movement type that the unit is. If a unit did not have enough movement points to traverse through the tile, it was not added to the queue.

By only adding tiles that are in the movement range, I am able to find every tile the unit can move to. I also keep track of which tiles are the parent tiles, and change the parents if there is a shorter way.

By keeping track of the parents, it is then easy to find a path from any of the tiles to the start (the unit’s location), therefore allowing movement.

I also have to know what the attack range is for the units, as this would help the player with clarity, but also be very useful for defining the actors’ behaviours. To determine the attackrange, I use a very simple algorithm that takes steps around a tile. A modified version of Breadth First could also work, as attack range does not take movement cost into consideration.

While movement and attack ranges used one pathfinding algorithm, different behaviours would include different ones to help determine a move for the enemy actor to make.

To build the behaviours, I have a state machine. Every turn, it looks at its units and chooses which state they are in based on the game world. Then, when it selects a unit to act, it follows the behaviour pattern defined for that state.

The state manager itself is fairly simple, only doing a few different checks based on the defined behaviours, and then setting the state of the unit based on that. The behaviours themselves, and the actions that the actors will take in the game are taking in the Behaviour class. Each unit takes their turn one at a time.

The general process for each state includes finding each tile the unit can go to and assigning a value to each tile. The value that is assigned is based on a certain number of factors including: if they’re able to attack a player (and then many factors about that – if they would be counterattacked, would they kill that unit, would they do a significant amount of damage), if they are in a defensive location, if they are blocking an ally from going here, etc.

Each state follows this process but adds additional values. The flanking state uses A* epsilon, using an ally unit who is engaged with the player as the epsilon case, making them more likely to take an alternative route to the player.

As shown above, the enemy Mage and Archer take the above route in order to flank the player on the top side.

The defensive state is when the enemy unit sees the player, but cannot reach them, so they do their best to get into formation. The unit who is the most defensive is assigned as the ‘tank’, and leads the front line, while the other units try to position themselves behind the tank and away from the player.

Aid Ally state is used when a unit wants to get in front of a low health ally, to give them a chance to retreat and heal. It uses an A* algorithm from its location to the nearest player unit to the low health ally. If the unit is a healer, then they will prioritise healing the low health unit.

The state system is only used if the player plays on the hard difficulty setting. In the easy mode, the units only move if a player unit is in range to be attacked, and in medium, they think about where their allies might want to go, and if an ally would be better to a certain tile than them.

In my game, there is an option to create your own map, as well as play it.

The map and unit data is printed out in a .txt file, and loaded in the BattleState, allowing the user to play any custom map with the game working as normal. Additionally, there is an option to Randomise the map. Instead of being a pure randomiser, it procedurally generates a map using breadth-first, as well as A* algorithms.

Initially, random groups are assigned to the map, and then between the groups an A* algorithm is used to find a path between all of them. The tiles in these paths are then set to being traversable terrain; they can only be grass/forest (easily movable through).

From a random spot in the map, the breadth-first algorithm begins. It checks all the adjacent tiles, adds them to the open list if they are not already on there, but also checks to see what terrain they have. From that terrain, a new list of possible terrain for this tile is built. So, for example, if a tile is surrounded by grass, it is very likely to be grass itself, but there is a small chance it could be something else. The algorithm continues until all tiles are checked, and therefore populated with a terrain value.

This ensures that you have a map that isn’t completely random (and so would look very strange), but does produce a different result every time. The groups that were determined earlier could then be populated with random ally or enemy characters, and then a playable map is created.

Overall, I am extremely pleased with the game I have created. I believe it shows off a variety of pathfinding algorithms as well as an interesting behavioural state system that leads to fun gameplay. The game runs well through a Game State and Game State Manager system, and is efficiently presented by using my Sprite Factory system.

I believe the game could have been improved by a more developed procedural generation tool, to deliver more visually pleasing maps, as well as ones that are directly playable. More research into that development would be better, as I did mostly just think about how I would do it myself. Additionally, I believe I could have made the program more efficient and better designed, as some cpp files did have many lines. Thinking more about where I could have the algorithms located could have cut down the number of lines.

I have thought about remaking the game with more complexity – having each actor have an individual personality value that could determine their behaviour, as well as more behavioural states, objectives that they want to complete and grouping them.

References:

CodeCompile, 2012. A* Pathfinding Tutorial. [video] Available from: https://youtu.be/KNXfSOx4eEE [Accessed 12 Aug. 2017].

Patel, A., 2017. Introduction to A*. [online] Redblobgames.com. Available from: https://www.redblobgames.com/pathfinding/a-star/introduction.html [Accessed 18 Aug. 2017].

Nystrom, R., 2014. Game programming patterns. Genever Benning.

The Inquisitor, 2005. World Map & Medieval Exterior. [image] Available from: http://downloads.rpg-palace.com/index.php?cmd=8&page=1 [Accessed 12 Oct. 2017].

Appendix:

https://drive.google.com/open?id=0ByuPQ6PGvEpuUzFxY0UzeDc1VWM

Google Drive with design documents for the game.

#programming #c #gamedesign #AI #UniEmblem