Pathfinding algorithm for walking through a grid
Hello, I'm not an expert on data structures and algorithms so sorry if this is a very banal question. I'm looking for a pathfinding algorithm, it doesn't have to mathematically perfect and return the shortest possible path in every case but it should be reasonably close and lightweight cause I plan to run it thousands of times. Here's the problem statement:
There's a rectangular 2D grid consisting of empty and filled cells and a starting point which may be anywhere on that grid. I want to generate a path which goes through all the filled cells atleast once and takes the least amount of steps. Each move forwards/backwards in a straight line takes one step while taking a turn takes another step. So for example if I decide to walk 5 cells east/west from the start and then walk 5 steps north/south it will take 11 steps in total.