Jason (jcreed) wrote,

I'm in jetlag can't-sleep-'cause-it's-a-bright-and-sunny-morning-in-my-mind limbo so obviously I started wondering whether a certain decision problem is NP-hard or not at 5am.

It started out as an abstract single-player game idea: you have, like, a planar graph that you think of as a Risk-map, a bunch of little territory connected to each other in some way. There is a territory that you start out "owning", and each territory is labeled by a list of pairs of (resource, int). Kamchatka might have on it [(silver, -5), (caribou, +1), (armies, -10)] or something like that. An action consists of taking over a territory adjacent to some territory you already own, adding its resource-vector to the running total of how many resources you have --- has long as it doesn't involve spending resources you don't have. If I currently have [(silver, 6), (armies, 9)], I can't take over Kamchatka yet, nor could I if I'm not in possession of any territory next to it, even if I did have more armies.

So, decision problem: given a map, an initial territory, and an initial vector of resources, can I take over the whole map? Assuming my 5am brain has not made any errors, I think it's a cute not-very-hard puzzle to see that if there's only one type of resource in the whole map, it's easily in P, and if you allow at least two types of resources, it's NP-hard.

Question I don't know the answer to yet: how hard is it when you restrict to only one type of resource to be mentioned per territory but allow multiple types of resources in the map as a whole?

Separate squishier question: can this actually be made into a fun game? It feels very dry and "woo I am trying to solve an NP-hard decision problem" to me in its present form. Is there a good way to automatically generate "tight" problems, maps that are solvable but suspensefully just-barely-so?
Tags: games, math
  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded