Hunting thine Wumpus [C/C++]

Overheal

Right; doing this to be fin by the end of the week. I know *kinda* what Im doing, but the real snag is stemming from generating the map (a 2-d array)

One idea Im pseudo'ing is for'ing through the whole array and assigning rand() variables in each adress for open passage/hole/wall

I'm grand and/or fine with that but the question arose: how do I path-check a 2-d array: to make sure that no areas of the cave are completely blocked off by a wall say?

eg. (a wall would be generated randomly with a 5% chance say: )

ooXoXooo
XooXoXho
oohooooo
XhXooXoo
ooXoooho

the problem being here is there is a room on the top row that is cut off. And in the lower left, a hole cuts off a passageway.

how (generally, not specifically ) do I get the code to recognise this, and perhaps take measures to change it?

or is there a better way to generate the cave that im not thinking of? (again, not looking for straight specifics, per boards rules)

OfflerCrocGod

For the whole maze and check that there is at least one valid entry point to every single valid grid position if there isn't then change one of the walls to an open space. I have no idea what exactly you are doing so take this with a bucket of salt

for ( each row )
for ( each collum )
if(TestGridPosition())
ChangeGridPosition();

I presume diagonal moves are illegal therefore you need to only test the four compass directions and you're done. If none of the four are OK then change an X to an o.

Overheal

that will work only where one room is concerned: what about the second case there? the problem being that your function would not identify the hole as being an obstruction to entering the lower left passage. Ive also just noticed there are actually 2 holes causing obstruction to the whole left side..

I'm going to do a preset map to get moving on with the rest of my code for now: but the assignment does require a Nightmare*-style genrator, and those kind of blockages aren't permissable.

(*Nightmare was the name of the Diablo Dungeon Generator afaik)

Overheal

I may have come up with something:

#NSEW

0 0000
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
9 1001
A 1010
B 1011
C 1100
D 1101
E 1110
F 1111


Now if I understood how pointers work (****!!!!) would that be how I mark player position and wumpus position?

oh god I was going somewhere with this theory now my brain has fried...Time for a chocolate milk. Please add any thoughts (need extra brainstorm power here, I think Im on the verge of success)

PhantomBeaker

My thought would be some sort of way of marking the cells, along with a Breadth first search.

Then I'd make some sort of queue-type structure, call it Q. When you're reading in your file, keep track of how many open spaces there are (i.e. 'o' characters), you'll need that later.

Then pick a point, p.

visited_counter := 0
put p on Q

WHILE Q is not empty:
DO
 POS := head of Q
 IF POS has no exits - 
   return with a failure. # that point is blocked, therefore failure
 ELSE # POS does have exits:
  for each exit of POS:
   IF exit is not marked:
    put exit on Q # I.e. we haven't visited it already
   FI
 FI
 mark POS as visited
 counter := counter +1
DONE

Now, all you have to do is satisfy yourself that the above will work. Figure out how you'll fit it in, and how you'll implement it.

I've left out one bit, about how to knit it all together, but it should be easy enough to figure out. You've got all the basics there.

As for how to rectify the situation if you do discover a failure, I've no real suggestions.

Hope that helps,
Aoife

OfflerCrocGod

Overheal wrote:

that will work only where one room is concerned: what about the second case there? the problem being that your function would not identify the hole as being an obstruction to entering the lower left passage. Ive also just noticed there are actually 2 holes causing obstruction to the whole left side..

I begin to understand what you are trying to achieve now.

Overheal wrote:

the assignment does require a Nightmare*-style genrator, and those kind of blockages aren't permissable.

Ummm I think you should rewrite your generator for it to generate valid maps as opposed to generate random maps and then correct them.

Boston

I've no help to offer just that I remember doing this project in second year engineering. I loved it, it was great fun to write the C++ program for.

Jim_No.6

I agree! This project was a load of fun!


/me digs up my code and starts playing

Overheal

the project gives 15% for randomly generated caves. Even with a fixed cave the holes and wumpusses (wumpii??) have to be placed randomly. Wumpuusses wont move to a room with a hole.

For that reason, the whole concept of path checking in this game begins to seem worthless, and I am convinced this is why the SuperBat was introduced: if you couldnt cross, the bat could theoretically teleport you anywhere.

Then, the only thing you really have to do is use #2's idea: so at the least your lad lands somewhere with a bit of walking room. Assuming the bat can ignore the walls it could always find the player.

One flaw: can make the game very boring; waiting around to be teleported to potentially a very small area where the wumpus is...

Overheal

So far this is what my map generator looks like:

//---------------------------------------------------------------------------

#include <vcl.h>
#include <iostream.h>
#include <conio.h>
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>

#pragma hdrstop

//---------------------------------------------------------------------------

#pragma argsused
int Nightmare(int argc, char* argv[])
{
        const int ROWS = 8;
        const int COLS = 8;


        int aRow, aCol, aCompass ;
        int map[ROWS][COLS];


        int iWallCheck = 0; //Counts number of blocked directions for a room
        int iMapChanges = 0; //Tracks number of map errors/changes during generation

        randomize(); //Initalise the Randomizer
        clrscr( ) ;

        //::::: Draft Map :::::\\
for (int i = 0 ; i < 15 ; i++ )
{//Debug
        for (aRow = 0 ; aRow < ROWS ; aRow++)//prints across rows
        {//  start for aRow
                 for (aCol = 0 ; aCol < COLS ; aCol++)//prints across columns
                {//aCol
                         map[aRow][aCol]= rand()%5; //1 in 5 chance a wall is generated

                         if(map[aRow][aCol]>0) map[aRow][aCol] = 0;
                         else map[aRow][aCol] = 1;

                         cout << map[aRow][aCol] << " ";

                 }//aCol
                 cout << endl;
        }//  End for aRow

        cout << "\n\n";

        iMapChanges = 0; //Reset Change Count

        //::::: Check Map :::::\\


        for (aRow = 1 ; aRow < ROWS - 1 ; aRow++)//scans across rows (Except top and bottom row)
        {//  Start for aRow
                for (aCol = 1 ; aCol < COLS - 1 ; aCol++)//scans across columns
                {//aCol
                        iWallCheck = 0; //Reset iWallCheck

                        if (map[aRow-1][aCol] == 1) iWallCheck += 1; //If 'North' is blocked for room
                        else iWallCheck += 0;

                        if (map[aRow+1][aCol] == 1) iWallCheck += 1; //If 'South' is blocked
                        else iWallCheck += 0;

                        if (map[aRow][aCol+1] == 1) iWallCheck += 1; //If 'East' is blocked
                        else iWallCheck += 0;

                        if (map[aRow][aCol-1] == 1) iWallCheck += 1; //If 'West' is blocked
                        else iWallCheck += 0;


                        if (iWallCheck == 4) //If all directions are blocked --> Open all directions
                        {
                                map[aRow-1][aCol] = 0;
                                map[aRow+1][aCol] = 0;
                                map[aRow][aCol+1] = 0;
                                map[aRow][aCol-1] = 0;
                                iMapChanges += 1;
                        }
                        else if (iWallCheck == 3) //If room is "Dead End" --> Seal off as a wall
                        {
                                map[aRow][aCol] = 1;
                                iMapChanges += 1;
                        }
                        else iMapChanges += 0;

                }//aCol
        }//End for aRow

        //::::: Redraw Map :::::\\

        for (aRow = 0 ; aRow < ROWS ; aRow++)//prints across rows
        {//  start for aRow
                 for (aCol = 0 ; aCol < COLS ; aCol++)//prints across columns
                {//aCol

                         cout << map[aRow][aCol] << " ";

                 }//aCol
                 cout << endl;
        }//  End for aRow



        cout << "\n\nTotal Map Changes: " << iMapChanges << endl << endl;
        getch();
}//End Debug Loop

}
//---------------------------------------------------------------------------

I'm begining to see why Blizzard dubbed it the Nightmare engine: must have been a monster bitch to write up