-rw-r--r-- | noncore/games/zsame/dropin/kapplication.h | 23 | ||||
-rw-r--r-- | noncore/games/zsame/dropin/krandomsequence.cpp | 240 | ||||
-rw-r--r-- | noncore/games/zsame/dropin/krandomsequence.h | 143 |
3 files changed, 406 insertions, 0 deletions
diff --git a/noncore/games/zsame/dropin/kapplication.h b/noncore/games/zsame/dropin/kapplication.h new file mode 100644 index 0000000..f83d08e --- a/dev/null +++ b/noncore/games/zsame/dropin/kapplication.h @@ -0,0 +1,23 @@ +#include <stdio.h> +#include <stdlib.h> +#include <sys/types.h> +#include <sys/stat.h> +#include <fcntl.h> +#include <unistd.h> +#include <time.h> + +static int _random() { + static int init = false; + if (!init) { + unsigned int seed; + init = true; + int fd = ::open("/dev/urandom", O_RDONLY); + if( fd<=0 || ::read(fd, &seed, sizeof(seed)) != sizeof(seed) ) { + srand(getpid()); + seed = rand()+time(0); + } + if(fd>=0) close( fd ); + srand(seed); + } + return rand(); +} diff --git a/noncore/games/zsame/dropin/krandomsequence.cpp b/noncore/games/zsame/dropin/krandomsequence.cpp new file mode 100644 index 0000000..d27a1c5 --- a/dev/null +++ b/noncore/games/zsame/dropin/krandomsequence.cpp @@ -0,0 +1,240 @@ +/* + This file is part of the KDE libraries + Copyright (c) 1999 Sean Harmer <sh@astro.keele.ac.uk> + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public License + along with this library; see the file COPYING.LIB. If not, write to + the Free Software Foundation, Inc., 59 Temple Place - Suite 330, + Boston, MA 02111-1307, USA. +*/ + +#include <qlist.h> +#include <string.h> + +#include "kapplication.h" +#include "krandomsequence.h" + +const int KRandomSequence::m_nShuffleTableSize = 32; + +////////////////////////////////////////////////////////////////////////////// +// Construction / Destruction +////////////////////////////////////////////////////////////////////////////// + +KRandomSequence::KRandomSequence( long lngSeed1 ) +{ + // Seed the generator + setSeed( lngSeed1 ); + + + // Set the size of the shuffle table + m_ShuffleArray = new long [m_nShuffleTableSize]; +} + +KRandomSequence::~KRandomSequence() +{ + delete [] m_ShuffleArray; +} + +KRandomSequence::KRandomSequence(const KRandomSequence &a) +{ + // Set the size of the shuffle table + m_ShuffleArray = new long [m_nShuffleTableSize]; + *this = a; +} + +KRandomSequence & +KRandomSequence::operator=(const KRandomSequence &a) +{ + m_lngSeed1 = a.m_lngSeed1; + m_lngSeed2 = a.m_lngSeed2; + m_lngShufflePos = a.m_lngShufflePos; + memcpy(m_ShuffleArray, a.m_ShuffleArray, sizeof(long)*m_nShuffleTableSize); + return *this; +} + + +////////////////////////////////////////////////////////////////////////////// +// Member Functions +////////////////////////////////////////////////////////////////////////////// + +void KRandomSequence::setSeed( long lngSeed1 ) +{ + // Convert the positive seed number to a negative one so that the Draw() + // function can intialise itself the first time it is called. We just have + // to make sure that the seed used != 0 as zero perpetuates itself in a + // sequence of random numbers. + if ( lngSeed1 < 0 ) + { + m_lngSeed1 = -1; + } + else if (lngSeed1 == 0) + { + m_lngSeed1 = -((_random() & ~1)+1); + } + else + { + m_lngSeed1 = -lngSeed1; + } +} + +static const long sMod1 = 2147483563; +static const long sMod2 = 2147483399; + +void KRandomSequence::Draw() +{ + static const long sMM1 = sMod1 - 1; + static const long sA1 = 40014; + static const long sA2 = 40692; + static const long sQ1 = 53668; + static const long sQ2 = 52774; + static const long sR1 = 12211; + static const long sR2 = 3791; + static const long sDiv = 1 + sMM1 / m_nShuffleTableSize; + + // Long period (>2 * 10^18) random number generator of L'Ecuyer with + // Bayes-Durham shuffle and added safeguards. Returns a uniform random + // deviate between 0.0 and 1.0 (exclusive of the endpoint values). Call + // with a negative number to initialize; thereafter, do not alter idum + // between successive deviates in a sequence. RNMX should approximate + // the largest floating point value that is less than 1. + + int j; // Index for the shuffle table + long k; + + // Initialise + if ( m_lngSeed1 <= 0 ) + { + m_lngSeed2 = m_lngSeed1; + + // Load the shuffle table after 8 warm-ups + for ( j = m_nShuffleTableSize + 7; j >= 0; j-- ) + { + k = m_lngSeed1 / sQ1; + m_lngSeed1 = sA1 * ( m_lngSeed1 - k*sQ1) - k*sR1; + if ( m_lngSeed1 < 0 ) + { + m_lngSeed1 += sMod1; + } + + if ( j < m_nShuffleTableSize ) + { + m_ShuffleArray[j] = m_lngSeed1; + } + } + + m_lngShufflePos = m_ShuffleArray[0]; + } + + // Start here when not initializing + + // Compute m_lngSeed1 = ( lngIA1*m_lngSeed1 ) % lngIM1 without overflows + // by Schrage's method + k = m_lngSeed1 / sQ1; + m_lngSeed1 = sA1 * ( m_lngSeed1 - k*sQ1 ) - k*sR1; + if ( m_lngSeed1 < 0 ) + { + m_lngSeed1 += sMod1; + } + + // Compute m_lngSeed2 = ( lngIA2*m_lngSeed2 ) % lngIM2 without overflows + // by Schrage's method + k = m_lngSeed2 / sQ2; + m_lngSeed2 = sA2 * ( m_lngSeed2 - k*sQ2 ) - k*sR2; + if ( m_lngSeed2 < 0 ) + { + m_lngSeed2 += sMod2; + } + + j = m_lngShufflePos / sDiv; + m_lngShufflePos = m_ShuffleArray[j] - m_lngSeed2; + m_ShuffleArray[j] = m_lngSeed1; + + if ( m_lngShufflePos < 1 ) + { + m_lngShufflePos += sMM1; + } +} + +void +KRandomSequence::modulate(int i) +{ + m_lngSeed2 -= i; + if ( m_lngSeed2 < 0 ) + { + m_lngShufflePos += sMod2; + } + Draw(); + m_lngSeed1 -= i; + if ( m_lngSeed1 < 0 ) + { + m_lngSeed1 += sMod1; + } + Draw(); +} + +double +KRandomSequence::getDouble() +{ + static const double finalAmp = 1.0 / double( sMod1 ); + static const double epsilon = 1.2E-7; + static const double maxRand = 1.0 - epsilon; + double temp; + Draw(); + // Return a value that is not one of the endpoints + if ( ( temp = finalAmp * m_lngShufflePos ) > maxRand ) + { + // We don't want to return 1.0 + return maxRand; + } + else + { + return temp; + } +} + +unsigned long +KRandomSequence::getLong(unsigned long max) +{ + Draw(); + + return max ? (((unsigned long) m_lngShufflePos) % max) : 0; +} + +bool +KRandomSequence::getBool() +{ + Draw(); + + return (((unsigned long) m_lngShufflePos) & 1); +} + +class KRandomSequenceList : public QGList +{ + friend class KRandomSequence; +public: + KRandomSequenceList() : QGList() { } + virtual void deleteItem( QCollection::Item ) {} +}; + +void +KRandomSequence::randomize(QGList *_list) +{ + KRandomSequenceList *list = (KRandomSequenceList *)_list; + KRandomSequenceList l; + while(list->count()) + l.append(list->takeFirst()); + + list->append(l.takeFirst()); // Start with 1 + while(l.count()) + list->insertAt(getLong(list->count()+1), l.takeFirst()); +} diff --git a/noncore/games/zsame/dropin/krandomsequence.h b/noncore/games/zsame/dropin/krandomsequence.h new file mode 100644 index 0000000..402e106 --- a/dev/null +++ b/noncore/games/zsame/dropin/krandomsequence.h @@ -0,0 +1,143 @@ +/* This file is part of the KDE libraries + Copyright (c) 1999 Sean Harmer <sh@astro.keele.ac.uk> + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License version 2 as published by the Free Software Foundation. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public License + along with this library; see the file COPYING.LIB. If not, write to + the Free Software Foundation, Inc., 59 Temple Place - Suite 330, + Boston, MA 02111-1307, USA. +*/ +#ifndef K_RANDOM_SEQUENCE_H +#define K_RANDOM_SEQUENCE_H + +class KRandomSequencePrivate; +class QGList; +/** + * A class to create a pseudo-random sequence + * + * Given a seed number, this class will produce a sequence of + * pseudo-random numbers. This would typically be used in + * applications like games. + * + * In general, you should instantiate a KRandomSequence object and + * pass along your seed number in the constructor. From then on, + * simply call getDouble or getLong to obtain the next + * number in the sequence. + * + * @author Sean Harmer <sh@astro.keele.ac.uk> + */ +class KRandomSequence +{ +public: + /** + * Creates a pseudo-random sequence based on the seed lngSeed. + * + * A Pseudo-random sequence is different for each seed but can be + * reproduced by starting the sequence with the same seed. + * + * If you need a single value which needs to be unpredictable, + * you need to use kapp->random() instead. + * + * @param lngSeed Seed to initialize the sequence with. + * If lngSeed is 0, the sequence is initialized with a value from + * KApplication::random(). + */ + KRandomSequence( long lngSeed = 0 ); + + /** + * Standard destructor + */ + virtual ~KRandomSequence(); + + /** + * Copy constructor + */ + KRandomSequence(const KRandomSequence &a); + + /** + * Assignment + */ + KRandomSequence &operator=(const KRandomSequence &a); + + /** + * Restart the sequence based on lngSeed. + * @param lngSeed Seed to initialize the sequence with. + * If lngSeed is 0, the sequence is initialized with a value from + * KApplication::random(). + */ + void setSeed( long lngSeed = 1 ); + + /** + * Get the next number from the pseudo-random sequence. + * + * @return a pseudo-random double value between [0,1[ + */ + double getDouble(); + + /** + * Get the next number from the pseudo-random sequence. + * + * @return a pseudo-random integer value between [0, max[ + * with 0 <= max < 1.000.000 + */ + unsigned long getLong(unsigned long max); + + /** + * Get a boolean from the pseudo-random sequence. + * + * @return a boolean which is either true or false + */ + bool getBool(); + + /** + * Put a list in random order. + * + * @param list the list whose order will be modified + */ + void randomize(QGList *list); + + /** + * Modulate the random sequence. + * + * If S(i) is the sequence of numbers that will follow + * given the current state after calling modulate(i), + * then S(i) != S(j) for i != j and + * S(i) == S(j) for i == j. + * + * This can be useful in game situation where "undo" restores + * the state of the random sequence. If the game modulates the + * random sequence with the move chosen by the player, the + * random sequence will be identical whenever the player "redo"-s + * his or hers original move, but different when the player + * chooses another move. + * + * With this scenario "undo" can no longer be used to repeat a + * certain move over and over again until the computer reacts + * with a favorable response or to predict the response for a + * certain move based on the response to another move. + * @param i the sequence identified + */ + void modulate(int i); + +private: + void Draw(); // Generate the random number + long m_lngSeed1; + long m_lngSeed2; + long m_lngShufflePos; + + static const int m_nShuffleTableSize; + long *m_ShuffleArray; + + KRandomSequencePrivate *d; +}; + +#endif + |