HDTenEightyP/NetNews huggingface dataset:
From: roberts@angelo.amd.com (Dave Roberts)
Subject: Re: Card Shuffling
Organization: Advanced Micro Devices, Santa Clara, CA
Date: Fri, 13 Nov 1992 18:51:12 GMT

In article <BxM16o.2n@immd4.informatik.uni-erlangen.de> hrjoist@immd4.informatik.uni-erlangen.de (Holger Joist) writes:
>I think a better way is:
>
>/* initialize */
>for (i = 0; i < DECKSIZE; i++)
>	deck[i] = i;
>
>/* choose one element randomly,       */
>/* exchange it with the last element, */
>/* repeat with the rest of the deck   */
>
>for (i = DECKSIZE - 1; i >= 0; i--)
>{
>	rnd = random(i + 1);
>	x = deck[i];
>	deck[i] = deck[rnd];
>	deck[rnd] = x;
>}
>
>
>Using that  method  you  get  a  perfect  permutation.  And  this
>alorithm  works  for  every  DECKSIZE  (Asuming  random() is good
>enough) in only DECKSIZE loops.

Another advantage of this algorithm that was pointed out to me is that
it can be run incrementally.  You can do this everytime you "deal" a
card.  This greatly decreases the amount of shuffling time when you
don't deal out the whole deck (poker, blackjack, etc.).

For instance:

static pos;

int shuffle()
{
	int x;

	if (pos < 0)
		return -1;  /* meaning we reached the end */
	rnd = random_0_to_n(pos);
	x = deck[pos];
	deck[pos] = deck[rnd];
	deck[rnd] = x;
	pos--;
}

You get the idea.

Dave Roberts
Advanced Micro Devices, Inc.
Network Products Division
david.roberts@amd.com
Newsgroups: rec.games.programmer
From: fxmlk@acad3.alaska.edu (KIENENBERGER MIKE L)
Subject: Re: deas for data exchange for modem games?
News-Software: VAX/VMS VNEWS 1.41.UAC
Organization: University of Alaska - Fairbanks
Distribution: na
Date: Fri, 6 Nov 1992 16:09:00 GMT

In article <Bx2su8.DoD@rahul.net>, wilsont@rahul.net (Timothy Wilson) writes...
>At any rate, i'm trying to figure out what types of data i should be
>sending across to the other players ( internet connection sockets and servers
>with 2400bps modems to home computers)
> 
>any other ideas on other aspects of modem gaming are greatly appreciated.
>Timothy Wilson <wilsont@rahul.net>

The key to networked games is to keep the information passed small.
Expecially for modem games.  Computations are normally cheap compared to
passing information across a network.  Information over a network is not
necessarily reliable either, and if it is, it just adds a further speed
slowdown. 

Obviously, one of the best ways to handle network traffic is to encode the
data before sending it:
first byte - constant describing the information packet.
further bytes - specifics of that packet.
=============================================================================
-Mike Kienenberger                       FXMLK@ALASKA           (BITNet)
 Academic Computing                      FXMLK@acad3.alaska.edu (Internet)
 University of Alaska-Fairbanks
 "I'm a computer programmer....<link><link><kludge><kludge> say-no-more!"
From: Neal.Sanche@ttlg.UUCP (Neal Sanche)
Sender: postmaster@ttlg.UUCP
Newsgroups: rec.games.programmer
Subject: Orbit Simulation Code
Date: 10 Nov 92  00:00:12 mst

Hi All,

I am looking for code in C which does Orbit simulations. I have
recently undergone a task to create one but have had troubles
implementing the calculations because the numbers cause roundoff
errors! Has anyone done this?

Please reply via neal@manning.cs.ualberta.ca.

Thanks!

-Neal
___
 X OLX 2.1 TD X Do radioactive cats have 18 half-lives?

 * Origin: Paradigm BBS: A programmer's paradise. (42:100/11)
From: oreillym@tartarus.uwa.edu.au (Michael O'Reilly)
Newsgroups: rec.games.programmer
Subject: Re: Advice needed for fastest sort algorthm
Date: 12 Nov 1992 12:21:08 +0800
Organization: Home
NNTP-Posting-Host: tartarus.uwa.edu.au
X-Newsreader: TIN [version 1.1 PL6]

Warwick Allison (warwick@cs.uq.oz.au) wrote:
: >A radix sort has a time complexity of O(N), which means that it
: >operates in linear time on N units of data.
: Gee, I'm sure the theoreticians would LOVE to see the algorithm,
: since it has been PROVED long ago that sorting takes O(N log N)
: time OPTIMALLY.

Maybe you should go back and check this. If the theorem exists at all,
it will only apply for a (very small) sub-class of possible
algorithms. The radix sort DOES run in N. While the radix sort is a
fairly restricted sort, you can (fairly easily) construct an alogrithm
that will beat N log N in the limit. (look up Knuth on the subject. He
has more than a few words to say about it).

On a parallel machine, I can sort N numbers in log N time.
 
: >This integer may then be
: >represented as the path in a binary tree, with the higher order
: >bits represented as paths near the root and the lower order bits as
: >paths near the leaves.
: Guess what?  The number of bits will be of the order LOG N !!!!!!

No it won't. The running time of the algorithm is N * M, where N is
the number of items of data, and M is the radix width.

1/2 a seconds thought will reveal to you that M is a constant, and
thus the running time is.... O(n).
 
: Let's rename this group to rec.games.!programmer, and succumb to the
: community's belief that "games programmers" aren't real programmers
: at all.  All the Windows programmers and DOS device driver programmers
: can then cross there arms smugly and shake their heads at us non-
: programmers, who can only write GAMES, saying "gee, they've discovered
: SORTING"...

Looks like you haven't quite got the hang of it all yet... ;) Just
FYI, sorting is still considered a rather hotly researched subject. 
 

: Warwick
From: blaisdel@ucrengr.ucr.edu (james blaisdell)
Newsgroups: rec.games.programmer
Subject: speedup PutBlock
Date: 6 Nov 92 06:32:56 GMT
Distribution: usa
Organization: University of California, Riverside

somebody writes:
JA>void PutBlock( int x, int y, int height, int width, char far * buffer )
add to arg list: unsigned far *table
table will point to a table of multiples of 320.  ex. 0,320,640,960,...
  >{   _asm {
  >        push    di
  >        push    si
  >        push    es
  >        push    ds
  >        mov     ax, 320                 <<<-- change this to mov bx, y
  >        mul     y       ; AX = y * 320  <<<-- and this to add bx, bx
	then set ds, si for the table lookup by:  lds si, table

        then load ax with screen addr by          mov ax, ds:[si+bx]
  >        add     ax, x   ;             + x
  >        mov     di, ax  ; ES:DI = destination of pixels
  >        mov     ax, 0A000h
  >        mov     es, ax  ; Segment of VGA memory
            .....
by making these changes you'll probably be saving at least 70 clock cycles,
the table can also be used for get_dot, or plot_dot any other graphics 
routine that addresses the screen.
From: sl8nl@cc.usu.edu
Newsgroups: rec.games.programmer
Subject: Re: Xmode Scrolling
Date: 10 Nov 92 15:22:44 MDT
Organization: Utah State University

>   What I am wondering is how games do scrolling (smooth) with a static 
> piece any other place on the screen, such as on the left.
>   
>   I have seen it done on Jill of the Jungle.  The left side of the screen
> is kept static while the rest scrolls very smoothly.  Is this done through
> hardware, or is the entire screen scrolling and the left side being
> redrawn every frame (I hope not because this would seem VERY slow...).

Jill of the Jungle is done by double buffering, that is, the pages are flipped
between 1 and 2 to achieve the effect.  There is no such thing as a static
window to scroll in using the IBM Graphics cards.  This technique exists on the
Amiga, though.

All Tim Sweeney did was replot the whole map each time (the current view). 
That's all there was to it.

Joshua Jensen

BTW, be watching for Epic MegaGames new releases!

Newsgroups: rec.games.programmer
From: jholdern@casper.cs.uct.ac.za (J E Holderness)
Subject: Re: speedup PutBlock
Organization: Computer Science Department, University of Cape Town
Date: Tue, 10 Nov 1992 09:17:27 GMT

In <23707@galaxy.ucr.edu> blaisdel@ucrengr.ucr.edu (james blaisdell) writes:

>  >        mov     ax, 320                 <<<-- change this to mov bx, y
>  >        mul     y       ; AX = y * 320  <<<-- and this to add bx, bx
>	then set ds, si for the table lookup by:  lds si, table

>        then load ax with screen addr by          mov ax, ds:[si+bx]

The way I usually do these things is:

    mov    ah, y
    sub    al, al
    mov    bx, ax
    shr    bx, 1
    shr    bx, 1
    add    ax, bx

I remember comparing that with the table method, and this was faster,
although I may be wrong. It probably also depends on what machine you're
using.

- James
From: dmb@case.ai.mit.edu (David Baggett)
Newsgroups: rec.games.programmer
Subject: Re: Help building a game?
Date: 13 Nov 1992 21:19:18 GMT
Organization: MIT Artificial Intelligence Laboratory
Distribution: usa
NNTP-Posting-Host: case.ai.mit.edu

In article <1992Nov12.183048.1308@schunix.uucp> sonix@schunix.uucp (Duane Morin) writes:
>Often at work the senior engineer and myself discuss AI and such topics as
>computer game strategy.  He proposed a game that he suggests I attempt to 
>code an "optimal" strategy for.
>
>The game:  [Description of Dots-and-Boxes]

Before investing any more time working on this on your own (or getting,
for example, advice on academic topics like game playing and sorting
from this newsgroup :), find a copy of the following book:

Berlekamp, Elwyn R., John H. Conway, and Richard K. Guy.  _Winning
Ways_ Volume 2, London: Academic Press, 1982.

Chapter 16 is entirely devoted to the game you describe, and contains
more than you could ever possibly want to know on related strategy.
(Needless to say, you have tackled a decidedly nontrivial problem.)
Both volumes of _Winning Ways_ are brilliant and fun -- must-reads for
anyone interested in game theory.

Volume 2 also contains a proof-by-construction that Conway's Game of
Life is Turing-equivalent.  Neat!

Dave Baggett
--
dmb@ai.mit.edu           MIT Artificial Intelligence Laboratory                  
ADVENTIONS: interactive fiction (text adventures) for the 90's!
dmb@ai.mit.edu *** Compu$erve: 76440,2671 *** GEnie: ADVENTIONS
Newsgroups: rec.games.programmer
From: mucds@uxa.ecn.bgu.edu (Corey D. Stinson)
Subject: Buffer-> VGA Video Mem (again!)
Organization: Educational Computing Network
Date: Tue, 10 Nov 1992 20:00:45 GMT

   I have posted this question in several different forms, unfortunely
my question was rather complicated or unclear as I never got any
answers which worked.  I posted some code I had written and received
many helpful replies on a gramattical error I made but everyone seemed
to overlook the question at hand.  I have two simple problems.

  I need to assign a pointer to the beginning of VGA (Mode 13h) video
memory.  Then, I need two know how to correctly increment this
pointer through the 0 - 64000 offset range of the VGA video buffer.
I assume that the pointer will have to be of type char since I am
loading byte-by-byte into video memory.  Please respond via email
with any suggestions.  Thanx *much* in advance for any help!
Newsgroups: rec.games.programmer
From: mcginle@obelix.gaul.csd.uwo.ca (JAMES MCGINLEY)
Subject: Redefining Characters in Text Mode
Reply-To: mcginle@obelix.gaul.csd.uwo.ca (JAMES MCGINLEY)
Organization: CS Dept, University of Western Ontario, Canada
Date: Wed, 11 Nov 1992 02:43:29 GMT

I need any information on how to redefine the IBM ASCII character set 
*WITHOUT* going into graphics mode. I know it involves interupts
and can be done without having to redefine the ENTIRE character set.
i.e. I would like to keep the alphabet and numbers but want to make
      all the other characters into happy faces, trees, etc.

Can it be done?
I tried to do it on my IBM which uses MCGA graphics and I have a sneaking
suspicion that if it can be done it can only be done on VGA cards or higher.
I *HAD* an example of how to do this but it didn't work and now I've lost it.
If someone could post or email me the exact C code on how to do it (I'm  using
Borland's Turbo C) I would be most appreciative.

Essentially, I don't need smooth flowing graphics in my game and would like to
take advantage of the speed of printing out characters in text mode.
i.e. I could have three hundred happy faces flying around without much slowdown
      or problems determining wether they were hit.

THANKS A MILLION. This info would help me a lot. Please reply
if you know of any way to do it on ANY card. I am stuck!

P.S. The example I used accessed registers and was supposed to redefine the letter 'a' only.
         It didn't - (AND IT CAME STRAIGHT FROM BORLAND TOO!)
Newsgroups: rec.games.programmer
From: roberts@angelo.amd.com (Dave Roberts)
Subject: Re: Advice needed for fastest sort algorthm
Organization: Advanced Micro Devices, Santa Clara, CA
Date: Wed, 11 Nov 1992 18:42:47 GMT

In article <BxIwoJ.Hr7@news.cso.uiuc.edu> jas37876@uxa.cso.uiuc.edu (John A. Slagel) writes:
>
>   John Slagel (Me!) writes:
>
>>>>   Definately the quick sort.  Its even built into ANSI C specs, so it
>>>>   should be easy to implement.  Look up quicksort in your C manual. If
>>>>   I remember right, bubble sort works in O(n*n) and quicksort works in
>>>>   O(n*log n).
>>>>
>>>>   In other words, if you're sorting n objects, QuickSort takes "on the Order
>>>>   of" n*log n steps, while bubble sort takes "on the order of" n*n steps.
>>>>
>
>   Dave Roberts chokes at my stupidy:
> 
>>Ack!!! People, remember that bubble sort has a *worst* case time of
>>n!.  It can be quite fast if most things are sorted.
>
>>Dave Roberts
>>Advanced Micro Devices, Inc.
>>Network Products Division
>>david.roberts@amd.com
>
>   Ack!!! Me, John Slagel, who is a soon-to-be-interviewing senior
>   in C.S., gives up all hopes of getting a job with AMD :-)

Of course, I screwed up in writing that the worst case was n!, and not
n*n.  The second poster wrote that and I blindly repeated it without
thinking (USENET is terrible when used without discrimination).

Anyway, my point was that it's worst case behavior (which is n*n as
many, and John, pointed out) differs from its degenerate cases, which
can be O(n) if the data is sorted or nearly sorted.

My post was a knee jerk response that bubble sort is bad.  It's not.
Used wisely and carefully chosen, it's a beautiful thing.  I just hate
it when people automatically think that quicksort is the be-all
end-all sort of the millenium.

You can now safely interview since you correctly recalled that bubble
is n*n. :-)

Dave Roberts
david.roberts@amd.com
From: oreillym@tartarus.uwa.edu.au (Michael O'Reilly)
Newsgroups: rec.games.programmer
Subject: Re: Advice needed for fastest sort algorthm
Date: 13 Nov 1992 12:37:29 +0800
Organization: Home
NNTP-Posting-Host: tartarus.uwa.edu.au
X-Newsreader: TIN [version 1.1 PL6]

Warwick Allison (warwick@cs.uq.oz.au) wrote:
: foo@netcom.com (Mark Hall) writes:
: >warwick@cs.uq.oz.au writes:
: 
: >   O(n logn) is optimal for arbitrary things. In some special cases,
: >you can do better. Radix sort fits one of these special cases.
: >)Guess what?  The number of bits will be of the order LOG N !!!!!!
: >   Number of bits will be log P where P is the largest integer. 
: >That doesn't have to have much to do with the number of items.
: >(hint: sort the government debt of the top 15 debtor nations, 
: >values expressed in lire. What is N? What is P?)
: 
: You're fighting against yourself here.  P will be GREATER than N, but
: once passed through an appropriate O(1) hashing function, the number
: of bits will still be of the order LOG N.  ie. O(log2 15), ie. 4, ie.
: you need a neato hashing function that maps those debts to unique,
: order preserving values in the range 0..15.

Nope. You are loseing it a little here. If you have 5,000,000 items of
32 bit data, it will take 32 passes over the 5,000,000 items for a
running time that is  ~5,000,000 * 32. If you take 1,000 item, it will
run in 1,000 * 32. I.e. looking very crefully you notice that it is...
	32 * N.
which is
	O(n).

: See?
Nope.
 
: Point is, Radix sort ONLY WORKS when there the number of distinct (unique)
: values in the unsorted data is less than O(log N).  If your data has
: that characteristic, go ahead and use Radix sort.  Such data is rare,
: however.  BUT, Radix sort can be very cheaply implemented on computers,
: reducing the constant - that's the real reason it is faster in some
: cases.

Radix sort works where the data can be reduce to a fixed length
bitstring. That data is very common. Any list of number can be sorted
useing radix sort.

A list of VARIABLE length strings on the other hand, couldn't be
sorted, as the concept of a LSB doesn't make sense.

In general, any data that has a well defined most-significant-bit, and
a well defined least-significant-bit can be sort in place in O(n) time.
 
: Warwick
Newsgroups: rec.games.programmer
From: colin.buckley@rose.com (colin buckley)
Subject: Animator .FLI files
Organization: Rose Media Inc, Toronto, Ontario.
Date: Mon, 9 Nov 1992 04:38:03 GMT
X-Gated-By: Usenet <==> RoseMail Gateway (v1.70)


Date Entered: 11-08-92 23:31
MI>Where can i find info about the data format of .FLI files?

Dancing Flame (AA Authors) has released a library called FLILIBx.ZIP, I have
version 3 and it includes source to a player and a doc file describing every
file format used by AA.  I was only interested in the doc file myself, as
I use DPIIE to design all my graphics/sprites, load them into AA, get
each cell in line so they animate smoothly, then I convert the FLI to my
own format.  No need for a Sprite Maker and I only had to convert the FLI.
I could have saved each frame as a cell with AA and made the conversion
to my own format easier, but saving all those frames was too much trouble
during conversion.

Anyways, look for FLILIB, I have seen someone post the FLI part in another
newsgroup so ask in a graphics newsgroup.  If you can't find it, I'll post
the FLI part only, but I'm sure you want the entire file.

I don't have FTP access and am forbidden from UUencoding files in messages,
so please don't ask.
.----------------------------------------------------.
| Colin Buckley -- 486 Powered (Packing Extra Socks) |
| Toronto, Ontario, Canada                           |
| InterNet: colin.buckley@rose.com                   |
|                                                    |
| So Eager to Play, So Relunctant to Admit it...     |
`----------------------------------------------------'
---
   RM 2.00 : RoseNet<=>Usenet Gateway : Rose Media 416-733-2285
From: dmatiske@nd.edu (DAvid matiskella)
Newsgroups: rec.games.programmer
Subject: Re: Software Pinball Machine
Date: 5 Nov 92 22:52:38 GMT
Followup-To: rec.games.programmer
Organization: University of Notre Dame

In article <1992Nov5.202313.7178@nntp.hut.fi>, jmunkki@vipunen.hut.fi (Juri
Munkki) wrote:
> 
> In article <1992Nov6.034457.11981@waikato.ac.nz> gford@waikato.ac.nz writes:
> >The ball is moving on a sloping table, (slope in y direction). The x component
> >of the velocity remains constant. And the y component  vy(t) = vy(t-1) + a
> >where a is a fraction of gravitational acceleration. 
> 
> I don't think that you can really realistically model a pinball without
> taking ball spin into account. Writing a less than perfect pinball program
> isn't hard, but making the collisions affect the ball spin can make things
> complicated.
> 
> -- 
>   Juri Munkki					       Windsurf: fast sailing
>  jmunkki@hut.fi					      Macintosh: fast software
	It shouldn't be that hard to create a pinball program. Just look in a any
physics book for the equations for consevation of momentum and the like. I
am not sure if you would have 
to take into account the friction of the ball on the surface or whether or
not it is neglible. The tough part should be figuring out how much energy
to add after hitting the ball with a flipper and the like. The way I would
set it up would to store to track the ball's energy and how direction and
moment. each "time" through you add the gravity and check to see if it
hit anything.
From: cs90mdh@cen.ex.ac.uk
Newsgroups: rec.games.programmer
Subject: Visual lib
Date: 7 Nov 92 15:32:15 GMT
Organization: University of Exeter, UK.


For those interested, the "Visual Lib" library provides routines for handling
3D wire frame graphics for Windows in Borland C++ V3. It is shareware, and
costs $50 to register.

The library includes code for double buffering the display, and I think also
handles shading and hidden line removal.

I downloaded the library from 'lancs.pdsoft' in the UK, so I am not sure if it
is in the US 'monster' archives like wuarchive.wustl.edu. I can mail anyone
a copy if they are interested.

		Mark.H.
Newsgroups: rec.games.programmer
From: cat@wixer.cactus.org (Dr. Cat)
Subject: Re: Help building a game?
Organization: Real/Time Communications
Distribution: usa
Date: Fri, 13 Nov 92 10:28:50 GMT


Generally, in the game of boxes, there are a certain number of moves that
don't create a 3, which the players can safely take turns making until one of
them is forced to make a 3 that the other player can score points from.  If
there's an odd number of these at the beginning of your turn, you're in good
shape - an even number, and you're not.  But some of these moves will render
some of the other previously safe moves unsafe.  You could have your program
take a move that renders an odd number of other moves unsafe if it detects an
even number of safe moves remaining, and preserve the status quo otherwise.
Also, when forced to give away boxes, you should analyze all the moves to
find the one that gives the opponent the least number of scorable boxes,
which shouldn't be too hard to figure out.
Newsgroups: rec.games.programmer
Subject: Quicksort/quicksort()
X-CitNet-ID: 32545
Date: Sun, 08 Nov 92 20:15:20 GMT

 
 Regarding sort algorithms, you may or may not want to use the ansi 
quicksort() function. ANSI standards mandate the function's presence, but do 
very little to define it's implementation. I know of a couple compilers 
which implement a bubble sort as quicksort()... If you don't have the RTL 
source for your compiler (so you could check) you might want to find another 
Quick Sort routine and test that for speed against your compiler's...