So, I implemented pathfinding a while back. But like everything else I’ve been working on, I just did a quick and dirty implementation and moved on. Fast forward to today, and now that I’m getting ready to finally embark on that journey that is Unit A.I., I’ve had to take a small detour to fix up a known bug.
In today’s GIF, you can see me selecting a tile across the water for a particular unit. And, you can see them do the right thing, which is go around the water, across the desert bridge (why do I even have that there, lol), and to the destination. But this wasn’t what would happen a few days ago. You’d get the following:
As you can see, the unit is going right across the water, which is definitely incorrect. So, how did I get here, and how did I fix it?
When you think about how I’ve implemented pathfinding, there’s 2 main components:
This is where you, the player get to select which tiles you can move to. I’ve been discussing things related to this for the past few weeks, most notably, my blog entries about tile highlighting. Long story short, I make sure to block tiles you cannot go to. Water, mountains, etc. You know, the usual stuff. Nothing too crazy here.
This is where things got hairy during my initial implementation. You see, while I block the player from selecting a final destination tile, I wasn’t blocking the pathfinding logic from said tiles. So, as you can see in the last GIF, you can select the tile across the water, but when the path is generated by my pathfinding class, any and all tiles were up for grabs.
Turns out, I needed to implement this concept of Tile Cost. This is basically a number that tells the system how much it will cost to enter a tile. Originally, this value was calculated by finding the range between tiles. So if you had a tile at coordinate (0, 0), and at (1, 0), the cost to move to the tile would be 1.
The real way it needs to be calculated is by looking at some properties I have in my TileData class, most important, IsWalkable, and Movement. The former gets a cost of Infinity, while the latter has a value of (abs(tself) + 1). So for grass terrain, the movement modifier is 0, so the cost ends up being 1. Desert terrain has a movement modifier of -2, so its cost ends up being (abs(-2) + 1), which ends up being 3. So what do all these numbers mean?
Simply put, when the pathfinder is trying to figure out the best way forward, let’s say it’s looking at some water, which is not walkable. It’s cost will be infinity, so the next thing the pathfinding is say, “Oh shit, infinity is a lot, is there a better path? Oh, look, there is some grass terrain that has a cost of 1. Yeah, I think I’ll take that one.” That’s why in the main GIF, you see the unit avoiding the water, as it should.
Now that I have this implemented, I just need to write some unit tests to confirm that the unit will always avoid high cost tiles, then I’ll be good. Then I can finally start writing some A.I. Oh man, this is gonna be fun. About time to get this game looking like a real game 🙂