Nekoculus: a cat, a bullet and movement prediction

[Krssst]

Hello,

A little while ago, I made a small game in C++ using SFML: Nekoculus. The goal is simple: you are a cat trying to escape a bullet and you must survive 67 seconds. You can move with the arrow keys. The bullet is slightly slower than you, but will remember every movement you make in order to predict what your next moves will be. To avoid collision, you will have to continually imagine new paths to confuse the AI.







Windows version is available here : https://www.dropbox.com/s/kmo1uz2co3u27xw/Nekoculus_R4.zip (4.5Mb). The game is using SFML 2.0, as text positioning seems to mess up when I use SFML 2.1.

Only problem is that I never managed to finish it (reached a 3500 score out of 4096), but this kind of game is more about always trying to improve the score than finishing it. But I believe it is theoretically possible to finish it :-)

This game is written in C++ and uses SFML for basically everything. The windows version is statically linked.

As it is quite simple, I now believe it would probably have been better to use something much higher-level, as 90% of the time I spent working on this game has just been for finishing touches (buttons (I had to write my own class for a rectangle with rounded corners), win/lose screen (especially the lose screen, if you reach 1024 score :-)), and making it run on Windows (I did it back when SFML 2 was in beta ; had to recompile SFML for windows under linux as I did not manage to do it in Windows...)). However, as the prediction algorithm is really computation-expensive, maybe it wouldn't have worked well.

[Grimshaw]

Its pretty hard smart ball

[Nexus]

Interesting gameplay... How does the AI work? Did you implement the learning from scratch or did you employ established AI techniques?

The eye animation when losing is also nice
By the way, you should probably forbid resizing the window, or map the mouse input correctly when resizing. And document that F enables fullscreen

[FRex]

It freaked me out a bit after a while of just running in circle it took me down super easily.
Very 'it reads my mind'/'it knows the future' feeling with 'I must think and do random things to confuse it' element to it.
Very fun thing to do for few minutes.

[Krssst]

Thank you for your comments

It freaked me out a bit after a while of just running in circle it took me down super easily.
Very 'it reads my mind'/'it knows the future' feeling with 'I must think and do random things to confuse it' element to it.
Very fun thing to do for few minutes.

In the first few seconds, the ball is just plain stupid and is basically following you so you make a few moves so it can start learning your movements. Passed that, the real thing begins.
I could make it a little less dumb (make it assume in the beginning that you will continue in your current trajectory), but that would make the beginning of the game much harder, which would be really discouraging. It is better to let the player hope things will be easy for a few seconds

Interesting gameplay... How does the AI work? Did you implement the learning from scratch or did you employ established AI techniques?

I don't know if it's an established technique. Basically, I have an enum "Orientation" storing all possible movements (nothing, up, up-left, up-right, left, down-left, down, ...) and an array Orientation [4096]. Each game cycle I store the player's current movement in the table.
Then, in order to predict, I just take the player's last 256 orientations and try to match them with some other 256 contiguous orientations in the past (recorded in the array). Once I find the best match, the idea is just to assume that what you will do next is what you did next in the past after doing nearly the same moves. I wrote some documentation in french here, but I don't think it is clearer.
It works well, but it is extremely computation-extensive (complexity O(256 * Number of cycles spent in game)). In fact, the main reason the game will only last for 67s is because on my netbook (reference low-end machine), more will make the game start frameskipping. Second reason is because I think 67s really is enough for this kind of game

The source code is kinda messy. I consider this game as finished so I will only work on bugfixes, but if I had to redo it a lot of things would be different.

The eye animation when losing is also nice
By the way, you should probably forbid resizing the window, or map the mouse input correctly when resizing. And document that F enables fullscreen

Nice catch for the window resize I corrected it in the repository (and, in the same time, added a small README documenting the F key).

[Geheim]

Very nice game
From 0 to about 2000 until the blue ball comes it's quite easy then it's challenging and at about 3000 it gets kind of impossible, because of 4 round AI's haha

Everything in the game sort of has to be in there, the 67 seconds, the eye, the cat, I like it, if things are a bit random

One "bug" I noticed: If you toggle fullscreen the cursor is visible again, which is not a big deal, but still not wanted I guess.
Thx for sharing

[Nexus]

Then, in order to predict, I just take the player's last 256 orientations and try to match them with some other 256 contiguous orientations in the past (recorded in the array). [...] It works well, but it is extremely computation-extensive

So you're computing a discrete convolution of the current pattern and all past patterns. This is a signal processing problem; the convolution can be represented as (the inverse transform of) a product of fourier transforms in frequency domain, and using FFT you get a better time complexity. Furthermore, there seems to be a constrained algorithm which is even faster and simpler.

Just in case you're interested in how this could be optimized

[Krssst]

Very nice game
From 0 to about 2000 until the blue ball comes it's quite easy then it's challenging and at about 3000 it gets kind of impossible, because of 4 round AI's haha

Everything in the game sort of has to be in there, the 67 seconds, the eye, the cat, I like it, if things are a bit random

One "bug" I noticed: If you toggle fullscreen the cursor is visible again, which is not a big deal, but still not wanted I guess.
Thx for sharing

Thank you
I fixed the fullscreen cursor bug in the source tree. I can imagine that it is disturbing, especially when the native resolution of the game is 640x480, making the cursor horribly big.

So you're computing a discrete convolution of the current pattern and all past patterns. This is a signal processing problem; the convolution can be represented as (the inverse transform of) a product of fourier transforms in frequency domain, and using FFT you get a better time complexity. Furthermore, there seems to be a constrained algorithm which is even faster and simpler.

Just in case you're interested in how this could be optimized

Not really a convolution ; more precisely, I am computing Sum((AttenuationFactor ** k) * Distance(Memory[i+k], Memory[k]), k=0..255), which would be a convolution if Distance(x, y) was x*y and if AttenuationFactor was 1.
However, assuming x and y are angles corresponding to the directions the player took, I use Distance(x, y) = Sqrt((cos(x)-cos(y))**2+(sin(x)-sin(y))**2) = Magnitude(exp(ix)-exp(iy)). (but since I only have 8 possible angles, I have everything already computed in an array).

The advantage of doing so is that, if the player moves up then left, I will put more weight on a solution in the past with (Up, Up-Left) than on a solution with (Up, Down).

But, if I have Distance(x, y)=(x-y)**2, or if I just try to max the autocorrelation, then I can make use of this and I should still have a decent result. I will keep that in mind if I use the same kind of prediction method again, thank you :-)

[Vot1_Bear]

Was doing pretty good for a while till the the bullet split to two and I freaked out (2745's my best atm btw)

Very interesting idea, as well as the implementation you mentioned above. Questions though... I presume the 67s is due to the 4096 cycle limit and that it's getting harder to calculate the orientation per cycle, yes? Then how do the game differentiate from a certain cycle repeated in the future? Say, I move constant left for 256 cycle early and turn up, then kept repeating it later on but instead of up this time I went down. Do you take the most recent, latest, or simply random? would be interested to find out (it'll also be beneficial in setting a new high score )

And also, do you ever consider dumping old cycle infos once the 4096 limit's reached? Kinda make it loop back to the beginning so new datas replace the oldest ones. It'll cause the overall prediction quality after 67s to be sub-optimal, but it should be sufficient to extend the game time.

Lastly, why the eye? Freaked me out the first time

Again, amazing game!

[Krssst]

Was doing pretty good for a while till the the bullet split to two and I freaked out (2745's my best atm btw)

Very interesting idea, as well as the implementation you mentioned above. Questions though... I presume the 67s is due to the 4096 cycle limit and that it's getting harder to calculate the orientation per cycle, yes? Then how do the game differentiate from a certain cycle repeated in the future? Say, I move constant left for 256 cycle early and turn up, then kept repeating it later on but instead of up this time I went down. Do you take the most recent, latest, or simply random? would be interested to find out (it'll also be beneficial in setting a new high score )

The probability of you doing twice the exact same cycle is extremely small (a human being is, in general, not able to achieve 1-frame precision on a 60fps game :-)). Still, if that were to happen, by looking at my old code, I would say the first one.
But, in real life, there will always be a small differences between several move cycles ; the game will then choose the one which matches better the one you just did. With your example, instead of having precisely several cycles of 256 'Up' followed by 'Left', you would have several cycles with something between 240 and 280 cycles of 'Up' followed by 'Left' for 2-10 cycles.

And also, do you ever consider dumping old cycle infos once the 4096 limit's reached? Kinda make it loop back to the beginning so new datas replace the oldest ones. It'll cause the overall prediction quality after 67s to be sub-optimal, but it should be sufficient to extend the game time.

When I started working on this, that is what was done. Each time I accessed memorized information, I did a modulo operation so it would loop. However, that increased code complexity everywhere and was a bit slower. As 67s is already long enough as it is, I just dropped it :-) But, I agree it would be better for a game that lasts more than one minute.

Lastly, why the eye? Freaked me out the first time

I love eyes, sorry

Again, amazing game!

Thank you!

EDIT: updated windows version, with mouse coordinates & mouse cursor in fullscreen fixed

[AlexxanderX]

After one round this is the result


I want to say I got when wanted to compile( Linux) erorrs: "undefined reference sf::xxx" so I needed to compile myself and after rename the Resource folder in "outResources".

[Krssst]

That was the surprise for adventurous gamers that went past 1024 in score :-)

The issue you describe is interesting... How did you compile it?
Normally, you should use:

Code: [Select]

.../Nekoculus$ cd Sources
.../Nekoculus/Sources$ make
.../Nekoculus/Sources$../Nekoculus
I can imagine that something went wrong if you built it yourself. There is an horrible hack in the code to find the resources directory (Resources/) and the game is expecting its executable to be called "Nekoculus" (Nekoculus.exe on windows) and to be in the same directory as the Resources/ folder. If it is not the case, it will not be able to find its resources. Next time I should probably think of a better way to find the resources directory :-)