Algorithm: Travelling through all array elements with limited move constraint

Question

Greetings.

I have an 2-D array of size [N][N] which will represent a rectangular area / map with N rows and N columns.

Let's say I pick the middle as starting point (or anywhere else), I want to walk through all elements with the constraint of moving only X times before having to reset back to starting point. I then can walk through the path I've went to, but that will waste a turn.

I'm just wondering if there is a specific algorithm for this problem so I can compare with my current way of doing which just stores the moves I already did. (quite messy tbh)

Thanks in advance.

Answer 1

It looks like you're talking about a turn-based game? So I think you should not look at them as turns, but look at objectives, than use a path finding algorithm to see how many steps away the objective is, than assume the objectives have a value and divide that by the amount of turns needed to get to that objective and chose the highest result as your current destination, the next turn you'll have to rethink your strategy again.

I tried to make my answer more clear, do the following for each turn.

1. Determine the value of the objectives
2. Determine the amount of steps needed to reach the objective using a path finding algorithm.
3. Calculate the amount of turns needed (Math.Ceil(steps / stepsPerTurn))
4. Determine the object with highest value for the least amount of turns.
5. Travel to that objective.

Answer 2

Heres a strategy which is not optimal, but it's easy, reasonably efficient, and you don't need to keep a big storage list or do fancy computing or coding.

Start at your current point, and walk right until a wall. Step down, walk left. Keep zig-zagging back and forth. If you reach the bottom, start over and zig-zag cover the top half in a similar way.

If you run out of steps doing your painting, just walk straight towards the location you were at before, and continue painting.

This algorithm is not optimal, but it's likely 10 lines of code and 2 variables.