Year

1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010

Month

Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec

Index

March 1997

Linear Quadtrees Carter T Shock
- Linear Quadtrees gzhang1234@yahoo.com
q-tree stuff Chris Gray

Thanks Todd! The picture came out fine on my Amiga, so it must have
worked on PC's, right? :-)

To summarize my understanding here (you never know, I could have missed
it altogether!), objects are stored in B-trees, in which the index is
the Morton code (or some other similar function) of the co-ordinates of
the object. Objects that are "nearby" in the co-ordinate space are
nearby in the B-tree, so searching for them is much faster than any kind of
linear scan of the whole set of objects. This works well in a setup where
there isn't a specific data structure for each location in the world, on
which to hang the object list, and on which to hang pointers to nearby
locations. Given a co-ordinate, it is fairly quick to find what would
be there, and keeping track of the B-tree search path lets you find the
nearest objects easily too.

I did a game system for CP/M, which was kinda like the old Ultima games.
I had "grids" representing tile-based surface maps, and "mazes" representing
the underground 3D view areas (line-drawing only - this *was* on a 1 Mhz
8080 with 64K RAM, including the graphics card). I had a global linked
list of all objects in the grid or maze, and simply did a linear scan,
checking the co-ordinates, in order to find things. This worked since I
was in a small world with only a few dozen objects (if that!), but it sure
wouldn't have worked in a big world with hundred's of objects.

To follow on to that, I'll mention how I did "special" things. I used
something like 6 bits to select the terrain for each location in a grid.
The terrain value gave me the tile, and the monster-set. One value said
"special". When I found that, I would search for that location in the
grid's list of special terrains. That gave me a new tile and/or monster
set. The Morton-indexed B-trees could be used for these terrain things in a
bigger world. The final tree entry could be a pointer to a database entry
giving detailed information for that special location. Similarly, for
3-D maze areas, the basic entry in the description array could give bits
describing the walls/floor/ceiling. "Special" entries could be used for
things like hidden doors, traps, monster triggers, etc. in a similar way.

If your "grids" get *very* big, so that having an array for them is not
practical, then you do as Todd said - just have quad-trees representing
the various properties that are needed to describe the location (terrain
type, monster sets, weather, temperature, etc.) You can layer the whole
thing - if you need smaller regions within your large world that are too
varied for efficient storage using quadtrees, then you can have a B-tree
entry for them that points to an array-based description, which in turn
can point at a few special single-location descriptions.

Note that in some cases you may be able to use a simple function on the
co-ordinates to calculate some properties, rather than having to store
it is a quadtree. Pseudo-random number generators, seeded by the co-ordinates,
are something I've always had in mind for this. I did it once in a little
CRT-based system (curses/termcap), and it worked OK, but not super.

--
Chris Gray cg@ami-cg.GraySage.Edmonton.AB.CA
- q-tree stuff Carter T Shock
- - q-tree stuff coder@ibm.net
Issues from the digests and Wout's list Alex Oren
- Issues from the digests and Wout's list coder@ibm.net
- Issues from the digests and Wout's list coder@ibm.net
- Issues from the digests and Wout's list coder@ibm.net
- Issues from the digests and Wout's list clawrenc@cup.hp.com
- - Issues from the digests and Wout's list Nathan Yospe
  - - Issues from the digests and Wout's list Shawn Halpenny
    - - Issues from the digests and Wout's list Nathan Yospe
      - Issues from the digests and Wout's list Shawn Halpenny
        Issues from the digests and Wout's list clawrenc@cup.hp.com
        Issues from the digests and Wout's list clawrenc@cup.hp.com
      - Issues from the digests and Wout's list clawrenc@cup.hp.com
      - Issues from the digests and Wout's list Shawn Halpenny
        Issues from the digests and Wout's list clawrenc@cup.hp.com
        Issues from the digests and Wout's list Shawn Halpenny
        Issues from the digests and Wout's list clawrenc@cup.hp.com
        Issues from the digests and Wout's list Shawn Halpenny
        Issues from the digests and Wout's list clawrenc@cup.hp.com
        Issues from the digests and Wout's list Shawn Halpenny
        Issues from the digests and Wout's list clawrenc@cup.hp.com
    - Issues from the digests and Wout's list clawrenc@cup.hp.com
    - - Issues from the digests and Wout's list Adam Wiggins
      - Issues from the digests and Wout's list coder@ibm.net
        Issues from the digests and Wout's list Chris Gray
        Issues from the digests and Wout's list clawrenc@cup.hp.com
        Issues from the digests and Wout's list Miroslav Silovic
        Issues from the digests and Wout's list clawrenc@cup.hp.com
        Issues from the digests and Wout's list Miroslav Silovic
        Issues from the digests and Wout's list Jeff Kesselman
        Issues from the digests and Wout's list Caliban Tiresias Darklock
        Issues from the digests and Wout's list clawrenc@cup.hp.com
        Issues from the digests and Wout's list Caliban Tiresias Darklock
        Issues from the digests and Wout's list Miroslav Silovic
        Issues from the digests and Wout's list clawrenc@cup.hp.com
        Issues from the digests and Wout's list Caliban Tiresias Darklock
        Issues from the digests and Wout's list clawrenc@cup.hp.com
        Issues from the digests and Wout's list Caliban Tiresias Darklock
        Issues from the digests and Wout's list coder@ibm.net
        Issues from the digests and Wout's list Miroslav Silovic
        Issues from the digests and Wout's list Jon A. Lambert
        Issues from the digests and Wout's list Ling
    - Issues from the digests and Wout's list Adam Wiggins
    - - Issues from the digests and Wout's list clawrenc@cup.hp.com
      - Issues from the digests and Wout's list Adam Wiggins
        Issues from the digests and Wout's list clawrenc@cup.hp.com
        Issues from the digests and Wout's list Adam Wiggins
        Issues from the digests and Wout's list clawrenc@cup.hp.com
        Issues from the digests and Wout's list Adam Wiggins
- Issues from the digests and Wout's list Shawn Halpenny
- - Issues from the digests and Wout's list clawrenc@cup.hp.com
  - - Issues from the digests and Wout's list Nathan Yospe
    - - Issues from the digests and Wout's list clawrenc@cup.hp.com
      - Issues from the digests and Wout's list Shawn Halpenny
    - Issues from the digests and Wout's list Chris Gray
    - - Issues from the digests and Wout's list Ling
      - Issues from the digests and Wout's list clawrenc@cup.hp.com
        Issues from the digests and Wout's list Jeff Kesselman
        Issues from the digests and Wout's list clawrenc@cup.hp.com
        Issues from the digests and Wout's list Chris Gray
        Issues from the digests and Wout's list Nathan Yospe
        Issues from the digests and Wout's list Shawn Halpenny
        Issues from the digests and Wout's list Jeff Kesselman
        Issues from the digests and Wout's list clawrenc@cup.hp.com
        Issues from the digests and Wout's list Jeff Kesselman
        Issues from the digests and Wout's list clawrenc@cup.hp.com
        Issues from the digests and Wout's list Jon A. Lambert
        Issues from the digests and Wout's list Jeff Kesselman
        Issues from the digests and Wout's list clawrenc@cup.hp.com
        Issues from the digests and Wout's list Jeff Kesselman
        Issues from the digests and Wout's list S001GMU@nova.wright.edu
        Issues from the digests and Wout's list Shawn Halpenny
        Issues from the digests and Wout's list Travis Casey
        Issues from the digests and Wout's list Nathan Yospe
        Issues from the digests and Wout's list Jeff Kesselman
        Issues from the digests and Wout's list Nathan Yospe
        Issues from the digests and Wout's list Jon A. Lambert
        Issues from the digests and Wout's list Adam Wiggins
        Issues from the digests and Wout's list Ling
        Issues from the digests and Wout's list clawrenc@cup.hp.com
        Issues from the digests and Wout's list Adam Wiggins
        Issues from the digests and Wout's list Adam Wiggins
    - Issues from the digests and Wout's list Orion Henry
    - - Issues from the digests and Wout's list clawrenc@cup.hp.com
  - Issues from the digests and Wout's list Ling
  - - Issues from the digests and Wout's list Shawn Halpenny
    - - Issues from the digests and Wout's list Nathan Yospe
      - Issues from the digests and Wout's list Jeff Kesselman
    - Issues from the digests and Wout's list clawrenc@cup.hp.com
    - - Issues from the digests and Wout's list Chris Gray
      - Issues from the digests and Wout's list Jon A. Lambert
      - Issues from the digests and Wout's list clawrenc@cup.hp.com
        Issues from the digests and Wout's list Jeff Kesselman
        Issues from the digests and Wout's list Jon A. Lambert
        Issues from the digests and Wout's list clawrenc@cup.hp.com
        Issues from the digests and Wout's list Jeff Kesselman
- Issues from the digests and Wout's list Chris Gray
- Issues from the digests and Wout's list Chris Gray
- Issues from the digests and Wout's list Adam Wiggins
- Issues from the digests and Wout's list Jeff Kesselman
ListMail dupes coder@ibm.net
Threads, IO handling, and Event Queues Nathan Yospe
- Threads, IO handling, and Event Queues Chris Gray
- - Threads, IO handling, and Event Queues coder@ibm.net
  - Threads, IO handling, and Event Queues Carter T Shock
  - - Threads, IO handling, and Event Queues Nathan Yospe
    - Threads, IO handling, and Event Queues claw@null.net
- Threads, IO handling, and Event Queues coder@ibm.net
mud grammar (was Just a bit of musing) Carter T Shock
- mud grammar (was Just a bit of musing) Nathan Yospe
- mud grammar (was Just a bit of musing) Chris Gray
- mud grammar (was Just a bit of musing) claw@null.net
- - mud grammar (was Just a bit of musing) Chris Gray
  - - mud grammar (was Just a bit of musing) claw@null.net
    - - mud grammar (was Just a bit of musing) Chris Gray
mud grammar Carter T Shock
- mud grammar Nathan Yospe
- - mud grammar Alex Oren
  - - mud grammar Nathan Yospe
- mud grammar Adam Wiggins
- mud grammar Chris Gray
Just a bit of musing (VRML) Dmitri Kondratiev
- Just a bit of musing (VRML) claw@null.net
Room coding Nathan Yospe
- Room coding Furball
command parsing Chris Gray
- command parsing Adam Wiggins
- command parsing claw@null.net
Room coding S001GMU@nova.wright.edu
- Room coding Chris Gray
Resets and repops Furball
- Resets and repops claw@null.net
- Resets and repops Jon A. Lambert
- - Resets and repops claw@null.net
  - - Resets and repops Nathan Yospe
    - - Resets and repops Jon A. Lambert
      - Resets and repops Nathan Yospe
        Resets and repops claw@null.net
        Resets and repops Adam Wiggins
        Resets and repops Nathan Yospe
        Resets and repops Adam Wiggins
        Resets and repops Nathan Yospe
        Resets and repops Chris Gray
        Resets and repops Chris Gray
        Resets and repops Adam Wiggins
        Resets and repops Travis Casey
        Resets and repops Chris Gray
        Resets and repops Adam Wiggins
        Resets and repops Shawn Halpenny
        Resets and repops Jeff Kesselman
        Resets and repops Chris Gray
        Resets and repops Nathan Yospe
        Resets and repops Jon A. Lambert
        Resets and repops Nathan Yospe
        Resets and repops claw@null.net
        Resets and repops claw@null.net
        Resets and repops claw@null.net
      - Resets and repops claw@null.net
      - Resets and repops Nathan Yospe
        Resets and repops Adam Wiggins
        Resets and repops claw@null.net
        Resets and repops Adam Wiggins
        Resets and repops claw@null.net
        Resets and repops Nathan Yospe
        Resets and repops claw@null.net
    - Resets and repops Jon A. Lambert
  - Resets and repops Furball
- Resets and repops Chris Gray
- - Resets and repops Adam Wiggins
  - - Resets and repops claw@null.net
    - - Resets and repops Adam Wiggins
      - Resets and repops claw@null.net
      - Resets and repops Chris Gray
      - Resets and repops claw@null.net
        Resets and repops Adam Wiggins
        Resets and repops claw@null.net
        Resets and repops Adam Wiggins
        Resets and repops claw@null.net
        Resets and repops S001GMU@nova.wright.edu
        Resets and repops coder@ibm.net
        Resets and repops S001GMU@nova.wright.edu
        Resets and repops clawrenc@cup.hp.com
        Resets and repops S001GMU@nova.wright.edu
        Resets and repops Chris Gray
        Resets and repops Nathan Yospe
        Resets and repops claw@null.net
      - Resets and repops Nathan Yospe
      - Resets and repops Adam Wiggins
        Resets and repops Nathan Yospe
        Resets and repops Adam Wiggins
        Resets and repops Nathan Yospe
        Resets and repops Chris Gray
        Resets and repops Nathan Yospe
        Resets and repops Chris Gray
        Resets and repops Adam Wiggins
        Resets and repops Chris Gray
        Resets and repops claw@null.net
        Resets and repops lhulbert@czn.com
        Resets and repops claw@null.net
        Resets and repops Chris Gray
        Resets and repops claw@null.net
        Resets and repops Adam Wiggins
        Resets and repops Chris Gray
- Resets and repops Chris Gray
- Resets and repops claw@null.net
- Resets and repops claw@null.net
- Resets and repops claw@null.net
mud grammar claw@null.net
- mud grammar Nathan Yospe
- - mud grammar claw@null.net
List software claw@null.net
- List software Nathan Yospe
- List software Chris Gray
- List software claw@null.net
- List software claw@null.net
I got your message..! MAYA DASWANI
3D graphics claw@null.net
Sorry for the dups (again) coder@ibm.net
mud grammar Jon A. Lambert
- mud grammar claw@null.net
- - mud grammar Nathan Yospe
  - - mud grammar coder@ibm.net
    - - mud grammar Nathan Yospe
      - mud grammar Chris Gray
      - mud grammar claw@null.net
EVOLUTION response claw@null.net
- EVOLUTION response Jon A. Lambert
- - EVOLUTION response claw@null.net
Garbage Collector Artur 'Revinor' Biesiadowski
A perspective out of time - the mudreport document Nathan Yospe
- A perspective out of time - the mudreport document claw@null.net
Old missing posts from old list coder@ibm.net
Execution Chris Gray
- Execution Nathan Yospe
- Execution Furball
- - Execution Jeff Kesselman
  - Execution Chris Gray
- Execution Cynbe ru Taren
Mixture Furball
- Mixture Adam Wiggins
- - Mixture Travis S Casey
  - - Mixture Adam Wiggins
    - Mixture Nathan Yospe
  - Mixture Furball
  - - Mixture Adam Wiggins
    - - Mixture Furball
      - Mixture Adam Wiggins
        Mixture Furball
        Mixture coder@ibm.net
        Mixture coder@ibm.net
    - Mixture Nathan Yospe
  - Mixture claw@null.net
  - - Mixture Adam Wiggins
    - - Mixture claw@null.net
      - Mixture Adam Wiggins
        Mixture Jon A. Lambert
- Mixture claw@null.net
- Mixture claw@null.net
- Mixture claw@null.net
- Mixture S001GMU@nova.wright.edu
- - Mixture Adam Wiggins
  - Mixture Furball
- Mixture claw@null.net
- - Mixture Nathan Yospe
  - Mixture Jon A. Lambert
Resets and repops (a really short post) claw@null.net
- Resets and repops (a really short post) Nathan Yospe
- - Resets and repops (a really short post) claw@null.net
  - - Resets and repops (a really short post) Adam Wiggins
    - - Resets and repops (a really short post) claw@null.net
      - Resets and repops (a really short post) Nathan Yospe
    - Resets and repops (a really short post) Nathan Yospe
Resets and repops (a really short post) <= hah! Chris Gray
VT100 codes ... Khanone@aol.com
VT102 codes Adam Wiggins
- VT102 codes Adam Wiggins
- - VT102 codes Adam Wiggins
Dupes coder@ibm.net
Efficiency Chris Gray
Event Handling Nathan Yospe
- Event handling Shawn Halpenny
- - Event handling Vadim Tkachenko
  - Event handling Maddy
A brief introduction.. ok, you got me: an introduction Greg Munt
- A brief introduction.. ok, you got me: an introduction Adam Wiggins
- A brief introduction.. ok, you got me: an introduction coder@ibm.net
Greetings. :) Michael Hohensee
- Greetings. :) claw@null.net
- - Greetings. :) Nathan Yospe
  - Greetings. :) Michael Hohensee
  - - Greetings. :) coder@ibm.net
    - - Greetings. :) Nathan Yospe
      - Greetings. :) Chris Gray
        Greetings. :) coder@ibm.net
        Greetings. :) Chris Gray
        Greetings. :) Nathan Yospe
        Greetings. :) Jeff Kesselman
        Greetings. :) Chris Gray
        Greetings. :) Greg Munt
        Greetings. :) Jon A. Lambert
        Greetings. :) Nathan Yospe
        Greetings. :) clawrenc@cup.hp.com
        Greetings. :) Furball
        Greetings. :) Chris Gray
        Greetings. :) clawrenc@xsvr1.cup.hp.com
      - Greetings. :) Shawn Halpenny
      - Greetings. :) Jeff Kesselman
        Greetings. :) Shawn Halpenny
        Greetings. :) Jeff Kesselman
        Greetings. :) Shawn Halpenny
        Greetings. :) Jon A. Lambert
        Greetings. :) Jeff Kesselman
        Greetings. :) Shawn Halpenny
        Greetings. :) Jon A. Lambert
        Greetings. :) clawrenc@cup.hp.com
- Greetings. :) Jeff Kesselman

MUD-Dev Archive

Year

Month

Index

March 1997