2
$\begingroup$

Given the 2D grid shown below, where blue tiles can be visited and island tiles cannot.

Given that we do not know the starting position of a player on this grid.

Given that the player can move 1 step in any cardinal direction every turn.

Given that the player cannot visit tiles he has already visited.

Given that we are told every turn in which direction the player has moved.

What would be a computationally efficient algorithm to pinpoint the player's location in the least amount of turns?

enter image description here

One way that comes to mind that would give me good results but would probably be computationally intensive is to try to apply the player's path to every possible starting position. If we can traverse the path without hitting an island or going off the map, then the end tile is a valid possible position for the player. At first we would have a lot of possible positions for the player but eventually, after several turns, we'd end up with only one possible position.

I don't very much like that approach as it seems computationally heavy.

Instead, I've implemented a simple solution using a bounding box. At the beginning of the game, the player could be anywhere. But as soon as he moves, we can narrow the bounding box. For instance, if the player's first move is north, we now know that he can't be in the bottom row of the map. All that is needed is to keep track of the top left and bottom right coordinates of that box and update them every turn according to the enemy's movement until the box is eventually narrowed down to the player position.

I like this solution because it is simple and computationally light. The problem is that it doesn't take into account the islands and the players' previously visited cells. Therefore, only when the bounding box hits the grids' limits can we narrow it down. If the player starts in the middle of the map and tends to stay there, it can take a long time before narrowing down his position.

Is there a way to refine my solution (bounding box) in a way that would at least account for the islands and at best for the player's visited tiles as well? If not, what other algorithm could I use?

$\endgroup$
  • $\begingroup$ I don't understand the setup. Each turn can the player choose the direction, or is it chosen for them? If the player chooses the direction, what does it mean to say that the player is told what direction they moved? Do you mean the player is told whether they moved in that direction or weren't able to? How large is the grid? 3x3? $\endgroup$ – D.W. Mar 30 at 17:07
  • $\begingroup$ I guess I wrote my question from the perspective of the AI. So when I talk about the player, I'm talking about the opposing player. He's able to choose the direction in which he travels each turn. We, the AI, are told the direction he moved in. The grid, as you can see from the picture, is 15 x 15. $\endgroup$ – snowfrogdev Mar 30 at 18:26
1
$\begingroup$

Don't be so quick to reject your approach! Your approach is a great solution. On a $15\times 15$ grid, you'll only have to try 225 different options. Checking each option is very fast, so it should be extremely fast to try all 225 different solutions -- I'd imagine it will finish in microseconds.

As Knuth supposedly said once, "premature optimization is the root of all evil". My advice: Try that solution, implement, and measure its performance, before you even consider anything else.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.