How we can extend this algorithm for adding walls in the board?

[maradanasai]

I would like to know how we can extend this algorithm (Hamiltonian path with shortcuts) for adding borders/walls in the board (similar to nokia 6110 snake game levels)? and how we can make this algorithm work for both width & height having odd numbers?

[taaha-khan]

I would like to know how we can extend this algorithm (Hamiltonian path with shortcuts) for adding borders/walls in the board (similar to nokia 6110 snake game levels)? and how we can make this algorithm work for both width & height having odd numbers?

In theory, a Hamiltonian circuit could be generated around certain walls in the board. This could probably be done with a modified Prim generator, which doesn't just generate a random Prim tree, but a tree that sort of loops around walls placed in the board, so that the Hamiltonian runner that traverses the tree should avoid the walls in the board. Also, the shortcut algorithm would need to be modified so that a snake wouldn't choose a shortcut through the cycle if there is a wall in between its next move. As for odd-shaped boards, I don't think that it is mathematically possible for a Hamiltonian Cycle to be generated in a grid with an odd width and height, or at least my approach cannot do it using a prim tree, because all the nodes in the tree can't be included.