The Battle Arrow
In nearly all of the tactics games I can think of, moving a unit is done by selecting a unit and then telling it where to go. In ISO TACTICS, this is also the case! It’s a great way to tell what path a unit will move along to get to a destination, something that is especially important when units must move to each tile along the way to a destination and not just teleport to their destination title.
It’s a great feedback mechanism and knew it was important for my game, but I hadn’t seen any good documentation of implementing it from back to front, so I wanted to take some time to talk about how I did it.
To start, you may have seen a hint of it in the last blog post (on Tumblr). Watch for the small yellow line that appears after a unit is selected:
You can see a rough implementation of pathfinding there, but to zoom out a bit before moving on, here’s that bit demonstrated specifically:
The biggest thing to notice is that, when I select a unit, it gives me a pathfinding arrow that looks like a a big “L-shape”. This was surprising to me, because I thought I had implemented the algorithm in question (Dijkstra’s) quite well and with a lot of help from Amit’s tutorial on A* over on his blog Red Blob Games (
which you should definitely check out).
I was somewhat confounded, because my paths looked nothing like Amit’s nor the “diagonal” path that you get in something like Advance Wars or Fire Emblem. I ended up tweeting at Amit and asking him what was wrong, and he advised I do something pretty simple. Basically, when doing the step where you establish a movement frontier for the algorithm to crawl, check to make sure the tile you are about to add to the frontier as having come from your previous tile
isn't in the same direction as the previous tile you added.
The “L-shapes,” despite their “ugliness”
are valid paths. The frontier, before modification, would search for new neighbors to the North, East, South, and West (as it should) each time it reached a new tile. Because tiles would almost always have a tile neighbor to the North of them, nearly every tile would resolve to have “come from” a tile to the North or South of it. This means that the process of getting to any tile would be a combination of either East or West movement, followed by either North of South movement, never alternating.
But as we said before, that’s not what we want. We want those nice diagonals, even if tile movement is restricted to cardinal directions. What was confusing about Amit’s tutorial is that he
does get diagonals, but obscures the parts of his algorithm that allow it. If you look closely at the
breadth first search section, you can see a bit of what his underlying algorithm is doing.
In the above picture, the number in each tile represents in what order that tile will be visited to search for further neighbor tile. The 1, grey out above, was the first tile, the 2 to the east was the second, and so on. When a tile is visited (indicated by it being grey), new neighbors are added to be searched. So when the 1 tile was visited, the 5,6, and 7 tile were marked. If this is confusing,
check out his page. The demo is interactive and you may be able to get a better sense of how it works.
Already though, there are oddities. The red blob, after it’s first placement, looks for a tile to the North, East, South, and West, in that order, indicated by the 1, 2, 3, 4. But even as tile 1 is visited, the neighbors are not added in that order! Instead we see that the next tile added is the tile to the East, 5, followed by West, then North. South is occupied by the reb blob, so it makes sense that it isn’t visited, but why wasn’t the tile to the North again the first tile?
This goes back to Amit’s suggestion. Internally, he’s checking to make sure the first tile to be visited in any new step is not also in the same direction the previously visited tile was to
its previously visited tile.
So, when implementing the check:
Ta-da! We’ve now go diagonal movement paths. For those that know Unity though, you likely notice that right now the pathfinding indicator is just a debug line. This work great if you are testing internally, but I need an actual sprite line to show the path. So next, how do you stroke the line?
Well first, we need art. Cobralad sent me over some arrow sprites:
There are two ways to go from here, and I’ll admit I’ve chosen the easier one for now. To render a sprite on the screen in Unity, it needs to be attached to a GameObject. Right now I’ve got two options for this. Either make a new GameObject for each needed arrow segment, or leverage a preexisting GameObject to render to through a shader. I thought for right now it would be best to just implement the line through GameObjects to make the coding a bit easier, but now that I’ve got the logic in I can port it to shader code by leveraging Unity’s Material.SetFloat to point to a texture offset of a loaded in texture (namely, the arrow one above), and just render it directly on top of the corresponding map tile GameObject.
To actually stroke the path, a function, strokePath(), is called every time a valid path is found. What stroke path does is take in the “valid” path, and then process the tiles in the path to figure out the corresponding sprite that must be placed at a given path tile. To process the path and find the right sprite, you need to know the direction between two tiles, then apply the sprite that corresponds to that direction. To find the direction, it’s a simple matter of subtraction. If one tile is at [2,0] and another is at [2,1], then the direction from the first tile is [2-2,1-0] or [0,1], aka, one tile to the North. That means that you can place the Sprite that goes North/South. Implementing that directly though gives us this:
That’s close, but obviously not right. What’s the issue? The problem is that, because you can only, by design, move in cardinal directions in the game, the “direction” finding never resolves into a diagonal heading like [1,1] or [-1,1], etc. despite the movement itself being “diagonal”. What we actually want isn’t the direction to the next tile, but instead to the tile
after the next tile. So if we start on Tile A, and are trying to find the sprite to place at Tile B, we have to actually find the direction to the tile
after Tile B, Tile C. This gives us the proper indices into the arrow sprite array!
A final note here. Notice that, along the diagonal paths, the sprite for a given direction alternates between a flipped version of itself! If you just implemented the diagonal checking above, you would, similar to the “L-shapes” above, only get one sprite that matches up to every other tile in the found path. This is the same issue as the “L-shapes” problem — you need to check and see if your current direction
is the same as your previous direction. If it is the same and is a diagonal path, you pick the opposite sprite!
Hope this helps other people looking to program the battle arrow in their games!
Community
