Level solving and pathfinding

Question

I have played a little flash game recently called Just A Trim Please and really liked the whole concept.

The basic objective of the game is to mow the whole lawn by going over each square once. Your lawn mower starts on a tile and from there you can move in all directions (except where there are walls blocking you). If you run on the grass tiles more than once it will deteriorate and you will lose the level. You can only move left, right, up, or down. However, as you finish the game, more tiles get added:

• A tile you can only mow once (grass).
• A tile you can run over twice before deteriorating it (taller grass).
• A tiie you can go over as much as you want (concrete).
• A tile you can't go over (a wall).

If you don't get what I mean, go play the game and you'll understand.

I managed to code a brute-force algorithm that can solve puzzles with only the first kind of tile (which is basically a variation of the Knight's Tour problem). However, this is not optimal and only works for puzzles with tiles that can only be ran on once. I'm completely lost as to how I'd deal with the extra tiles.

Given a starting point and a tile map, is there a way or an algorithm to find the path that will solve the level (if it can be solved)? I don't care about efficiency, this is just a question I had in mind. I'm curious as to how you'd have to go to solve it.

I'm not looking for code, just guidelines or if possible a plain text explanation of the procedure. If you do have pseudocode however, then please do share! :)

(Also, I'm not entirely sure if this has to do with path-finding, but that's my best guess at it.)

Virility

Answer 1

The problem is finite so, sure, there is an algorithm.

A non-deterministic algorithm can solve the problem easily by guessing the correct moves and then verifying that they work. This algorithm can be determinized by using for example backtracking search.

If you want to reduce the extra tiles (taller grass and concrete) to standard grass, you can go about it like this:

• Every continuous block of concrete is first reduced into a single graph vertex, and then the vertex is removed, because the concrete block areas are actually just a way to move around to reach other tiles.
• Every taller grass tile is replaced with two vertices that are connected to the original neighbors, but not to each other.

Example: G = grass, T = tall grass, C = concrete

G G T
G C T
C C G

Consider it as a graph:

Now transform the concrete blocks away. First shrink them to one (as they're all connected):

Then remove the vertex, connecting "through" it:

Then expand the tall grass tiles, connecting the copies to the same nodes as the originals.

Then replace T, T' with G. You have now a graph that is no longer rectangular grid but it only contains grass nodes.

The transformed problem can be solved if and only if the original one can be solved, and you can transform a solution of the transformed problem into a solution of the original one.

Bartels

Wow, that did it! Can't believe I didn't think of this. – Virility

Given the transformed problem, you're looking for a Hamiltonian path in the graph. Determining whether there is such a path is NP-complete. See this post on SO for possible algorithms. – Antilogism

@FlorianBrucker Thanks for the link, didn't know of that till today. – Virility

Just keep in mind that it is not NP-complete for some graph classes. For example, in solid grid graphs, i.e. grids without "holes" (or: walls), the problem is polynomial time solvable. link – Bartels

Answer 2

There is a DP approach for the travelling salesman.

Perhaps you could modify it (recalculating as more pieces are added). For a long piece of grass, you could perhaps split it into two nodes since you must visit it twice. Then reconnect the two nodes to the nodes around it.

Rahal