srand() and rand() 
Author Message
 srand() and rand()

Hi there. Can someone please explain to me how srand()/rand() tandem
is supposed to work? I'm trying to write a simple sea battle game
under Windows - and the problem lies within the random map generator -
it enters an infinite loop only *occasionally* (roughly once every 20
runs). Here's the code:

#define NUM_CELLS 10
typedef enum { ctFree, ctShip, ctHit, ctMiss } cell_t;
typedef enum { dirHorz, dirVert, dirEnd } dir_t;
/* ... */
void map_randomize(cell_t (*map)[NUM_CELLS]) {
    int ship_kind, ship_num;
    POINT cell;

    map_reset(map);
    for (ship_kind = 1; ship_kind <= NUM_SHIPS; ship_kind++) {
        for (ship_num = 0; ship_num < NUM_SHIPS - ship_kind + 1;
ship_num++) {
            do {
                cell.x = rand() % NUM_CELLS;
                cell.y = rand() % NUM_CELLS;
            } while (!map_fit_ship(map, cell, ship_kind, rand() %
dirEnd));
        }
    }

Quote:
}

I'm calling srand() once when the program starts feeding it the number
of ticks since the OS booted. I suspect that it's the do/while loop
that spoils the party - the rand calls keep returning same numbers, so
map_fit_ship() never suucceeds.. map_fit_ship() in turn calls
map_fit_cell() which in turn calls some other function. This whole
process is not that slow - it only takes 0-1% of CPU even if I hold
down the map generation key shortcut - so my first guess that the code
was too {*filter*} the CPU was soon rejected.. The code is rather simple
for me to follow but I couldn't find where the problem is.

What do you think?

TIA



Sat, 10 Jan 2004 00:50:35 GMT  
 srand() and rand()


Quote:
> Hi there. Can someone please explain to me how srand()/rand() tandem
> is supposed to work? I'm trying to write a simple sea battle game

You call srand() once at the beginning of the program, and after, srand()
any times you want.

Quote:
> under Windows - and the problem lies within the random map generator -
> it enters an infinite loop only *occasionally* (roughly once every 20
> runs). Here's the code:
> #define NUM_CELLS 10
> typedef enum { ctFree, ctShip, ctHit, ctMiss } cell_t;
> typedef enum { dirHorz, dirVert, dirEnd } dir_t;
> /* ... */
> void map_randomize(cell_t (*map)[NUM_CELLS]) {
>     int ship_kind, ship_num;
>     POINT cell;

>     map_reset(map);
>     for (ship_kind = 1; ship_kind <= NUM_SHIPS; ship_kind++) {

I hope you start with the biggest ship.

Quote:
>         for (ship_num = 0; ship_num < NUM_SHIPS - ship_kind + 1;

sounds weird, but I suppose you know waht you are doing...

Quote:
> ship_num++) {
>             do {
>                 cell.x = rand() % NUM_CELLS;
>                 cell.y = rand() % NUM_CELLS;

This makes a poor distribution, but can work.(see the FAQ for a better
distribution)

Quote:
>             } while (!map_fit_ship(map, cell, ship_kind, rand() %
> dirEnd));

You have only one output condition. If the placement test always returns 0,
you're dead. It can happen if
- you place the small ships before the big ones (design)
- the placement constraints are too high (specs)
- the ship density is too high (specs)

Not seeing the whole beast, it's hard to say more.

Quote:
>         }
>     }
> }

> I'm calling srand() once when the program starts feeding it the number
> of ticks since the OS booted. I suspect that it's the do/while loop

What about the value returned by time()? To have a constnt behaviour
(useful for debugging) you can display the seed value and note it whan it
hangs. Then you seed with it, and the hang condition will happen again.

#define DEBUGGING 0 /* 0 | 1 */

#if DEBUGGING
   {
      srand(FOO);
   }  
#else
   {
      int seed = (int)time(NULL);
      srand(seed);
      printf ("seed=%d\n", seed); /* prints FOO */
   }  
#endif

Quote:
> that spoils the party - the rand calls keep returning same numbers, so

Is it the infinite loop ?

Quote:
> map_fit_ship() never suucceeds.. map_fit_ship() in turn calls
> map_fit_cell() which in turn calls some other function. This whole
> process is not that slow - it only takes 0-1% of CPU even if I hold
> down the map generation key shortcut - so my first guess that the code
> was too {*filter*} the CPU was soon rejected.. The code is rather simple
> for me to follow but I couldn't find where the problem is.

--
-hs-    "boycott Beijing 2008" email: emdel at noos.fr
CLC-FAQ: http://www.*-*-*.com/ ~scs/C-faq/top.html
ISO-C Library: http://www.*-*-*.com/
FAQ de FCLC : http://www.*-*-*.com/ ~rumeau/fclc


Fri, 09 Jan 2004 13:27:30 GMT  
 srand() and rand()


Quote:
> You call srand() once at the beginning of the program, and after,
> srand() any times you want.

Grrr...

You call srand() once at the beginning of the program, and later,
rand() any times you want.

--
-hs-    "boycott Beijing 2008" email: emdel at noos.fr
CLC-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
ISO-C Library: http://www.dinkumware.com/htm_cl/index.html
FAQ de FCLC : http://www.isty-info.uvsq.fr/~rumeau/fclc



Fri, 09 Jan 2004 13:29:47 GMT  
 srand() and rand()
Quote:
>I hope you start with the biggest ship.

Wow, it never occurred to me that the order of placement could make
any difference...

#define NUM_SHIPS 4
I changed this line
        for (ship_kind = 1; ship_kind <= NUM_SHIPS; ship_kind++) {
to
        for (ship_kind = NUM_SHIPS; ship_kind >= 1; ship_kind--) {

and now it doesn't crash anymore :)))) Thanks a lot!!



Sat, 10 Jan 2004 01:54:15 GMT  
 srand() and rand()


Quote:


> > You call srand() once at the beginning of the program, and after,
> > srand() any times you want.

> Grrr...

> You call srand() once at the beginning of the program, and later,
> rand() any times you want.

Hehehe, yeah but there are times where you would call srand() more than
once.

Tom



Fri, 09 Jan 2004 18:42:39 GMT  
 srand() and rand()


Quote:





>> > You call srand() once at the beginning of the program, and after,
>> > srand() any times you want.

>> Grrr...

>> You call srand() once at the beginning of the program, and later,
>> rand() any times you want.

>Hehehe, yeah but there are times where you would call srand() more than
>once.

But you would need a very good reason to do so. If you don't have a very
good reason then don't. :-)

--
-----------------------------------------


-----------------------------------------



Fri, 09 Jan 2004 21:05:02 GMT  
 srand() and rand()



Quote:

> > You call srand() once at the beginning of the program, and later,
> > rand() any times you want.

> Hehehe, yeah but there are times where you would call srand() more than
> once.

> Tom

Could you tell me when you would feel the need to do this? If you call srand
again in your program, you are going to interfere with the period of the
random generator (which is quite poor for most implementations, so Id
recommend using another generator like Mersenne Twister or whatever) and
this may lead to correlation of your numbers. As you normally want "random"
numbers you would like to avoid correlation as far as possible, therefore
calling srand() more then once is something you should only do, when you
really know what you (and the random generator!) are doing!

chris



Fri, 09 Jan 2004 22:05:14 GMT  
 srand() and rand()

Quote:



> > Hehehe, yeah but there are times where you would call srand() more than
> > once.

> Could you tell me when you would feel the need to do this?

When, for some reason, you need to re-use the same run of pseudo-random
numbers. No, I can't think of a practical application either, but I
wouldn't be surprised if there were one.

Richard



Fri, 09 Jan 2004 22:54:38 GMT  
 srand() and rand()


Quote:



>> > Hehehe, yeah but there are times where you would call srand() more
>> > than once.

>> Could you tell me when you would feel the need to do this?

> When, for some reason, you need to re-use the same run of pseudo-random
> numbers. No, I can't think of a practical application either, but I
> wouldn't be surprised if there were one.

I've seen games that do this to recreate game items that were
randomly generated in the first place.

--

                           by the object denoted by t." -- KIF



Fri, 09 Jan 2004 23:57:38 GMT  
 srand() and rand()

Quote:

>>I hope you start with the biggest ship.


Quote:

>Wow, it never occurred to me that the order of placement could make
>any difference...

Now you know what "memory fragmentation" is all about. :-)

Conside the following 4-by-4 grid-point array:

    .  .  .  .
    .  .  .  .
    .  .  .  .
    .  .  .  .

Suppose you want to place four "ships", one of length 4 and the
rest of length 2, e.g.:

    .  .  1  5
    2  2  1  5
    .  .  1  3
    4  4  1  3

where "1" is ship 1, "2" is ship 2, and so on.  If you put
down the small ships first:

    .  2  2  5
    4  4  .  5
    .  .  3  .
    .  .  3  .

you can easily "plug up" all possible orientations for the
larger one.  There is enough *space* left on the grid, but
none of the "sub-spaces" are large enough for the large object.

The same applies to a linear arrangement -- instead of a 4x4 grid
you have something like 16 dots, which we might call "bytes":

    .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .

If you call a function -- let us call it balloc() -- to reserve
some of these bytes, followed by bfree() to release them, you
can eventually end up with a pattern like this:

    .  .  .  1  1  .  3  3  .  5  5  .  .  .  7  7

Here we did:

    mem[0] = balloc(3);
    mem[1] = balloc(2);
    mem[2] = balloc(1);
    mem[3] = balloc(2);
    mem[4] = balloc(1);
    mem[5] = balloc(2);
    mem[6] = balloc(3);
    mem[7] = balloc(2);

followed by:

    bfree(mem[0]);
    bfree(mem[2]);
    bfree(mem[4]);
    bfree(mem[6]);

As you can see, there are still 8 bytes free -- but balloc(4)
will fail, because there is no place where four dots are available
all in a row.

Make the arena much bigger, change balloc() to malloc() and bfree()
to free(), and you now have a pretty good idea what goes on "under
the hood", and why malloc() can fail even though "there is plenty
of memory left".

In languages like Lisp, where you have a lot of dynamic allocation
but no "raw" pointers available to users, the implementation can
use a "compacting garbage collector" that will go in and move the
allocated objects (1, 3, 5, and 7 above) to the left edge, changing
any values that "point" to them.

It is not impossible to do the same in a C implementation, but it
tends not to be terribly efficient, and people who want Lisp know
where to look for it. :-)
--
In-Real-Life: Chris Torek, Wind River Systems




Sat, 10 Jan 2004 00:10:41 GMT  
 srand() and rand()

Quote:




> > > Hehehe, yeah but there are times where you would call srand() more than
> > > once.

> > Could you tell me when you would feel the need to do this?

> When, for some reason, you need to re-use the same run of pseudo-random
> numbers. No, I can't think of a practical application either, but I
> wouldn't be surprised if there were one.

    As a general case, this is useful in the time/space trade-off. To
use the same sequence, one could do one of the following:

    1) Save the seed, and call srand() with that seed to regenerate the
sequence.
    2) Save the whole sequence.

    Option 1 can be used with a very long sequence, where it would be
too expensive to save the entire sequence out to disk.
    Option 2 can be used for a short sequence, when storage space isn't
an issue or where the PRNG is too expensive in terms of CPU usage to do
more than once.

    In the game "Diablo II", they do just this. when a new game is
created, it is randomly generated, however the seed is stored with the
character data, so that when the character is saved and then later
loaded, the same "random" level can be regenerated, and the player can
pick up where (s)he left off.

--
Clark S. Cox III

http://www.whereismyhead.com/clark/



Sat, 10 Jan 2004 01:36:39 GMT  
 srand() and rand()

Quote:

> When, for some reason, you need to re-use the same run of pseudo-random
> numbers. No, I can't think of a practical application either, but I
> wouldn't be surprised if there were one.

Regression testing.


Sat, 10 Jan 2004 09:22:18 GMT  
 
 [ 12 post ] 

 Relevant Pages 

1. need help on srand and rand

2. srand and rand Question

3. Using srand() and rand()

4. Problem with rand() and srand()

5. help for Rand,randomize,srand;

6. Problem with rand() and srand()

7. rand, srand and time

8. rand and srand

9. rand, srand

10. rand(), srand() source code

11. difference between rand, random, randomize and srand

12. Please help with: rand(), srand(), srand48(), drand48() ???

 

 
Powered by phpBB® Forum Software