[Game]Raquer*Mete - A Hack*Match clone for Pokitto

release
puzzle
game

#1

Hack*Match is a minigame inside Exapunks.

screenshot

You can do two things: invert the two last pieces in a column, or grab the last one to place it in another column. When four pieces match, they disappear.

More info, code and binary in the repository: https://github.com/denismr/raquer-mete

Frames (background images) by @Vampirics.

Latest version 1.05: raquer.bin (76.3 KB)


#2

Very nice! Looks like a fresh take on the famous match-three (or four in this case) genre.


#3

I just released a new version fixing a very small bug where a bomb could be generated while near another bomb of the same type (and they would not be triggered until you interacted with them). This should not happen anymore (bombs can’t be generated near other bombs of same type).

On a side note, I’m thinking of replacing one of the colors of the palette (probably the orange) with purple to try and have more contrast.


#4

Looks awesome,


#5

This is so awesome! Thank you for sharing :smiley:
Also, I love Exapunks xD


#6

Thanks!
I hope you’ll like it.

Just on thing… While I observed my sister playing, I noticed that it’s not easy to realize that you can hold the directional button and the robot keeps going in that direction. It just takes a moment before gaining momentum (so that you can do precise movements in short distances).

In a close note, I just wanted to know whether a button (which button given by a variable) were being pressed ATM and didn’t find the correct method to get that info. I then wrote the following code

 // pokitto is an instance of Pokitto::Core
pokitto.buttons.repeat(button, 1)

Then I noticed that sometimes (very rarely), it keeps returning true even when I released the button, and I have to press it again to make it stop.

So maybe there is a bug there, but I didn’t check any further.
I saw that I could have written buttons.leftBtn() and etc… But is there any method that receives the code for a button and returns if it’s currently being pressed?


#7

I noticed that kind of behavior with some other games on the pokitto. I think it does that in Planet Escape as well… Always thought it was more a problem with the hardware. ( I must be wrong )


#8

I think Pokitto::Buttons::pressed(buttonCode) > 0 should work.

Could be the 255 frame limit, or the interrupt not firing properly or something.


I just noticed drawPiece, did Pokitto::Display::drawBitmap not work for you?

And Pokitto::Core::update() already clears the display, so you don’t need to call Pokitto::Display::Clear() manually.

Also, for future reference, the standard library already has a shuffle algorithm built in.
Prior to C++17 there’s std::random_shuffle, and after C++11 there’s std::shuffle:
https://en.cppreference.com/w/cpp/algorithm/random_shuffle


#9

“Raquer*Mete”
I see what you did there… :stuck_out_tongue:


#10

Interesting! Could you elaborate what is that limit?


#11

@Pharap
Thanks for your response

The problem with

Pokitto::Buttons::pressed(buttonCode)

is that it returns true only once (when the button is pressed). I was looking after something that kept returning true every time while the button is down.

I used Pokitto:Display::drawBitmap at some point. I didn’t use it for the pieces for two reasons.
First, originally I had only one bitmap for every color, and changed the color depending on the piece. Later, I added more images (one per piece), but I still use the technique for pieces that are matching.

Another thing is that drawBitmap doesn’t seem to use transparency, and I need that for the background in the selected column, and to draw the piece over the robot.

Also, I’m aware of the shuffle in the algorithm library. I use this library already (and it’s included in the file).
However, as far as I know (and I can be wrong here), the “random” used by the C++ stdlib is not the same as the random used by the C lib so that srand doesn’t affect it. As srand affects the random in pokittolib, I assume it uses the random from the C library. I just wanted to use the same random across the entire game, and writing a shuffle is no big deal ahaha… It’s exactly the same algorithm as in the stdlib (Fisher–Yates)… :stuck_out_tongue:


#12

Can’t you use something like this?
Pokitto::Buttons::upBtn() for example, for the ‘up’ button, similar for other buttons


#13

It’s been a while since I messed around with the button code but I seem to recall the frame counting being done with an array of uint8_t, which gives a theoretical cap of 255 frames, though I think 255 might have been used for another purpose so it might only be 254 frames.


I see that now. That’s annoying.

In that case I think this should work:

Pokitto::Buttons::states[button] > 0

It does have transparency, but you have to single out a specific colour index as ‘transparent’.

You have to use Pokitto::Display::setInvisibleColor,
but I don’t know whether it’s an index or an actual colour that you give to it.
I’m assuming it’s a palette index.

<stdlib.h> (deprecated) behaves as if each name from is placed in global namespace

I.e. the std::rand from <cstdlib> should be the same as the rand from <stdlib.h>.

The Pokitto really shouldn’t be using the deprecated headers either,
I think I’m going to make an issue about that.

Actually, the algorithm used by std::random_shuffle/std::shuffle isn’t specified by the standard:

Note that the implementation is not dictated by the standard

So it might not be Fisher-Yates.

Out of interest, what most people call ‘Fisher-Yates’ is actually a modified version of Fisher-Yates’.
The original Fisher-Yates didn’t swap the entries,
that was a modification made by Richard Durstenfield.


#14

See my reply above, I think that that is returning true as long as the button is pressed


#15

I don’t feel like this is related to the problem given your description and how the bug manifests. But can’t know for sure.

Thanks, I may update the code with this.

Oh! I didn’t notice that method. Good to know. I still can’t use that for the cases where I reuse a same bitmap with different parts of the palette, but I can replace the other cases. Thanks.

That’s also true, but this not what I was talking about.

C++ STD has classes for RNG that have their implementation specified for portability (contrary to std::rand) and can be fed with different distributions than uniform. std::random_shuffle uses an internal default generator (that is an instance of the C++ random generator class) and is unaffected by srand. You cannot change the seed of std::random_shuffle, and for this reason, if I used it, the games would always be the same.

C++ has (since C++11) a std::shuffle that accepts the same parameters as random_shuffle plus a generator to generate the numbers (and this last parameter doesn’t have a default value).

In fact, std::random_shuffle was deprecated in C++14 and I can’t even compile my code with C++17 if I use std::random_shuffle.

And to use std::shuffle, I have to first create a generator. It can either be an instance of a C++ random generator or a function pointer (or even std::function with lambda) that can potentially use the std::rand if I feel like it.

So at the end of the day, it was kinda easier and mindless to keep using the std::srand and implement a shuffle, which is no work at all.

Also, I’d like to add that there is a function called random (it’s in the global scope, not std::random) that also has a different implementation than std::rand and is not affected by srand. I don’t know how to change its seed and could not find this information in my quick search. I previously thought that its name was std::random and that this was the implementation used by random_shuffle, but I was mistaken.

True. Although I can’t see many reasons why it would be any other (at least for vectors and arrays).
It’s unbiased, O(n) with a negligible constant multiplier, and probably the easiest algorithm to implement.
It’s not really like I’m missing out something better.

To be honest, I didn’t even remembered the name Fisher-Yates :stuck_out_tongue_closed_eyes: I always called it Knuth shuffle, although I knew he (Knuth) wasn’t the original inventor. I just googled Knuth Shuffle and found the wikipedia for Fisher-Yates with a pseudo-code identical to my implementation.

Anyway thank you so much.


#16

The difference is that this way would work by accepting a ‘button code’.

The reason @denismr wants that is because he’s using a class called BtnHelder that uses the button code for flexibility:

If he were to use Pokitto::Buttons::upBtn() and its variants then he’d either need an array of function pointers or a switch statement to be able to fulfil the ‘accessible by a button identifier’ condition.


Interrupts are mysterious beasts.
I believe there’s an interrupt queue/circular buffer so it’s always possible that some interrupts get ignored because the buffer overflows.

But it’s just a guess, to come up with a better theory I’d need more information about the circumstances and I’d have to dig around the code more.

If that doesn’t work quite right then it might have to be:

Pokitto::Buttons::states[button] > 0 && Pokitto::Buttons::states[button] != 255

As I say, it’s been a while since I was digging around the button code.
It’s quite spread out and there’s a few redundant bits that haven’t been removed.

In fairness I don’t think anyone has wanted a ‘palette of palette indices’ before.

If you’ve got the space left over for more than one bitmap then you could just squash them all into a tile sheet and use void Display::drawBitmap(int16_t x, int16_t y, const uint8_t * bitmap, uint8_t frame) to draw them - with each colour arrangement being a different ‘frame’.

According to cppreference:

  1. The random number generator is implementation-defined, but the function std::rand is often used.

So technically it might not be std::rand in use,
but the C++ random generation classes weren’t added until C++11,
so either std::random_shuffle uses an internal custom-build PRNG that can’t be seeded or it uses std::rand.

It might be worth experimenting to find out if std::rand is being used.

Ultimately this flaw is why std::random_shuffle was deprecated and why std::shuffle was introduced in C++11.

I don’t know for definite without checking, but I suspect even if it used something other than std::rand it would be required to generate different sequences each time without requiring a user seed.

As you point out though, other overloads allow you to specify your own function.

Yep, it said so on cppreference.

(deprecated in C++14)
(removed in C++17)

I’m assuming you’re compiling in C++14?

Technically for std::shuffle it would have to satisfy the named requirement UniformRandomBitGenerator,
which would mean it would need to be a class with a static min function, a static max funtion and a result_type type alias,
but that would be easy enough for std::rand:

class rand_generator
{
public:
	using result_type = unsigned int;
	
	static constexpr result_type min()
	{
		return 0;
	}
	
	static constexpr result_type max()
	{
		return RAND_MAX;
	}
	
	result_type operator()()
	{
		return static_cast<result_type>(std::rand());
	}
};

But std::random_shuffle would accept just a function though, so you could do:

std::random_shuffle(std::begin(tries), std::end(tries), std::rand);

(And that would work even if you resized the array.)

Perhaps, but it’s worth bearing the one in the library in mind in future.

Actually there’s two, and neither are part of the C++ standard library, they’re part of the Pokitto library.

One in the core Pokitto library and one in an external library.

The one you’re using is probably this:

It’s designed to mimic the one supplied by Arduino:

It should be affected by srand.
If it isn’t then something odd is going on.

If your aim is to write portable code then as long as the standard says ‘implementation defined’ you have to pretend it could be anything,
even if every implementation in existance used FIsher-Yates.
(The same for things like using std::size_t for taking the size of objects, and many other things.)

If you don’t care about portability at all then feel free to write to a specific implementation.

The advantages of using the version in the standard library aren’t from the algorithm used (which is pretty much irrelevant),
they’re from the correctness it provides.

E.g. it’ll still work when:

  • you try to sort an array of 2147483648+ elements
  • your elements require a custom swap function
  • you only want to swap a partial range of numbers instead of the entire container

Et cetera.

But my point was more the whole “the standard’s word is law” thing.
If some code gets compiled on a platform where a char is 16 bits wide and the code breaks because of that then it’s the code that’s incorrect, not the implementation using a 16-bit char.

I’d never heard it called that until reading the wikipedia article,
but then I’ve never read any of Knuth’s books either.
I tend to use online resources more than physical books.
(I don’t really have the space or money for a book collection.)

No problem. Any questions at all, just ask.


#17

Actually, I have plenty of space left. I can create replicas in different color, but I really do not have much reason to.

I don’t know about that. I tested and consistently got the same shuffling (but I didn’t test on the Pokitto with gcc-arm, just on my macbook with clang).

And I really don’t see the reason for this requirement. There are plenty of cases where you actually want to reproduce the same sequence across different instantiations.

First, I assume that I want to get rid of std::random_shuffle and instead are going to use std::shuffle, since the former is deprecated and I’d rather compile with C++17.

I was wrong before and there is no overload that accepts a function in the case of std::shuffle. The third parameter must be a URNG (uniform random generator).

The third parameter of std::random_shuffle can be a function, but now that’s irrelevant, because I don’t want to use it.

However, if I were going to use it, simple passing std::rand is not an option since it does not have the signature expected by std::random_shuffle.
The example in C++ reference does:

int myrandom (int i) { return std::rand()%i;}

Then I can pass myrandom. It’s fairly simple, but now it’s irrelevant.

I was not talking about the Pokitto nor Arduino at all. I tested some code in a macbook compiling with clang. I’m also fairly certain that this function exists in GCC as well, since I remember using it in some contest sites as codeforces or UVA.

And in both cases (clang and gcc), it’s not affected by srand.

But I don’t know where this function is defined, tho.

Sure… I only know the signature of the function (what comes in and what comes out). I should not assume anything about how the function is implemented if I’m not the implementer. However I just made an informed guess to assess the possible complexity and compare it with my implementation. I did not use the function and expected a side effect to come from its use, in which case the expected side effect could not happen if I compiled to a different target or in a different environment. That would make my code not portable.

Examples would be to assume that a sorting algorithm is stable when stability is not specified by the standard, and assume that a random generator produces the same sequence everywhere if this is not specified.

Additionally, this only applies when I’m using the library’s function, which is not the case. I implemented the shuffle, so I know exactly what the implementation is. I just wanted to compare against the best scenario (in the std) to assess whether it was worth it implementing it myself. Provided that your own implementation is correct and you don’t have any dependences on software or hardware, using it over stdlib should be more portable, not less.

Not always and a good example is std::unordered_map. I’d say that one needs to know which environment the code is going to be compiled on to make use of it effectively. The results can be abhorrent.
In some cases it’s just better to use specific libraries or your custom code over std’s offerings.

You really shouldn’t rely on that.
When I was in my internship, I heard of an employee that had to fix a bug in Java’s binary search (JDK) a few years earlier. It was summing the numbers before dividing by two, and this caused some overflows. Thing is: many standard libraries were doing that. It’s a pretty known case, you can google it for details.
People that write standard libraries are just software engineers like (presumably) you and me. It’s true that the code is infinitely more battle-tested by hundreds of thousands or millions of users, and the engineers must have written unit tests and integration tests. However, no test is perfect, and sometimes things go wrong.

Anyway, I was pretty straightforward in the repository’s README when I said that my code is a mess. I played with it as a toy and did not worry about pretty much anything. I bought the Pokitto more than a year ago and never touched it to do anything, and just wanted to do something on my holidays (Carnaval in Brazil). I was not aiming at producing code with any maintainability whatsoever (and maintainability has nothing to do with portability). I knew the random_shuffle before, and actually I can say that I am fairly versed in C++ stdlib (although, by and large, this particular code is absolutely not a good demonstration of that).

I’ll admit that I was even afraid of using anything from the stdlib. For instance, I didn’t use vectors to not use the heap and also because it usually (in many implementations) doubles the allocated size every time you reaches its limits, because doing so is O(n) to insert n values.

I still understand the reasons why you recommended using the std and tried to make me aware of its functions. I appreciate that and thank you. I still don’t see a case to replace the shuffle here.

edit: just to clarify, I’m aware that std provides many useful things besides data structures (like the vector I mentioned) and that shouldn’t have any undesirable side effects on performance (actually, the opposite is more likely). E.g.: std::fill, std::copy, etc. However, as I said, I wasn’t really looking for making an industry standard code and I was not trying to make anything didactic either. Just having fun.


#18

I found the same thing using VS2015, but I also found that VS2015’s version is using std::rand behind the scenes.

In which case I suspect the rules declare the default behaviour as ‘implementation defined’ and most places chose to use std::rand, which isn’t seeded to start with.

I checked the standard and then realised we already had the answer.
The standard says:

The underlying source of random numbers for the first form of the function is implementation-defined.

Whether the function generates the same sequence each time or a different sequence depends entirely on the underlying source of random numbers, hence that too is implicitly implementation-defined.

And of course, for all implementations using std::rand:

If rand() is used before any calls to srand(), rand() behaves as if it was seeded with srand(1).

Which explains the behaviour of the VS2015 code, and most probably the other platforms.

This is probably why the version that doesn’t require a parameter specifying what engine to use was deprecated and removed.

Forcing the PRNG to be supplied manually makes the user specify what they think the behaviour should be.

If you want to use C++17 then yes, you’d have to get rid of std::random_shuffle.

Be aware that you’d be forcing people who want to compile your code to be compiling on at least C++11 though.
That would mean people who use mbed-online to compile wouldn’t be able to compile it.
(Though that’s not much of an issue since your code is already restricted to at least C++14.)

Technically a “UniformRandomBitGenerator” (URBG),
though the difference is only really a small semantic detail.

std::random_shuffle is a template, it doesn’t match ‘by signature’ as such,
but I see the clause that’s causing the problem now

in the interval [0,n) if invoked as r(n)
And of course std::rand doesn’t accept n as an argument.
(Though Pokitto’s random would.)

You wouldn’t have to write a function for it though, a lambda expression would suffice:

std::random_shuffle(std::begin(tries), std::end(tries), [](std::size_t max) { return std::rand() % max; });

(Personally I wouldn’t implement it like that because I wouldn’t want the modulo bias,
but that probably isn’t much of an issue in this case.)

You’re compiling the Pokitto simulator in clang?

I would suspect that’s the source of your 'not using std::rand’ problem then.
Had I known you were using a non-Pokitto environment, that would have put a different light on matters.

‘gcc’ being on a physical Pokitto?

The version of random supplied by the Pokitto lib is most definitely using rand,
so either std::rand and rand are somehow something different (which shouldn’t be the case) or if GCC is defining some kind of random function then that’s interfering with the Pokitto’s version.

I’d advise against using std::unordered_map on an embedded device anyway (if possible), regardless of the implementation.

But cases where the behaviour is poor tend to be rare specific cases rather than the norm.
I suspect the case you’re thinking of was the GCC 4.7 bug from a few years ago.

Unless the specific implementation or specific constraints are documented.

For example, something the standard mentions that cppreference neglected to mention about std::random_shuffle and std::shuffle:

Complexity: Exactly (last - first) - 1 swaps.

I fear that there are a lot of people who do think std::rand is always the same implementation.

But getting it correct and not hardware dependant can be very difficult.
For example, I’ve seen a lot of code that assumes that int is 32 bits rather than 16 bits or 64 bits.
I have specifically run into a bug that was happening because someone was assuming that int is 16 bits and depending on overflow behaviour.

Only if it’s provable that the version provided by a particular implementation of the standard library is inadequate or you’re really confident in your ability or the other library’s ability to do a better job, or you have some very specific requirements.

I was mainly thinking of things like using std::size_t rather than int for indexing and properly using argument dependent lookup to pick a user-defined swap function over std::swap.
The sort of things most people wouldn’t even think of.

Yeah, that’s quite a famous example.

But that sort of thing isn’t a common occurance thankfully,
and in that particular case pretty much everybody had got it wrong,
so someone writing their own version wasn’t necessarily more likely to get it correct.

I’m not really a software engineer, I’m just a well-read hobbyist.

I’d like to think the people writing the standard library implementations are much more intelligent and much more experienced than I am.

True, but that’s much less likely to happen to battle-tested code written by (presumed) seasoned experts than it is to code written by Joe Average.

(And if it breaks you can blame someone else.)

That’s one of the reasons why some people recommend std::deque instead.
It probably upsets the cache on modern CPUs, but the memory usage is generally a lot better.

(It also has the bonus that iterators aren’t invalidated when objects are inserted at the front or back, which is why it’s the default backing store for std::queue and std::stack.)

Fortunately on the Pokitto you can get away with a bit more heap allocation than on some other platforms,
though it should obviously still be avoided if possible.

I will admit I didn’t see the text in the README.
Usually people put all their explaining in their main thread post here,
so I assumed it was going to just be another group of images matching the main thread post.

In fairness it’s easier to port maintainable code.
If the code is unmaintainable then it would be a struggle to port.

It was just as much for the benefit of others.
Most Pokitto users aren’t experienced programmers.

As I said earlier, I didn’t necessarily mean here, I meant in future cases.

Fair enough.

As I said earlier, most of our users are inexperienced,
so my default mode is to try to offer advice and suggestions.

I assume less experience rather than more because it’s usually less awkward to explain something someone already knows than it is to assume someone has knowledge that they don’t as the latter usually makes people feel too embarrassed/inferior to ask questions, which in turn harms their progression.


#19

Well, I was not testing on VS2015.
With clang and GCC, std::random_shuffle’s seed is not altered by std::srand.

Which is already old. Anyways, my intention was never to make a code for other people read/modify/learn from/recompile. I only cared about the game, which is fun, and for that I released the binary.

Is it? it’s a sincere question. I don’t remember using anything beyond C++11, but I’m not sure. I set to C++17 because I did not want to restrict myself while I was coding, but I ended up not using anything that really needs it. However, even if I were targeting C++11, I would not use something that cannot be used with later versions.

That was just pedantic. Templates can impose restrictions. Maybe the right term is not “by signature”, but the idea of restricting according to parameters, return and types is pretty much the same and you got what I meant, even though I didn’t use the correct term (as I have no idea what it is).

I also would not use the modulo and I’m well aware of modulo bias. I explicitly said that I was just copying and pasting the example from the c++ reference of what could be done.
The example also does not use lambda. I didn’t modify the example whatsoever. Don’t lecture me just for the sake of doing it.

First, there is no “problem” at all… I just commented on the existence of a random function (I’m not even using it). As I said:

Second, I’m not talking about Pokitto at all. Not talking about PokittoSim either. I just compiled very simple code with these compilers and checked the output in a terminal window. This function is declared somewhere. I explicitly said that I don’t know where. I don’t know if they belong to any standard either. I just talked about the existence of such a function out of curiosity. I realize that this is not behind behind random_shuffle (as I explicitly said).

Not talking about that bug at all. This read eventually brings some of the points I was thinking of.

I have absolutely no reason to believe that these people are much more intelligent than me. Where their knowledge is diverges from where my knowledge is, and they should be infinitely more experienced and knowledgeable with their line of work, tho. However, even experienced and intelligent people commit errors. You just mentioned a bug in GCC 4.7.

IIRC, an old colleague from college, not older than me, fixed another bug in GCC as well.

And there are plenty of other examples, like the infamous Apple’s SSL bug, which had critical consequences.


#20

Ok… I just checked and actually my code was compiling and running just fine with -std=gnu++98 ! Apparently, I was not using anything from C++11 onward. Sticking to the basics :stuck_out_tongue:

However, I modified the code just now to try to circumvent the problem with Pokitto::Buttons::repeat, and the easiest modification was to use std::function. Now it requires at least -std=c++11, and it compiles just fine with both -std=c++11 and -std=c++17.

I hope this bug doesn’t happen anymore. I have to test it on the hardware a little bit more to be sure.
I’m attaching the newest bin right here.

raquer.bin (68.9 KB)