I am currently working on a turn based RPG with chess movement. The characters move around is if they were following chess rules, but their attacks follow different rules. An example of how they will move can be seen below.

I don’t want pieces to have a lot of movement, so pieces like the rook or bishop won’t have infinite movement along its directions. Instead, movement is determined by a child tilemap layer with movement tiles. A piece is allowed to move onto any of it’s movement tiles (for pieces that move in a straight line, I’ll probably do something to prevent a piece from moving through an obstacle.

My question is this: How hard will this be to program enemy pathfinding for? The only solution I have thought of is checking every single tile the enemy can reach in the next 6 or so turns, and recording the shortest path to each, but that seems like overkill and like it’ll cause a lot of performance issues. For a more visual example, look at this?

How would I go about calculating the best path that will take the fewest turns for the rook on the left to reach the “knight” (I only have art for rooks rn)? What about the same but for the knight?

I don’t have much code at all for the project, I’ve mostly come here so I can confirm this kind of thing possible. If I need to I can come back when I’ve programmed more of the project, but I figured it may be more helpful to ask first before I code myself into a corner and have to reprogram something.

If anyone has any tips that may help, or resources I could have a look at, that would be much appreciated, but I’m kind of worried I’m stepping into new territory; this isn’t as simple as just drawing a straight line.

  • xyz replied to this.

    Probably same as normal pathfinding, the A* algorithm. Use the chess moves instead of just going to the next cell.

    What you can do for perf is only recompute when necessary instead of on every frame.

    At least with those, the bishop can't move diagonally and can only move two positions.
    The knight can only move 3 squares.
    You should be able to do a quick test of all possible moves and pick the best according to position.
    But yeah, astar would work for obstacle avoidance. You might be able to use the cost of a move somehow, also. You can set up astar to use diagonal movement or not. In chess you don't actually need obstacle avoidance so it's hard to say how useful it would be. Maybe you could use a raycast to check for a line of sight or something. If you are going to change the rules of chess, it might be a good idea to give the pieces a different look.

      Lukie4reals This is not really a problem for A*, but rather a regular tree search problem. Start by implementing a pure brute force breadth-first search, then proceed to look for possible optimizations, which would depend on the specifics of your system. Note that some targets may be completely unreachable with some movement rules (e.g. white bishop reaching black bishop)

          fire7side I'll probably end up going with A*, but probably just to find the path. It'll probably work pretty well for Rooks, Bishops, Kings and Queens, but less so for the knight. Also, yeah, the games art is very rudimentary at this point. The pieces will probably stay the same, but the environment isn't going to be a normal chess board, it'll be stuff like dungeons, dark forests, etc. These locations will be a lot bigger than a normal chessboard, which is why I'm worried checking every position is going to be resource intensive. The reason I'm looking for a general solution (I'll probably end up with specific solutions at this point though) is also because I plan on having custom pieces (with unique movement patterns) that you can recruit to your adventuring party. This game is basically just a normal RPG, but the "characters" have movement patterns similar to chess pieces.

            xyz My only worry is with checking brute force is the fact some of the maps will be quite large, and have a bunch of obstacles in them. Checking every possible move to get somewhere sounds like it may come with performance issues. I may go with a combination of using A* and brute force. I'll use A* to get a path, and just get the piece to follow it as closely as it can. Once they get close to the target location, start brute forcing only a few moves ahead at a time.

              xyz Bishops not being able to reach a target should be fine as well. This is an RPG, so the pieces will have spells, and other abilities so they won't need to get right on top of their target to actually attack them.

              • xyz replied to this.

                  Lukie4reals It's not about targets per se. Your search algorithm needs to be aware that there is a set of completely unreachable positions for certain movement rules, so it doesn't end up in an endless search. This is even more important if you want have a fully generalized system with rules that go beyond what we have in an actual chess.

                  Not sure that including A* in any way would be helpful here. It just may needlessly complicate things. Implement pure brute force and see if you get the results you want. Then worry about accelerating it.

                      xyz It'll be aware, don't worry about that. I'll need to program a brute forcing method anyways, so I can always do that first. It's not like it has to calculate every frame, just at the start of the enemy's turn. If that isn't performant, I'll probably mess around with A. maybe only test paths that go in the direction of A's shortest path (once you get super close you wouldn't need A, and it would stop calculating so a knight or something wouldn't overshoot). Honestly, on most instances brute forcing will probably work, I just want to have some method for calculating longer distances. The only reason I've thought about using A is in the event I have a larger map with lots of walls or something.