Path finding and action planning for Fire Emblem-like games (large images beware)

Hi everyone, I’m working on a blueprint plugin that should make your lives easier when creating games like Fire Emblem and Advance Wars. I’m doing this all in blueprint and I want to submit this to the marketplace in time! Here are some details:

Action grids
The main purpose of this plugin is to construct action grids. Action grids define the actions that a character can do from his current position, specifically:

  • which tiles he can move to
  • which tiles he can attack right away or after moving
  • which tiles he can attack from (there are enemy units in attack range)

For each reachable tile, the action grid can retrieve a shortest path to that tile in linear time. So these grids are meant to be used for path finding, for validating player input commands and for helping AI decide their next move. I’m using a modified Dijkstra to allow for different tile costs for different terrain pairs. Terrain costs are also customizable per unit.

Logic and view separated
I have kept the logic separated from the view, so users who just want to use the logic can do that out of the box. I will include the view blueprints that you can see in action in the screenshots, which can be used to show the entire level (white tiles), action grids (red and blue tiles) and any retrieved path (arrows).

Plugin usage
I aim to make the API as intuitive as possible. The three phases to computing paths are as follows:

  • Populate and maintain a LevelGrid
  • Compute an ActionGrid for any unit on the level grid, supplying walk range and attack range
  • Retrieve any number of paths efficiently from the action grid, or perform queries for whether a tile is reachable, attackable etc

The level grid can be populated by anything that implements the blueprint interface MDActor (GetGridPosition, SetGridPosition). Since its an interface, you don’t have to reparent your existing character blueprints or create dummies for them, just implement the interface. For most games, you only need to create one level grid ever. The level grid has functions for adding, removing and moving (reposition an already added actor). Whenever you modify a level grid, any prior computed action grids become invalidated. If you try to use an invalidated action grid it will print a warning, to save you time hunting down bugs when the cause is that you are using an outdated action grid. Also to help you out, all operations have a Success and Error Message output, to help you debug. Error messages are for example: actor is null, target tile out of bounds, target tile is occupied (when adding), etc.

When computing an action grid, you supply a walk range (with Dijkstra this will be walk cost), and a min-max attack range. Example usages:

  • 0 walk range if your move is already spent
  • 1-1 attack range for melee characters
  • 2-2 attack range for archers a la Fire Emblem
  • 3-5 attack range for rockets a la Advance Wars

Test cases
I will include my test cases, which involve unit tests and preset path tests. Those who want to modify the algorithm can run these test cases once in a while to make sure they didn’t break any prior features. If a test case fails, it will print some info about which test failed and on what condition. This should help you find the cause. The test cases are all contained in one blueprint that will run at BeginPlay, so you just need to drag an instance into the world and start playing to run the test cases. The purpose behind each case is commented so you can decide to leave some test cases out if your modifications intentionally break them.

Update: I decided against including test cases since it took too much time to update the cases during development

I will post updates later to include more info. Please let me know what you think, any feedback is welcome. Questions too!

Some new footage here:

Framerate is rather low, but this is a recording issue rather than performance. I’m satisfied with the features now and have spent the last days making the blueprints as intuitive as possible and optimizing the View blueprints that I use for showing the level grid and the action grid. I consider this system actually feature complete, because my aim was only to provide path finding and a queriable structure for assisting in handling player input and AI.

I’m very impressed with how fast you managed to make this! I love the clean and neat presentation, too. I guess you’ll be beating me to the marketplace. Especially since I have a few more features I would like to add before my own release. I see you even got node costs implemented. Does this mean you also ended up using Dijkstra’s algorithm, or did you end up doing something else?

Hey, thanks for the kind words. :slight_smile: I’ve actually worked on a turn based hobby project for the past year so I had my own tried and tested C++ implementation as reference. Yes, I changed my BFS to Dijkstra by storing cost in each node and re-evaluating visited nodes if a shortest path to that node is found. There is some difference because I am dealing with a maximum cost. I don’t queue a node’s neighbor if the new shortest path found exceeds maximum cost, but that does mean that whenever a shorter path to any previously visited tile is found, we have to re-discover all paths starting from that tile, because we might find more tiles within the max cost. Are you also doing something like this? I can’t imagine any other ways from the top of my head, if you want to use maximum cost to limit your search.

Yes, I’m submitting the marketplace form soon. I see that you’re aiming more for a complete toolkit. I like your drag-and-drop tile editor a lot! Mine is not so intuitive: to specify the terrain you either have to call functions on the blueprint (SetTerrain for a rectangular area) or predefine a list of these rectangular areas in the editor properties of the level grid. So both involve typing indices and width/height, although the second method does give direct color feedback in the editor. I’m keeping it at that, because my intention is that people just use the colors for debugging, but really do the imagery of the scene themselves. I think thats quite a big difference between our aims and hopefully there are enough people with either preference.

I’m also very interested in what tools you’re going to provide for AI. I never got to that part yet and I’m curious what you’re going to come up with. Are you going to focus on scripted, intelligent, or a bit of both? Maybe going for something like potential fields, so giving tiles a score using multiple conditions and then moving to the highest scoring?

Yeah, I saw your older systems in the links you gave me, so I knew you had implemented it before. If not I would probably be quite disheartened by how fast you got this far, seeing how long it took me :stuck_out_tongue: It seems like we are doing similar things when it comes to tile costs, with both of us doing things similar to, but not exactly like Dijkstra.

Your debugging tools look really neat. I haven’t got anything like that myself. I guess you saw the benefit of them immediately, as you have more of a programming background than me. It will probably be very useful for users. I also see the differences between our systems to be you providing more of a bare-bones framework, which is perfect if you need the basics in place to build your own system without any clutter. My system will be better if you want a more complete system out of the box, that you can tweak and customize.

You’ve done AI before, right? It seemed like it in the video link you gave me. I’m planning on making actual artificial intelligence, that weighs the costs and benefits of all possible paths and choosing the most beneficial. Later I plan to add the ability to tweak the personality of different AIs to make some more agressive, for instance, and perhaps throw in some random elements.

Liking all the work on pathfinding systems! :slight_smile:

We should start a turn based strategy lobby so we can pester the devs for things that our genre needs. :smiley:

The AI I’ve done in the past isn’t much more than “move to any tile from which I can attack an enemy, and then attack the enemy”. So nothing with a purpose or multi-turn thinking. I’m really interested in ways to achieve that in a way that still gives level designers control (other than rigid scripting).

Turn based strategy games are great! I hope there will soon be a turn based or turn based strategy template, just so this genre gets more exposure for new UE devs. I actually tried to contact someone at Epic and asked them if I could help them with a turn based template free of charge because I saw the ticket… no reply yet. :frowning: Edit: That was before I fleshed out my implementation or discovered Monokkels though, I would still be interested in creating a template, but would leave path finding out.

And wow I need to check out your map generator as well Zeustiak! Looks awesome. :o

Looking sharp :slight_smile:

Yeah, the AI I will be including in my initial release won’t be that much more complicated. It will probably just choose the target that has the lowest health or defense within reach. I’ll use that as a base for building more complex in the future. Honestly though, I think some of the AI in successful turn based strategy games isn’t really all that complicated. The melee units in King’s Bounty seem to operate by a similar logic to the one I described above, for instance.

Zeustiak’s map generator is indeed something to behold :slight_smile:

I actually asked Unreal if they were working on a turn based template before I even bought UE4. After I bought it I searched the forums every day for mentions of turn based games and path finding, but after waiting for a long time I decided that if it was going to be done I had to do it myself :stuck_out_tongue: Looking back I see it as a good thing. I’ve learned a lot about path finding and blueprints, and I’ve managed to make something I’m very proud of.

Yeah I got them to add the Turn Based template to Trello back in May, but they have had higher priorities I guess. I hope when they begin work on the template that they realize some features that are needed for the genre and implement/expose them. I think by the time they do add a template that it won’t be that useful to me anyway, and I am fine with that. Learning a lot of these things from scratch is probably the best way to learn.

Hoping to start my own pathfinding work sometime early next year, though I won’t be releasing it to the marketplace.

Cool, I didn’t notice that it was you who suggested the template Zeustiak. ^^ I guess it is a low prio and probably because to have basic turn based stuff already requires a lot of setup, as opposed to basic 1P/3P/top down shooter.

Monokkel, very true that many TBS games have simple AI, I sometimes forget that. Having chessmaster type AI probably isn’t even fun at all. But I do hope that you can get personalities to work, especially from a designer tools perspective. Specifying unit AI at a high level and getting emergent behavior from that would be really fun to see come to life. ^^

Great news, I just got accepted for community voting! Please support by voting if you think this should be on the marketplace. :slight_smile:

Cool, up voted you.

For some TBS games a simple AI works, but for many, including Civ 5, that becomes a major flaw in the design. I think perhaps the hardest thing to execute with TBS AI is combined execution involving large numbers of units. I think if you can get that down, you can pretty much accomplish whatever you want with your AI.

You have to be careful with AI in general that you don’t make it always optimal, thats not very fun to play against in many cases. But having the optimal solution at your disposal is certainly useful.

Right. My plan is to actually make the most optimal AI possible, and then all the difficulty levels minus the hardest would be stepped down from that. I think it would be easier to step an AI down rather than up.

While the voting process is on-going I’m spending some time improving user friendliness. Before, you could iterate over all tiles of a unit’s action grid yourself and query per tile whether it was reachable, occupied (and by whom), had enemies within your attack range, etc. I have been thinking of how to improve on that, to decrease the number of nodes you need to get the result you want. I now made a search function that you can use to retrieve all tiles that satisfy conditions set by you. Of course you can still use the single tile queries, they are useful for their own purposes like handling player input.

When searching, there are a number of conditions for which you can specify whether they should be True (1), False (2), or you Don’t care (3) per tile. Only tiles that satisfy all are returned. As for occupant, you may require it to be None or Self (1), Enemy (2), Ally (3) or again Don’t care (4). Default is always Don’t care. Here is how it looks, assuming that “MyLevelGrid” is set up to represent your level and MyGridCharacter is placed on that level:

Here are example uses of the search function:

  • For displaying tiles, for example find all reachable tiles and paint them blue. Find all attackable, non-reachable tiles and paint them red. (Attackable AND non-reachable because blue has priority over red)
  • For an AI character that hasn’t moved yet, find all reachable, unoccupied tiles* and make a decision from the search results. Then use your selected coordinates to retrieve the corresponding path from the Action Grid. You can set “Enemies Within Attack Range” to true to only consider positions from which the unit can attack in this turn.
  • For an AI character that has moved, compute the action grid with Max Movement Cost set to 0. Find all attackable tiles with an enemy occupant. Choose a tile from the returned list, use the tile coordinates to retrieve the occupant from the Action Grid

Note: Tiles can be reachable and occupied at the same time, because some units are allowed to move through others. Who can move through whom can be defined by you.

Hope this search function is intuitive, feedback is welcome. :slight_smile:

I created a utility function that merges two action grids into a new one that contains all information except for pathing (but it does know the reachability). This can be used for computing the combined walk and attack range of multiple units. The immediate use of this feature is that players and AI can query the combined grid to know which tiles are safe during the enemy’s next turn.

Below you see the result where the walk and attack range of all black units is shown. Each unit has 2 walk range and 1 attack range.

This is awesome! Makes me want to play Final Fantasy Tactics :slight_smile:

Thanks! I’m hoping it will help people create their own FF Tactics. :smiley:

Nice updates! I am curious how big your blueprints are for this pathfinding. Could give me a good idea how long it will take to get some of this started. :slight_smile: