I'm trying to develop a pathfinding algorithm that's a bit different from the standard ones. The main idea is to mimic a knight's movement in chess, moving from any edge of the board to a specific point while avoiding obstacles. The twist is that I want to count how many times the knight jumps over or lands on pieces, aiming to minimize that jump count to find the optimal path. I hope that makes sense!
I'm familiar with using Dijkstra's algorithm for pathfinding, where I typically set the cost of moving onto occupied squares to 1 and unoccupied squares to 0. But this doesn't align with what I need because it counts all the landing spots instead of just the jumps. I want a method that's scalable too, since I might be looking at huge grids (up to millions of cells).
If I simplify it, consider a 1-wide grid stretching infinitely with a piece that can move 1 or 2 spaces forward. There might be some empty spaces followed by occupied ones leading to the end point. I want to minimize the jumps, but Dijkstra's approach doesn't effectively do this. If anyone has suggestions or can point me toward how to tackle this, I would really appreciate the input!
2 Answers
I think another way to handle this could be by representing the knight's movement as its own network of connected nodes. When you move to a node, you can check the nodes along that path to see if any contain occupied spaces. If they do, you can add one to your jump counter for that move. It might simplify how you keep track of things, especially given your changing board state scenario.
You might want to try using a Breadth-First Search (BFS) approach, also known as flood-fill pathfinding. It works by keeping a queue of reachable spaces and marking them as visited as you explore. In your case, if you want to find the shortest path in terms of jumps, you'd store not just whether a cell has been visited but also the minimum number of jumps made to reach each cell. Once you reach your target, you can retrace your steps to find the optimal path.
That sounds promising! But how do I track whether a piece has been jumped over? I want to ensure that every time I jump over or land on an occupied space, I increase the jump count. Any tips?
That's a really interesting idea! I hadn't thought about it that way. I might give that a shot and see how it fits with the dynamic board approach.