HDTenEightyP/NetNews huggingface dataset:
From: oreillym@tartarus.uwa.edu.au (Michael O'Reilly)
Newsgroups: rec.games.programmer
Subject: Re: Advice needed for fastest sort algorthm
Date: 8 Nov 1992 22:01:26 +0800
Organization: Home
NNTP-Posting-Host: tartarus.uwa.edu.au
X-Newsreader: TIN [version 1.1 PL6]

John A. Slagel (jas37876@uxa.cso.uiuc.edu) wrote:
: kds@phy.duke.edu (Stokes Kevin) writes:
: 
: 
: >  This new project has objects much closer to the observer, and I fear
: >there may be significant changes in the list order between every sort.
: >Which sorting algorthm is the most time efficient?
: 
:    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).

Wait a bit..
Quicksort is nothing like the best. It has an AVERAGE running time of
N log N,  but the worst case is n^2. The worst case occurs when the
data is already sorted.... Nearly sorted data does very badly. On top
of this, the quicksort is difficult to implement efficently.

If you want a real FAST sort, implement a merge sort, or a radix sort
(radix is O(n), but it is only useful for small numbers). Merge has a
worst case of N log N, but needs more memory than a quicksort. On the
up side, it can be made very fast.
 
:   John A. Slagel, email: jas37876@uxa.cso.uiuc.edu
Michael
Newsgroups: rec.games.programmer
From: vputz@nyx.cs.du.edu (Victor Putz)
Subject: Re: Software Pinball Machine
Organization: University of Denver, Dept. of Math & Comp. Sci.
Date: Thu, 5 Nov 92 15:59:47 GMT



Yes, the software was "Bill Budge's Pinball Construction Set" or some
such.  it was a very capable piece of software (even on the apple II), and
I haven't seen anything that could compare to it in a while.

-->Vputz

Newsgroups: rec.games.programmer
From: sigma@picasso.ipl.rpi.edu (Kevin Martin)
Subject: Re: Software Pinball Machine
Date: Sun, 8 Nov 1992 01:02:16 GMT

jmunkki@vipunen.hut.fi (Juri Munkki) writes:
>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.

I agree.  As far as I've been able to tell, the commercial game Tristan for
the IBM and Mac does not take spin into account, and the game suffers
greatly for it.  Feels very unnatural, and once you get used to it, you
find your real-world pinball scores dropping for a coupla days.

A simulator should also allow for a variety of nudges, not the generic
nudge which is in Tristan.  Anyone remember the pinball for Vectrex?  That
was pretty good, actually - it even allowed glassies, although it was sort
of just that the ball could accidentally go through things.

-- 
Kevin Martin
sigma@ipl.rpi.edu
"I told you I'd shoot, but you didn't believe me! WHY didn't you BELIEVE me?!"
Newsgroups: rec.games.programmer
From: mike@sabrina.dei.unipd.it (Lorenzo Micheletto 260777/IL)
Subject: Animator .FLI files format
Organization: D.E.I. Universita' di Padova, Italia
Date: Fri, 6 Nov 1992 12:53:51 GMT

Hi! I'm working on a set of super-fast routines for 320x200 mode-X
and i'd like to include a playback routine for Autodesk Animator files.

Where can i find info about the data format of .FLI files?

Thanks in advance.
			Lorenzo Micheletto

Newsgroups: rec.games.programmer
From: ttobler@unislc.uucp (Trent Tobler)
Subject: Re: Card Shuffling
X-Newsreader: Tin 1.1 PL5
Organization: Unisys Corporation SLC
Date: Mon, 9 Nov 1992 22:31:25 GMT

U. N. derGrad (u519876@csi.UOttawa.CA) wrote:
: Hi there,
: 
: I'm looking for a quick and simple algorithm for shuffling a normal
: deck of cards.  A joker or two could also be added to the deck (I'm 
: making a poker game).
: 
: Any suggestions?  Programming language is C, on a Unix station.
: 
: Much appreciated,

make a single pass through the array of cards, and swap each card with another
card chosen at random:  ie:

	for i = 1 to NUM_CARDS
		r = random number between 1 and NUM_CARDS
		swap card[i] and card[r]
	end for

As long as the random generator is reasonably random, this will shuffle the
deck.

--
  Trent Tobler - ttobler@unislc.slc.unisys.com
Newsgroups: rec.games.programmer
From: jas37876@uxa.cso.uiuc.edu (John A. Slagel)
Subject: Re: More on loading into vga video mem!
Organization: University of Illinois at Urbana
Date: Fri, 6 Nov 1992 18:27:40 GMT

mucds@uxa.ecn.bgu.edu (Corey D. Stinson) writes:

> 

>     Someone posted that one correct method might be:
>         (unsigned char far*)VideoMem = 0xA00000000L;
                                         0xA0000000L;

       This should be a 32-bit far pointer.  Segment=A000, Offset=0000,
       which combined make 0xA0000000L (7 zeros, not 8!)

>     This doesn't seem to work at all.  Could someone provide
>     some advice?  Thanx

-- 
------------------------------------------------------------------------
  John A. Slagel, email: jas37876@uxa.cso.uiuc.edu
From: huw@siesoft.co.uk (Huw Roberts)
Newsgroups: rec.games.programmer
Subject: Re: Card Shuffling
Date: 11 Nov 92 17:00:46 GMT
Organization: Siemens Nixdorf Information Systems Ltd.
X-Newsreader: Tin 1.1 PL4

u519876@csi.UOttawa.CA (U. N. derGrad) writes:
: Hi there,
: 
: I'm looking for a quick and simple algorithm for shuffling a normal
: deck of cards.  A joker or two could also be added to the deck (I'm 
: making a poker game).
: 
: Any suggestions?  Programming language is C, on a Unix station.
: 
: Much appreciated,
: 
HeroSoftware@cup.portal.com (Bits of Magic) writes
: 
: A quick and dirty way is:
: 
: 	[quick and dirty way deleted]
: 
: Basically it's just:
: 	swap two randomly selected cards in the deck
: 	repeat as needed

This is THE WORST way to randomise a deck of cards.  Your value for SWAPS
has to be HUGE (over 1000) in order to get any degree of randomness.  
This algorithm does not guarantee that every card is swapped at least once.

ttobler@unislc.uucp (Trent Tobler) writes
: make a single pass through the array of cards, and swap each card with another
: card chosen at random:  ie:
: 
: 	for i = 1 to NUM_CARDS
: 		r = random number between 1 and NUM_CARDS
: 		swap card[i] and card[r]
: 	end for
: 
: As long as the random generator is reasonably random, this will shuffle the
: deck.

This will shuffle the deck but will not give a decent random distribution.
This was discussed recently on one of the bridge groups (or perhaps it was
here.  I don't remember).  It is certainly sufficiently unrandom to seriously 
affect the hands you get in a bridge game.

Try this one (guarantees that each possible ordering is equally likely given
a perfectly random random number generator).

    for (i = NUM_CARDS; i > 0; i--)
	r = random number between 1 and i inclusive
	swap card[i] and card[r] (may be the same card)

Huw
--
Huw Roberts (huw@siesoft.co.uk) Siemens Nixdorf Information Systems Ltd.
+44 344 850982                  Oldbury, Bracknell, Berks. RG12 4FZ England
Newsgroups: rec.games.programmer
From: jew5001@zeus.tamu.edu (WILLIAMSON, JOHN EDWARD)
Subject: Borland C++ 'Nintendo'-type game code wanted
News-Software: VAX/VMS VNEWS 1.41    
Organization: Texas A&M University, Academic Computing Services
Date: Thu, 12 Nov 1992 17:22:00 GMT

I have hooked up my SEGA 3D glasses to my computer and need a better
demo than the simple static images I currently use it for.  I am
scheduled to give a presentation on the SEGA glasses and other 
interface "gimmicks" next month.

I would like to be pointed to several simple, 'Nintendo' type games
with their Borland C++ source code, so that I could quickly
modify them to be 3D (stereoscopic) games.  These need to be 320X200
VGA and the typical scrolling/shooting/jumping game would be prefered.

Any ftp sites would be appreciated.

John
From: goetz@acsu.buffalo.edu (Phil Goetz)
Newsgroups: rec.games.programmer
Subject: Re: ?Parsers
Date: 13 Nov 92 20:05:44 GMT
Organization: State University of New York at Buffalo/Comp Sci

In article <QeyLXsm00WAyQby21s@andrew.cmu.edu> angst+@CMU.EDU (Jon C. Slenk) writes:
>Parsers are usually the let down of adventure games - I mean, even if the
>story line is really interesting, if the parser sucks then the game is
>very frustrating to play. 
>
>Does anyone know of some PD code to do good parsing?
>
>Jon Slenk           angst+@cmu.edu     EVERYTHING is
>Carnegie Mellon     Pittsburgh PA      Disclaimed

Most of the source code to my adventure _Inmate_ is available for anonymous
ftp at ccosun.caltech.edu (login anonymous) in /pub/apple2/8bit/games/inmate.
It is 6502 assembly, written for the S-C Macro Assembler 2.0.
It uses an ATN for parsing.  I don't like ATNs anymore for general parsing,
but for adventure games they are fine.

Please tell me if you find this code interesting; I posted it over a year
ago and to my knowledge no one has ever looked at it.

Phil Goetz
goetz@cs.buffalo.edu
From: oreillym@tartarus.uwa.edu.au (Michael O'Reilly)
Newsgroups: rec.games.programmer
Subject: Re: Advice needed for fastest sort algorthm
Date: 8 Nov 1992 22:14:55 +0800
Organization: Home
NNTP-Posting-Host: tartarus.uwa.edu.au
X-Newsreader: TIN [version 1.1 PL6]

libh@Jane.UH.EDU wrote:
: In article <BxD5pt.DyI@news.cso.uiuc.edu>, jas37876@uxa.cso.uiuc.edu (John A. Slagel) writes:
: >kds@phy.duke.edu (Stokes Kevin) 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.
: >
:   The bubble sort takes N! (# factorial) steps, rather than N*N steps.  A BIG
: difference. 

Good god. What a brilliant piece of work! ;)
Just FYI, it really is N*N. a Q&D proof. In worst case it will move an
item of data D1 one place, and if D1 is at the opposite end of the
list from where it should be it will take N passes.. So it has to
handle N items of data N times --> O(n^2).

: But as pointed out, the quicksort is the easiest to implement
: since it is in C libraries.  Why reinvent the wheel.  If that isn't
: quick

That isn't implementing it, thats useing it.  If the speed of sorting
matters, DON'T use the qsort from the libs. two reasons.
1) It is has a big overhead on comparisons.
2) Q-sort is no where near the best sort to use, and it has an
abominable worst case performace. O(n^2).

: enough then I would check out Knuth's 'Art of Programming' Vol. 3 since it is
: pretty much only about sorting.

Knuth is a good place to look. Pretty much the definative work, but
starting to get a little dated.

Michael
Newsgroups: rec.games.programmer
From: cctr120@cantua.canterbury.ac.nz (Brendon Wyber)
Subject: Re: Text Adventure Languages
Organization: University of Canterbury, Christchurch, New Zealand.
X-Newsreader: TIN [version 1.1 PL6]
Date: Sat, 14 Nov 1992 06:35:10 GMT

Joseph Rivera (jrivera@den.mmc.com) wrote:
> I am interested in writing a text based adventure game and I would like
> some opinions on the different adventure systems (i.e. ADL vs ADVSYS).
> Flexibility and ease of use are my main concerns.

Sadly flexibility and ease of use don't come together in the same package
when it comes to adventure game compilers. 


When it comes to which adventure compiler to use their is only one
answer and that is TADS.

TADS: Clearly the best of the systems available, certainly by far the most 
powerful and is very readable (no recursing brackets or anything like that)
though it shows some C similarities. It costs however, being shareware, but
is worth it.

Read rec.arts.int-fiction and rec.games.int-fiction for information on
this thread.

Be seeing you,

Brendon Wyber                     Computer Services Centre,
b.wyber@csc.canterbury.ac.nz      University of Canterbury, New Zealand.

"Ph-nglui mglw'nafh Cthulhu R'lyeh wgah'nagl fhtagn."
From: censwm@cend3c7.caledonia.hw.ac.uk (Stuart W Munn)
Newsgroups: rec.games.programmer
Subject: XGOLF
Date: 12 Nov 92 14:59:49 GMT
Organization: Department of Computer Science, Heriot-Watt University, Scotland

I am trying to find source for XGOLF the archives, that I have loaded it from are incomplete can any one help?


-- 
=========================================================================
Stuart Munn		DOD# 0717
Heriot-Watt University                  "The sky is BLACK . . .
Edinburgh                                therefore GOD, he is a St Mirren
Scotland, EH14 4AS                       supporter!!!"
031 451-3265
031 451-3261 FAX                        God may have a Harley . . .
E-Mail censwm@UK.AC.HW.CLUST            But the Pope rides a Guzzi! 
=========================================================================
From: foo@netcom.com (Mark Hall)
Newsgroups: rec.games.programmer
Subject: Re: Advice needed for fastest sort algorthm
Date: 11 Nov 92 04:35:26 GMT
Article-I.D.: netcom.1992Nov11.043526.26732
Organization: Netcom - Online Communication Services  (408 241-9760 guest)

In article <10991@uqcspe.cs.uq.oz.au> warwick@cs.uq.oz.au writes:
)>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.

   You are invited to read any decent book on sorting before posting, next 
time.

   O(n logn) is optimal for arbitrary things. In some special cases,
you can do better. Radix sort fits one of these special cases.



)>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 !!!!!!

   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?)

)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"...
   no, "They haven't a CLUE about SORTING" as evidenced by many posts.
Lines: 30
Date: Thu,  5 Nov 92 20:45:54 MST
Newsgroups: rec.games.programmer,comp.lang.pascal
From: KirkA.Baum@ernie.cs.byu.edu (Kirk A. Baum)
Subject: Re: Loading pallete (PAL) files in TP 6.0
Organization: Computer Science Department, BYU

In article <1992Oct31.065024.19845@nevada.edu> tommy@nevada.edu (GREG HJELSTROM) writes:
>From: tommy@nevada.edu (GREG HJELSTROM)
>Subject: Loading pallete (PAL) files in TP 6.0
>Date: Sat, 31 Oct 1992 06:50:24 GMT
>
>Ok, its me again.  I am using Imageprocessor to draw my graphics for a game 
>that I am writing in Turbo Pascal 6.0.  How does one set the pallete to the sa
>using a .PAL file?  
>
>I am using anivga for my sprite routines and it uses the default pallete by
>default :-) while my paint program uses a different pallete.  I would like to 
>be able to load in the .PAL file and initialize the pallete to be the same as
>my paint program....  

There is a new version of ANIVGA (1.1) that has routines and a sprite
editor that save/load/modify the palette.  This version can be found
via FTP from some sites in finland.  I don't recall the site from 
memory but if you can't find it send me some Email.


>
>any advice?
>
>Thanks in advance...
>
>-tommy@redrock.nevada.edu


Kirk A. Baum
kirk@ernie.cs.byu.edu
Newsgroups: rec.games.programmer
From: foo@netcom.com (Mark Hall)
Subject: Re: Advice needed for fastest sort algorthm
Organization: Netcom - Online Communication Services  (408 241-9760 guest) 
Date: Thu, 12 Nov 1992 06:57:32 GMT

In article <11008@uqcspe.cs.uq.oz.au> warwick@cs.uq.oz.au writes:
)foo@netcom.com (Mark Hall) writes: (about radix sort)
)>   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.
)
)See?

   Not really. If you had such a hashing function, it seems you could
sort N arbitrary size integers in O(N) time. 

   You propose a O(1) hash that takes N arbitrary integers of P bits 
each, mapping them to integers of log N bits *preserving the 
order of the original numbers* ? The order is what you are 
trying to find in the first place! 

   If you can find such a hash function, just use it to map the 
original numbers to integers from 1 to N, then print the original
numbers corresponding to 1, 2, 3 etc.  You are done. No need to 
radix sort at that point. 

   I suspect that your O(1) hash function doesn't exist.

   - mark
From: nak@cbnews.cb.att.com (neil.a.kirby)
Newsgroups: rec.games.programmer
Subject: Re: Advice needed for fastest sort algorthm
Date: 12 Nov 92 15:43:08 GMT
Organization: AT&T

In article <1992Nov11.161052.5552@panther.mot.com> asu@panther4.panther.mot.com (Russ Trotter) writes:
>I hate to jump on this seemingly runaway train but.... 
>
>In one of my classes, I remember the teacher saying that it
>had been proven that O(n log n) was the best one could do
>for _comparison_ based sorting...  Is this a more correct assertion?

The Order n log n is itself an approximation of (this is from memory with
out books close at hand) log n!  Check the text for any graduate level
class on algrithms for the derivation.

This raises the possibility of sorts faster than n log n.
Not lots (as such things go) faster, but somewhat faster.

>
>I don't know much (at all :) ) about Radix sort  (only how to spell it :) )
>so I can't be sure if it disproves the statement above.

Knuth has already been quoted here on this one, so I'll defer to the
expert.  In class the order is taught as k * n where k is the number of
radices.

The upper bound on k is log of the number of bits used to represent the
values.  Hence, as k increases, n log n behavior can be seen.


*THE* thing to remeber in all of this is that order notation is applicable
only as n rises.  Bubble sort has a very low overhead, it works well on
semi-sorted data, and most programmers can write it correctly.  That third
point should not be ignored.  Classical quicksort has to be modified to
keep from choking (O n*n )on sorted data.

My advice is: profile your code first, and worry about the slow parts that
profiling finds.


Neil Kirby
Newsgroups: rec.games.programmer
From: neves@aristotle.ils.nwu.edu (David &)
Subject: Re: Advice needed for fastest sort algorthm
Organization: The Institute for the Learning Sciences
X-Newsreader: Tin 1.1 PL5
Date: Fri, 13 Nov 1992 16:23:53 GMT

Tommy Nordgren (f85-tno@nada.kth.se) wrote:
: 	Not only has quicksort bad worst-case performance, but this worst 
: case WILL occur in the considered application, since the list will always be
: nearly sorted after any reasonable wievpoint movement.
There is a simple fix called median-of-three that eliminates this
particular worse case.  The partition is picked from the median of the
first,last, and middle in the set to be sorted.  Thus in already
sorted lists the partition is picked from the middle, which is the
ideal for Quicksort.
--
neves@ils.nwu.edu
Institute for the Learning Sciences, 1890 Maple, Evanston Il 60201
From: al660261@academ01.mty.itesm.mx (Armando Leonardo Franco Carrillo)
Newsgroups: rec.games.programmer
Subject: Request for 'Game of life' algorithm
Date: 10 Nov 92 04:25:40 GMT


	I'm writing this hoping somebody has the rules of 'Game of life',
specially one named 'Daemons'. One of my teacher talked about it in class,
it is supposed to change one cell color with certain rules and considering
the neighbors cells colors. The rules may have something to do with 'Cellular
automata', 'the game of life' or 'Daemons' as I have said. I think is something
about why the zebras and the tigers have that skin patterns. Thanks in advance.
I hope I didn't post to the wrong group.:)

Armando Leonardo Franco Carrillo	al660261.721369540@academ01
Newsgroups: rec.games.programmer
Subject: ?Parsers
From: "Jon C. Slenk" <angst+@CMU.EDU>
Date: Thu,  5 Nov 1992 14:41:44 -0500 
Organization: Robotics Institute, Carnegie Mellon, Pittsburgh, PA

Parsers are usually the let down of adventure games - I mean, even if the
story line is really interesting, if the parser sucks then the game is
very frustrating to play. 

Does anyone know of some PD code to do good parsing?

-Jon.

----------------------------------------------------
Jon Slenk           angst+@cmu.edu     EVERYTHING is
Carnegie Mellon     Pittsburgh PA      Disclaimed
Newsgroups: rec.games.programmer