Bit Masking Wall Tiles

Howdy, ya’ll!!

I’m working on the new version of Circuit Dude, which is re-written to include a lot of new levels, features, etc. Needless to say, I’m trying to save as much space as I can while still making the game look better than ever. One of the things that I would like to do is a nice bitmasking tiling solution for the walls in the game.

image

As you can see, a lot of times, the walls will simply be snaking through the level. (I helped by coloring them green.)

image

When making bigger sections of walls, it adds to the noise of the level and I think it makes reading levels a little harder. Since I only have a few wall tiles saved as bitmaps. (This is the older version of Circuit Dude for reference.)

What I’m hoping is that the walls can be smushed together like in this mock-up:

image

This is one of the new additions I’m adding to the PC/mobile/Switch version of Circuit Dude and would like to add it to the Arduboy version.

I’ve come up with a few different solutions, ranging from including a bitmap of each different possible style of wall and selectively drawing the right one (takes up space!) or coming up with an alg to draw them nicely, but it’s so convoluted and possibly slow… I’m wondering what the ‘right’ way to tackle this that would be memory efficient is.

Right now, each level is compressed and then expanded into a 2D array of unsigned char’s when the level is selected, and I already have a function to figure out the surrounding blocks in all 8 directions and even to account for the boundries of the screen (that’s treated like it’s surrounded by more walls).

One of the things making my alg a little ugly is that I’m trying to account for the 1-pixel border that I want to seperate between the wall and the other stuff that could be next to it to give the level a little more readability and breathing room.

image

This is what the single block would look like as an 8x8 tile in my game where you can see that border. Here are a few more possible combinations of tile blocks, in no particular order, if this helps illustrate what kind f drawing I’m looking for.

image image image
image image

Anyway, this community is full of great programmers, like @Pharap, @MLXXXp, etc, etc, so I’m sure this could be a cool discussion as well as a way for me to learn something I never actually got a chance to work with, before.

4 Likes

You could encode a sort of vector vertices algorithm to draw walls based on where the corners are (and knowing walls must be closed forms it is just a matter of the function connecting the dots so to speak) but like you said you are just trading memory for cpu cycles in drawing them with this type of method. And it would really only be effective for larger complex shaped walls. I’m imagining you’d need one starting point and for each side of wall a direction and magnitude. Since walls are pretty small you could use bitfields to pack both direction and magnitude into one byte (2 bits for direction, and 6 bits for magnitude making walls of up to 64 pixels long possible, though you could extend them by having the next byte be in the same direction).

Ok, to make sure I’ve got this right, you’re just concerned with how to draw the walls like your 3rd image and that’s it?

If so:

  • Do all wall tiles use the same tile ID?
  • How are the levels currently packed in RAM? (E.g. 1 nibble per tile)
  • How much RAM do you have left over to play with?

The simplest solution I can think of off-hand is to select the right version of the tile by examining the tile’s 8 neighbours.

The fact that the tile’s appearance depends on whether or not each of its 8 neighbouring tiles is also a wall implies that there are 256 possible variants.

However, the actual patterns involved may be fewer.

For example
(W = wall, N = not wall, T = target tile, ? = ‘don’t care’):

? ? ?
? T W
? W N

Will result in the corner part being:
HalfCornerLarge

Regardless of what the ? tiles are, so you can use that fact to your advantage.

I think another rule might be:

? N ?
W T W
? ? ?

Producing:
TopLineLarge

I think using drawFastVLine and drawFastHLine should give you fast enough drawing if you need to forgo using extra bitmaps.
(Though a bitmap-based approach could work out cheaper depending on the circumstances.)

Figuring out exactly what patterns occur and how to take advantage of them would take some time,
but I’m relatively convinced that it’s actually not that many.
Most of the variants I can think of consist of only a few lines.

1 Like

Yeah, they are all saved as the same value of unsigned char in RAM. I have 48% RAM left. The game is about 75% complete, so I do not see that increasing by a whole lot by the time it’s done.

That’s what I actually ended up using at one point and it seemed okay… The code was something like this:

SUR0 SUR1 SUR2
SUR3 TILE SUR4
SUR5 SUR6 SUR7
if( SUR0 == NONE || SUR1 == NONE || SUR3 == NONE ) ) {
	if( SUR0 != WALL && SUR1 && SUR3 == WALL  ) {
		//DRAW #1
	} else if( SUR1 == NONE && SUR3 == WALL  ) {
		//DRAW #2
	} else if( SUR1 == WALL && SUR3 == NONE  ) {
		//DRAW #3
	} else if( SUR1 == NONE && SUR3 == NONE ) {
		//DRAW #4
	}
} else {
	//DO NOT DRAW CORNER
}
... (Repeat for each corner) ...

For each corner, you have the 4 possibilities:

//Do not draw
WALL WALL ????
WALL TILE ????
???? ???? ????

Results in: image

//DRAW #1
NONE WALL ????
WALL TILE ????
???? ???? ????

Results in: image

//DRAW #2
???? NONE ????
WALL TILE ????
???? ???? ????

Results in: image

//DRAW #3
???? WALL ????
NONE TILE ????
???? ???? ????

Results in: image

//DRAW #4
???? NONE ????
NONE TILE ????
???? ???? ????

Results in: image

If I save these 4 corner configurations saved as bitmaps, and do that for all 4 corners, I’ll save 16 bitmaps in an array. I could do a drawBitmap() for each corner (if it’s needed). If I offset them when I draw them, I do not need to save 8x8 bitmaps. Here are all of the corners that would be needed to make this work if I saved them as 4x8 bitmaps, which allows me to remove more duplicates: (There are now 6 of them.)

image

image

image

image

image

image

I hope that clears up what I’m trying to accomplish. :slight_smile:

Can’t wait for this game! One of my favourite on the Arduboy! Screams like an excited girl :heart_eyes:

2 Likes

Wow! Thank you! I hope you enjoy the revamped/new levels and mechanics. :slight_smile:

1 Like

Since you do not use diagonal wall pieces you do not need to check the diagonal walls. so you have 16 combinations of surrounding walls.

in your level tilemap you can just use a single tile for a wall and then use a function to look for the surrounding walls to get a proper wall tile to draw.

Mystic Balloons uses that method too.

Actually, I did take a look at this, but, for things to be drawn the way that I’d like, I would have to look at the diagonal piece.

For instance, if I had…

NONE WALL NONE
WALL TILE WALL
NONE NONE WALL

I would want it to look like this:
image

And if I put in a piece in the 1st diagonal spot, like this…

WALL WALL NONE
WALL TILE WALL
NONE NONE WALL

I would want it to look like this:
image

1 Like

Ah I missed that part. Will the tiles be drawn at multiple of 8 positions or will there be scrolling? if the first you could perform some logic operations on the screen buffer instead of drawing a bitmap.

1 Like

That’s not a bad idea. Unfortunately, I just implemented screenshake when increasing your temperature, so it may not be the best idea, unless I move over to a screen-buffer-level screenshake effect where I just draw the UI after drawing the shake.

What would this look like in some sort of psuedo code?

EDIT: To answer the question more directly, yes, always at an interval of 8 pixels.

I’ll have to get back on that later. My brains are not quite online :crazy_face:

1 Like

I stayed up like 42 of the last 48 hours. I understand! :zombie:

1 Like

I am extremely bad at these kind of things, but I have a feeling this could be done procedurally, do you actually save anything by doing the bitmaps? I’m curious if @sjm4306 suggestion where you are drawing lines might work out?

What this reminds me of a little bit of how quasi 3d games like doom or wolfenstine resolve inside and outside spaces.

Again, I wouldn’t have a clue where to start constructively but if you could get the code to some how walk clockwise through known “wall spaces”.

It would add a lot to render time but the code to do this I can’t imagine being smaller than just storing the bitmap versions.

Good luck sir, you are awesome.

It should be way less flash if you do this with an array of vectors instead…

#psuedo code
wall_sense = 
[
 # if these offset are blank and 0,0 is wall...
 [-1, -1], [-1, 0], [0,-1], kind_of_wall, # top left
 # top right, etc
]

Then you loop over the wall sense array until (if) you find a match, then you know what kind of wall you need… and you’re only writing the code once… instead of 4 times (for each corner)… the lookup table does the work for you. So actually the items are probably structs.

Using a data table and a loop almost always wins out over a huge if/else/case statement in my experience.

Actually it may make sense to figure out the 4 corners of the 8x8 individually rather than trying to code for EVERY possible case.

EDIT: I deleted this because there were a few errors. In fact, I tried walking backwords to fix some bugs, but I keep making things worse. :stuck_out_tongue:

Anyways the core point was that often a data table with 100 entries will out-perform a case statement with 100 complex conditionals… because each condition will get compiled into code… but if the actual CODE is the same (and only the data is really different) then with a loop all that compiled code gets reduce down to a SINGLE branch along with the data table.

YOu can always find me on slack. :slight_smile:

The maps must be fairly smallish if you can use a whole byte per tile.

That’s good to know.
That means there’s RAM free to use if it can be of any use.

If I’d seen this sooner I would have basically suggested roughly what @Dreamer3 suggested - trying to make a lookup table out of this somehow.

If it’s possible to determine what to draw in a corner of the target tile just by looking at a corner and two edges then that’s pow(2, 3) (8) possibilities.
You could fit that in a lookup table so it’s something like this:

WallLookupData
{
	bool sideA;
	bool corner;
	bool sideB;
	uint8_t cornerVariant;
};

WallLookupData wallLookup[] PROGMEM
{
	{ true, true, true, 0 },
	{ false, true, true, 1 },
	// ...
};

You’d probably pack this data more densely than 4 bytes though.
If there’s less than 32 corner variants then this will easily fit in a byte per entry.

In fact, there might even be a simpler way than that now that I think about it.
If you encode the ‘is this a wall’ as bits for the 3 sides then you could interpret those three bits as a number and use that as a lookup index.

E.g.

uint8_t wallVariantLookup[] PROGMEM
{
	0, 0, 1, 2, 3, // et cetera
};

uint8_t lookupWallVariant(bool isSideAWall, bool isCornerWall, bool isSideBWall)
{
	uint8_t index = 0;
	
	if(isSideAWall)
		index |= 0x1;
	
	if(isCornerWall)
		index |= 0x2;
	
	if(isSideBWall)
		index |= 0x4;
		
	return pgm_read_byte(&wallVariantLookup[index]);
}

Hopefully NONE isn’t a valid option because that complicates things.
Reducing this to ‘wall’ and ‘not wall’ makes matters much easier.

Are these all the valid possibilities?
And what does NONE even mean?

Have you tried switching to Sprites yet?
I’m pretty confident that it could probably save you a few bytes.

I almost fell into this trap at one point but managed to stop myself in time.

Not having corners to worry about would indeed make this much easier.
Sadly this is a ‘Moore neighbourhood’ situation rather than a ‘Von Neumann neighbourhood’ situation.

I know what you’re getting at.

Drawing an 8 pixel vertical line can be replaced with sBuffer[y * WIDTH + x] = 0xFF,
and drawing other line lengths should only be a few bitwise operations (shifting and masking mainly).

I also agree with this.
As I said earlier I think drawFastVLine and drawFastHLine should be fast enough.
They’re not as fast as what they could be admittedly (or at least drawFastVLine isn’t), but they should be fast enough.
(Much, much faster than drawLine at any rate.)

Almost certainly.

They are 14w by 8h!

NONE is anything except for another WALL.

Not quite, but I’d be interested in switching over if it helps. I think this is secondary, though, and would require re-writes elsewhere in the code, so I’ll sit on that change and wait for later if I need it.

Oh, thank you for reminding me of the names for this kind of search!

Oh, very interesting. I’m not sure I understand how to implement that, so I’m excited to see if ya’ll could elaborate. :smiley:

Not sure if it’s helpful, don’t know how efficient this kind of code would be… but if you could “mask” the area that is not a wall and basically draw a border around it?

But just thinking if you look at code samples for drawing borders might help. In art programs this is called stroking.

Still looking for help for this… :cry: I am hoping to finish Circuit Dude up in the next few days…

2 Likes