[GAME] Shape Fill

First of all, here's the completed game:

Pulp JSON:
Shape_Fill_-_Emit_Version_2.json.zip (5.8 KB)

Playdate PDX:
Shape_Fill_-_Emit_Version_2.pdx.zip (45.8 KB)


Changes
v1.2 (downloads above):

  • Only use a single emit function type
  • Swap shapes as they are processed to limit lag

v1.1:

v1.0:


Technical Info


Shape_Fill_Demo

I went into this project with two goals in mind; to get my feet wet with Pulp and to stretch the bounds of Pulp a bit. Shape fill was inspired by the game Flood-It, which consists of a grid of random colors with the goal being to flood the entire board with a single color within a turn limit.


Shapes

Shape Fill Shapes

As the playdate's screen is monochromatic, color-based gameplay was obviously the first element that needed to be changed. I settled on a set of 6 unique shapes to represent the different "colors". These shapes are items so that they all can have behavioral scripts attached to them. I set up a 10x10 grid of placeholder objects in the middle of the screen surrounded by a border to contain them. Each of the shapes are labeled as shape{number}Board so that randomization of the game board can be done on room load by the placeholder object:

on random do
	num = random 1,6
	swap "shape{num}Board"
end

Selection

Shape selection is handled by an invisible player character which only can move left and right on top of the shape selection area below the main game board. This is implemented with walls surrounding the shape selection area to limit the player character's movement:

Shape Fill Selection Walls

The tiles in this area are world tiles named with the shape{number} syntax to differentiate them from the item tiles that make up the game board and to prevent them from being updated with the rest of the game board. The player's appearance is swapped on each movement to match that of the tile below it and the arrow follows the player to provide information about which object the player is selecting. The player movement can be controlled from either the d-pad or the crank and the selection loops around in both directions.


Game Logic

[Edit] - Unfortunately, the recursive algorithm was too much for the Playdate hardware to handle in certain instances and was causing crashes. The below write-up will be retained for posterity, but isn't how the game is currently implemented. The code can still be accessed under the v1.0 changelog above.

One of the biggest restrictions to work around was handling the state of the game and updating the tiles without arrays or standard recursive functions. Normally, I would have stored the state of the game board in a 2d array. As there are no arrays in PulpScript, I utilized the screen as the storage of the game board's state and used functions to convert x,y positions to 1-dimensional positions and back again.

Implementing the flooding algorithm is easiest with recursion. However, with all user-made variables in PulpScript being global, the child functions created through recursion end up modifying the variables that will end up being used by their parents when the child function returns.

This problem took me a while to work my head around, but I eventually came up with a solution that allowed me to mimic recursion without the problems that global variables were causing. The magic lies in the event object. From the docs:

In events being handled by an instance of a tile, its x and y members will be set to the coordinates of the tile handling the event.

As such, for each cell on the board, I could "recursively" call each of its neighboring cells. This posed another problem, however -- what stops the cycle of endless calls?

This problem was complicated by the lack of arrays and local variables. With arrays we could just store a 1 dimensional view of the grid and then store 1s to mark cells as visited. With local variables, we could set each cell to have a visited flag. As neither of these solutions were supported by PulpScript, I had to get a bit creative. The solution I came up with was to duplicate the frames of all of the shapes and use the current frame number to determine if a cell had been updated or not. Then, I just reset all of the cells to frame 0 after the flooding algorithm had completed to prepare the game for the next selection.

	if event.x>xOffset then
		leftX = event.x
		leftX -= 1
		tell leftX,event.y to
			call "getTileFrame"
		end
		
		if tileFrame!=1 then
			targetTile = name leftX,event.y
			if targetTile==startTile then
				modifiedTiles += 1
				tell leftX,event.y to
					swap newTile
					frame 1
					call "updateNeighbors"
				end
			end
		end
	end

Final Thoughts

This ended up being a more difficult endeavor than I had anticipated, but both the process and end result were well worth the effort. The restrictions that come about from building a game in Pulp as well as the hardware itself lead to interesting design decisions. The process for architecting the game became an unexpectedly fun part of the whole process. There's also something to be said for completing a project and the satisfaction that brings.

8 Likes

Nice work figuring out the frame-as-tile-data that too appears to be the only viable method for storing per tile variables. It makes a bunch of genres possible, but too cumber sum to implement. Runtime frame/tile generation might be a viable workflow if the API allowed it. Otherwise more event.tile variables would be nice.

ShapeFill looks like a neat game. I wish I had a playdate to play on device, sadly I don't think the web json sharing workflow, well "works" for distributing games. The barrier to play is rather high.

Thanks! I agree that storing tile data is pretty cumbersome to implement, but still a useful trick to have for these sort of situations at this point.

I am really looking forward to seeing it run on a physical device. I definitely agree that the json sharing is not ideal.

Here's a video of your game running on my Playdate:

It's smooth and it's fun!

P.S. I did get several crashes after, say, my fifth move. I'll try to see if they're on our end or in the game.

1 Like

Wow! It's really cool seeing it run on the physical device!

Thanks for looking into that! I'll take a look as well and see if I can determine the cause, but I haven't seen any crashes or javascript console errors in my testing.

I have an update on the crash. It's overflowing the stack due to too much recursion :sweat_smile: I suspected it was something like that. I realize recursion is probably central to how you assess the game board, but I wonder if it could be broken up into chunks or something…

Makes sense! I'll look into how I can break it into chunks! I assume it's running out of memory on the device but not in the web browser, then?

Yup! It would be hard to overflow a modern desktop computer the way that it happens on our little handheld :slightly_smiling_face:

It’s not really memory as in RAM, it’s just the recursion exhausting the stack. I would suggest trying to flatten the updateNeighbor logic with emit. That function iterates over all tiles that implement the emitted handler in the order they appear in the room (left to right, top to bottom) at the time of the function call (meaning that order doesn’t change even if you change tiles as part of the handler) but you can still access the current state of the room.

If I’m following the logic correctly you could do the same thing with two emits and no recursion. In the first emitted event each tile would 1. do nothing if it’s already the new tile, 2. see if the previous tile has the same name as itself and if that tile was scheduled to be swapped (which I think you’re tracking with the frame), 3. if 2 isn’t true perform the same checks but for the tile above, 4 schedule itself for swap to the new tile if 2 or 3 are true. Then the second emitted event would swap all scheduled tiles to the new tile. It might be more work for the runtime but it’s flatter work. :playdate:

Thanks for the ideas! I assumed that stack size wasn't a huge limiting factor with this game based on the recursive "base cases" being handled by the current tile rather than neighbor, but that doesn't seem to be the case.

I'll need to think a bit on the implementation you've suggested, but it's definitely a possibility!

For reference, the current logic is:

  1. (Board PulpScript) - If the new shape is different than the current shape, set the top left corner to the new shape and set its frame to 1 (to mark as swapped).
  2. (Board PulpScript) - Call the top left corner's updateNeighbors
  3. (Shape PulpScript) - Check each neighbor that is within the game board bounds (left, right, above, and below in that order).
  4. (Shape PulpScript - updateNeighbors) - Each of the above checks are as follows:
    a. Check the tile frame of the neighbor
    b. If the neighbor's tile frame is 0 and if the tile matches the top left corner's starting shape
    c. swap the neighbor with the new tile
    d. Set the neighbor's frame to 1
    e. Call the neighbor's updateNeighbors (step 3)
  5. Loop through all tiles and set the frames back to 0 to prepare for the next player action.

@shaun I haven't finished implementing this, but one thing is standing out to me as a potential issue.

Please correct me if I'm misunderstanding the pseudocode you posted above.

Take the following board state, for example:
Shape Fill Flood Example Before

I believe the logic you posted would go as follows:

Starting in the top left and moving right and down, row by row, each X would be swapped to O until the first +. The X on the other side of the plus wouldn't be scheduled to be swapped due to the previous tile being a + and there is no tile above, so step 3 is also skipped. The remaining Xs in the first row wouldn't be scheduled to be swapped based on the step 2/3 logic as well. The next row would have no updates until the middle X which have false for step 2, but true for step 3 as the tile above is also an X and is scheduled to be swapped. Row 3 and 4 would be the same however all of the Xs in those rows should have been scheduled to swap. Row 5 would only be scheduled for swapping from the middle X to the end of the Xs going to the right. Finally, the bottom row would have no tiles scheduled for swapping as none are Xs.

This would result in the following board state:
Shape Fill Flood Example After

Whereas, the desired state is:
Shape Fill Flood Example Desired

I had originally implemented the flood fill logic as a while loop going from left to right, top to bottom. The issue I ran into was that neighbors to the left and above were not being filled in as they had already been processed. I believe the implementation you provided would result in the same problem due to how the emit function loops through the tiles in much the same way.

However, I believe that your implementation could be slightly modified to fully work. The first emit function (which schedules the swaps) would need to be called in a loop until there were no new tile updates from the last emit, as well as having each tile check to the right and below in step 3 of your implementation to see if that tile matched and was scheduled to change. Unfortunately, this is slightly slower than your implementation to some extent as, after the majority of tiles were scheduled for swapping in going down and to the right, it would only update one additional tile to the left and up for each arm of the fill area during each iteration.

Ok, I have the game now working with the new emit code. I'm curious as to the speed of the update code as the recursive one was designed to touch as few cells as necessary and this loops through the whole board a minimum of 2 times. I had to make a few more changes to the logic than what I thought, but it does run now. There's definitely room for some optimization, but I'm going to hold off at the moment.

Nevertheless, here are the files:

Pulp JSON:
Shape_Fill_-_Emit_Version.json.zip (6.0 KB)

Playdate PDX:
Shape_Fill_-_Emit_Version.pdx.zip (46.2 KB)

No more crashing! :tada: It's a bit slow on the device, takes a second or two for the turn to process. I wonder if it'd be possible to flip the tiles individually as they're processed?

1 Like

Thanks for checking it out and I'm glad it isn't crashing anymore! I should be able to do something like that pretty easily with the current logic. At the very least, it'll hide the delay a bit.

1 Like

I've updated the game to use a single emit function name which is still looped and to swap each tile as it is processed so that hopefully it hides the slow processing time.

Also, I learned that the frame function allows you to call it directly on x,y coordinates.

So, where I was previously calling:

tell x,y to
  call "getTileFrame"
end

if tileFrame == 0 then
  // do something
end

where getTileFrame was defined as:

on getTileFrame do
  tileFrame = frame
end

Now, I am just using:

tileFrame = frame x,y

Here are the updated files:

Pulp JSON:
Shape_Fill_-_Emit_Version_2.json.zip (5.8 KB)

Playdate PDX:
Shape_Fill_-_Emit_Version_2.pdx.zip (45.8 KB)