Resource centre for ZX Spectrum games
using Manic Miner and Jet Set Willy game engines
Archive of the
Manic Miner & Jet Set Willy Yahoo! Group
messages
|
|
|
|
|
Message: 2821
Author: andrewbroad
Date: 27/04/2002
Subject: Re: Abstract JSW rooms / Psuedo-random JSW designer
A (non-trivial) pseudo-random room-generator would have to be
semi-automatic, i.e. it would require human post-editing.
Unfortunately the problem of deciding whether a given MM/JSW room is
possible to pass is NP-complete, i.e. it would require exponential
time to compute. On any given time-frame, there are six possible
moves: do nothing, walk left, walk right, jump, jump left, jump right.
So in two time-frames there are 6^2 = 36 possible moves, in three
time-frames there are 6^3 = 216, and so on.
It would take very strong heuristics to overcome such combinatorial
explosion without loss of soundness (if the algorithm says it's
possible to pass this room then it really is possible) and
completeness (if the room is possible to pass then the algorithm
says so). And yet it's amazing how a human expert can just look at a
room and decide in seconds whether it is possible to pass!
I was thinking about this the other day in the concept of an automatic
route-planner for JSW, which would tell you how to reach a given
target room from the start room. But this problem subsumes the
"possible-to-pass-room" problem - a naïve algorithm that only
considers connectivity might suggest, say, going up from "The
Bathroom" to reach "Emergency Generator"! ;-)
But it is an interesting idea to poke random bytes into a room and
massage the resulting chaos into order. I tried it once and came up
with a tunnel-like room, but I didn't save it. I'm sure the technique
promises much more interesting rooms when you hit upon the right
functions...
--
Andrew Broad
http://www.cs.man.ac.uk/~broada/
http://www.cs.man.ac.uk/~broada/spectrum/
http://www.cs.man.ac.uk/~broada/spectrum/willy/
filsoft_2000 wrote:
>
> Reading about Radiohead's abstract lyrics and the challenge of shoe-
> horning the atmosphere of the songs into a JSW room reminded me of a
> project I started a year or three ago.
>
> It was a random JSW room designer and IIRC I got to the stage where
> on paper and in my head I had a program (mainly in BASIC) which was
> able to create fairly basic JSW games with psuedo-random JSW rooms,
> titles (from a bank of words/dictionary), item placements (it was
> difficult conjuring up a routine which could make almost all of the
> items collectable), etc.
>
> I never progressed to coding any of it bar a small test to see how
> random rooms would look (as you might expect, a complete mess), so I
> then progressed onto pseudo- (rule-led) random rooms.
>
> I don't know if I shall ever attempt to code this program, as my
> desire to play around with JSW has waned over the last two years
> (I've done half-an-hour's worth of editing in that time). I still
> play other people's games, though! :-)
>
> Imagine trying to cover for every eventuality of quirky features!
>
> Phil
|
|
|