Mark Gritter (markgritter) wrote,
Mark Gritter
markgritter

Trying to Solve a Silly Game

One of the flash games I currently have bookmarked is Globs. The game layout is a grid with each square containing one of six colors. You control the color of the upper-left square and all connecting squares of the same color (a "glob"). The goal is to grow the region you control to fill the entire grid.

Is there an efficient way of solving this game?

We can easily arrive at a lower bound on the number of moves remaining, by using breadth-first search to assign a distance to each of the remaining globs, where "distance" == # of moves required to absorb the glob. But this bound is not very tight--- we might follow one branch of moves to absorb a distant glob and still have just as many moves left to reach a different glob. I tried using the max distance as the heuristic for an A* search, but this didn't work particularly well--- there are just way too many possible paths for a reasonably-sized game.

Depth-first search will feasibly identify an upper bound, but again not a particularly good one.

I have been trying to think of a dynamic programming approach but it seems hard to come up with a formulation of the problem that doesn't either leave out valid solutions, or suffer exponential blowup.

One property that seems useful is that a path to a glob can be arbitrarily interleaved with other paths. That is, inserting an extra move into a path doesn't break the path. So if the minimal path to a glob on the far right is Red-Green-Yellow-Blue-Purple, and the minimal path to a glob on the bottom is purple-green-yellow-blue, then the path pRGgYyBbP will reach both globs, and can obviously be simplified to purple-red-green-yellow-blue-purple.

But does this interleaving really result in the minimal path to hit _both_ globs? I think that in some cases it does not. It is certainly the case that (more generally) given a set of globs, the optimal path to reach every glob in the set need not contain every minimal path as a subpath.

For example, here's a small game with optimal solution blue-yellow-purple-red-green (or blue-purple-red-green-yellow, or blue-purple-red-yellow-green):

RGGGGRG
RGGGGRR
RBYYYPG
RBBBBPG


But, the optimal path to the upper right red region is green-red, which is not a subpath of the complete solution.
Tags: algorithm, games
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 23 comments