Fun at first, but between level 7 or something and at least level 15, it's the same problem over and over (sure, positions change a little bit, but the method is exactly same). I wonder if it changes a bit later, but even if it does, it would be cool if some of these redundant levels were removed so people don't get bored.
Edit: level 17 is a little bit more interesting (albeit being the same thing) but level 18 and 19 aren't… Level 20 is the first one with 3 moves, so it starts becoming interesting again. Level 10 to 19 should really be summarized in just two or 3 levels.
Edit2: level 51 still has three moves. Three moves are more interesting than two, and most of those aren't too straightforward and repetitive (many aren't too hard, but some are a little bit tricky, which is cool), yet it causes a little sense of stagnation… I'm done.
It took me to about level 12, 13 or 14 to become .95 confident that I had learned to solve any solvable puzzle consisting of a 3-dot region and a 4-dot region using only 2 slices. (My probability that I had learned started rising fast 2 or 3 levels earlier, but it took a few levels to reach .95 confidence.)
I.e., my curiosity over whether I had learned a general solution to that class of puzzle kept my interest.
But more importantly, I enjoy purely perceptual tasks. There is almost no cognitive skill involved for example in piecing together a jigsaw puzzle or playing a game of billards. (At very high levels of skill, maybe billards demands significant cognitive work, e.g., leaving the table in a state designed to exploit weakness in one's opponent's skills, but that does not apply to the game under discussion.) Maybe the difference between you and I is that I enjoy purely perceptual tasks whereas you do not.
I agree with this, it matches what I felt too. I stopped playing at level 10 because it started to feel repetitive (also, I could see myself spend too much time on this :P)
If you haven't yet maybe implement statistics so you can see at which level people give up at?
I feel like around level 10 another mechanic needs to be introduced. Maybe 1 mirror and 2 lasers that you can position to cut and then 2 mirrors and 3 lasers, etc.
I'm at 49 now, and while I think your point is valid I don't agree that it's a problem.
Some repetition or easy levels do occur, but i solve them quite quickly so it's fine. One could even argue that interspersing easy and hard levels makes for good pacing.
Well, if you're level 49, you still have 40 three-moves levels to complete before going to the four-move mode, so maybe you'll sympathize with me by then ;)
It's hard to make one-size-fits-all. If you figured it out, then I think it's fairly quick to get through the ~10 problems. If you hadn't figured it out yet, then it's good practice, and then the game doesn't get too hard too quickly.
Strange, It's 90 on my computer… Btw, 70 levels with three moves is waaay to much. I've carried on up to 90 because I wanted to know if there would be a four moves level at all, but it was ridiculously long to come. 15 would have been more than enough.
OK I couldn't control myself and kept going... it actually goes all the way to 118. Some of 100-118 are really tough but some are just beautiful. It never goes above 4 slices. Anyways good luck :)
Since some people are complaining about the difficulty curve, you could randomly generate puzzles and rate them, and players, with Bayeselo (or similar; like chesstempo does). Then you have to use this ratings data to somehow discover how quickly to increase the difficulty of puzzles presented to the player (for example, perhaps select one with a 0.8 prob of success every time).
Actually, thinking about it some more, a player's rating should increase over time as they learn, while a puzzle's (true, latent) rating should be fixed, so you should allow for that.
Yeah, it's one of the most fun puzzle games ever. But it's not a mobile-style quick play game like this where you solve a series of puzzles. It's more of a world you walk around where you find the puzzles sitting around in the world waiting to be solved. But without spoiling anything, there's a lot more to The Witness than just the obvious puzzles in the world.
> Yeah, it's one of the most fun puzzle games ever.
I can't disagree more. While I can appreciate the visuals and the idea of stretching a single game mechanic until it a single atom thick, I found the game itself to be plain boring after the first hour or so.
It pales in comparison with Machinarium, Love You To Bits and even the Myst series. If The Witness weren't made by Braid's author, I seriously doubt it would've gotten any sizeable traction.
Edit, as far as unusual puzzle games goes, there's also Please Don't Touch Anything, which is absolutely ridiculous in its depth.
Part of this is having played Myst in the 2010s (rather than in its heyday) and comparing it to its successors, but I enjoyed The Witness much more than Myst.
Myst falls down in the same way as many adventure-style games I've played, in that it has too few puzzles.
Each one is self-contained, without much relation to any of the other puzzles in the game, and is dropped in your lap, fully-formed and fully-complex.
As a result, there's a lot of guess-and-check and you can kind of muddle through some of them without any understanding.
As a result of that, while each of the puzzles has its own internal consistency, the whole thing feels very arbitrary.
In comparison, because The Witness has so many (over 600) puzzles, it is able to ease you into full understanding of their logic.
You acquire a mastery of each individual mechanic over a series of puzzles, and nothing feels arbitrary or forced.
Because all of them are the same kind of puzzle, it can combine mechanics with delightfully cohesive results.
I really enjoy this kind of game design, it's the "show, don't tell" of progression (while Myst felt more "don't tell, but don't show either").
I will say that Myst is better at world-building than The Witness (despite The Witness feeling much more consistent).
But I'd rather play a really good walking-simulator and a separate really good puzzle game than a half-baked adventure game combining the two.
(All of this isn't to say you shouldn't try Myst if you haven't. I'd recommend RealMyst for that.)
> If The Witness weren't made by Braid's author, I seriously doubt it would've gotten any sizeable traction.
The Witness got a lot of initial attention because of the author, but it is also one of the games I enjoyed playing the most (far more than Braid, which was fine). But it's a certain kind of game that won't appeal to everyone's play style and probably depends on your mood.
But I guess what's so cool about modern video games is that there are so many good choices for different people.
It's true, the puzzle boards get repetitive, even with new mechanics added in every area. But the environmental puzzles are unlike any game I've played.
Myst was neat for the time, but I don't think it holds up all that well 30 years later, without the nostalgia factor.
Personally I never completed it but I still enjoyed the parts of the game that I did do. So it's not like you have to spend that many hours on a game, you can quit at any time. And on the flip side if you do want to put many hours into it there are a lot of puzzles to be explored.
After about 20 levels, I got more interested in skipping to the end for free. Poking around, it turns out that the game state is stored in browser local storage and fairly easy to reverse engineer (lesson for the motivated reader). Suffice to say with a few edits I was able to skip to the end and get to level 118. Still only 4 slices :)
Really neat, simple game. Worked great on Firefox Android.
I play plenty of puzzle games, and I always wonder what the process of designing the problems is like. Do designers develop some notion of solvability, and quickly generate puzzles "in reverse", procedurally, or nearly so? Or do they start sketching an idea of a puzzle and then tweak it until it's solvable at just the right difficulty level, with lots of gameplay testing?
I'm sure it depends on the puzzle mechanic, and this one seems particularly amenable to the procedural approach, being almost purely geometry-based.
Really enjoyed the game. One feature which would be nice: extend line segments to the whole plane. Right now, only partitions created by the line segment alone are counted, so even if you begin a line ‘before’ a dot but inside an island which would partition that dot if extended, partition is not counted.
In other words: For all points on an island which are either the beginning or end of a line segment, extend the segment from that point to infinity in the other direction. Maybe show this extension while the line is being drawn.
General logic - If there's 4 points on a blob, you want to break it into 2|2, not 1|3, because each move can only split a group of 3 into 1|2, but can often split 2 groups of 2|2 if they line up. The exception to this is if you can draw a line between two points that crosses a gap, then you can break a group of 3 in one move. At higher levels, you might need to create these gaps yourself with your extra moves. Idk, didn't play much beyond level 20ish
I got to level 20 or so and had figured out a working algorithm for two cuts whereby you would cut off 1 in the first cut and then find a good angled second cut to split off all the remaining pairs. This got a little more complicated when it went up to 3 cuts though...
There has got to be some math theorem to generalize a solution to n swipes.
I think it got really complicated when the initial shape was not convex. If its convex initially,then at best you can split all the groups in two, and in most of the puzzles you had to split all the groups in half (possibly not evenly if the group is odd) because you the number of lines you were allowed to make was roughly ceil(log_2) the number of dots.
But when its not convex you can potentially do better than just splitting all groups in half, and i found those the most challenging levels (i think it was either 20 or 21 that was like that)
I had the impression that the optimal swipes had an equal amount of dots on either side with the swipe going across as many open gaps (edges) of the shape as possible.
What would be an efficient solver for this problem, and what would the running time be? Seems like a naive solver would be too slow for this, could it be restated into finding the minimal number of cuts needed to fully disconnect a planar graph?
My gut intuition says you don't need to check the entire space of possible lines, just the lines between any two dots (rotated by an trivially small degree to separate the two), because a "correct" cut should always be defined by the bounds between which some dot on the border is included or excluded in a given cut.
You also don't need to check each sequence of legal cuts. Most positions can be deduced to be unwinnable given n-remaining moves.
I came up with basically this same idea independently when writing my solver (pasted in my top-level comment). It mostly works well, but it isn't obvious how to extend it to capture non-convex geometry.
E.g. cutting off 2 ears to create 3 regions vs cutting off whole head to create 2 regions.
My second initial gut reaction says you could add a point to the graph at the local minima of a non-convex curve and use it as a way to generate additional candidate, but not require the solver to eliminate it? Could probably smoosh an extra rule inn there somehow to eliminate pieces on that particular piece, but it wouldn't generalize to all non convex curves.
After some thought I think it works as-is if you just delete all edges between points which can't directly see each-other, as long as the visibility graphs are still connected.
The best cuts could then sometimes be edge->edge instead of always vertex->vertex. (e.g. each point at a random position in a little bump, where you want to slice off all the bumps in one go without going off at a random angle.
I'm trying to think about the topology of cuts in the plane but its hard to visualize. I guess it must be related to Voronoi and Delaunay.
Reminds me of mobile games ('Fruit Ninja' comes to mind) ... Having said that, there used to be a cottage industry of remaking old Flash games for mobile (and making a ton of money from that). Lots of great ideas in those Flash games.
I was inspired to write a solver for this kind of puzzle (it's not pretty but it seems to work well):
import numpy as np
import z3
import matplotlib.pyplot as plt
from sklearn.svm import LinearSVC
from sklearn.cluster import KMeans
def normalize(v):
return v / np.sqrt(np.dot(v, v))
def line_normal(v):
return np.array([v[1], -v[0]])
def line_segment_intersection_test(e0, e1):
a, c, b, d = e0[0], e1[0], e0[1] - e0[0], e1[1] - e1[0]
n = line_normal(b)
l = np.dot(n, d)
if l == 0:
return False
t1 = np.dot(n, a - c) / l
if not 0 <= t1 <= 1:
return False
if b[0] == 0:
return False
t0 = (c[0] + t1 * d[0] - a[0]) / b[0]
return 0 <= t0 <= 1
def min_cover(n, subsets):
#some simple pruning makes z3 run much faster
subsets = list(enumerate(map(set, subsets)))
subsets.sort(key=lambda t: len(t[1]))
redundant = set([])
for i, (_, s) in enumerate(subsets):
for j in range(i + 1, len(subsets)):
_, s1 = subsets[j]
if all(x in s1 for x in s):
redundant.add(i)
break
subsets = [t for i, t in enumerate(subsets) if i not in redundant]
s = z3.Solver()
included_subsets = [z3.Bool('subset_%d_included' % i) for i, _ in subsets]
for i in range(n):
covering_subsets = [j for j, (_, s) in enumerate(subsets) if i in s]
s.add(z3.Or(*[included_subsets[j] for j in covering_subsets]))
for bound in range(len(subsets)+1):
print("trying %d cut%s..." % (bound, 's' * (bound != 1)))
s.push()
s.add(z3.PbEq([(v, 1) for v in included_subsets], bound))
if s.check() == z3.sat:
model = s.model()
return [subsets[i][0] for i, v in enumerate(included_subsets) if model.eval(v)]
s.pop()
return []
def solve(islands):
edges = []
islands = [[np.array(v) for v in island] for island in islands]
print("enumerating edges...")
for island in islands:
for i, v_i in enumerate(island):
for j, v_j in enumerate(island):
if j == i:
break
edges.append((v_i, v_j))
vertices = np.array([v for island in islands for v in island])
x, y = vertices.T
x_min, y_min = np.min(vertices, axis=0)
x_mean, y_mean = np.mean(vertices, axis=0)
x_max, y_max = np.max(vertices, axis=0)
d_max = 2 * np.sqrt((y_max - y_min) ** 2 + (x_max - x_min) ** 2)
cuts = []
print("enumerating cuts...")
for i, v_i in enumerate(vertices):
for j, v_j in enumerate(vertices):
if j == i:
break
dv = normalize(v_j - v_i)
n = line_normal(dv)
eps = 1e-7
#try both cut orientations (left+right and right+left), and extend the cuts to poke out of the domain
c0 = (v_i + eps * n - d_max * dv, v_j - eps * n + d_max * dv)
c1 = (v_i - eps * n - d_max * dv, v_j + eps * n + d_max * dv)
cuts.append(c0)
cuts.append(c1)
print("finding intersections...")
cut_sets = [[] for _ in cuts]
for i, cut in enumerate(cuts):
for j, edge in enumerate(edges):
if line_segment_intersection_test(cut, edge):
cut_sets[i].append(j)
print("solving for min-cover...")
included_cuts = [cuts[i] for i in min_cover(len(edges), cut_sets)]
print("refining cuts using SVM...")
refined_cuts = []
for cut in included_cuts:
v0, v1 = cut
dv = v1 - v0
n = line_normal(dv)
side = (np.sum((vertices - v0) * n, axis=-1) > 0).astype(np.long)
svm = LinearSVC(C=1e9, loss='hinge', max_iter=10000)
svm.fit(vertices, side)
if svm.score(vertices, side) == 1:
m, c = svm.coef_[0], svm.intercept_[0]
dv = line_normal(m)
if m[1] == 0:
v0 = np.array([-c/m[0], y_mean])
else:
v0 = np.array([x_mean, -(c+m[0] * x_mean)/m[1]])
else:
print("SVM fitting failed: (falling back to grazing cut)")
dv = normalize(dv)
proj = np.sum((vertices - v0) * dv, axis=-1)
proj_min, proj_max = np.min(proj), np.max(proj)
proj_range = proj_max - proj_min
refined_cuts.append([v0 + (proj_min - 0.1 * proj_range) * dv, v0 + (proj_max + 0.1 * proj_range) * dv])
return refined_cuts
vertices = np.random.uniform(-1, 1, (15, 2))
n_clusters = 5
k_means = KMeans(n_clusters=n_clusters).fit(vertices)
labels = k_means.labels_
islands = [[v for j, v in enumerate(vertices) if labels[j] == l] for l in range(n_clusters)]
cuts = solve(islands)
for island in islands:
plt.scatter(*np.array(island).T, marker='+')
for cut in cuts:
plt.plot(*np.array(cut).T, color='black')
plt.show()
Are you sure you can’t do this with a linear programme? Surely there is a way to encode the line choices, the partitions they create and the number of dots within those partitions as a linear programme. Might be fun to try.
Edit: Outsourced to codegolf. Had to move the question to the sandbox, as I was unsure on grading. Will update when accepted.
Well,it is a set cover problem so you can use ILP and mip is actually much faster than z3. I'm sure it's possible (though maybe not easy) to use more geometry. I don't see how to make a simple linear program though.
Edit: level 17 is a little bit more interesting (albeit being the same thing) but level 18 and 19 aren't… Level 20 is the first one with 3 moves, so it starts becoming interesting again. Level 10 to 19 should really be summarized in just two or 3 levels.
Edit2: level 51 still has three moves. Three moves are more interesting than two, and most of those aren't too straightforward and repetitive (many aren't too hard, but some are a little bit tricky, which is cool), yet it causes a little sense of stagnation… I'm done.