Top Mud Sites Forum Return to TopMudSites.com
Go Back   Top Mud Sites Forum > Mud Development and Administration > MUD Coding
Click here to Register

Reply
 
Thread Tools
Old 12-04-2012, 07:25 PM   #1
ww_crimson
Member
 
Join Date: Sep 2011
Home MUD: Aarchon
Posts: 62
ww_crimson is on a distinguished road
Really struggling with qsort (sorted areas list)

Hey all.. I'm a relatively inexperienced coder and I'm really struggling with grasping the concept of qsort and manipulating arrays.

I want to sort our area list by level (from smallest to largest) and it seems that qsort is the best way to do this from the research that I've done. I've added two integers to our AREA_DATA struct. int minlevel, and int maxlevel.

I've been looking at this old post from Erwin as a reference but I'm still stumped. http://darkoth.mudmagic.com/Code/qsort.c

Code:
void show_areas_sorted()
{
    AREA_DATA * areas[top_area];
    /* put in all aras in the areas array */

    qsort(
        areas,        /* Where does the data to sort start? */
        top_area,    /* How many elements? */
        sizeof(areas[0]), /* How big is each element? */
        compare_area);    /* What function to use to display? */

    /* Run through areas[] displaying it */
}
Putting all of the areas in the array, and then running them through areas[] and displaying the information is what I am particularly struggling with.

To put the areas into an array, I think a for_loop is probably the best solution, but I don't know exactly how to do this. Here is a simple loop that I've started on, but I'm not even really certain that it's correct.

Code:
    for ( pArea1 = area_first; pArea1 != NULL ; pArea1->next )
    {
        if (pArea1->security>4)
            count++;
        else
            pArea1 = pArea1->next;
    }
This gives me a total count of the areas that I want to include, but it certainly doesn't add them to an array, and once I figure that out I'm still not sure how to run through the array displaying the information that I want.

Any help is appreciated. Please keep in mind I'm relatively new to this.

Thank you
ww_crimson is offline   Reply With Quote
Old 12-05-2012, 01:00 AM   #2
camlorn
Member
 
Join Date: Aug 2011
Posts: 144
camlorn is on a distinguished road
Re: Really struggling with qsort (sorted areas list)

Well, problem is, we aren't on your codebase, but:

All right, before I start gicving out answers, you have one major problem. You have to be passing a parameter, unless this is c++--most mud codebases aren't, so I'm going to assume it isn't. What you have really isn't going to work, not easily--you can hack it together, but...I'll come back to that in a moment. This applies to diku derivatives, mostly. If you're using something else, you need to say what. No matter what you're using, please come back and say what.

Your first loop is almost correct, however, move the last line to be the third part of the for expression, as in:
for ( pArea1 = area_first; pArea1 != NULL ; pArea1 = pArea1->next )
{
if (pArea1->security>4)
count++;
}

The count++ only gets executed if security is greater than 4. In your old implementation, the mud would definitely crash if there was a security 4 area, as it would get stuck on it--because the advancing logic is in an else, the if becomes true (we're on a security 4 or greater area), the else doesn't get executed. The loop then happily goes around again, with the same pArea1, and does the same thing, never executing the reassignment. In c, = is legal anywhere, and I do mean anywhere: a=b=c is legal, but don't use it. if(a=b) is legal, setting a to whatever b is and making sure a is nonzeero, and a common trap is using = in if instead of ==. The third part of the for expression is to advance the loop. If you aren't assigning something to a variable (via the increment ++ or decrement -- operators, or the = sign), the loop won't "advance", and is likely to become infinite. Don't use the last line of the for loop for advancement even though you can, it will eventually cause you problems, and the for loop provides the third expression for that purpose.

Now, there's a couple problems I need to address before getting to the part about displaying and putting this in an array. Well, just one. But it's major.

To who?

Your function is taking no parameters. His wasn't really real code, it was more of an example. You need to make this a command: typically, you're going to have a function taking a CHAR_DATA* ch and a char* args...go look at another command, to see what the function needs to look like, and add an entry to the table in interp.c. It should look like this, most likely.
do_sortedareas(CHAR_DATA* ch, char* args)...
And a corrisponding entry in merc.h. I'd recommend going and writing a joke command, call it joke perhaps, that simply sends a message. The function you want is called send_to_char.

Now, this is where I get to discourage you with scary things. I suspect you don't know much c, as you said new and all, and you are jumping off a cliff by going straight to mud hacking. Good luck--this has been done before, but here's the scary stuff, and I see much wikipedia in your future. Have you worked through a good c tutorial? To the end? If not, go do that sometime (not necessarily now, and make sure it is *not* c++, though writing your mud in c++ instead is not a bad idea at all).

There's a thing. It's called a hashtable. Muds liked to use them, and this may not work. It probably will, but sometimes, the mud does stupid things like deciding that a linked list of 50 areas needs to be in a hashtable too. Your code will probably be the problem, but if you are absolutely, absolutely sure that your code is absolutely correct, it is possible that iterating through areas in the "expected" way isn't right for your codebase. You will know this is the problem if no matter what you do it abstanantly refuses to give all areas. Most codebases will allow this to work fine, but do be aware that it almost certainly won't work on rooms, mobs, or objects, because they are typically in the hashtable (It's that stuff, that scary stuff, probably in db.c, with the % operator, and a few other places). When this was first written, muds took up entire mainframes, and every single line had to be hand optimized, etc. Moving on now.

To put things in an array, first be aware that this is horrible. There is a reason I dislike c: we don't get the stl, which makes doing what you want to do maybe 3 lines. I could probably even do it in two. But they're cryptic-ish.

You must:
Make an array that is garenteed to be large enough to hold all areas always. Typically, you #define a MAX_AREAS in merc.h, somewhere in the thousands.
or:
Dynamically allocate an array with malloc.

For simplicity, we are going to assume that you are a sane person and that you don't care about the wasted space of the first approach.



First, you need a line like this:
AREA_DATA *sorted_areas[MAX_AREAS];

And this one for displaying later:
char* buf[MAX_STRING_LENGTH];
Both, probably, at the top of your function.

And then, instead of your counting loop, you need this, which is admittedly a bit scary. We're going to assume you've declared pArea1 at the top of your function, as well as count:
AREA_DATA *pArea1 = first_area;
int count = 0;
And the loop fragment.
for(;pArea1!=NULL;pArea1=pArea1->next) {
if(pArea1->security >= 4){
sorted_areas[count] = pArea1;
count++;
}
}

At this point, you've got a variable called count which is equal to the highest index in the array that contains an area (the actual count of areas is count+1--remember that arrays start at 0), an array with pointers to all your areaas, and the ability to sort. Add 1 to count:
count+1;
Call the sort function, as you did:
qsort(sorted_areas,
count,
sizeof(sorted_areas[0]),
compare_area);


Next, the displaying. This is actually simple, if you know about sprintf, which I shall not go into here. It would take up a lot of time, and google is your friend. So is sprintf, as a mud coder.

The lloop is simply something like.
for(int i = 0; i != count;i++) {
sprintf(buf, "name:%s minlevel:%i maxlevel:%i\n",
sorted_areas[i]->name, sorted_areas[i]->minlevel, sorted_areas[i]->maxlevel);
send_to_char(buf, ch);
}

I have not tested this, and leave it to you to put it together. Do note the following:
-without being a coder on your codebase, I can't test this anyway.
-I may have gotten send_to_char parameters backwards. I do that a lot.
-Trial and error is also your friend. This is close to what you want.
-It is late. I may and probably have made mistakes.
-I will not provide the full function. On the one hand, aren't easy answers nice? On the other, I should have given all the pieces above, including 99% of the code you need, I can't write the function without looking at your codebase (not and garentee it works), learning experiences are good, and it is late. I may also have structure member names wrong--again, can't verify this without your codebase. But this should get you almost all the way there.

Last edited by camlorn : 12-05-2012 at 01:07 AM.
camlorn is offline   Reply With Quote
Old 12-05-2012, 11:51 AM   #3
ww_crimson
Member
 
Join Date: Sep 2011
Home MUD: Aarchon
Posts: 62
ww_crimson is on a distinguished road
Re: Really struggling with qsort (sorted areas list)

Hi Camlorn,

Thank you for your well thought out reply. I'll try to respond to all of your points / comments / questions in order.

To start, the MUD is a ROM codebase (so yes, Diku derivative). It has been pretty heavily modified, but still retains most of ROMs core implementation.

Thank you for fixing/explaining the first loop. That makes total sense and was a silly error on my end.

The "to who" issue:" I'll be using "CHAR_DATA *ch" and displaying it to the char, with the "do_areas" command. I mentioned that I was relative inexperienced but I have wrote a decent amount of code.. I'm just not really familiar with many concepts. I've put together an achievements system (with a little help), a crafting system, and a large handful of skills/spells/bug fixes. Send_to_char, sprintf.... I'm familiar with all that. Anyway, I'm just mentioning that so you know that I have some experience. I always make sure I mention that I'm relatively inexperienced because I've often found when reseraching MUD-specific issues, that many of the responses are on a real "coder to coder" level and I'm not quite there yet. I think a "C" tutorial is a great idea; I'll look into it more today.

I've very recently started researching hashtables but they're still a bit over my head at this point.

You lost me a tiny bit in your next section about "first be aware that this is horrible" and then continuing on about a "MAX_AREAS" define. I know that we don't have one, and while I don't know how to dynamically allocate an array yet, I'm fine moving on from it for now... you mentioned that we can move on to a second approach.. Wasted space isn't a huge issue right now. I'd like to get the functionality down first and then optimize further later on, as I learn more.

I'll work on a complete function today and post back with what I end up with. Thank you again!
ww_crimson is offline   Reply With Quote
Old 12-05-2012, 12:13 PM   #4
ww_crimson
Member
 
Join Date: Sep 2011
Home MUD: Aarchon
Posts: 62
ww_crimson is on a distinguished road
Re: Really struggling with qsort (sorted areas list)

-WOW- . I can't believe how close my original code was to working. Just after making my post (a few mintues ago) I got to work and the code now works. Here is the full function (it's missing some formatting but the structure is there). For the time being I just used a simple number of MAX_AREAS 1000, even though it's incorrect. I need to research how to dynamically allocate that value based on the number of areas we have I suppose so that it's accurate.


Code:
/* Erwins sample for sorting areas. Change the relational
   operators to reverse sorting. Currently it goes from lowest
   to highest. Can make a duplicate function later with the
   operators reversed so players can add arguments to the areas
   command and sort however they want */

int compare_area (const void *v1, const void *v2)
{
    AREA_DATA *a1 = *(AREA_DATA**)v1;
    AREA_DATA *a2 = *(AREA_DATA**)v2;

    if (a1->minlevel < a2->minlevel)
        return -1; 
    else if (a1->minlevel > a2->minlevel)
        return +1;
    else
        return 0;
}

#define MAX_AREAS 1000



/* New areas command that displays areas in order from lowest to
   highest level by default. Add arguments later for additional
   sorting */

void do_areas( CHAR_DATA *ch )
{
    char buf[MSL];
    AREA_DATA *pArea1;
    AREA_DATA *sorted_areas[MAX_AREAS];
    BUFFER *output;
    int count=0;
    int i;
     
    output = new_buf();

    /* The first loop to cycle through all areas that meet our criteria
       of being "in-game" (greater than 4 security) */        
    
    for ( pArea1 = area_first; pArea1 != NULL ; pArea1 = pArea1->next )
    {
        if (pArea1->security>4)
        {
            sorted_areas[count] = pArea1;
            count++;
        }
    }
    
    /* Quicksort - standard C function that is doing all of the hard work
       for us */

    qsort(
                sorted_areas,          /* Where does the data to sort start? */
                count,                      /* How many elements? */
                sizeof(sorted_areas[0]),  /* How big is each element? */
                compare_area);              /* Uses the above "int compare_area" to do the sorting */

    
    /* Loop for displaying the information. Needs formatting */
    
    for (i=0; i != count; i++)
    {
        sprintf (buf,"%-35s %3d - %3d\n\r",sorted_areas[i]->name, sorted_areas[i]->minlevel, sorted_areas[i]->maxlevel);
        add_buf(output, buf);
    }

    page_to_char_bw(buf_string(output),ch);
    free_buf(output);
        
    return;
}
Thanks a ton Camlorn. Any suggestions for further improvement?
ww_crimson is offline   Reply With Quote
Old 12-05-2012, 12:24 PM   #5
camlorn
Member
 
Join Date: Aug 2011
Posts: 144
camlorn is on a distinguished road
Re: Really struggling with qsort (sorted areas list)

horrible, perhaps, was the wrong word. It's more that I would do it a different way because my way would be marginally better--I see arrays, I see the words "add to", and a little part of me dies inside, because I'm one of those coders who codes things to be beautiful and functional for the next thousand years, and I'd have gone and modified the whole codebase to store the area list sorted (which is more than you need). Also, when I originally wrote that part, I thought one of the following loops was going to involve some odd c syntax. Also, I just took the final for a class called data structures yesterday which talks about what to use instead of arrays and why and when you would want to use them.

The truth is, because muds are now so little compared to even your word processor, you can do all sorts of this-is-awful coding, and it'll still run plenty fast [1].

The code I gave you was the easy way. The hard way is dynamically allocating arrays.

The MAX_AREAS looks something like this:
#define MAX_AREAS 1000
Somewhere in merc.h. The number needs to be larger than the total number of areas you're likely to have. In gcc, I believe you can use a variable for array allocation, so it may be possible to declare the array in a smarter fashion, but let's not go there right now. I don't think you're overly worried about losing 4kb ram. If you have over 1000 areas, well, time for me to come play your mud.

The proper way to iterate through a hashtable is a bit more complicated, and highly implementation specific. Again, let's not go there. Just be aware of the phenominon I call drunken coding, where people want to be "cool" and use them in places they shouldn't be used, i.e. the area list. If you can't get this working, at all, that's worth checking. Knowing about hashtables, binary search trees, and linked lists are really cool and will help you understand what is going on in a lot of the code in your mud, but is by no means necessary for this (I just finished a class on them as part of my computer science major, so I have them on the brain). The ->next bit in rom coding seems to be highly context sensitive, even on the same object, and it can be a bit tricky to be sure what you're iterating through (All effects on the mud? on the player? Is that all objects, or all objects in this room? etc.) [1].

1: I'm super complete in my answers, giving every detail that I think might be pertinent, even if most of me knows that it is not going to be the slightest bit helpful. I tend to write code for efficiency, even when no one will see the gains without a profiler. My solution would be to sort the area list in-place, because we save about 4k ram, and to modify the mud to always insert areas in the correct position to keep it sorted (not a small task--this is why I have never got a mud under way. I spend too much time on what is "best", and never code it unless someone is breathing down my neck). Basically, I try to be helpful, but have trouble letting it go at "this is the simplest way". I read the gcc c extension manual for fun, for example, so that I know what kind of things I can get away with.
camlorn is offline   Reply With Quote
Reply


Thread Tools


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off

All times are GMT -4. The time now is 02:25 AM.


Powered by vBulletin® Version 3.6.7
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
Style based on a design by Essilor
Copyright Top Mud Sites.com 2014