[MUD-Dev] Re: AFAP: As fast as possible, non linear...

[quzah]

From: Greg Connor <gconnor at nekodojo.org>
Date: Friday, January 01, 1999 2:29 PM
Subject: [MUD-Dev] Re: AFAP: As fast as possible, non linear...


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


Nod. The reason I titled it thusly was because before I attempted to do
a maze generator I did a tiny bit of searching on the topic. The first
three or four mentions/algorithms I turned up were regarding a particular
PASCAL implementation where they said something like "in Pascal it takes
just about an hour to generate a 10x10x10 maze." I quit searching then
and decided to make my own. Since this particular (found searching) method
for making mazes was the the one that showed up the most, I though that
everyone as a whole was saying it was the best/most common, and so I was
thinking "damn if that's the best [most used] and it takes an hour?!"

I don't know too much about optimizing, OS specifics, and the like and
what I know I've managed to teach myself, so most of my methods are sure
to be inefficient, and most of the time I don't know what I'm talking
about as much as I'd like to. At any rate, some day with luck, money
and free time I'll get to take a few classes on said subjects. But in
the mean time I'll have to settle for the best I can manage.

Anyway, that's the reason for the topic name.

>quzah [softhome] wrote:
>>(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.


Again I'm not too sure what ways are faster than another, but the whole
idea was to keep it under a second and to keep it compact. I just didn't
want some horrid maze creator that stopped the entire MUD dead in its
tracks for an hour, minute, or even more than a second.

[snip re: space vs time]

>>(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


Ah, yeah, this is a good idea. I think I will go back to using a single
'char' for each cell of the maze. I am rather happy with being able to
store each maze plain packed into 8 short integers (16 bits * 8), but I
think I will do it this way, and keep track of each direction in each
cell. It will take a bit more work (1 more line of code per shot) for
creating a doorway to the next cell, but I think I'll do this anyway.

The main reason is, the maze as is doesn't scale. Period.

>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".


So it would be something like this?

#define DIRNORTH 0
#define DIREAST  1
#define DIRSOUTH 2
#define DIRWEST  3
#define DIRMAX   4

char cell[x][y][DIRMAX];
...
if( cell[3][3][DIRNORTH] ) go_north();

I think I'll toy with that and see what I can do with it. :)

>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.


Yes. It sucks to try and scale it up. I did yesterday for a short while.
I made it so you #define MAZESIZE_EIGHT if you wanted it to be an 8x8
maze, and if it wasn't defined it assumed a 16x16 maze. This worked fine
in theory since I just jumped up to an 'int' rather than a 'short int'.
Then I did a

#ifdef MAZESIZE_EIGHT
#define MAZESIZE 8
#else
#define MAZESIZE 16
#endif

and replaced all the correct occurences of "8" in the code with "MAZESIZE"
and all of the "7" in the code with "MAZESIZE-1". I had to redo a few of
the macros which were bitshifting by 3 to either do by 3 or 4 depending on
the size of the maze. In the end I deleted the whole thing (what I had
been doing yesterday, not the original) because I never did end up getting
it to work right. All in all, it doesn't scale. I'm sure someone could
get it to scale, I probabaly could, but it isn't worth my time right now.
I'm happy with the way it works for now, since it was my first "working"
first effort. It makes a nifty little maze, and now I know I can make one,
so it gives me something to improve upon, coupled with the added bonus of
knowing I succeded this far. :)

>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".


Nod. I hadn't even thought of other shapes yet. I was just trying for a
tiny little working maze generator. However, I think I'm going to make
it scaleable, at least as far as X and Y go, rectangular, plus Z number
of plains. (Circles, triangles and such will have to wait until I'm
feeling a bit more gutsy, and have a bit more know-how.)

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


I faked calling itself by having it not change the case variable and just
keeping track of the current "path" we were working in. I have a link to
stack-free recursion, but it's a bit beyond me, which is why I though up
doing it this way.

All in all, I am pretty pleased with myself, having made one that works
in its current size, is fairly quick, doesn't really use recursion and
should not really lag a mud down. Thanks everyone for the replies. Feel
free to keep commenting/sharing ideas, I appreciate all the help and
discussion.

Now I have to decide if I want to rewrite it now, or continue with my
latest idea. I'm thinking of hard-coding in objects. A single item will
represent all swords in the game. When Boffo wants a sword, he will go
and get one made to his specifications - but it will still be a single
VNUM for the sword. It's values will just be set differently:

obj->value[0] = BLADE_WIDTH_NARROW;
obj->value[1] = BLADE_SHAPE_CURVED;
obj->value[2] = 60; /* blade_length in cm */
...

Something like that. Then it will be either re-strung to get a different
short description and its long description will be generated when it is
looked at, or something like that. Shrug. Anyway. Thanks all for the
info, input and help.

Quzah.