07-28-2019, 07:28 PM

After quite an absence due to work and life, absence that may continue a bit more (I should read all the posts that got updated after the first week of May), I would like to drop a little problem that I find interesting.

You may know age of empires, well one can extract many interesting problems from strategy games. The problem is to see them.

One of those is the question: ok, there is a grid (a matrix), an object start in the middle of it (or in the 4 middle positions), then moves to the center of each other square, does an action for a certain time (chopping), and then comes back.

The problem is: how much time it takes to visit all the grid locations, provided that it goes always back to the center of the matrix/grid, and once returned to the center, it goes visiting the nearest non-visited square. The time problem is an indirect problem of the question I want to pose here. The sum of all distances.

Of course it can be done programmatically (it is a nice intensive task for the calculator), but is there a less "brute force" formula for it? Aside from basic ideas like computing the distances only for a quadrant of the matrix, that reduces the computation by a factor of four.

I tried with some friends and we didn't see any better than, at the end, a long list of terms in a summation. Even in a continuous case, we didn't make much progress. For example in the continuous case one can say "ok I have concentric circles, thus I have the sum of the radiuses multiplied by the number of the points on the circles" but, yeah, the points are infinite so it doesn't work.

If the problem is not clear, please ask so I'll try to clarify. Although the youtube video below can help plenty.

source: https://youtu.be/_UEPVFjNgfs

You may know age of empires, well one can extract many interesting problems from strategy games. The problem is to see them.

One of those is the question: ok, there is a grid (a matrix), an object start in the middle of it (or in the 4 middle positions), then moves to the center of each other square, does an action for a certain time (chopping), and then comes back.

The problem is: how much time it takes to visit all the grid locations, provided that it goes always back to the center of the matrix/grid, and once returned to the center, it goes visiting the nearest non-visited square. The time problem is an indirect problem of the question I want to pose here. The sum of all distances.

Of course it can be done programmatically (it is a nice intensive task for the calculator), but is there a less "brute force" formula for it? Aside from basic ideas like computing the distances only for a quadrant of the matrix, that reduces the computation by a factor of four.

I tried with some friends and we didn't see any better than, at the end, a long list of terms in a summation. Even in a continuous case, we didn't make much progress. For example in the continuous case one can say "ok I have concentric circles, thus I have the sum of the radiuses multiplied by the number of the points on the circles" but, yeah, the points are infinite so it doesn't work.

If the problem is not clear, please ask so I'll try to clarify. Although the youtube video below can help plenty.

source: https://youtu.be/_UEPVFjNgfs