December 1998
- Hex-grid mapping Matthew R. Sheahan
- Hex-grid mapping Jon Leonard
- Hex-grid mapping James Wilson
- Hex-grid mapping Jon Leonard
- Hex-grid mapping James Wilson
- Hex-grid mapping Par Winzell
- Hex-grid mapping quzah [sotfhome]
- Hex-grid mapping Nathan F Yospe
- Hex-grid mapping Ling
- Hex-grid mapping Jon A. Lambert
- Hex-grid mapping Nathan F Yospe
- Hex-grid mapping Alberto Barsella
- Hex-grid mapping (example from PSL empire) Pericolo DiMorte
- Hex-grid mapping (example from PSL empire) Nathan F Yospe
- Hex-grid mapping (example from PSL empire) quzah [sotfhome]
- Hex-grid mapping (example from PSL empire) Pericolo DiMorte
- Hex-grid mapping (example from PSL empire) James Wilson
- ADMIN: Personalities... J C Lawrence
- Hex-grid mapping (fwd) Nathan F Yospe
- Hex-grid mapping (fwd) J C Lawrence
- Electric Communities' E Ola Fosheim Grøstad
- Electric Communities' E Ola Fosheim Grøstad
- mud client development systems Sunny Gulati
- mud client development systems Caliban Tiresias Darklock
- mud client development systems Chris Gray
- mud client development systems greear@cyberhighway.net
- mud client development systems Sunny Gulati
- mud client development systems Benjamin D. Wiechel
- mud client development systems Sunny Gulati
- mud client development systems J C Lawrence
- mud client development systems Per Vognsen
- mud client development systems Sunny Gulati
- mud client development systems Scatter
- mud client development systems Per Vognsen
- mud client development systems Chris Gray
- mud client development systems Jon Leonard
- mud client development systems Bruce Mitchener, Jr.
- mud client development systems Sunny Gulati
- mud client development systems Chris Gray
- Stack-Based NPC AI Eli Stevens {KiZurich}
- Stack-Based NPC AI Mark Gritter
- Stack-Based NPC AI Marc Hernandez
- Stack-Based NPC AI Richard Woolcock
- Stack-Based NPC AI Par Winzell
- Stack-Based NPC AI David Bennett
- Stack-Based NPC AI Mik Clarke
- Stack-Based NPC AI Felix A. Croes
- Introduction Mik Clarke
- Introduction Adam J. Thornton
- Introduction Mik Clarke
- Introduction ApplePiMan@aol.com
- Introduction Mik Clarke
- Thought Treasure Adam Wiggins
- Netscape's "Gecko" Browsing Engine (fwd) Nathan F Yospe
- Netscape's "Gecko" Browsing Engine (fwd) Adam Wiggins
- Netscape's "Gecko" Browsing Engine (fwd) Bruce Mitchener, Jr.
- Netscape's "Gecko" Browsing Engine (fwd) greear@cyberhighway.net
- Error tolerant UDP data streams J C Lawrence
- Error tolerant UDP data streams James Wilson
- Error tolerant UDP data streams J C Lawrence
- Error tolerant UDP data streams Ola Fosheim Grøstad
- ADMIN: (IMPORTNANT) Server down time and possible service interruption J C Lawrence
- [DevMUD] Error tolerant UDP data streams Darren Henderson
- MUD Design doc (long) Thinus Barnard
- MUD Design doc (long) Benjamin D. Wiechel
- MUD Design doc (long) Thinus Barnard
- MUD Design doc (long) J C Lawrence
- MUD Design doc (long) Koster, Raph
- MUD Design doc (long) Emil Eifrem
- MUD Design doc (long) Adam Wiggins
- MUD Design doc (long) Michael Willey
- MUD Design doc (long) Adam Wiggins
- MUD Design doc (long) J C Lawrence
- MUD Design doc (long) Mik Clarke
- MUD Design doc (long) Caliban Tiresias Darklock
- MUD Design doc (long) Thinus Barnard
- MUD Design doc (long) Mik Clarke
- MUD Design doc (long) Mik Clarke
- MUD Design doc (long) Travis Casey
- MUD Design doc (long) Nathan F Yospe
- MUD Design doc (long) Mik Clarke
- MUD Design doc (long) Nathan F Yospe
- MUD Design doc (long) Mik Clarke
- MUD Design doc (long) Nathan F Yospe
- MUD Design doc (long) Mik Clarke
- MUD Design doc (long) Adam Wiggins
- MUD Design doc (long) J C Lawrence
- MUD Design doc (long) Ling
- MUD Design doc (long) J C Lawrence
- MUD Design doc (long) Koster, Raph
- MUD Design doc (long) J C Lawrence
- MUD Design doc (long) Mik Clarke
- MUD Design doc (long) J C Lawrence
- MUD Design doc (long) J C Lawrence
- MUD Design doc (long) Emil Eifrem
- MUD Design doc (long) Travis Casey
- MUD Design doc (long) Emil Eifrem
- MUD Design doc (long) Travis Casey
- MUD Design doc (long) Emil Eifrem
- MUD Design doc (long) Travis S. Casey
- MUD Design doc (long) Caliban Tiresias Darklock
- MUD Design doc (long) Marian Griffith
- MUD Design doc (long) Koster, Raph
- MUD Design doc (long) Chris Gray
- MUD Design doc (long) Sunny Gulati
- MUD Design doc (long) J C Lawrence
- MUD Design doc (long) Chris Gray
- MUD Design doc (long) Benjamin D. Wiechel
- MUD Design doc (long) J C Lawrence
- MUD Design doc (long) Nathan F Yospe
- MUD Design doc (long) Chris Gray
- MUD Design doc (long) Emil Eifrem
- MUD Design doc (long) Chris Gray
- MUD Design doc (long) Mik Clarke
- MUD Design doc (long) Chris Gray
- MUD Design doc (long) Caliban Tiresias Darklock
- Hex grids. quzah [softhome]
- small dev-mud invite Chris Gray
- small dev-mud invite J C Lawrence
- mud client development systems Sunny Gulati
- mud client development systems Jay Carlson
- mud client development systems J C Lawrence
- AFAP: As fast as possible, non linear... quzah [softhome]
- AFAP: As fast as possible, non linear... Jon Leonard
- AFAP: As fast as possible, non linear... quzah [softhome]
- AFAP: As fast as possible, non linear... Mik Clarke
- AFAP: As fast as possible, non linear... Alex Oren
- AFAP: As fast as possible, non linear... Dan Shiovitz
- AFAP: As fast as possible, non linear... Mik Clarke
- AFAP: As fast as possible, non linear... quzah [softhome]
- AFAP: As fast as possible, non linear... quzah [softhome]
- AFAP: As fast as possible, non linear... Greg Connor
Your previous messages in this thread talked about optimization (i.e. "as
fast as possible" - thus the subject line), so I thought I would add some
general comments about optimizing that might be helpful for this example
(and might possibly stimulate thought and discussion about optimizing in
general)
quzah [softhome] wrote:
>Greetings everyone. I've got a simple maze generator working if anyone
>cares to take a peek at it. I replied to this message because it is the
>last one in this thread that I have saved. Anyway, regarding the above,
>yes, the old method was really bad and I scrapped it all together. This
>is what I do now:
>
>(1) Store only the inner E and S walls for each row. This fits nicely
>into a short integer for an 8x8 maze, requiring only 15 bits of each
>short integer. The even bits (starting with bit0) are used for "south
>walls" and the odd bits (starting with bit1) are used for "east walls".
You seem to be using bitwise storage, which implies that you would need to
do bitwise AND/OR operations to get yes/no decisions or to change data in
the bit array. This seems like it would be an optimization in the "space"
domain at the expense of the "time" domain... probably this would be a good
place to investigate if you really want something to run as fast as possible.
Using the least amount of storage really needed is usually a good idea...
until you get down to the granularity smaller than the machine's native
units (probably bytes). In particular, you may have a high-level language
that lets you write statements like
if bit 3 of integer x is set, do procedure y
but the machine code may turn out to be something more tortured like
load quantity "1"
shift left "3" places
load integer x
do "AND" on these two
check result for 0, if so, terminate
go to procedure y
There are quite a few optimizations that can be done regardless of how you
implement storage and parameter passing, and most compilers are smart
enough to do this on their own (like, not computing a value if you're never
going to check its result). However, there are other optimizations that
you can make (or tell your compiler to make) where you have to make a
choice: do you want to optimize for "space" or for "time". (Space/Time
optimizations are the main reason there are two versions of the Oxford
English Dictionary: one as a twenty-volume set, and one as a single volume
with a magnifying glass included :)
So, you may want to investigate what, for your particular computer, is the
smallest quantity that can be compared with zero in one step.
>(2) I only check east and south when generating the maze. If the room
>to the east is unused, or south is unused, pick one and remove the wall.
>
>The outer wall of the maze is never used. In addition, it is not even
>stored. It is assumed, and therefore it is never needed. Since it is
>not needed, why bother keeping track of it?
There is another optimization hidden here... sometimes you may choose to
store something that is redundant to speed up your lookups (such as all
four walls instead of only two). If you are walking the maze, and your
position is 3,3, you will want to know whether you can go north, south,
east or west. For east and south, no problem, look up 3,3 in the table.
But for north you have to subtract one from Y and lookup 3,2 for its
"south" number. What is the performance penaly for subtracting (or
"decrementing" even) one of the integers?
You have also set up a number of "special cases" or "border cases" where
you actually need to do the equvalent of two IF's instead of one most of
the time. For example, if you want to go north, from 3,3, you have to read
the value from 3.2, but if you want to go north from 3,0 the answer is
automatically No, there is no North from here. This means every time you
push N the computer needs to calculate:
if direction is north
if y = 0
no
else
lookup x,(y-1)
is "south" open? return yes
There is a similar condition on the east and south frontier... only the
comparison is "less than 8" which a computer might translate as "subtract 8
and branch on minus"
One way to optimize in this situation might be to store all four values as
another index to the array... then instead of all the IF's you just have
"lookup 3,3,0, and branch if zero".
There's another place where you can choose to store actual data, or
remember an implicit assumption, which is the outer frontier (points past
8). You said "Since it's not needed, why bother keeping track of it?"
Well, one reason might be to save the programmer additional grief when it
comes time to change the size. Right now you are kind of stuck with 8
because of the reliance on bitwise operations, but let's assume you can get
around that or code it away. What happens when you want to go to a 16x16
square instead of 8? Replace all occurences of 8 with 16. If you want to
specify any size square? Replace 16 with "SIZE" and #define SIZE 16 at the
top. If you decide you want rectangles instead of squares? Replace SIZE
with either WIDTH or HEIGHT and set #defines.
Then there is the question of how to fill an arbitrary-sized space with
maze, like a circle. Well, you immediately start thinking about how to
"store" the values at the edges rather than "assume" they are there :)
Assumptions like "where the edges are" are something that need to decide
early on whether you want to go for "more code" or "more data".
>I "cheat recurrsion" by using a switch/loop, and avoid any overhead that
>the recurrsion normally would produce. In addition, I was (I'm sure it
>was very inefficient) running out of stack space in the early versions
>of the old generator, and this avoids that aspect all together.
This is a clever technique. If an algorithm is recursive, you can make a
recursive function, or "simulate" recursion with your own "stack" (such as
an array and counter). You may still run out of "stack" but at least you
have more control over memory usage (ie. you don't have to store "return
address" of the calling function :) - AFAP: As fast as possible, non linear... quzah [softhome]
- AFAP: As fast as possible, non linear... Greg Connor
- Graphic design, client questions Thinus Barnard
- Graphic design, client questions Caliban Tiresias Darklock
- Graphic design, client questions Jo Dillon
- Graphic design, client questions Caliban Tiresias Darklock
- Graphic design, client questions Jo Dillon
- Graphic design, client questions Thinus Barnard
- Graphic design, client questions Sunny Gulati
- Graphic design, client questions J C Lawrence
- Graphic design, client questions Caliban Tiresias Darklock
- Graphic design, client questions J C Lawrence
- Graphic design, client questions J C Lawrence
- Graphic design, client questions Jay Carlson
- Graphic design, client questions Ben Greear
- More Laws, was DIS: Client-Server vs Peer-to-Peer Koster, Raph
- More Laws, was DIS: Client-Server vs Peer-to-Peer Ola Fosheim Grøstad
- More Laws, was DIS: Client-Server vs Peer-t o-Peer Koster, Raph
- More Laws, was DIS: Client-Server vs Peer-t o-Peer J C Lawrence
- More Laws Niklas Elmqvist
- More Laws J C Lawrence
- Re[2]:MUD Design doc (long) Michael Willey
- Re[2]:MUD Design doc (long) Adam Wiggins
- Re[2]:MUD Design doc (long) Caliban Tiresias Darklock
- Re[2]:MUD Design doc (long) J C Lawrence
- Re[2]:MUD Design doc (long) Sunny Gulati
- Re[2]:MUD Design doc (long) quzah [softhome]
- Re[2]:MUD Design doc (long) David Bennett
- Re[2]:MUD Design doc (long) quzah [softhome]
- Some useful links Niklas Elmqvist
- Response (Was MUD Design doc (long)) Ola Fosheim Grøstad
- Response (Was MUD Design doc (long)) Chris Gray
- Response (Was MUD Design doc (long)) J C Lawrence
- example custom protocol and its uses Chris Gray
- client stuff... Andrew Wilson
- Developing a MUD for the first time? Alex Oren
- Re[2]:MUD Design doc (long) J C Lawrence
- [DevMUD] Database module J C Lawrence
- [DevMUD] Database module cynbe@muq.org
- [DevMUD] Database module J C Lawrence
- [DevMUD] Database module cynbe@muq.org
- [DevMUD] Database module T. Alexander Popiel
- [DevMUD] Database module Jay Carlson
- [DevMUD] Database module cynbe@muq.org
- [DevMUD] Database module Felix A. Croes
- Re[2]:MUD Design doc (long) Caliban Tiresias Darklock
- [RRE]AAAI 1999 Fall Symposium: Narrative Intelligence Bruce Mitchener, Jr.
- (fwd) DESIGN: Proposed topic of Discussion (Injecting Pure Signal) J C Lawrence
- Terragen Vadim Tkachenko
- [RELEASE] Insanity To Infinity (I:I_OS) v.01a Bobby Bailey
- [RELEASE] Insanity To Infinity (I:I_OS) v.01a Robin Carey
- [RELEASE] Insanity To Infinity (I:I_OS) v.01a Bobby Bailey
- META: 1998 Topic Summary Jon A. Lambert
- [RELEASE] Insanity To Infinity (I:I_OS) v.02a Bobby Bailey
- ADMIN: New text formatting rule for MUD-Dev J C Lawrence
- More Laws Jon A. Lambert
- More Laws Travis Casey
- MUD Design doc - Combat Jon A. Lambert
- MUD Design doc - Combat J C Lawrence
- MUD Design doc - Combat cynbe@muq.org
- MUD Design doc - Combat Koster, Raph
- MUD Design doc - Combat Caliban Tiresias Darklock
- MUD Design doc - Combat quzah [softhome]
- MUD Design doc - Combat Caliban Tiresias Darklock
- MUD Design doc - Combat T. Alexander Popiel
- MUD Design doc - Combat J C Lawrence
- MUD Design doc - Combat Koster, Raph
- MUD Design doc - Combat Adam Wiggins
- MUD Design doc - Combat J C Lawrence
- MUD Design doc - Combat quzah [softhome]
- MUD Design doc - Combat Dr. Cat
- MUD Design doc - Combat T. Alexander Popiel
- MUD Design doc - Combat Caliban Tiresias Darklock
- MUD Design doc - Combat J C Lawrence
- MUD Design doc - Combat James Wilson
- MUD Design doc - Combat Nathan F Yospe
- MUD Design doc - Combat James Wilson
- MUD Design doc - Combat Nathan F Yospe
- MUD Design doc - Combat diablo@best.com
- MUD Design doc - Combat Kristen Koster
- MUD Design doc - Combat Chris Gray
- MUD Design doc - Combat Scatter
- MUD Design doc - Combat Koster, Raph
- MUD Design doc - Combat Kristen Koster
- MUD Design doc - Combat Caliban Tiresias Darklock
- MUD Design doc - Combat T. Alexander Popiel
- Levels versus Skills, who uses them and when. Till Eulenspiegel
- Levels versus Skills, who uses them and when. Travis Casey
- Levels versus Skills, who uses them and when. Koster, Raph
- Levels versus Skills, who uses them and when. Adam Wiggins
- Levels versus Skills, who uses them and when. Marian Griffith
- Levels versus Skills, who uses them and when. Andy Cink
- Levels versus Skills, who uses them and when. Ling
- Levels versus Skills, who uses them and when. Till Eulenspiegel
- Levels versus Skills, who uses them and when. Caliban Tiresias Darklock
- Levels versus Skills, who uses them and when. Justin Robinson
- Levels versus Skills, who uses them and when. Andy Cink
- Levels versus Skills, who uses them and when. Mik Clarke
- Levels versus Skills, who uses them and when. J C Lawrence
- Levels versus Skills, who uses them and when. Koster, Raph
- Levels versus Skills, who uses them and when. J C Lawrence
- Levels versus Skills, who uses them and when. Koster, Raph
- Levels versus Skills, who uses them and when. Adam Wiggins
- Levels versus Skills, who uses them and when. Marian Griffith
- Levels versus Skills, who uses them and when. J C Lawrence
- Levels versus Skills, who uses them and when. Marian Griffith
- Levels versus Skills, who uses them and when. J C Lawrence
- Levels versus Skills, who uses them and when. Alex Oren
- Levels versus Skills, who uses them and when. Mik Clarke
- Levels versus Skills, who uses them and when. Adam Wiggins
- Levels versus Skills, who uses them and when. J C Lawrence
- Levels versus Skills, who uses them and when. Koster, Raph
- Levels versus Skills, who uses them and when. Mik Clarke
- Levels versus Skills, who uses them and when. Matt Wallace
- Levels versus Skills, who uses them and when. Adam Wiggins
- Levels versus Skills, who uses them and when. Adam Wiggins
- Levels versus Skills, who uses them and when. Marian Griffith
- Levels versus Skills, who uses them and when. J C Lawrence
- Levels versus Skills, who uses them and when. Koster, Raph
- Levels versus Skills, who uses them and when. Caliban Tiresias Darklock
- Levels versus Skills, who uses them and when. Andy Cink
- Levels versus Skills, who uses them and when. Koster, Raph
- Levels versus Skills, who uses them and when. Caliban Tiresias Darklock
- Levels versus Skills, who uses them and when. J C Lawrence
- Levels versus Skills, who uses them and when. Caliban Tiresias Darklock
- Levels versus Skills, who uses them and when. Andy Cink
- Levels versus Skills, who uses them and when. Koster, Raph
- Levels versus Skills, who uses them and when. Caliban Tiresias Darklock
- Levels versus Skills, who uses them and when. Marian Griffith
- Levels versus Skills, who uses them and when. Caliban Tiresias Darklock
- Levels versus Skills, who uses them and when. Koster, Raph
- Levels versus Skills, who uses them and when. Mik Clarke
- Levels versus Skills, who uses them and when. Koster, Raph
- Levels versus Skills, who uses them and when. Adam Wiggins
- Levels versus Skills, who uses them and when. J C Lawrence
- Levels versus Skills, who uses them and when. Holly Sommer
- Levels versus Skills, who uses them and when. Adam Wiggins
- Levels versus Skills, who uses them and when. J C Lawrence
- Levels versus Skills, who uses them and when. Mik Clarke
- Levels versus Skills, who uses them and when. Matt Wallace
- Levels versus Skills, who uses them and when. J C Lawrence
- Levels versus Skills, who uses them and when. Mik Clarke
- Levels versus Skills, who uses them and when. D. B. Brown
- Levels versus Skills, who uses them and when. Mik Clarke
- Levels versus Skills, who uses them and when. J C Lawrence
- Levels versus Skills, who uses them and when. J C Lawrence
- Levels versus Skills, who uses them and when. Vladimir Prelovac
- Levels versus Skills, who uses them and when. J C Lawrence
- Levels versus Skills, who uses them and when. Caliban Tiresias Darklock
- Levels versus Skills, who uses them and when. Nathan F Yospe
- Levels versus Skills, who uses them and when. J C Lawrence
- Levels versus Skills, who uses them and when. J C Lawrence
- Levels versus Skills, who uses them and when. Jon A. Lambert
- Levels versus Skills, who uses them and when. Travis S. Casey
- Levels versus Skills, who uses them and when. Caliban Tiresias Darklock
- Levels versus Skills, who uses them and when. J C Lawrence
- Levels versus Skills, who uses them and when. Petri Virkkula