Hi, I’m working on a game that will always be an n x n grid. I’d like to be able to always generate a new start position from the outer edge and have a path to the center cell. My issue is that I wan to be able to specify the path length instead of choosing the shortest path. Does anyone have an idea of how to do this?
I’ve looked at several CompSci forums, but unfortunately I’m unable to make heads or tails of what they’re saying.
Hi
Solving this for when self intersections are not allowed is an NP-complete (very hard) problem. See the very related wikipediate article https://en.wikipedia.org/wiki/Hamiltonian_path (your query is at least as hard as getting the hamiltonian path since the hamiltonian path would have to be computed by specifying the length as the number of nodes in the graph). This is unfortunately impractical to solve even for relatively small graph sizes.
In that forum, they talk about a solution that allows self intersections in the path (i.e the path may visit the same node multiple times), which is usually not what you want, but maybe it will be good enough for your use case. It is nothing that the A* Pathfinding Project supports out of the box however.
