Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

enclose.horse

enclose.horse

Post reply on HN
Print view View original

221–230 of 242 posts

Re: enclose.horse

#221

Post by banannaise »

gorgoiler wrote: post #41

Great game, I love it! I hope the author is collecting juicy analytics. They would be useful if they ever want to bundle 100 levels in order of difficulty and release this as a Steam game (which I would absolutely buy!) I don’t think the gates should animate up into the air. It breaks the visual logic of 2D for no benefit. It’s subconsciously confusing to see a gate I place in one cell move to occupy pixels in the ce…

The turn-based version sounds interesting, but I think it falls on its face in practice. The game then becomes:

1. lure the horse to an optimal point on the map.

2. trap it in a small circle of fences.

3. build part of your final wall with the remaining fences.

4. one by one, move the fences trapping the horse in place into position.

Re: enclose.horse

#222

Post by tasuki »

the_shivers wrote: post #213
rob001 wrote: post #64

This is a very cool and enjoyable game. I'd be really interested in knowing what framework/library was used to make it. I inspected the source and can see the game is done on canvas, but can't work out more than that.

Just vanilla canvas + Typescript.

Thank you for an interesting game! Is the code also available in a nicer-to-read way?

Re: enclose.horse

#223

Post by elestor »

xp84 wrote: post #190
Aardwolf wrote: post #189

Nice puzzle! But I'd like a button to go back to your most optimal solution so far: it's tedious to try other options but then have to convert it back to your better solution again...

There is one! Or maybe dev is just that fast. Tap where it says “Best: 67” and it reverts to previous best.

Say that again

Re: enclose.horse

#224

Post by sltkr »

emil-lp wrote: post #145
johanvts wrote: post #31

Earlier quoted context omitted.

I think it's NP hard, maybe from Sparsest Cut. But you could probably find the min-cut and then iterate by adding capacity on edges in the min cut until you find a cut of the right size. (if the desired cut-size is close to the min cut size at least).

It's NP-hard from Minimum s–t Cut with at least k Vertices. That's the edge version, but since the grid graph is 4-regular(-ish), the problem is trivially convertible to the vertex version. Edit: apex-4-regular

That conclusion may be too hasty. If min cut with k vertices is NP-hard on arbitrary graphs, that doesn't automatically mean that that applies to a 2D grid too.

Is NP hardness proven for just planar graphs? Those are closer to the 2D grid, but still slightly more general. All I could find was a reduction to densest k subgraphs, but Wikipedia tells me that whether that problem is NP hard for planar graphs is an open question.

To be clear, I would be very surprised if the problem turns out to be _not_ NP hard, but there is no trivial equivalence to min cut in general graphs to show that it is.

Re: enclose.horse

#225

Post by sltkr »

emil-lp wrote: post #145
johanvts wrote: post #31

Earlier quoted context omitted.

I think it's NP hard, maybe from Sparsest Cut. But you could probably find the min-cut and then iterate by adding capacity on edges in the min cut until you find a cut of the right size. (if the desired cut-size is close to the min cut size at least).

It's NP-hard from Minimum s–t Cut with at least k Vertices. That's the edge version, but since the grid graph is 4-regular(-ish), the problem is trivially convertible to the vertex version. Edit: apex-4-regular

Also I don't think the equivalence between edge/vertex versions is trivial at all (though maybe we just have different standards of triviality).

For example, in a grid like this:

    ..####
    .....#
    #.#..#
    #...H#
    ######
A single wall placed (i.e. vertex removed) can block two edges, and it's not obvious what graph transformation can turn that into a single edge.

Re: enclose.horse

#227

Post by plastic3169 »

gorgoiler wrote: post #41

Great game, I love it! I hope the author is collecting juicy analytics. They would be useful if they ever want to bundle 100 levels in order of difficulty and release this as a Steam game (which I would absolutely buy!) I don’t think the gates should animate up into the air. It breaks the visual logic of 2D for no benefit. It’s subconsciously confusing to see a gate I place in one cell move to occupy pixels in the ce…

Great game, I returned back to play next day.

> I don’t think the gates should animate up into the air. It breaks the visual logic of 2D for no benefit.

I also feel it would make more sense either for everything to be 2.5D or pure top down. Having appear / disappear animation is nice feedback to user though.

Other thing is that maybe the hitbox should change when the wall comes up. Now to remove it you need to press the grid, essentially the root of the wall. Unintuitive to me.

Thanks for the game, looking forward to when there is multiple horses or sheep to enclose.

Re: enclose.horse

#228

Post by zimpenfish »

zimpenfish wrote: post #47
savolai wrote: post #5

I would like to be able to compare/switch optimal with my solution with single click.

Side by side or a diff view would be great.

Happy to see there's now a toggle between "your solution" and "optimal" once you've submitted. Makes it much easier to see what you missed.

Re: enclose.horse

#229

Post by emil-lp »

sltkr wrote: post #225
emil-lp wrote: post #145

Earlier quoted context omitted.

It's NP-hard from Minimum s–t Cut with at least k Vertices. That's the edge version, but since the grid graph is 4-regular(-ish), the problem is trivially convertible to the vertex version. Edit: apex-4-regular

Also I don't think the equivalence between edge/vertex versions is trivial at all (though maybe we just have different standards of triviality). For example, in a grid like this: ..#### .....# #.#..# #...H# ###### A single wall placed (i.e. vertex removed) can block two edges, and it's not obvious what graph transformation can turn that into a single edge.

You transform it into the directed case and then you turn each vertex into an arc.

There is a standard construction for going between vertex and edge cuts.

Re: enclose.horse

#230

Post by emil-lp »

sltkr wrote: post #224
emil-lp wrote: post #145

Earlier quoted context omitted.

It's NP-hard from Minimum s–t Cut with at least k Vertices. That's the edge version, but since the grid graph is 4-regular(-ish), the problem is trivially convertible to the vertex version. Edit: apex-4-regular

That conclusion may be too hasty. If min cut with k vertices is NP-hard on arbitrary graphs, that doesn't automatically mean that that applies to a 2D grid too. Is NP hardness proven for just planar graphs? Those are closer to the 2D grid, but still slightly more general. All I could find was a reduction to densest k subgraphs, but Wikipedia tells me that whether that problem is NP hard for planar graphs is an open q…

I agree, that is a good point. Although it is (induced) subgraphs of 2D grids, which gets you a bit closer to the planar case (albeit with bounded degree).

It might be polytime on planar graphs, but that would be surprising.

Post reply on HN