Copy Link
Add to Bookmark
Report
Doom Editing Digest Vol. 01 Nr. 019
From: owner-doom-editing-digest
To: doom-editing-digest@nvg.unit.no
Subject: doom-editing-digest V1 #19
Reply-To: doom-editing
Errors-To: owner-doom-editing-digest
Precedence: bulk
doom-editing-digest Tuesday, 25 October 1994 Volume 01 : Number 019
Re: What sector is thing #NN in?
Re: What sector is thing #NN in?
Re: What sector is thing #NN in?
Re: What sector is thing #NN in?
Re: What sector is thing #NN in?
Re: What sector is thing #NN in?
Re: What sector is thing #NN in?
Re: (Dis)Appearing parts of a level
Re: What sector is thing #NN in?
DUL/DEL license
cc's
Re: What sector is thing #NN in?
Re: What sector is thing #NN in?
Re: (Dis)Appearing parts of a level
Re: What sector is thing #NN in?
Re: What sector is thing #NN in?
Re: What sector is thing #NN in?
----------------------------------------------------------------------
From: MATTHEW J LEDDINGTON-HILL <n1419587@student.fit.qut.edu.au>
Date: Mon, 24 Oct 1994 15:17:19 +1000 (EST)
Subject: Re: What sector is thing #NN in?
Matt Fell scripsis:
>
> Does anyone have a simple, efficient algorithm to determine what
> sector a given thing is in? Any clues as to how id does it?
>
Does id actually test this? I can see no neccessity in this kind of check:
1. an item does not have to be in a sector; it can be off the map and
you can idclip/spispopd to find it. Such an eventuality does not crash doom.
Indeed spispopding (how's that for a new word?) invariably takes you into
null space..
2. to determine whether an item can be picked up or not would require
simply matching up co-ordinates. If there is no way into a room which
contains an item then the item can simply be never collected. If it is
on say a pillar too high to reach again it will never be gained.
Of course I may be missing something fundamental here... feel free to
vent your spleen on me. After all who am I to question the guru? :)
mlh
*++- _['>_ ---===Matthew Leddington-Hill===--- _<`]_ -++*
|= / \ / \ Flame me... / \ / \ =|
|= | ) ( | ...and I'll frag your ass! | ) ( | =|
*++- |/`W'\| ---=============================--- |/`W'\| -++*
==n1419587@water.qut.edu.au==
------------------------------
From: Mark Alan Lang <Elistan+@cmu.edu>
Date: Mon, 24 Oct 1994 01:56:34 -0400 (EDT)
Subject: Re: What sector is thing #NN in?
MATTHEW J LEDDINGTON-HILL <n1419587@student.fit.qut.edu.au> writes:
> Matt Fell scripsis:
> >
> > Does anyone have a simple, efficient algorithm to determine what
> > sector a given thing is in? Any clues as to how id does it?
> >
>
> Does id actually test this? I can see no neccessity in this kind of check:
>
> 1. an item does not have to be in a sector; it can be off the map and
> you can idclip/spispopd to find it. Such an eventuality does not crash doom.
> Indeed spispopding (how's that for a new word?) invariably takes you into
> null space..
>
Perhaps - elevation and light level?
- ---------------------------------------------------------
| Mark Lang | elistan+@cmu.edu | elistan@metronet.com |
| It's Time! October 24th -- Ask me for details! |
- -http://www.contrib.andrew.cmu.edu/usr/ml5t/elistan.html-
------------------------------
From: Stanley Stasiak <stasiak@iinet.com.au>
Date: Mon, 24 Oct 1994 17:51:26 +0800 (WST)
Subject: Re: What sector is thing #NN in?
>
> Does anyone have a simple, efficient algorithm to determine what
> sector a given thing is in? Any clues as to how id does it?
No. 8)
>
> Pondering briefly, I came up with something like this:
>
> - Go east from the test-thing's coordinates. Whatever linedef you
> cross first, take the sector number from its appropriate sidedef.
> - To discover which linedef is crossed first, use the blockmap to
> simplify intersection calculations. Going block by block, test each
> linedef that is in that block to see if it is the one.
>
> Obvious weaknesses are the fact that the first "intersect" when heading
> east might be at a vertex, which would require much further testing. Also,
> the funky "crystal walls" trick of marking both sidedefs with the same
> sector number could mess things up.
Why not got to the nearest vertex straight off. That way once of the cases
is avoided. Of course finding a nearest vertex is not trivial.
Some sort of intelligent search-n-test algorithm has to be made
for traversing the vertex list to find the closest to the thing cordinates.
Once a vertex is found it can be used as a key for matching linedefs
referencing it... blah blah.... some of which will be the nearest lines...
etc.
Stan.
==============================================================================
.-_!\ | Stanley Stasiak
/ \ | (stasiak@iinet.com.au)
I am here! --->> P_.-._/ <<---- Australia| Perth, Western Australia
==============================================================================
------------------------------
From: Stanley Stasiak <stasiak@iinet.com.au>
Date: Mon, 24 Oct 1994 17:59:31 +0800 (WST)
Subject: Re: What sector is thing #NN in?
>
> Matt Fell scripsis:
> >
> > Does anyone have a simple, efficient algorithm to determine what
> > sector a given thing is in? Any clues as to how id does it?
> >
>
> Does id actually test this? I can see no neccessity in this kind of check:
>
> 1. an item does not have to be in a sector; it can be off the map and
> you can idclip/spispopd to find it. Such an eventuality does not crash doom.
> Indeed spispopding (how's that for a new word?) invariably takes you into
> null space..
What if by mistake there's a 2-sided line that lets a player enter into such
null space. Ok so other checks will probably detect it, so we're relying on
cetrain check precedence now... Hmmm
>
> 2. to determine whether an item can be picked up or not would require
> simply matching up co-ordinates. If there is no way into a room which
> contains an item then the item can simply be never collected. If it is
> on say a pillar too high to reach again it will never be gained.
Of course this requires checks to see if the pillar isn't 'chained' to
a switch that will lower it for example.... or maybe operate a
lift (those floors that go up & down ) to raise up to it
or maybe there is a nearby 'chasm' to enable a player to jump onto the
pillar (take e1m9 the room with all those goodies as example)
or maybe the whole floor around the pillar can be raised.
Or maybe the author was a bastard and hid a teleport somewhere that
gets you to the pillar ;)
etc.
Stan.
==============================================================================
.-_!\ | Stanley Stasiak
/ \ | (stasiak@iinet.com.au)
I am here! --->> P_.-._/ <<---- Australia| Perth, Western Australia
==============================================================================
------------------------------
From: S.Benner@lancaster.ac.uk (Steve Benner)
Date: Mon, 24 Oct 94 11:00:28 +0100
Subject: Re: What sector is thing #NN in?
MATTHEW J LEDDINGTON-HILL <n1419587@student.fit.qut.edu.au> wrote:
>Matt Fell scripsis:
>>
>> Does anyone have a simple, efficient algorithm to determine what
>> sector a given thing is in? Any clues as to how id does it?
>>
>
>Does id actually test this? I can see no neccessity in this kind of check:
>
For most items, no, it's immaterial, (isn't it?) but if the item is the
player or a monster, DOOM needs to know the sector to check the REJECT map.
My guess would be that DOOM never works this out from scratch during play
(that feels fairly time consuming) but does it for all monsters/players at
initialisation and then keeps track of their movement as they cross
linedefs. Pure guess, as I say, but it seems the easiest (i.e. fastest
running) thing to do. Which doesn't answer the question of how they do it
at initialisation!
Matt Fell wrote:
>Pondering briefly, I came up with something like this:
>
>- Go east from the test-thing's coordinates. Whatever linedef you
>cross first, take the sector number from its appropriate sidedef.
>- To discover which linedef is crossed first, use the blockmap to
>simplify intersection calculations. Going block by block, test each
>linedef that is in that block to see if it is the one.
>
It's probably easier just to use the blockmap to give you a subset of lines
to see which one the THING's closest to and then get the sector number off
that line's (appropriate) sidedef. It doesn't matter that this won't find
the line that is actually the closest to the THING (that may be in another
block) as it still gives you the line that you'll hit first heading in some
'arbitrary' direction. This avoids the problem of possibly hitting a
VERTEX or, worse, of just wandering endlessly through the blockmap, which
could happen if you really chose an arbitrary direction and the THING's in
a void. This method will tell you if the tHING's in void space (there
being no sidedef on the line you found). Of course, you'll have to widen
the search (by considering adjacent block(s)) if the block-list for the
THING's block is empty but this shouldn't be tricky.
This help?
- -Steve
------------------------------
From: "Dewi Morgan (PC GROUP)" <D.Morgan@bradford.ac.uk>
Date: Mon, 24 Oct 1994 11:09:42 +0000 (GMT)
Subject: Re: What sector is thing #NN in?
On Mon, 24 Oct 1994, Stanley Stasiak wrote:
> > Does anyone have a simple, efficient algorithm to determine what
> > sector a given thing is in? Any clues as to how id does it?
> No. 8)
I think it more that likely uses the blockmap, but no ideas here either.
> > [find closest line in arbitrary direction, (ie East).]
> > Obvious weaknesses are the fact that the first "intersect" when heading
> > east might be at a vertex, which would require much further testing. Also,
> > the funky "crystal walls" trick of marking both sidedefs with the same
> > sector number could mess things up.
> Why not got to the nearest vertex straight off. That way once of the cases
> is avoided. Of course finding a nearest vertex is not trivial.
> Some sort of intelligent search-n-test algorithm has to be made
> for traversing the vertex list to find the closest to the thing cordinates.
>
> Once a vertex is found it can be used as a key for matching linedefs
> referencing it... blah blah.... some of which will be the nearest lines...
> etc.
Test fails when:
a------------b
| Sector 2 |
| | T2
c------------d
T3
e---------------------------------------------f
| |
| T1 Sector 1 |
| |
g---------------------------------------------h
The nearest vertex (d) can be completely unrelated to the sector containing
the Thing, T1. In fact, if you do your test properly, you will find that
the closest line from the closest vertex is c-d. The thing is on the 'outside'
side of that line, which means your algorithm will tell you that the object is
in 'void space!'
You HAVE to test for the first point at which a ray cast from the player
in a direction will collide with the edge of a sector. Not only that, but
you have to know that there is a line there, even if the thing is in void
space, such as T2 in the diagram above.
If you cast a ray east from the thing T2, you will either loop forever,
looking for a linedef, or you will wrap around the map, and return void
space when the ray collides with the line a-c. This second option
returns a correct value, but again it will not hold if the object, ie T3,
is not in line with anything.
This can be avoided if you can define some arbitrary boundary limits to
the map, and draw a box around them. Then, any ray that collided with
the box will result in the object being in void space.
Ideally, though, each of your rays should be as short as possible, unless
you have a routine that can find the closest intersection of a line in an
arbitrary direction without the amount of processing being a function of
distance.
Take your pick:
Closest line in all directions.
Closest line in arbitrary direction.
Either way, you are going to have to take into consideration EVERY SINGLE
vertex on the level, since the sector you are in might be a triangle
formed by the three farthest vertexes.
Mind you, all this is IMHO, and doubtless Foley & Van Damme have a mauch
better solution.
Why do you want to know?
Let me guess: you want to have a menu that shows up where the things are
in the level, so you can, say, find Thing 4, or 'select all things of type
AMMO_BOX' on the level.
This would be cool. Which editor?
- D.
------------------------------
From: Jason Hoffoss <hoffo002@gold.tc.umn.edu>
Date: Mon, 24 Oct 94 08:35:28 CST
Subject: Re: What sector is thing #NN in?
On Sun, 23 Oct 1994 18:54:12 -0400,
MSFell@aol.com <MSFell@aol.com> wrote:
>Does anyone have a simple, efficient algorithm to determine what
>sector a given thing is in? Any clues as to how id does it?
>
>Pondering briefly, I came up with something like this:
>
>- Go east from the test-thing's coordinates. Whatever linedef you
>cross first, take the sector number from its appropriate sidedef.
>- To discover which linedef is crossed first, use the blockmap to
>simplify intersection calculations. Going block by block, test each
>linedef that is in that block to see if it is the one.
>
>Obvious weaknesses are the fact that the first "intersect" when heading
>east might be at a vertex, which would require much further testing. Also,
>the funky "crystal walls" trick of marking both sidedefs with the same
>sector number could mess things up.
Heh, lot of responses to this little topic. :) Anyway, since I've
actually written just such an algorithm, which works flawlessly, and now
that I'm back and reading my mail, I thought I'd go ahead and settle this.
First, the way I do it makes the assumption that your sectors are closed,
and the void isn't a sector (any boundries at infinity). So, with this in
mind..
I don't trace a line east.. I trace a line stright downward. I do this by
checking every single line (doesn't take very long really), and see if
has an X endpoint on one side of your test X, and the other on the other
side. If so, we know we will cross the line going up or down, and so I
next see if it is closer than the last checked line. I check the line's
distance by finding the intersection of the test line and an imaginary
vertical line at whatever X your point is at. Anyway, you then just
compare Y's and look for a minimum one. If it doesn't hit a vertex, this
will work. If you do hit a vertex, however, then you will find that all
lines to that vertex are all the same distance away. So, you need to check
which line has the least difference from 90 degrees (your imaginary
vertical line), and use that as your closest line. Then, just take the
sidedef on the inside of your polygon, and the sector number from that
sidedef. This is exactly how I do it in DMapEdit, and v3.01 has the source
code available, so you can go look at it if you want to see exactly how I
did it. I use it in several places, but mainly for sector edit mode to
figure out which sector the mouse cursor point is inside of. In v4.0 I am
also using it for Thing consistancy checking, to see if Things are inside
a sector. Any other editoring checking for this yet? Just curious.
Later..
-Jason
------------------------------
From: Robert Forsman <thoth@cis.ufl.edu>
Date: Mon, 24 Oct 1994 12:18:04 EDT
Subject: Re: (Dis)Appearing parts of a level
Gregory Alan Lewis <gregl@umich.edu> ,in message <Pine.SOL.3.90a.941023011513.1
6192B-100000@defender.rs.itd.umich.edu>, wrote:
> I just finished experimenting with a little application of the F_SKY1
> texture in Doom, with some semi-interesting results. Basically it's the
> ability to make parts of a level disappear or re-appear, by making them
> look like empty sky. It requires some tinkering to get it to work right,
> but once you've got it, it could have some interesting applications...
>
Let me guess... Lower an intervening ceiling?
------------------------------
From: Robert Forsman <thoth@cis.ufl.edu>
Date: Mon, 24 Oct 1994 12:18:27 EDT
Subject: Re: What sector is thing #NN in?
MSFell@aol.com ,in message <9410231854071217568@aol.com>, wrote:
> Does anyone have a simple, efficient algorithm to determine what
> sector a given thing is in? Any clues as to how id does it?
>
> Pondering briefly, I came up with something like this:
>
> - Go east from the test-thing's coordinates. Whatever linedef you
> cross first, take the sector number from its appropriate sidedef.
Score.
Using the blockmap is a GREAT idea. And you can't really go
forever (it does have array bounds, you know...)
If you hit a vertex, then just find all other linedefs that share that
vertex, pick the one with the numerically greatest cosine (trivially
computable from the dot product with the west vector) and you
have a good linedef.
I'm going to have to do something more complicated than this if I
ever hack on a "build sector around vertex" to DEU.
------------------------------
From: Bernd Kreimeier (++49-228-550-247) <Bernd.Kreimeier@nero.uni-bonn.de>
Date: Mon, 24 Oct 1994 17:45:43 +0100
Subject: DUL/DEL license
This is only remotely related to doom-editing, my apologies
in advance.
The LICENSE.DOC of 1.666 states:
"In order to commercially distribute any such map editor or
data utility you must first sign ID's Data Utility License
and ID reserves the right to deny authorization to commercial
distribute the any such map editor or data utility. You may
request a copy of the Data Editor License from ID."
This has not been in the LICENSE.DOC of 1.2, right?
Just for curiosity, has anybody already seen this DUL/DEL
license document? It has been announced long ago (by Jay
Wilbur?), AFAIRK. I asked Id about this (two times at least/
two weeks ago ;-), but haven't received anything yet.
IMHO this DUL stuff relates to DOOM/HOE marketing
policy/strategy in 1995, which (as Id will be developing a
new game) might quite change a bit?
Perhaps this will give some hints on the probability of any
so-called "Official" DOOM Specs as well.
If anybody has any knowledge to share, please let us/me
know. :-).
B.
- ---------------------------------------------------------------
Bernd Kreimeier THIS SPACE INTENTIONALLY
bernd@nero.uni-bonn.de LEFT BLANK ...
- ---------------------------------------------------------------
------------------------------
From: joost schuur <zxmsu01@studserv.zdv.uni-tuebingen.de>
Date: Mon, 24 Oct 1994 18:15:04 +0100 (MET)
Subject: cc's
uhm.. guys? could you watch out what's in the 'cc' line beore you send
off a mail? you're sending multiple copies to this list. thanks.
j
/=======GB d--(-) p--- c++ l+(++) u++(+) e+ m---@ s+/- n-(--) h--()========\
|joost schuur, reutlinger str. | "anger is a gift" |"the state must |
|92d / 23, d-72072 tuebingen | zack de la rocha, ratm | die." diablo |
\=======f(+) t+(++) r y+=====jschuur@studserv.zdv.uni-tuebingen.de========/
------------------------------
From: Robert Forsman <thoth@cis.ufl.edu>
Date: Mon, 24 Oct 1994 14:03:53 EDT
Subject: Re: What sector is thing #NN in?
Jason Hoffoss <hoffo002@gold.tc.umn.edu> ,in message <44823.hoffo002@gold.tc.um
n.edu>, wrote:
> I don't trace a line east.. I trace a line stright downward.
Obviously either will work. I can hand you a trivial affine transform
that will turn down into east and vice-versa. Just pick a direction
(picking a coordinate axis does simplify things...)
> I do this by
> checking every single line (doesn't take very long really),
Didn't think so :)
> So, you need to check
> which line has the least difference from 90 degrees (your imaginary
> vertical line),
Yup. The cosine that I mentioned in my earlier article is the cheapest
way to do this (only uses sqrt instead of trigonometric transcendentals).
> also using it for Thing consistancy checking, to see if Things are inside
> a sector. Any other editoring checking for this yet? Just curious.
Yea, glad someone is taking my suggestions (or at least, taking someone
else's that was identical to mine).
------------------------------
From: Gregory Alan Lewis <gregl@umich.edu>
Date: Mon, 24 Oct 1994 15:23:15 -0400 (EDT)
Subject: Re: What sector is thing #NN in?
> Does id actually test this? I can see no neccessity in this kind of check:
I know this has already been somewhat answered, but I'll throw in my
two or more cents.
Doom does keep stringent track of what Things are in which sector.
When it first starts the level (this is somewhat guesswork, somewhat
fact), it first goes through and creates a linked list for each sector.
Each list contains all of the Things in that sector, with a pointer to
the next one. Doom uses that info for a number of reason, the most
important being the light level of each Thing, the height of each Thing,
and (when dealing with the monsters), it uses the linked list to
determine which monsters in which sectors are activated by a gunshot.
Now as to how they do it, I dunno. Garnering info from what others have
said, it's likely done with the blockmap, at least partially.
Greg Lewis (Tree)
Author, DeHackEd
Author, TREE*.WAD
------------------------------
From: Gregory Alan Lewis <gregl@umich.edu>
Date: Mon, 24 Oct 1994 15:28:12 -0400 (EDT)
Subject: Re: (Dis)Appearing parts of a level
> Let me guess... Lower an intervening ceiling?
Pretty much, that's how to do it. There are a bunch of things to watch
out for though, or you'll get bad-looking results. Especially if you
just lower the ceiling to the floor, and use one of the Id's ceiling
textures... Yuck!
Greg Lewis (Tree)
Author, bunch o' stuff
------------------------------
From: Matthew Ayres <ayres@cdrom.com>
Date: Mon, 24 Oct 94 15:44:24 -0700
Subject: Re: What sector is thing #NN in?
MSFell@aol.com said...
>Does anyone have a simple, efficient algorithm to determine what
>sector a given thing is in? Any clues as to how id does it?
>
>Pondering briefly, I came up with something like this:
>
>- Go east from the test-thing's coordinates. Whatever linedef you
>cross first, take the sector number from its appropriate sidedef.
>- To discover which linedef is crossed first, use the blockmap to
>simplify intersection calculations. Going block by block, test each
>linedef that is in that block to see if it is the one.
>
>Obvious weaknesses are the fact that the first "intersect" when heading
>east might be at a vertex, which would require much further testing. Also,
>the funky "crystal walls" trick of marking both sidedefs with the same
>sector number could mess things up.
WADED has this algorithm to determine which SECTOR the user is clicking
within. WADED's algorithm first looks upward on the map, and then downward.
Depending on the direction of the first LINEDEF it hits in each direction,
it determines which SIDEDEF to pick from each. The SECTOR value of each
SIDEDEF should be the same, and if they are, you've found what you're looking
for. If they're different, then the SECTORS haven't been built properly.
If you want the psuedo-code for this algorithm, I'll be happy to write up
a text file real quickly. It doesn't use the BLOCKMAP (having the BLOCKMAP
loaded just wastes more memory), but it does have several optimizations in
it, so it's quick.
- ----------------------------------------------------------------------------
-Matthew Ayres, a.k.a. White Fang -Author WADED, a DOOM map editor
-SysOp Lithium BBS, 510-455-0425 -Diagnosed with DOOMophobia, the
-Email: ayres@cdrom.com fear of not playing DOOM enough
- ----------------------------------------------------------------------------
------------------------------
From: Matthew Ayres <ayres@cdrom.com>
Date: Mon, 24 Oct 94 16:09:48 -0700
Subject: Re: What sector is thing #NN in?
Jason Hoffoss <hoffo002@gold.tc.umn.edu> said...
[...talk about finding which SECTOR you're in...]
>also using it for Thing consistancy checking, to see if Things are inside
>a sector. Any other editoring checking for this yet? Just curious.
Yup, WADED v2.00 will be checking for that (out soon)... speaking of
consistency checking, does anyone have a list of things to be checked? I
know a good portion of what needs to be checked to avoid DOOM hangin' or
aborting with some strange error. Most of them are or will be implemented
in v2.00.
-Matt
------------------------------
From: Matthew Ayres <ayres@cdrom.com>
Date: Mon, 24 Oct 94 16:13:08 -0700
Subject: Re: What sector is thing #NN in?
Robert Forsman <thoth@cis.ufl.edu> said...
>MSFell@aol.com ,in message <9410231854071217568@aol.com>, wrote:
>
>> Does anyone have a simple, efficient algorithm to determine what
>> sector a given thing is in? Any clues as to how id does it?
>>
>> Pondering briefly, I came up with something like this:
>>
>> - Go east from the test-thing's coordinates. Whatever linedef you
>> cross first, take the sector number from its appropriate sidedef.
>
> Score.
>
> Using the blockmap is a GREAT idea. And you can't really go
>forever (it does have array bounds, you know...)
Uhm, if you're talking about such use in a map editor, this means that
the BLOCKMAP will have to be constantly updated everytime a new line or
vertex is drawn or moved.
-Matt
------------------------------
End of doom-editing-digest V1 #19
*********************************
