One mechanic Rogue Pawn will feature is "chessboard" style battles. 

Unlike the free-roam movement that was featured in the Ludum Dare (LD) release, we want these "chessboard" interactions to feature grid-based movement, just like a real game of chess. 

We're still figuring out exactly how these interactions will work, but as you step onto these boards, your movement is constrained to the grid, a border pops up around the board,  and your foes appear and come to life.

When it came to enemy AI for these "chessboards," for a while I (Arden) kept hoping that I could get away with AI that simply makes a best guess at how to hunt you down, mixed with random decisions when best guesses weren't easy to figure out. 
But after trying to tweak that approach, I realized looking one step ahead just wasn't enough.  Enemies need to know how to actually make a path toward you.

Enter pathfinding. 

This is a topic that indie developers might love to have a reason to avoid programming (hence my previous approach), and for something that moves in 4 directions, like a traditional grid-based-baddie, that might not be hard to fake. You just move in the square that's closest to the player, and hope there's nothing in the way, right?

But what about the Knight? 
As you may remember, if you've ever played chess, knights move solely in "L" shapes:

With Knight movement, simply moving to the nearest square isn't a very elegant solution, since the nearest square (by distance) isn't necessarily the nearest square (in number of moves)

So I set out to creating an "Breadth First Search algorithm" that could manage Knight movement.

The first step was to populate the grid with  relevant data. 

Shown here is:

• green - player coordinates (starting with row and column 0)
• yellow 0 - "empty" squares
• orange 2 - enemy 
• pink 1 - solid obstruction

This data will be useful in finding the grid locations that pieces can actually move to.

The next step is to do a "Breadth First Search" from the player location, using a technique similar to this article.

In this photo, I've removed the yellow 0s in favor of green numbers indicating how many "knight moves" away that square is from the player. This is done by starting from the player's location, and moving in "knight shapes" away from the player, incrementing squares as you go, similar to the linked article. (Just in knight movement options, rather than cardinal directions) 

With this information populated into the grid, we now have enough info to begin the knight AI.
I will start by having the knight simply move to the "lowest number" grid it can reach in one move.As you can see in this image, two of the available movement options for the bottom knight put him two moves away from the player, while 3 of them put him 4 moves away from the player.  So the chess unit can just move to one of those two squares, and be one step closer to the player! Here it is in action:

Here, you can see the pathing algorithm updating every time a knight moves or when the player moves. For demonstration purposes, I have the algorithm run both when any unit lands, and right before knights move, so you can see the numbers and path lines update. In the final version, it will only need to run right before the knights move.

But  we're not done there... that's not how you play chess. If you can't safely threaten or attack your target in one turn, you don't just try to move closer to it, but instead you try to think ahead. Often, that means blocking or restricting a piece's movement options. 
So when knight-style pieces are more than 2 moves away, they need to run a second pathing check that looks for smarter moves:

If you look at the picture on the left, I've shown two different options each knight has (yellow circles), and which path they plan on taking (green). As you can see on the right, with a tweaked special-case pathing algorithm that also targets the locations the player can move to, the top knight can bock the player in 1 move if he chooses the green circle. In the left picture, that square is marked as 6 moves from the player, and wouldn't have been though of as a valuable move had we not considered blocking moves!

That's all for now! Thanks for reading!
-Arden

My twitter: @ArdenJD

Rogue Pawn Facebook page: Dija Studios