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!
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.
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.
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.
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.
