Skip to main content
GameDev.net gamedev.net
🔒 Locked

Direction Booleans into single Integer

Started by JulianLoehr Apr 24, 2015 at 10:37 PM 17 replies 7.3k views
Original Post
JulianLoehr
JulianLoehr

Hey,

i have Input Data from a Gamepads DPad in form of 4 Booleans (Up, Down, Left and Right).

I need those to be converted into an Integer ranging from 0 to 8, where 0 is the Null State.


Up		1		0000 0001
Up-Right	2		0000 0010
Right		3		0000 0011
Down-Right	4		0000 0100
Down		5		0000 0101
Down-Left	6		0000 0110
Left		7		0000 0111
Up-Left		8		0000 1000

I haven't come up with a nice solution, nor found any pattern yet. So that's what i am asking for. Is there any nice Bit Operation Magic to put that into 1-5 nice lines?

Currently i am using this trivial but horrible way:


        if (Up && Down)
	{
		Up = FALSE;
		Down = FALSE;
	}

	if (Left && Right)
	{
		Left = FALSE;
		Right = FALSE;
	}

	if (Left)
	{
		ReportByte[0] = 0x07;
	}
	else if (Right)
	{
		ReportByte[0] = 0x03;
	}

	if (Up)
	{
		if (Right)
		{
			ReportByte[0] = 0x02;
		}
		else if (Left)
		{
			ReportByte[0] = 0x08;
		}
		else
		{
			ReportByte[0] = 0x01;
		}
	}
	else if (Down)
	{
		if (Right)
		{
			ReportByte[0] = 0x04;
		}
		else if (Left)
		{
			ReportByte[0] = 0x06;
		}
		else
		{
			ReportByte[0] = 0x05;
		}
	}

So any suggestions are welcome.

SiCrane
SiCrane

Does any 0 to 8 mapping work, or are you set on using the constants in your table?

Nypyren
Nypyren
Use a bit field. Also, why is this in Coding Horrors?

Following code is C# but the bitfield concept holds elsewhere:


[Flags]
public enum Direction
{
  None  = 0,
  Up    = 1,
  Down  = 2,
  Left  = 4,
  Right = 8,

  UpLeft = Up | Left,
  UpRight = Up | Right,
  DownLeft = Down | Left,
  DownRight = Down | Right,
}
Use | and & to perform bitwise manipulation.



This breaks your existing values, but will be much easier to deal with in the long run.

If the 0-8 range cannot be changed, then just go with your current code; it's not that bad.
JulianLoehr
JulianLoehr

The 0-8 range and values are fix and cannot be changed.

I forgot to mention that the code is for a Windows Kernel-Mode Driver, so it's Microsoft C and it uses the Windows Kernel-Mode Run-Time Library(Rtl) instead of STL.

On one hand i personally just don't like such nested multi-branch conditional statements. I think they are not good in terms of readability and maintainability.

On the other hand i just tinkered around myself and wasn't able to find any bit pattern for such conversion. So i am just curious if there is one.

I put it into coding horros because of the forums description. If this topic might be better suited in the General Programming forum feel free to move it.

Nypyren
Nypyren
In that case, you can do the bitfield as a temporary, then use that in a lookup table (this is C-like pseudocode so it won't necessarily actually compile):


int lookups[] = { 0, 1, 5, 0, 7, 8, 6, 7, 3, 2, 4, 3, 0, 1, 5, 0 };

int index = (up ? 1 : 0) + (down ? 2 : 0) + (left ? 4 : 0) + (right ? 8 : 0);

ReportByte[0] = lookups[index];
Should be damn efficient, and the code is compact.


(edit) My lookup table had zeroes for all of the 3-bit combinations instead of only cancelling out the opposing directions. Fixed.
SiCrane
SiCrane
Well, since we are in the coding horrors forum, I give you a branch-less, lookup table free solution:

return (up * (1 + down * 3 * (1 + 2 * (left + right + left * right)) + right * (7 + left * 2)) +
        down * (5 + left * 3 + right * 5 + left * right) + left * 7 + right * 3 + left * right * 8) % 9
This assumes up, down, left, right are always 0 or 1. This simplifies quite a bit if you don't need to support the situation where both up and down or left and right are true at the same time.

return (up * (1 + right * 7) + down * (5 + left * 3 + right * 5) + left * 7 + right * 3) % 9
Nypyren
Nypyren

Well, since we are in the coding horrors forum...


Well, we sure are NOW anyway smile.png
Waterlimon
Waterlimon 

int lookup[3][3] = {
{8,1,2},
{7,0,3},
{6,5,4}
};
int direction = lookup[1+down-up][1+right-left];

I thought this is a nice way to represent it if you go with a lookup... Array has only the values you need, and theyre arranged visually so its easy to change them if you want. You can easily extend it into 3D too if you need another axis of freedom.

o3o
Krohm
Krohm

STOP

Previously "Krohm"
Hodgman
Hodgman
Even if using the look-up-table approach, I'd highly recommend using one bit per direction instead of assigning each direction it's own ID number, as this will let you write logic that tests for a specific direction (e.g. up-left) but also easily test for classes of directions (e.g. any direction involving left: up-left, left, down-left).
enum DirectionBits {
  LEFT  = 0x01,
  RIGHT = 0x02,
  UP    = 0x04,
  DOWN  = 0x08
};
int lookup[3][3] = {
{LEFT|UP,    UP,  UP|RIGHT},
{LEFT,        0,     RIGHT},
{LEFT|DOWN,DOWN,DOWN|RIGHT}
};

int dir = lookup[...];

if( dir == UP|LEFT )
  DoUpLeftThing();
if( dir & LEFT )
  DoAnyLeftThing();
JulianLoehr
JulianLoehr

The single Direction ID is only used to be passed forward to the HID Class Driver. So i am not using it other than that i need to generate and forward it.

When i want to check for directions myself i still have my initial Booleans.

Nypyren
Nypyren 


int lookup[3][3] = {
{8,1,2},
{7,0,3},
{6,5,4}
};
int direction = lookup[1+down-up][1+right-left];
I thought this is a nice way to represent it if you go with a lookup... Array has only the values you need, and theyre arranged visually so its easy to change them if you want. You can easily extend it into 3D too if you need another axis of freedom.



That's brilliant. I'm going to steal this from now on instead of the bitfield-lookup approach.
SiCrane
SiCrane
The more I think about it, there's entirely too much danger that someone might actually understand the full factorial interaction matrix approach I used in my first try. So I give you the polynomial evaluation version:

  int64_t x = 3 * (up - down) + left - right;
  return x * (x * (x * (x * (x * (x * (x * (x * (-31) - 28) + 938) + 840) - 8519) - 6972) + 24412) + 12880) / 3360;
More seriously, the full factorial interaction matrix has 16 different possible coefficients, but the solution had 14 non-zero coefficients. For the polynomial evaluation, there are nine coefficients, and eight of them were non-zero. This basically says that the mapping structure is slightly more regular than just random assignment, but not by much. I'm not going to say there isn't some clever way to do this computation more efficiently, but the horrible brute force techniques aren't simplifying into anything nice.
l0calh05t
l0calh05t

The more I think about it, there's entirely too much danger that someone might actually understand the full factorial interaction matrix approach I used in my first try. So I give you the polynomial evaluation version:


  int64_t x = 3 * (up - down) + left - right;
  return x * (x * (x * (x * (x * (x * (x * (x * (-31) - 28) + 938) + 840) - 8519) - 6972) + 24412) + 12880) / 3360;
More seriously, the full factorial interaction matrix has 16 different possible coefficients, but the solution had 14 non-zero coefficients. For the polynomial evaluation, there are nine coefficients, and eight of them were non-zero. This basically says that the mapping structure is slightly more regular than just random assignment, but not by much. I'm not going to say there isn't some clever way to do this computation more efficiently, but the horrible brute force techniques aren't simplifying into anything nice.

No, it isn't random at all, but rather based on angles!


auto x = (float)right-left;
auto y = (float)up-down;
if(!(x || y)) return 0;
return 1+(int(round((4.f/3.14159265f)*atan2(x, y)))+8)%8;
Sik_the_hedgehog
Sik_the_hedgehog

Wait a second, is this related to a hat device or such? Because it sounds like 0-8 is what the device is returning (it is mentioned it's driver code, and I recall hats being returned as angles). That'd explain why the values can't be changed.

In this case yeah, a look-up table sounds like the best approach.

Don't pay much attention to "the hedgehog" in my nick, it's just because "Sik" was already taken =/ By the way, Sik is pronounced like seek, not like sick.
Sik_the_hedgehog
Sik_the_hedgehog

So you actually need the opposite look-up table, i.e. you have an entry for each boolean combination and the values in the table are the hat angle.

I'd suggest you to treat opposite directions as negating each other, i.e. if both get pressed simultaneously for some reason then set the table like nothing was pressed. The look-up table would look like this (assuming the order is up, down, left, right):


unsigned dpad_to_hat[] =
{
   0, 1, 5, 0,
   7, 8, 6, 7,
   3, 2, 4, 3,
   0, 1, 5, 0
};
Don't pay much attention to "the hedgehog" in my nick, it's just because "Sik" was already taken =/ By the way, Sik is pronounced like seek, not like sick.
frob
frob




In this case yeah, a look-up table sounds like the best approach.
It may the best approach, but the branchless polynomial version would be more fun to see in code.

Even if you comment it out and use the table (which is probably the best idea) it would absolutely make my day to see that commented out in the source code.


// The branchless polynomial version:
// int64_t x = 3 * (up - down) + left - right;
// return x * (x * (x * (x * (x * (x * (x * (x * (-31) - 28) + 938) + 840) - 8519) - 6972) + 24412) + 12880) / 3360;
// the boring but faster table version:
int lookup[9] = ...

I love seeing gems like that in code. It can make me smile for days on end.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.