aliens

Author Topic: A bug in battlescape and a fix for it  (Read 13732 times)

Offline djemon_lda

  • Captain
  • ***
  • Posts: 52
    • View Profile
A bug in battlescape and a fix for it
« on: September 20, 2013, 02:22:03 am »
Hello again! :)

SupSuper or Warboy, could you please take a look on that?

I remember that I've read hear on the forum, that there is no reason to try and load the state of the battlescape and try to save units, because you save the seed. I've taken a look into the code, because I was wandering what random generator are you using ( would it be a mersenne twister, or some simple noncryptographic randomizer ) and found out that you are using a global seed (at least for the battlescape). I immedieately have found a way to trick your anti cheating security done with saving the seed.

Scenario 1:
1) alien, and two of my soldiers see it, my turn
2) I save the game.
3) I shot with guy1. I miss. Alien retaliates. My guy dies.
4) I load. I shot with guy1. I miss. Alien retaliates. My guy dies.
5) I load. I take guy3, that is somewhere far away. I shot a random wall.
6) I shot with guy1. I miss. Alien retaliates. ALIEN MISSSES

Why this happens in detail?
1) Lets say my seed is A, and because of that the sequence of numbers generated is B,C,D,E,F,G,...
2) You have saved a global seed, so no matter who uses the random number, the sequence goes forward.
3) in scenario 1, right after I save the game, guy1 gets value B from the RNG and he misses. Alien gets value C, and hits.
then I load the game, so the seed is again A, guy1 gets value B from the RNG and he misses (again) and the alien gets C, so he hits.
then I load the game, so the seed is again A, guy3 shoots the wall getting B from RNG, guy1 gets C and he misses, but alien gets D (no juvenile humor here!) and misses.

I have came up with multiple scenarios of this, and the only way to handle this properly is to keep an instance of a random number generator in each of the battle units.

Let's take the same scenario, with a random number generator instance per a battle unit, shall we?

alien has seed A, guy1 has seed G and guy3 has seed M.

Scenario 1 with an instance of a random generator per a battle unit.
1) alien, and two of my soldiers see it, my turn
2) I save the game. ( with all the different seeds for each unit )
3) I shot with guy1(he has A, so his generator generates B). I miss. Alien retaliates (it has seed G, so he gets number H, and hits). My guy dies.
4) I load. I shot with guy1(he has A, so his generator generates B). I miss. Alien retaliates (it has seed G, so he gets number H, and hits). My guy dies.
5) I load. I take guy3, that is somewhere far away. I shot a random wall(he has seed M, hence getting number N and not changing the next value that the alien and guy1 will get).
6) I shot with guy1(I loaded, so his seed is A, and he gets B from RNG, because he has his own seed). I miss. Alien retaliates(he has his own seed G so he gets H again and hits! :) ). my guy dies

a lazy fix would just be to have an int in each battle unit named _seed and get his test values by a method like:
Code: [Select]
int BattleUnit::GenerateOwnRandomNumber()const
{
srand(_seed);
_seed = rand();
return _seed;
}
but I would advise using an object, because this method is "a bit" slow. You can try something from <random> header (c++11), or if you wait a day or two I will get you a nice, and small piece of code ( compact in size and fast ) random generator, that isn't cryptographic, but had nice results... I just need to find that implementation on my email :)

Regards,
djemon_lda

Offline kevL

  • Colonel
  • ****
  • Posts: 466
  • pitchforks and torches
    • View Profile
Re: A bug in battlescape and a fix for it
« Reply #1 on: September 20, 2013, 03:10:44 am »
i think (no doubt ther've been threads on this, there sure have on the 2k forum, heh ) that saving a global seed is more so that bugs can be tested consistently, rather than to prevent save-scrubbing.

Personally i'm in the camp that says, the seed should not be saved if the only reason it's there is to prevent 'cheating'.

and i think the RNG is a simple stock one ( I'd certainly like a better one... just 'cuz! )


If a guy really wants a different result, can he/she just change a digit in the .Sav? Or perhaps a *new option* : Save Seed. If seed not found when loading, generate a new one (but i think that should wait till after v.1 for reasons above)

or maybe use a 'latent-seed' /cough -> 'latency' ( pun intended  :)  Anyway,

Offline SupSuper

  • Lazy Developer
  • Administrator
  • Commander
  • *****
  • Posts: 2159
    • View Profile
Re: A bug in battlescape and a fix for it
« Reply #2 on: September 20, 2013, 04:57:10 am »
Yeah the seed is to make bugs easy to reproduce, punishing people for retrying the same action over and over is just a nice bonus (if you're gonna cheat be creative about it :P). But having a seed for every single unit is a bit overkill, pretty sure not even commercial games do that.

Trying to defeat cheating is kinda a fruitless endeavor, if people wanna cheat they will always find a way to cheat, hell the save files are YAML. :P

I have considered replacing the current RNG (which is just the stock C++ rand()) with something more robust though like the one in Game Coding Complete.

Offline djemon_lda

  • Captain
  • ***
  • Posts: 52
    • View Profile
Re: A bug in battlescape and a fix for it
« Reply #3 on: September 20, 2013, 07:47:19 pm »
If you want a nicer global random number generator use mersenne twister from the <random.h> , there are two versions of it in the header. You are using VS2010, so you should have that header. an implementation of mersenne twister is also easy to find on the internet if you can't include this header.

I have looked into that issue in terms of bug/not bug according to what I have read here on the forum, hence I analysed and found a solution. I have called it an "anti cheating mechanism" because I haven't found better words for that. I, in general, don't consider bug-using as cheating. Whether it is a bug or not - this is a feature of the game.

Quote
the seed is to make bugs easy to reproduce
Well, if the bug is related to anything generated by the RNG ( and from that comment I guess that is the case at least from time to time ) then it is easy for the user to forget about something that would seem to him an unrelated detail. Like, for example, shootting the wall in the scenario I've given you before. Good luck with deducing what made the sequence of random numbers in the user's case other than the case of your bug reproduction. Because of that you can never actually know if the bug is not reproduced because it is not there, or if it was not reproduced, because you didn't do exactly the same thing that the user did :)

Seed per unit is no overkill, to be honest, it's just 16 bytes if you get a small generator ( 4 for the dirty fix ), which is very little when you take into account the scale of a battlescape instance - no more than 50 units on the map.

real time commercial games have a random generator per thread. those which want to have a "replay" functionality, use saving the seed, they use a single random generator for mechanics ( game mechanics are "single threaded", although the game as a whole uses multithreading ) and a constant update step for the game state. the model is different in that case, because the time flow is constant. there is also no chance of one unit making all of his moves before every other unit ( like here - utilizing the whole pool of time units ) and also the majority of games have a very little use of random number, like in starcraft:broodwar it was used only in case of attacks vs units on upper ground and behind obstacles which was really rare. here it is a key concept ;)

Offline redv

  • Colonel
  • ****
  • Posts: 335
    • View Profile
Re: A bug in battlescape and a fix for it
« Reply #4 on: September 20, 2013, 08:13:56 pm »
If player will feels, that all results of his actions is predefined, then he will lose interest for the game.
In this case one random seed is good trade-off.

Offline kevL

  • Colonel
  • ****
  • Posts: 466
  • pitchforks and torches
    • View Profile
Re: A bug in battlescape and a fix for it
« Reply #5 on: September 21, 2013, 12:14:11 am »
"latent-seeding"

save a seed, but give the option to regenerate it

Offline MKSheppard

  • Colonel
  • ****
  • Posts: 249
    • View Profile
Re: A bug in battlescape and a fix for it
« Reply #6 on: September 25, 2013, 07:40:50 pm »
"latent-seeding"

save a seed, but give the option to regenerate it

CTRL-ALT-R - and "Random Seed Re-Rolled" appears on screen?

Offline kkmic

  • Commander
  • *****
  • Posts: 582
  • Undefined
    • View Profile
Re: A bug in battlescape and a fix for it
« Reply #7 on: September 26, 2013, 11:16:35 am »
Scenario 1:
1) alien, and two of my soldiers see it, my turn
2) I save the game.
3) I shot with guy1. I miss. Alien retaliates. My guy dies.
4) I load. I shot with guy1. I miss. Alien retaliates. My guy dies.
5) I load. I take guy3, that is somewhere far away. I shot a random wall.
6) I shot with guy1. I miss. Alien retaliates. ALIEN MISSSES

A while ago, after Firaxis releases the 2012 XCOM, I stumbled upon this article: Is XCOM Truly Random?. It is an early analysis of the RNG used by the game.

They use the exact same system that OXC uses: save the random seed, so reloading gives you the very same results if you follow exactly the same path as before.

Now, while searching for the previous article, I found this one: Why XCOM’s Random Results Sometimes Aren’t (and You Should Play on Ironman). It contains this:
Quote
The random numbers in games like XCOM are sequences of non-repeating numbers, but they’re not plucked from the ether — they depend on a seed (usually a number) to initialize the sequence. The first time through, the numbers will appear random (and in XCOM, unpredictable from your vantage) because you’ve never seen them. But load a saved game, which generates its random numbers from the same seed, and if you repeat the same actions, the scenario will draw upon the same sequence of numbers and produce the same results each step of the way.

A problem? Not necessarily. In fact when I asked XCOM creative lead Jake Solomon about it, he said random number generation in the game works exactly as intended:

Quote
We use synchronous random in combat so the player can’t just reload when they miss a shot. Now, obviously there are ways around this, but this is a decent way of ensuring that the player’s choices do matter.

What Solomon and the design team at Firaxis are trying to prevent is the sort of play-through where you save and reload for every action to get the results you want. Did one point of damage instead of two? Reload. Didn’t hit that sectoid peeking around a corner? Reload. Can’t find the best position to get the highest-percentile shot? Reload. That’s no way to play a game, or at best it’s a tedious one. What’s XCOM without risk and consequences?

You have listed the disadvantages of the current system. Let me point the big advantage of it:

Preamble:
When you have a truly random number generator for each action (like the original did), you can easily abuse it too (I did so quite a lot in the original): save and reload until you get the desired result - like a rookie that can take out an entire battleship all by itself. It's hard, but with enough sweat and clicks, it's doable.

Point:
Getting the same result for the same action after reloading forces you to think an alternative path/strategy/action.

Conclusion:
OXC is made for fans, not speed runners that look to exploit every weakness of the system. As SupSuper pointed out, the savegames are plain text, and are open to modifications by anyone. That alien killed your team time and time again? Remove his blaster launcher or erase him from the game. You cannot remove cheating, but you can make the game fun. If you really want a hard time, play ironman. If you want to cheat, find a way around the system.

Bottom line:
Every system has a weakness, but if I have to choose between these two, I would happily go with the current implementation.

Offline djemon_lda

  • Captain
  • ***
  • Posts: 52
    • View Profile
Re: A bug in battlescape and a fix for it
« Reply #8 on: September 27, 2013, 03:53:26 pm »
well I've seen and played the 2012 ufo, and I think it's a bad product. now, there is a substantial difference between bug abusing, and cheating. if you change the save - yeah, you've cheated. but when you are utilising the existence of the bug you do what is perfectly legal in the world of the game. its like pushing units through minerals in starcraft broodwar, or pushing away stasised units on the ramp with your workers in that game. it was legally used in professional tournaments, because it IS a feature of the game.

and as it is with 2012ufo, this isn't actually working like that. i didn't play too much of 2012ufo, because i get no fun from it and deem it to be shit and nothing more, but my coworker did play a lot, and he used the "load and retry" tactics, and with the same set of moves he got different results in the end - it sometimes took up to 20 tries, but it DID NOT work as designed - there is a bug, and anyone can abuse it ; )



I'm not pushing on this solution - i've just signaled that it is there, and what are it's consequences it is up to you guys to make decissions on your product. I do sometimes abuse this bug in critical moments, because it is a part of the game.

Quote
When you have a truly random number generator
you NEVER have one. no random generator created and working in a deterministic environment ( on a processor ) will EVER be trully random. All software random number generators are fully deterministic. to get a trully randomized sequence you need special hardware - usually this is a (quite big) box, with radioactive material and a geiger counter inside. those things and nothing more can provide you with a trully random sequence of bits.


Quote
exploit every weakness of the system

really? how about mind controlling mutons, and giving them laser pistols to artificially boost training of your soldiers? this is also bug using - as far as I remember the ufopedia remakrs on mind controll sais that you will not be able to access the alien's inventory.

another bug abusing scenario is making the alien drop his weapon - he will never pick it up which is simply stupid but it is a bug that facilitates the game so everyone accepts it without a word of protest :P

another example:
time relativity is not conserved. you can have 10 guys, one spots an alien and spends half of his time units on that (hence logically for the half of the turn there was no knowledge of the alien standing where he was spotted), then you take all the rest of the 9 guys, shot out all their time units ( hence, not preserving the parallelity of the actions in a turn ), and then use the other half of the first guys time units, so that he isn't reaction shot by the alien.

there are numerous things like these, and none of them can be called cheating - bug is still a feature of the game and describes the world's game. no more, no less than that.

there are numerous "tricks" like those. abusing the weaknesses of the enemy and using features of the game to get better results is a winning strategy and will  be used.

Quote
Bottom line:
Every system has a weakness, but if I have to choose between these two, I would happily go with the current implementation.


Offline Yankes

  • Commander
  • *****
  • Posts: 3194
    • View Profile
Re: A bug in battlescape and a fix for it
« Reply #9 on: September 27, 2013, 08:57:40 pm »
sometimes is hard to distinguish between bug and feature. Probably best example of this is zerg Carrier form SC1 (zerg?! yes because is one big flying bug, and only pretending that is protos unit :>). Most of way pro-players uses carriers exploits bug/sloppy code in it behavior:
a) Interceptors get command in that same moment as carrier even if carrier is of the range. This increase effective range of carrier attack.
b) As long carrier move, interceptors cant dock. This allow bigger initial attack (all interceptors are ready to strike), that normally not possible because carrier eject only 1 interceptor per time.

In SC2 they fix all this bugs/sloppy logic but pro-players didnt like this because Carrier lost lot of it power without it.

quote from creator of SC1:
Quote from: Patrick Wyatt
Some bugs were related to the development process itself. The Protoss Carrier regularly lagged behind other units because it had its own way of doing … everything. At some point in time the code for the Carrier was branched from the main game code and had diverged beyond any hope of re-integration. Consequently any time a feature was added for other units, it had to be re-implemented for the Carrier. And any time a bug was fixed for other units, a similar bug would later be found in the Carrier code too, only more devious and difficult to fix.

Offline djemon_lda

  • Captain
  • ***
  • Posts: 52
    • View Profile
Re: A bug in battlescape and a fix for it
« Reply #10 on: September 29, 2013, 11:39:22 pm »
you sound like a terran noob to me, if I am to be honest. having goliaths it is simply impossible to lose vs carriers unless the terran gets surprised by a swift switch, which is basically a consequence of "fruitful" thinking "I will so 200/200 3/3 him in one push lol ;3" which hundreds of terrans have for whatever reason, which basically conflicts with their cry about terran being the most impossible difficulty level race to play ever.

to keep your post from being a manipulation I will just add that interceptors that did not come back to the carrier weren't repaired, hence being easier to kill. they also cost quite a lot. I also find the protoss to be ultimately silly not to use an optimisation like this, and politely released the interceptors one by one when their armada is facing the whole army of the enemy. I recommend visiting the TL page. the thing with firing "outside the range" is that when the carrier sends interceptors it's as if a projectile was shot. the same thing happens if a dragoon shoots a vulture that runs out of its range - sometimes the hit happens almost at the distance twice the range. it even happens with zealots sometimes, making an impression of "ranged zealots" when the marine dies from the second hit when he is a bit away.

I could name an actual bug, when at times sunken colonies can hit a siege tank in siege mode despite it is outranged in reality, and that is due to the whole attack being done in 3 parts in the engine.

I wouldn't call sc2 that is a grid based game a FIXING 'thing'. making terran able to outproduce the zerg, when the zerg is on more bases, making the zerg the least mobile race ( excluding mutalisks ).

ending the off-topic : I fail to understand how a broodwar terran cry, or bringing up blizzards mistakes addresses the problem. bugs exist while development, and only a few categories still remain bugs after the game is shipped. only the obvious things. those are things like crashes, denials of part of functionality ( such as being unable to finish the game, or advance a certain branch of the plott ) or documented behaviour that should be guaranteed ( such as when your manual sais A and your game does B ) or when the case just looks like shit - for example in one of the versions of ufo I've been plaing on an amiga where there was no checks of the caps of soldier stats, and after one mission my soldiers time units extended above 255, the unsigned char was overflown, and the soldier had 1 time unit making all of his attacks cost 0 time units giving him the capability of destroy everything that was before him if you only have given him a laser weapon :P

and the reason for that is trivial and very pragmatic - you actually have to prove something is a bug. how will you prove something is wrong if it is undocumentet? ;)


Offline Yankes

  • Commander
  • *****
  • Posts: 3194
    • View Profile
Re: A bug in battlescape and a fix for it
« Reply #11 on: September 30, 2013, 01:37:50 am »
https://www.youtube.com/watch?v=1Rqx8s2qKXM
he dont look like terrain noob ;P

Offline kkmic

  • Commander
  • *****
  • Posts: 582
  • Undefined
    • View Profile
Re: A bug in battlescape and a fix for it
« Reply #12 on: September 30, 2013, 11:15:10 am »
So, you're unhappy with the 2012 X-Com, you are unhappy with the current RNG OXC uses, and you seem to be extremely unhappy with the fact that your ideas don't seem receive the expected approval from the community.

I won't take this discussion further off-topic.

This is my suggestion: stop talking, start coding. As you might have noticed, there are many 'alternate' modes for OXC, so if you are THAT unhappy about the current RNG, make a better one as an alternative. If it will prove itself, it will become the default one, you can be sure of that (after all, X-Com had a 'more random' RNG system than the current one OXC uses).

Offline djemon_lda

  • Captain
  • ***
  • Posts: 52
    • View Profile
Re: A bug in battlescape and a fix for it
« Reply #13 on: September 30, 2013, 03:38:50 pm »
Quote
https://www.youtube.com/watch?v=1Rqx8s2qKXM
he dont look like terrain noob ;P
nice material for people that don't know broodwar, but I don't get what you are relating to tbh. if you play on iccup then we can perhaps play some games - but be aware I haven't been playing for a really long long time, so I don't know if I will be able to match your skill nowadays.

Quote
If it will prove itself, it will become the default one
that is one of the first logical comments I have found on this forum, thank you for that. I encourage others, to do the same.

I will start from fixing the code around reaction fire as, to my surprise, it still isn't fixed, and the latest fixes were revoked, despite I've given pointers on why was that failing. I will post all the code on the forum with my commends for a review that everyone can take part in. Can you please tell me if the compilers used by the team support c++11 features ?

YET:
Quote
So, you're unhappy with the 2012 X-Com, you are unhappy with the current RNG OXC uses, and you seem to be extremely unhappy with the fact that your ideas don't seem receive the expected approval from the community.
extreme manipulation in these generalizations. let's apply a bit details so that your cheap marketing style wouldn't look as meaningful as they do where the information is insufficient.

Quote
So, you're unhappy with the 2012 X-Com
it's hard to say that I am happy or unhappy with it. I think it is a bad product - sure - because it's a bad realization of the original. it's overly simplified. I have commented the way it actually works, with the way it is supposed to work according to what's said about it.

what I am unhappy with is that bethesda has bought the company that was making a really neat remake of the original version and then closed the project, because their managers have expected a great game project to be closed as fast as their regular shit projects.

Quote
you are unhappy with the current RNG OXC uses
really? I wander how did you develop such an assumption. all I actually did was comparing what was written on the forums on the functionality and it's current implementation, and signalized a discrepancy, simply not accepting a "well, it's not a bug... it's a feature kind of bug, let's call it a bug-ture" response, which I don't agree as a right approach to solve problems.

and to note: changing the implementation of the RNG OXC uses was proposed by SupSuper, which I actually agree with ( so it worked in the different direction than you have implied it to be ) and I have only proposed an implementation which would be the mersenne twister, and I still keep my advice on that one without a slight difference : use mersenne twister, best if it's taken from the random.h from the new c++11 standard headers - there are two to chose, and very easy to use.

Quote
and you seem to be extremely unhappy with the fact that your ideas don't seem receive the expected approval from the community.
I'm not making my logic out of my emotions - I'm not a woman. I'd advise others do the same, it makes communication a lot easier. If you were reading the posts carefully, you'd notice one of the first posts on that forum I have posted have a comment, that I only PROPOSE and it is up to the development, because it is their product. I have my own private project, where I make all decisions, and I have my work projects (I have more than one under my supervision) where I make most decisions. believe me I have a lot of things to put my hands on, and very little time to catch some sleep ; )

Offline kkmic

  • Commander
  • *****
  • Posts: 582
  • Undefined
    • View Profile
Re: A bug in battlescape and a fix for it
« Reply #14 on: September 30, 2013, 05:03:20 pm »
Oh my... why don't you follow my previous advice and transform that wall of useless hair-splitting text into a useful wall of code?

To be honest, my words are sometimes quoted by other members of the community, but to have one line split in three, and every section quoted separately and analysed for hidden meanings, and in turn to generate a whole page of text by itself... no sir, that never happened to me.