next »

[codekitchen]

Update: playable WebGL alpha build here, works well in Chrome.

Welp, I'm seriously dabbling in gamedev for the first time in almost 15 years.  



2001: A Carrot Odyssey is intended to be a very small puzzle game, it's my way of diving back in and practicing some of my (very rusty) skills while I work toward some larger game ideas. It's a pretty direct adaptation of a classic puzzle game: you have to place your space carrots (they were light bulbs in the original puzzle) on the grid in such a way that you light up every tile while satisfying the monolith's unbendable constraints. I've added a player avatar that you have to move around the board, rather than just directly clicking on tiles to add/remove lights.

Puzzles are randomly generated with a solver algorithm, though I plan to add a series of set levels as well.

Nothing groundbreaking here, I wanted to keep the scope small and relatively well-known so that I can focus on all the other stuff. My end goal is to have a small, but enjoyable and polished puzzle game. Right now I've got it running on desktop and appletv, I may port it to ipad as well but I think phone screens are probably too small.

The above animation will eventually become the title/menu screen. Here's an in-game screenshot from the current build:



Obviously I'm going for a clean, minimal voxel aesthetic, though currently it's too minimal. I really like the camera angle that I've ended up on -- it took a lot of fiddling, but I've ended up on an almost-isometric ortho view that is tilted at 15° rather than 45° on the y axis, to make more map fit on screen and navigation not so confusing (diagonal movement is always trickier).

[codekitchen]

I just solved a fun little problem with my random puzzle generation. A little background first: the high-level algorithm for generating a puzzle is:

• Create an empty playfield grid.
• Place wall tiles at random until we reach our desired percentage of walls (say, 20%).
• Fill the entire rest of the playfield with lights.
• Remove lights until no light is visible to any other light, but all floor tiles are still lit.
• Place monoliths on some walls, indicating how many lights must be adjacent to that wall.
• Remove all the lights, then try to solve the puzzle. If we can do it without too much "guessing", then call it good.
• If we had to guess too much, throw away the puzzle and try again.

It can take 20-30 attempts to successfully get past that "guessing" check, but that's OK because that still takes 50ms or less. But here's the wrinkle: the classic version of this puzzle doesn't have a player character, you simply click on a tile to add or remove a light (space carrot). When I added a player character to my game, I decided that they wouldn't be able to cross over walls or monoliths, and in fact they can only walk on lit-up tiles, never dark tiles. Because of this new wrinkle, my puzzle generation has to do a reachability check at the end to ensure that all floor tiles are connected, otherwise you end up with sad unbeatable levels:



A straightforward way to do a reachability check is to use a flood fill algorithm, which is basically the paint bucket tool in MS Paint. Start at one floor tile, then paint outwards. After we're done painting, verify that every floor tile was painted. If not, we've got a reachability problem, we have to trash the puzzle and try again. The problem I was running into is that once my puzzles reach 10x10 tiles or so, the puzzle generator was failing the reachability check sometimes 2000 times in a row without successfully generating a puzzle, and that was taking much too long.

You might have already come to the same conclusion that I did: instead of one reachability check at the end, how about we do a reachability check after we place each wall tile, and move the wall if the check fails? This is a great approach, I love the levels it generates:



But, the downside: this is super slow, since we're doing a flood fill every time we try to place a wall (and as the board gets crowded, it could take many attempts to find a suitable spot for each new wall). At least, it was super slow with my naive initial flood fill algorithm, resulting in this sad debug logging:

Succeeded in 32 attempts with wallPct = 25. Spent 35.23 seconds total, avg of 1.1 seconds per attempt.

35 seconds to generate a level! Ouuuuuch. But we can fix it! According to Jimbo's Crowd-Sourced Encyclopedia, a great optimization is the scanline fill. Basically, rather than cycling through one pixel at a time throwing all neighboring pixels on the queue, attack each horizontal run of pixels all at once in an inner loop. A few minutes banging on the keyboard later, and we get this new timing:

Succeeded in 32 attempts with wallPct = 25. Spent 0.034 seconds total, avg of 0.001 seconds per attempt.

Great success! We can definitely live with 32 attempts at "0.001 seconds per attempt". I threw the flood fill code into a gist, in case anybody is interested.

[codekitchen]

Today I started out working on some animations and other need-to-do's, like showing a victory sequence when you solve a puzzle. Then I moved on to implementing mouse controls in addition to the existing keyboard controls. This uses a pretty standard A* search to move the player and place a light wherever you click.

I'm still not 100% sure I like the way it controls currently. The primary problem is that you place carrots on the tile next to the one you're standing in, so I need heuristics to decide whether you should move to the clicked tile, or move next to it and place a carrot into it. Right now the heuristic is to place a carrot if the square is dark (can't move there anyway), or remove the existing carrot if there is one. Otherwise, just move don't place. But this gets fiddly sometimes, so right now I'm cheating and allowing you to click yourself to place a carrot in your current tile, even though the keyboard controls don't allow for that.

I could do something like left-click always moves then places, right-click always just moves, but I'd really like to stick with just one mouse button if possible. I'll keep noodling on it. 

This is the first build that's actually playable from start to finish, so I've published an alpha build for WebGL. It seems to work well in Chrome and Safari.