#74134 - silent_code - Thu Mar 02, 2006 7:01 pm
hi!
first of all i'll like to say THANK YOU VERY MUCH! to everyone in the scene for sharing information and helping noobs to get into NDS programming.
ok, let's get started.
i'm working on my first NDS demo and so far i've done quite good with the information available on the net. but there's one thing i don't know how to implement - though i have done it many times on the pc: a random number generator.
the basic idea is to initialize the randomWhatever() funktion with a timer like "srand(time());". *not_so_real_code*
now, how can i do it on the ds? is it possible to use the standard c/c++ functons? what NDS timer (4 for each cpu...???) could/should be used with it and how would one write that down (in c/c++)?
please give me a hint, some lines of code, a link to a tutorial or something.
after that'll be implemented i might release the sources (for beginners).
i only use the devkitPro and it's libs... no PAlib or anything.
oh, btw: it's a really simple zombie shooter (a sidescroller) ;p
just my starting project. (i also did some stuff for the gba, but that's ages ago... :D)
greetings to all you forum members!
#74137 - genfish - Thu Mar 02, 2006 7:34 pm
i've been wondering about this too, i wanna make a sprite animation and want to know where i can get a time in milliseconds from. I suppose its the same sort of thing because in windows you seed with timeGettime for random numbers :)
_________________
there is no rl only afk
#74138 - DekuTree64 - Thu Mar 02, 2006 7:41 pm
Random numbers: See FAQ. You can probably use the standard functions too though.
Seeding the generator: The 'standard' trick is to have a title screen, and count VBlanks. When the player presses start, use the number of VBlanks that have passed as the seed.
On DS, you can use the real time clock as the seed, similar to the PC. I don't know the libnds calls for it offhand, but you can probably find them in the headers (look for real-time clock or rtc, not hardware timers).
For animation speed, count VBlanks with an interrupt handler. That will give you the time in (very close to) 60ths of a second. If you want milliseconds, multiply by 1000/60.
_________________
___________
The best optimization is to do nothing at all.
Therefore a fully optimized program doesn't exist.
-Deku
#74139 - dovoto - Thu Mar 02, 2006 7:43 pm
| Code: |
#include <stdlib.h>
int main(void)
{
DisplayTitleScreen();
while(!keyPressed) rand();
while(!done)
{
//do cool random game stuff here
}
}
|
Or you could grab the time from the ipc and seed with that if you like the seed with time thing...but the above works great for most as rand will be nice and random depending on when the user hits a key.
_________________
www.drunkencoders.com
#74141 - silent_code - Thu Mar 02, 2006 8:02 pm
well, thanks a lot!
i knew about that title screen stuff, but i didn't think about the vblanks as a counter... it's a very nice idea! :) i'll check that out...
dovoto: i'll also take a look at that. sounds good, too.
am i right that each time you call rand() it iterates through the initially generated "random number list"? don't know the propper term, but i think it generates some kind of list or at least some "generator polynom" or something like that, so it doesn't need to generate a real random number on each call, reducing calculations - but when one presses a button exactly at the same time in two sessions, these sesions will be the same.
ok, let's make some random stuff :)
thanks again!
ps: pretty fast replys... :D
#74155 - Joat - Thu Mar 02, 2006 10:23 pm
no, rand() doesn't maintain a buffer of random values, it generates a new one each time. There are a number of different methods to do this, but rand() is normally implemented as a linear congruential generator (google for more info), which isn't too expensive, the worst operation is a mod, and a good choice of m turns that into an and.
rand() isn't a fantastic RNG, but it's fine for almost all game uses.
You are correct RE: if someone pushes start after exactly the same number of frames on two different game sessions that you'll get the same sequence of random numbers, and this could be a problem on a GBA or other system where you don't have any clock (timers don't count, they have to be seeded themselves, e.g. by player input). There are a couple of ways to get around this on those systems, but on the NDS, you have a realtime clock, so just convert the current time and date into seconds, and srand with that.
If you *do* want to have a buffer of random numbers that are returned very quickly most of the time, and can afford the occasional (very expensive) buffer refill, look into a mersenne twister RNG. It maintains a state of 650 odd numbers, but if you exhaust those 650, the buffer refill is expensive, so I don't particularly like using this in a realtime environment, but it's a much better RNG than rand().
And a 3rd option, if you just want fast 'randomish' numbers for a starfield animation or something where anything will do, just create a buffer of 256 or 512 entries or whatever, and fill that with rand() or MT or whatever.
_________________
Joat
http://www.bottledlight.com
#74194 - silent_code - Fri Mar 03, 2006 12:33 pm
ah, thanks joat!
ok, i implemented dovotos approach tonight and i just have to put in the seeding (srand(...)) of some sort.
seems rand() is ok for me as i use it quite often for particles and monsters... when spawning one of these i asign random values to thair members. maybe i'll put in some odd sized buffer (lookup table) and fill it with random numbers and use it as pseudo random numbers for the particles as one wouldn't notice that...
btw: i figured out that instead of rand() you have to do "rand() % 1000 / 1000.0f" to get some sort of random number between 0 and 1. correct me if i'm wrong or if there exists a better way of doing it (less operations). that brings me back to the lookup table thing...
if i used the rtc, do i really need to convert it into seconds? can't i just read the register (didn't look it up, but i suppose it's a register or a combination of a few of these)?
that's it.
thanks in advance for answering.
ps:
| Joat wrote: |
| no, rand() doesn't maintain a buffer of random values |
i meant it more like in perlin noise, not a real list of values (would be a memory eater)... sorry for the screwed explanation and thanks for your precise answer (again)
#74242 - knight0fdragon - Fri Mar 03, 2006 8:12 pm
just use srand ( -(~IPC->curtime[7]) - 1) ;
_________________
http://www.myspace.com/knight0fdragonds
MK DS FC: Dragon 330772 075464
AC WW FC: Anthony SamsClub 1933-3433-9458
MPFH: Dragon 0215 4231 1206
#74325 - silent_code - Sat Mar 04, 2006 12:57 pm
cool! thanks, i'll check it as soon as possible!
EDIT:
compiles with no problems, but: having no hw and i must rely on emus. i need to check which implements the clock. dualis doesn't seem to have that feature (the game is always the same...).
[i wish i had ??? for hw... :( ]
#104773 - Juice - Mon Oct 02, 2006 4:25 pm
I have been looking for how to read the clock for a looong time (two weeks or so). Finally someone who can tell me.
I've checked the code, works fine on my NDS Lite!
Keep up the good stuff!
#104798 - knight0fdragon - Mon Oct 02, 2006 7:22 pm
that just reads in the seconds, there are other spots in curTime for everything else, search around in the forums or in the libnds header files, and you should find it.
_________________
http://www.myspace.com/knight0fdragonds
MK DS FC: Dragon 330772 075464
AC WW FC: Anthony SamsClub 1933-3433-9458
MPFH: Dragon 0215 4231 1206
#104969 - HyperHacker - Wed Oct 04, 2006 8:08 pm
Do commercial GBA games use that "count VBlanks at the title screen" method?
_________________
I'm a PSP hacker now, but I still <3 DS.
#104982 - tepples - Wed Oct 04, 2006 9:54 pm
| HyperHacker wrote: |
| Do commercial GBA games use that "count VBlanks at the title screen" method? |
I have partially mapped out the memory usage of the commercial game Tetris for NES, published by Nintendo. It counts vblanks at the title screen.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#104985 - silent_code - Wed Oct 04, 2006 10:00 pm
you can "cheat" that way in some yoshi's island (gba) minigames... i found that out by myself ;) it sure uses vblanks at the start of each minigame to randomize it. check it out (like the memory game), you'll get the pretty lives a lot easier if you manage to press the required button fast enough (can't remember which one it was).
oh... i did that only for educational purpose... not for cheating (and the 99 lives i got afterwards) ... ;p
... so they use that method in commercial games, because it's cheap and on some other systems it's the only way. i guess it's kind of a legacy method from the old days. though i use it too and the results are fine. not perfect, but you get your random games and that's what you want.
#104999 - HyperHacker - Wed Oct 04, 2006 11:36 pm
Hm, I wonder if the Pok?mon Advance games do that, then? I always found the RNG seemed broken in them and that would certainly explain why. Seems dumb to do that when the game has a real-time clock, but there could be reasons. (They actually coded the game, complete with error message, to still work if the clock battery dies, so they might have avoided using the clock for that in fear it'd break the RNG if the battery died. Or they just used some standard library that does it for them.)
_________________
I'm a PSP hacker now, but I still <3 DS.
#105301 - zzo38computer - Sat Oct 07, 2006 3:47 pm
I have used ARCFOUR for random number generator, I don't know exactly how good that is
_________________
Important: Please send messages about FWNITRO to the public forum, not privately to me.
#106239 - spencer723 - Tue Oct 17, 2006 3:24 am
How about this? What if you took information in from the mic when you go to generate a random number and just mix that number up a bit. I'm sure there will be different information coming in through the DS mic everytime you generate a number.
#106271 - silent_code - Tue Oct 17, 2006 12:36 pm
not so good. believe me. though you don't have to. nice idea, but there are better ways and they work great. using the rtc or vblank method works fine. trust me.
;D
#106286 - Sausage Boy - Tue Oct 17, 2006 3:39 pm
Getting the seed from the mic in combination with rtc and vblank would make it very impossible to get the same number again.
_________________
"no offense, but this is the gayest game ever"
#106289 - silent_code - Tue Oct 17, 2006 4:31 pm
if anyone needs it *that* random, go for it. ;) but in a rather silent environment there won't be much mic input, will it? i'm just curious. i believe a.t.w. has mic support and you have to make *some* sounds to see the effect, even with high gain. again, i'm just curious if that would work in a normal gaming environment. or you had to force the player to say 'start' or something to get the game started. that would be a nice idea ;p [remember to mention me somewhere if you use this *lol*]
#106346 - HyperHacker - Wed Oct 18, 2006 4:47 am
Most games have music. Assuming the volume is up, the mic should pick it up.
_________________
I'm a PSP hacker now, but I still <3 DS.
#106370 - Optihut - Wed Oct 18, 2006 12:58 pm
| DekuTree64 wrote: |
| Seeding the generator: The 'standard' trick is to have a title screen, and count VBlanks. When the player presses start, use the number of VBlanks that have passed as the seed. |
How about using that for random numbers in general: Have the time cycle through 0 to 9 and whenever a button is pressed that value is put on a stack, which is used for random numbers. In case of an empty stack and a request for a random number, generate one with rand().
#106457 - silent_code - Thu Oct 19, 2006 8:46 am
@Optihut: that would essencially be the same as vblanks. only with the method i use you can increase a counter with every vblank what will give you more than just 10 possible seeds. there are 256 possibilities with chars. now take an integer or even a long ;^)
@ HyperHacker: that's a good one, but there's one problem: headphones. think about it. the game would obviously behave different when using headphones or no sound at all. i imagine playing the same game over and over just because it's late and my gf is sleeping besides me and i don't want to wake her up by being forced to raise the volume or make some sounds when starting a new game, level or whatever, just to get another random game... ;^p that's a limitation that should be considered. such features may sound great in the begining, but they often turn out not being used in the end.
i think i commented enough on this topic. go with rtc or vblanks, it's fine, it works, it's as random as one needs it and it's not that limited and "complicated". ;^D
#106471 - Optihut - Thu Oct 19, 2006 1:21 pm
| silent_code wrote: |
| @Optihut: that would essencially be the same as vblanks. only with the method i use you can increase a counter with every vblank what will give you more than just 10 possible seeds. there are 256 possibilities with chars. now take an integer or even a long ;^) |
You misunderstood me, which is mostly my fault for not explaining it better. What I propose doesn't touch the method of seeding. Seeding should still work the way it is done at the moment.
However, even with seeding there is still the problem that rand() yields quasi random numbers, which can be predicted if you happen to know the seed. In order to avoid that, I thought it might be nice to generate a random number without using rand() whenever a button is pressed: When the player presses a button in the game - for instance when moving his character in the game - the program takes a number, based on the timer, and puts it on a stack. This stack is supposed to hold these player generated random numbers. Whenever the game requests a random number, it first checks if there is a number on the stack and takes that. If there is no number on the stack, then a quasi random number can be generated with rand() instead.
This way, we would mostly avoid quasi random numbers, but I am a bit concerned if the distribution of timer based numbers with the above outlined method is equal and whether this method wouldn't bog down the CPU.
#106557 - silent_code - Fri Oct 20, 2006 4:12 pm
i understand. unfortunately i guess i can think of issues here aswell... but modulating the random number with some random "real world" data is a nice idea ;)
#106577 - josath - Fri Oct 20, 2006 10:04 pm
| Optihut wrote: |
This way, we would mostly avoid quasi random numbers, but I am a bit concerned if the distribution of timer based numbers with the above outlined method is equal and whether this method wouldn't bog down the CPU. |
1. What happens if you need 10 random numbers, but user only pressed a button 7 times?
2. What happens if in your game, the user is pressing a button at a very regular interval, you may get numbers that look like 6 - 7 - 8 - 7 - 8 - 6, which might not be very random.
Really, the best way is to use RTC/vblanks to seed, then use a pre-existing PRNG that is known to work good enough.
#106580 - tepples - Fri Oct 20, 2006 10:52 pm
| josath wrote: |
1. What happens if you need 10 random numbers, but user only pressed a button 7 times?
2. What happens if in your game, the user is pressing a button at a very regular interval, you may get numbers that look like 6 - 7 - 8 - 7 - 8 - 6, which might not be very random. |
That's why you mix each random number you get into the PRNG's seed.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#106586 - Optihut - Sat Oct 21, 2006 12:45 am
| josath wrote: |
1. What happens if you need 10 random numbers, but user only pressed a button 7 times?
2. What happens if in your game, the user is pressing a button at a very regular interval, you may get numbers that look like 6 - 7 - 8 - 7 - 8 - 6, which might not be very random. |
1. After request #7 the stack is empty and then for random number 8, 9 and 10 the rand() function would be used as mentioned in my post above.
2. That's similar to the concern I have - is the distribution of numbers roughly equal and thus random? I doubt that anyone can time button pressing with the accuracy of microseconds, so your scenario shouldn't be an issue. But agreed, I have voiced the concern that the numbers may not be random, even though in theory they should be random. That's something that can only be answered by a test, though. If I ever get off my ass and actually program something again, I am definitely looking into this.
#106588 - tepples - Sat Oct 21, 2006 1:33 am
| Optihut wrote: |
| I doubt that anyone can time button pressing with the accuracy of microseconds, so your scenario shouldn't be an issue. |
Most emulators, and many input devices (such as a future DS Player for Wii), round all input to the nearest frame (16.7ms).
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#106619 - Optihut - Sat Oct 21, 2006 2:27 pm
| tepples wrote: |
| Optihut wrote: | | I doubt that anyone can time button pressing with the accuracy of microseconds, so your scenario shouldn't be an issue. |
Most emulators, and many input devices (such as a future DS Player for Wii), round all input to the nearest frame (16.7ms). |
Damnation - that's a serious problem then.
#107000 - Optihut - Wed Oct 25, 2006 4:59 pm
I had to give it a try and programmed it for the PC. I have used the millisecond timer of SDL, so this might not be applicable to the DS. Then I tested it for 1000 keystrokes, typing a short letter. The results are as follows:
0: 105
1: 99
2: 95
3: 94
4: 106
5: 96
6: 104
7: 105
8: 96
9: 100
This looks fairly random and equally distributed to me. In case anyone is interested, here is the quick and dirty code:
| Code: |
/***************************************************************************
Copyright (C) 2006
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
***************************************************************************/
#include "SDL.h"
#include <stdio.h>
using namespace std;
int main(int argc, char *argv[]){ //The program prints out a timer based number from 0 to 9 when a button is pressed
SDL_Init(SDL_INIT_EVERYTHING);
SDL_Event event;
Uint32 timer;
int distribution[10];
for (int i=0; i< 10;i++){distribution[i]=0;}; //initialising field "Distribution[10]" with 0s
#define NUMKEYSTROKE 1000 // number of userinputs before program termination
int counter=0; // counting variable used to terminate the program after NUMKEYSTROKE userinputs
SDL_Surface *screen;
screen = SDL_SetVideoMode(640, 480, 32, SDL_SWSURFACE );
printf("Start\n");
while (counter< NUMKEYSTROKE){
while( SDL_PollEvent( &event ) )
{
if( event.type == SDL_KEYDOWN )
{timer = SDL_GetTicks()%10;// random number from 0-9 based on the timer is taken on a keystroke
counter++;
distribution[timer]++;
printf("%d", timer);
};
};
}
printf ("\n");
for (int j = 0; j < 10; j++){printf ("%d distribution: %d\n",j,distribution[j]);};
SDL_Quit();
return 0;
} |
EDIT: After googling for "Entropy Gatherer" I have found this website, which states:
| Quote: |
| Interactive programs commonly use things like mouse movements or keyboard interaction to generate the randomness that we are looking for. Clearly this method of random number generation is not suitable for batch or background applications, so we need to come up with something else... |
So I guess my novel idea wasn't new after all and is already implemented.
#107040 - sonny_jim - Wed Oct 25, 2006 10:11 pm
Mashing the keyboard randomly was the method pgp used to create it's seed way back when I had my 486sx ;-)
The wierdest RNG I've seen relied on a camera looking at a lava lamp. http://www.lavarnd.org/what/index.html