[Request] What is the complexity in solving a grid-based least optimal path puzzle?
I created a puzzle game on reddit as part of the reddit "Games with a Hook" hackathon. The objective of the game is to force the longest path possible by placing blocks on a grid. There are other fixed blocks, waypoints, and teleports that extend the path even longer.
Is there a deterministic solution and how hard would it be to find?
The "Bot" I built for it basically does a recursive block placement along the current path, continues if it makes it longer, returns if it doesn't, then quits after set iteration count because I need it quickly. A "breadth first" approach. It does OK given that it doesn't prioritize teleports or placing blocks more strategically.
P.S. I am intentionally not posting the link because I genuinely want an answer and don't want to be accused of self promotion.
EDIT: Another aspect of the game is that the board size changes based on difficulty. The max Width/Height is 25x30, so 750 empty tiles worst case, however there are also randomly occupied tiles such as fixed blocks, waypoints, teleports, and the start/finish tiles that cannot be built on.
So lets say 650 empty tiles on the hardest difficulty.
I think a simple start -> finish on a 10x10 board is easily solvable, but I believe the more complex boards are NP-Hard and there is no solution outside brute force which would take a lifetime. I am no mathematician, which is why I am asking the people smarter than me.