LinuxQuestions.org
Visit Jeremy's Blog.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Reply
 
Search this Thread
Old 05-01-2013, 09:12 PM   #1
errigour
Member
 
Registered: May 2009
Posts: 269

Rep: Reputation: 5
Need help with a Breadth first search for a circle M. U. D.


Im hoping anyone that looks at this will post some kind of tip or trick that might help me
to make a map that will only show rooms accecable from the currect room in at most a
9 by 19 area of rooms. I already have the formatting down I just need to make an
array[9][19] tell me which rooms are visible from my current location and doors block
that visibility. if array[0][0] == -1 then I wouldn't see the room at the very upper left
corner. thanks.

Also if anyone is familiar with circlemud I could really use the help for my personal mud I
have. I don't know how to set up ssh to work though so you might have to download the
source or help me set up ssh.
 
Old 05-01-2013, 11:01 PM   #2
ntubski
Senior Member
 
Registered: Nov 2005
Distribution: Debian
Posts: 2,446

Rep: Reputation: 829Reputation: 829Reputation: 829Reputation: 829Reputation: 829Reputation: 829Reputation: 829
Quote:
Originally Posted by errigour View Post
I already have the formatting down I just need to make an
array[9][19]
What is your actual difficulty? To declare a 9x19 array in C (is this in C??):
Code:
int array[9][19];
Quote:
I don't know how to set up ssh to work though so you might have to download the
source or help me set up ssh.
Maybe you should start a thread about setting up ssh.
 
Old 05-01-2013, 11:11 PM   #3
errigour
Member
 
Registered: May 2009
Posts: 269

Original Poster
Rep: Reputation: 5
I asked for tips not critism or help with ssh.
 
Old 05-02-2013, 03:10 AM   #4
Ramurd
Member
 
Registered: Mar 2009
Location: Rotterdam, the Netherlands
Distribution: Slackwarelinux
Posts: 548

Rep: Reputation: 74
1: you are trying to make a map, I presume?
1.1: Where in the map / array is your current location?
1.2: Define visible;
1.2.1: can you look around corners?
1.2.2: what are the obstructions?

There are many other things that are unclear here; how are the exits defined? As a linked list, as an array? As separate entities?
Having coded on a DIKU mud ages ago, I do know something about this kind of stuff... but it has been ages :-)

Those are my tips for now: define your problem clearly. What do you think yourself?
Starting on a project the size of a regular MUD with little to no experience in C will be a steep learning curve.
Get used to the code and try easier things than a map routine.
 
Old 05-02-2013, 07:18 AM   #5
ntubski
Senior Member
 
Registered: Nov 2005
Distribution: Debian
Posts: 2,446

Rep: Reputation: 829Reputation: 829Reputation: 829Reputation: 829Reputation: 829Reputation: 829Reputation: 829
Quote:
Originally Posted by errigour View Post
I asked for tips not critism or help with ssh.
That wasn't criticism, I'm just genuinely unsure what it is you need help with.
 
Old 05-02-2013, 09:20 AM   #6
errigour
Member
 
Registered: May 2009
Posts: 269

Original Poster
Rep: Reputation: 5
Quote:
1: you are trying to make a map, I presume?
1.1: Where in the map / array is your current location?
1.2: Define visible;
1.2.1: can you look around corners?
1.2.2: what are the obstructions?
1: Map yes
1.1: The size of the map can changes but Id like to start with the largest so mapt[4][9] == 1
1.2: Visible means so much more now that I think about it. I was going for if theres a path to
the room and a door open but I really like obstructions better and hey what a convenience
its even easier to do.
1.2.1: The comment above has moved me to say no.
1.2.2: The obstructions are anything that would block the view including doors.

The array above is just to tell me if the room is visible before I copy every thing I can see to a the output buffer and the game uses an array of rooms for world data. Ill post a small example of this below. The only other obstruction is walls and doors now that I think about it and it wont be as hard as what I was originally planning and I get to use the vision stat. I dont know how helpful that is but if you wanna post any tips for me that would still be some cool stuff. I also added a pointer to the world data structure room_data that points to room maps so basically I have to put 9 * 19 room maps size 3 x 3 into a buffer which makes every room visible and every room contains a 3x3 map.

So just to clear things up about what I am doing. Basically using a vision variable to determine the amount of rooms a character can see from his location and obstructing that vision with doors and walls and just anything else that obstructs vision which are all integers anyways. You dont gotta go into detail and write up a huge piece of code just tips and anything that will make my life easier would be cool.
Code:
/* The direction north is pointing to, from the room the character is in,
    but that will crash if world[IN_ROOM(ch)].dir_option[0] == NULL (isn't allocated).*/
if ( world[IN_ROOM(ch)].dir_option[0]->to_room != NOWHERE )
{
     /* This just says if the exit 0 (north) is a door and if the exit isn't closed */
     if ( EXIT_FLAGGED(world[IN_ROOM(ch)].dir_option[0], EX_ISDOOR) &&
         !EXIT_FLAGGED(world[IN_ROOM(ch)].dir_option[0], EX_CLOSED))
     {
     }

     /* This is the direction north is pointing to from the room north of the room the
         character is in. I actually got it down pretty good here. */
     nextroom = world[world[IN_ROOM(ch)].dir_option[0]->to_room].dir_option[0]->to_room;

     /* This is the next room north of that room etc... */
     nextroom = world[nextroom].dir_option[0]->to_room
}
 
Old 05-02-2013, 04:06 PM   #7
ntubski
Senior Member
 
Registered: Nov 2005
Distribution: Debian
Posts: 2,446

Rep: Reputation: 829Reputation: 829Reputation: 829Reputation: 829Reputation: 829Reputation: 829Reputation: 829
It sounds like you just want to check in the 4 cardinal directions? Something like this:

Code:
north = (-1, 0)
south = (1, 0)
east  = (0, 1)
west  = (0, -1)

visibleFrom(curLocation) {
    set all visible = no

    curLocation = (r, c)
    // so that (r, c) + north = (r-1, c)

    visible[r][c] = yes // current location visible

    // look in 4 directions
    look(visible, north, curLocation)
    look(visible, south, curLocation)
    look(visible, east, curLocation)
    look(visible, west, curLocation)
}

look(visible, dir, location) {
    while not obstructed(location, dir) {
        location += dir; // this shouldn't modify caller's value
        visible[location.r, location.c] = yes. // this should modify caller's value
    }
}
If that is too simple check out Field of Vision.
 
Old 05-03-2013, 10:55 AM   #8
errigour
Member
 
Registered: May 2009
Posts: 269

Original Poster
Rep: Reputation: 5
No Im not trying to just check four cardinal directions. I am trying to make a map that looks like the code
section below putting a * in the middle using rooms like just below.
Every square below Is a room and thats what I mean by a 9 x 19 room map.:
###
#
###

Anyways from the center of the map below I want to check (short int) vision squares to see if the
player can see in that direction. Yea I have to some how go in a circle from the start room untill all
19 vision is accomplished which is tedious but thanks for the tip. Also Im using C to answer your question
earlier.

Code:
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
Also again I dont want anyoner to actually hard code an example just tips and tricks that might help
or make like easier.
 
Old 05-03-2013, 11:00 AM   #9
errigour
Member
 
Registered: May 2009
Posts: 269

Original Poster
Rep: Reputation: 5
So I do gotta check four cardinal directions but I have to check four cardinal directions in each room surrounding the
center room that is visible and tell the array which rooms the player can see and continue untill 9 squares from the
center are all handled and then display the rooms that the player can see. Not to hard Im just gonna do a circle starting from north west of the center square each time.

Heres a snippet of what Im doing atm it doesnt compile but you might be able to say something about this.
Code:
const char *parse_display(struct char_data *ch, char *buffer)
{
     char color = 0x00;
     
     short int a = 0x00;
     short int x = 0x00;
     short int dir = -1;
     short int count = 0x01;
     
     short int starty = 0x00;
     short int startx = 0x00;
     
     short int placey = 0x00;
     short int placex = 0x00;
     
     char *tmp = 0x00;
     char *buf = 0x00;

     room_rnum nextroom = 0x00;
     
     room_rnum mapt[MAX_MAP_HEIGHT][MAX_MAP_WIDTH];
     
     char buff[MAX_MAP_LENGTH];
     
     for ( a = 0x00; a < MAX_MAP_HEIGHT; a++)
          for ( x = 0x00; x < MAX_MAP_WIDTH; x++)
               mapt[a][x] = -1;
/*
     1 1
     ###
     ###
     ###

     3 5
     ###############
     ###############
     ###############
     ###############
     ###############
     ###############
     ###############
     ###############
     ###############
     
     3 7
     #####################
     #####################
     #####################
     #####################
     #####################
     #####################
     #####################
     #####################
     #####################
     
     5 9
     ###########################
     ###########################
     ###########################
     ###########################
     ###########################
     ###########################
     ###########################
     ###########################
     ###########################
     ###########################
     ###########################
     ###########################
     ###########################
     ###########################
     ###########################
     
     7 13
     #######################################
     #######################################
     #######################################
     #######################################
     #######################################
     #######################################
     #######################################
     #######################################
     #######################################
     #######################################
     #######################################
     #######################################
     #######################################
     #######################################
     #######################################
     #######################################
     #######################################
     #######################################
     #######################################
     #######################################
     #######################################
     
     9 19
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     #########################################################
     */
     nextroom = IN_ROOM(ch);
     
     starty = (ch->map_height / 2) + 1;
     startx = (ch->map_width  / 2) + 1;
     placey = starty;
     placex = startx;
     
     if ( ch->map_width > 1 && ch->map_height > 1)
     {
          for ( a = 0x00; a < 10; a++)
          {
               if ( a == 4 || a == 5 )
                    a = 6;

               if ( world[nextroom].dir_option[a] != NULL)
               {
                    if ( world[nextroom].dir_option[a]->to_room != NOWHERE )
                    {
                         if ( EXIT_FLAGGED(world[nextroom].dir_option[a], EX_ISDOOR) &&
                             !EXIT_FLAGGED(world[nextroom].dir_option[a], EX_CLOSED))
                         {
                              if ( count == 1 )
                              {
                                   if ( a == 0 ) /* North */
                                        mapt[placey + 1][placex] = world[nextroom].dir_option[a]->to_room;
                                   if ( a == 1 ) /* East  */
                                        mapt[placey][placex + 1] = world[nextroom].dir_option[a]->to_room;
                                   if ( a == 2 ) /* South */
                                        mapt[placey - 1][placex] = world[nextroom].dir_option[a]->to_room;
                                   if ( a == 3 ) /* West  */
                                        mapt[placey][placex - 1] = world[nextroom].dir_option[a]->to_room;
                                   if ( a == 6 ) /* North west */
                                        mapt[placey + 1][placex - 1] = world[nextroom].dir_option[a]->to_room;
                                   if ( a == 7 ) /* North east */
                                        mapt[placey + 1][placex + 1] = world[nextroom].dir_option[a]->to_room;
                                   if ( a == 8 ) /* South east */
                                        mapt[placey - 1][placex + 1] = world[nextroom].dir_option[a]->to_room;
                                   if ( a == 9 ) /* South west */
                                        mapt[placey - 1][placex - 1] = world[nextroom].dir_option[a]->to_room;
                              }
                              else if ( count == 2 )
                              {
                                   if ( a == 0 ) /* North */
                                        mapt[placey + 1][placex] = world[nextroom].dir_option[a]->to_room;
                                   if ( a == 1 ) /* East  */
                                        mapt[placey][placex + 1] = world[nextroom].dir_option[a]->to_room;
                                   if ( a == 2 ) /* South */
                                        mapt[placey - 1][placex] = world[nextroom].dir_option[a]->to_room;
                                   if ( a == 3 ) /* West  */
                                        mapt[placey][placex - 1] = world[nextroom].dir_option[a]->to_room;
                                   if ( a == 6 ) /* North west */
                                        mapt[placey + 1][placex - 1] = world[nextroom].dir_option[a]->to_room;
                                   if ( a == 7 ) /* North east */
                                        mapt[placey + 1][placex + 1] = world[nextroom].dir_option[a]->to_room;
                                   if ( a == 8 ) /* South east */
                                        mapt[placey - 1][placex + 1] = world[nextroom].dir_option[a]->to_room;
                                   if ( a == 9 ) /* South west */
                                        mapt[placey - 1][placex - 1] = world[nextroom].dir_option[a]->to_room;
                              }
                              else if ( count == 3 )
                              {
                                   
                              }
                              else if ( count == 4 )
                              {
                                   
                              }
                              else if ( count == 5 )
                              {
                                   
                              }
                              else if ( count == 6 )
                              {
                                   
                              }
                              else if ( count == 7 )
                              {
                                   
                              }
                              else if ( count == 8 )
                              {
                                   
                              }
                              else if ( count == 9 )
                              {
                                   
                              }
                              else if ( count == 10 )
                              {
                                   
                              }
                              else if ( count == 11 )
                              {
                                   
                              }
                              else if ( count == 12 )
                              {
                                   
                              }
                              else if ( count == 13 )
                              {
                                   
                              }
                              else if ( count == 14 )
                              {
                                   
                              }
                              else if ( count == 15 )
                              {
                                   
                              }
                              else if ( count == 16 )
                              {
                                   
                              }
                              else if ( count == 17 )
                              {
                                   
                              }
                              else if ( count == 18 )
                              {
                                   
                              }
                              else if ( count == 19 )
                              {
                                   
                              }
                         }
                    }
               }
               
               if ( world[nextroom].dir_option[a]->to_room == NOWHERE && world[nextroom].dir_option[a] == NULL)
               {
                    if ( a == 0 ) /* North */
                         mapt[placey + 1][placex] = -2;
                    if ( a == 1 ) /* East  */
                         mapt[placey][placex + 1] = -2;
                    if ( a == 2 ) /* South */
                         mapt[placey - 1][placex] = -2;
                    if ( a == 3 ) /* West  */
                         mapt[placey][placex - 1] = -2;
                    if ( a == 6 ) /* North west */
                         mapt[placey + 1][placex - 1] = -2;
                    if ( a == 7 ) /* North east */
                         mapt[placey + 1][placex + 1] = -2;
                    if ( a == 8 ) /* South east */
                         mapt[placey - 1][placex + 1] = -2;
                    if ( a == 9 ) /* South west */
                         mapt[placey - 1][placex - 1] = -2;
               }
               
               if ( a == 9 && count <= ch->vision)
               {
                    starty--;
                    starx--;
                    placey = starty;
                    placex = startx;
                    count++;
                    a = 0;
               }
               
               if ( count >= ch->vision)
                    break;
          }
     }
     
     buf = buff;
     
     for ( x = 0x00; x < MAX_MAP_LENGTH; x++, buf++)
     {
          if ( x == (MAX_MAP_LENGTH - 3) )
          {
               buffer[x++] = '\r';
               buffer[x] = '\n';
               return buffer;
          }
          else if ( *buf == '.' && (buf[1] == '\r' || buf[1] == '\0'))
          {
               if ( buf[1] == 0x00)
               {
                    buffer[x++] = '\r';
                    buffer[x] = '\n';
                    return buffer;
               }
               buf+=2;
          }
          else if (*buf == '#')
          {
               tmp = buf;
               buf++;
               if (*buf == '[')
               {
                    buf++;
                    if (*buf >= '0' &&  *buf <= '5')
                    {
                         if ( *buf == '0' )
                              dir = 0;
                         if ( *buf == '1' )
                              dir = 1;
                         if ( *buf == '2' )
                              dir = 2;
                         if ( *buf == '3' )
                              dir = 3;
                         if ( *buf == '4' )
                              dir = 4;
                         if ( *buf == '5' )
                              dir = 5;
                         buf++;
                         if (*buf == ']')
                         {
                              buf++;
                              if ((*buf >= '0' &&  *buf <= '7') ||
                                   *buf == 'd' ||  *buf <= 'D'  ||
                                   *buf == 'b' ||  *buf <= 'B'  ||
                                   *buf == 'g' ||  *buf <= 'G'  ||
                                   *buf == 'c' ||  *buf <= 'C'  ||
                                   *buf == 'r' ||  *buf <= 'R'  ||
                                   *buf == 'm' ||  *buf <= 'M'  ||
                                   *buf == 'y' ||  *buf <= 'Y'  ||
                                   *buf == 'w' ||  *buf <= 'W'  ||
                                   *buf <= 'n')
                              {
                                   color = *buf;
                                   buf++;
                                   /* Color formats end here, you can add if statements for different types of map caases
                                      that you may want.
                                      D means treat as door in direction  dir*/
                                   if (*buf == 'D')
                                   {
                                        //find out if door # is open or closed 012345 noerth east south west up down
                                        buffer[x] = '@';
                                        x++;
                                        if ( x >= MAX_MAP_LENGTH )
                                             break;
                                        
                                        if ( EXIT_FLAGGED(EXIT(ch, dir), EX_CLOSED) )
                                             buffer[x] = color;
                                        else
                                             buffer[x] = 'n';
                                        continue;
                                   }
                                   else
                                        buf = tmp;
                              }
                              else
                                   buf = tmp;
                         }
                         else
                              buf = tmp;
                    }
                    else
                         buf = tmp;
               }
               else
                    buf = tmp;
          }
          
          buffer[x] = *buf;
     }
     
     if ( buffer[0] == 0x00 )
          return NULL;
     else
          return buffer;
}
 
Old 05-04-2013, 08:11 AM   #10
sundialsvcs
Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 5,363

Rep: Reputation: 1106Reputation: 1106Reputation: 1106Reputation: 1106Reputation: 1106Reputation: 1106Reputation: 1106Reputation: 1106Reputation: 1106
I am not familiar with this programming system, but here is an excellent example of a "class" .. an "object" .. an "abstract data-type."

What you want to first define is a Thing ... called a "Map." It's a black-box sitting on the table in front of you with buttons and dials on it. And it can "do things for you." Although you can't open the box to see how it does it, you don't have to concern yourself with what's inside the box. For instance, you can dial a room-location such as (1,1) on this-here pair of dials, then set a location, say "North," on this-here dial, and push that thingamabobby that says "Can_I_See_That_Way?" and ... well, it rattles and churns a little bit, but ... here on this window it will always correctly tell you, "Yes" or "No."

Define an object called Map with methods like can_I_see_that_way( [i]locationX, locationY, direction ) : BOOLEAN.

Define methods for every button you need to push, and properties for the knobs that you set (or need to look at), to create this Thing called a "Map." Decide every possible thing that you need "a Map" to do, and that you need to do with "a Map."

Now, open the box and start building what's inside of it. You can use arrays, lists, anything that you please, as long as, at the end of the day, you can prove (through a set of rigorous tests that you must also construct), that it does exactly what it's supposed to do and that it does not do anything it shouldn't. Then, close the box again and start using this now-trustworthy thing in your application.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

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

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


Similar Threads
Thread Thread Starter Forum Replies Last Post
Drawing a circle in c++ jadhravi Programming 4 04-12-2010 06:05 AM
The Circle is Complete.. Hitboxx General 1 07-28-2007 02:56 AM
HAL... the circle. Peingune Linux - Newbie 10 08-16-2005 06:01 AM
breadth first search implementation bahadur Programming 1 03-19-2005 07:04 AM
Draw Circle Gerardoj Programming 11 08-24-2003 05:32 PM


All times are GMT -5. The time now is 01:46 PM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration