Sign in to follow this  

Please dont Ban me....

This topic is 3928 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Its really ugly... The objective Make 10x10 square, with a border, start and end spot position. Inside the square: Setup random squares either wall square or walk square The walk squares have to be connected so you can walk from start to end position. It works but its... ugly
int level1[ArraySize*ArraySize] = {

44,44,44,44,44,44,44,44,44,44,
33,44,44,55,55,55,55,55,55,44,
44,44,44,44,55,44,55,44,55,44,
44,44,44,55,55,55,55,55,55,44,
44,44,44,55,55,55,55,55,55,44,
44,44,44,55,55,55,44,44,44,44,
44,44,44,55,55,55,44,44,44,44,
44,44,44,44,44,44,44,44,44,44,
44,44,44,44,44,44,44,44,44,77,
44,77,44,44,44,44,44,44,44,44
};// these numbers all get changed except 33 and 77



// 33 start walk square
// 77 end walk square
// 66 outside border
// 22 walls
// 55 walking squares

int RandNum(int n){
	return rand() % n;
}// end random number generator

void SetUpMap(){
	srand(time(NULL));
	bool RandomNumber;
	int x = 0;
	int y = 0;
	for(int i = 0; i < (ArraySize * ArraySize);i++){
		x++;


		if(x == ArraySize){
			x = 0;
			y++;

		}
			// set up outside walls
			if(x == 0 || y == 0)
						if(x == 0 && y == 1)// start location
						level1[x + y * ArraySize] = 33;
						else
						level1[x + y * ArraySize] = 66;// outside borders show as walls
					
			else if(x == (ArraySize-1) || y == (ArraySize-1))
						if(x == (ArraySize-1)    && y == (ArraySize-2))// end location
						level1[x+y * ArraySize] = 77;
						else
						level1[x + y * (ArraySize)] = 66;//outside border show as walls
			// make sure squares beside start and end are walking space
			else if(level1[x-1 + y * ArraySize] == 33 || level1[x+1 + y * ArraySize] == 77)
						level1[x+y * ArraySize] = 55; // walking space
			
			else{
				// rest of the square gets filled with either 22(walls) or 55(walking square)
				RandomNumber = RandNum(2);

				if(RandomNumber)
				level1[x+y * ArraySize] = 22; // walls

				else	
				level1[x+y * ArraySize] = 55; // walking space



			}// end first else

			

}// end first for loop  creates random squares and borders

	//a new loop to makes sure walk is connected to anothere 
	// supposed to connect from the start square to end square
int XX = 0;
int YY = 0;
int count = 0;
bool top = false;
bool bottom = false;
bool right = false;
bool left = false;
bool WallHasNotBeenChanged = true;
for(int i = 0; i < (ArraySize * ArraySize);i++){
	XX++;
	if(XX == ArraySize){
		YY++;
		XX = 0;}

	// only check walk blocks
		if(level1[XX + YY * ArraySize] == 55){
			// check how many walls surround walk block
							if(level1[XX-1 + YY * ArraySize] == 22){
								count++;
								left = true;
							}
							if(level1[XX+1 + YY * ArraySize] == 22){
								count++;
								right = true;
							}
							if(level1[XX + YY-1 * ArraySize] == 22){
								count++;
								bottom = true;
							}
							if(level1[XX + YY+1 * ArraySize] == 22){
								count++;
								top = true;
							}
		}				
							// if more walls then ... surround this walk add more walk squares
							if(count > 1){// this number should be at 2
											// before i had a random number choose these
											// which did not work so well
								if(left)
										level1[XX-1 + YY * ArraySize] = 55;
								if(right)
										level1[XX+1 + YY * ArraySize] = 55;
								if(bottom)
										level1[XX + YY-1 * ArraySize] = 55;
							
								if(top)
										level1[XX + YY+1 * ArraySize] = 55;
							}// end count if
				
// set numbers back
count = 0;
top = false;
bottom = false;
right = false;
left = false;



}// end second for loop makes sure walking squares are connected

}// end setupmap function


Share this post


Link to post
Share on other sites
I agree, it is quite ugly. Among things you should do:
  • Replace integer literals with an enumeration.
  • Encapsulate 2D array access in a class. Candidates are, by order of simplicity, boost::multi_array, nested boost::arrays, nested std::vectors, and your own matrix class with overloaded T& operator()(int x, int y).
  • Use two for loops instead of that dirty i, xx and yy hackery.
  • Use more explicit variable names. xx and yy are lousy variable names. If you have to, use x and y as loop variables, and x_something, y_stuff to describe all other coordinates you would use.
  • The responsibility for "boundary" goes into its own function. Responsibility for start and end position goes into its own function. Responsibility for randomly generating everything else goes into its own function. The setup function calls all three functions in turn.
  • Changing variables "back" to their value at the end of a loop is silly. Just make the variables local to the loop, so they are initialized to the correct value on each iteration.
  • Comment your algorithm, and not your code. I should expect to see a ten-line comment block before the loop explaining how the loop will do what we want it to. Preferably, the loop should be in its own function to start with.
  • You might wish to choose another algorithm for connecting start to end. The current one is hackish and difficult to both understand and prove. I would suggest associating a random value with each tile, and then performing a breadth-first search on the graph, using the tile value as the priority. Once you reach the exit, automatically cull any values smaller than the smallest value found so far. When you're done exploring, transform explored tiles into paths, and unexplored tiles into walls. Other approaches are possible based on what you want your map to look like.
  • bool WallHasNotBeenChanged = true; is never used. But your compiler should have told you that. Tip: use the maximum level of warnings, and treat warnings as errors. This will help you sort out all the little problems that you wouldn't have otherwise noticed.


In other news, I have a maze-generation algorithm more or less documented here, but it's based on

Share this post


Link to post
Share on other sites
I had some free time before going to sleep, so here is an untested example of refactoring. There are probably some syntax errors, but they should be fairly easy to overcome.

#include <vector>
#include <queue>
#include <pair>
#include <cassert>
#include <cstdlib>

// What a tile is. Silly numeric values, but we don't care.
enum tile_type
{
START = 33,
END = 77,
BORDER = 66
WALL = 22,
PASS = 55
};

// What a map is. We assume here that maps are always of fixed size.
template<int Width, int Height>
class map
{
// The tiles inside the map. It is a private member, so we
// access its values using operator()
tile_type tiles[Width][Height];

public:

// Access a map tile as read/write
tile_type & operator()(int x,int y)
{
assert (x >= 0);
assert (x < Width);
assert (y >= 0);
assert (y < Height);

return this->tiles[x][y];
}

// Access a map tile as read-only
const tile_type & operator()(int x,int y) const
{
assert (x >= 0);
assert (x < Width);
assert (y >= 0);
assert (y < Height);

return this->tiles[x][y];
}

// A static function for returning a freshly initialized
// map.
static map setup_map()
{
map created;
generate_borders(created);
place_start_end(created);
compute_path(created);
return created;
}

private:

// Private implementation of the first step of map generation:
// we initialize a border around the map, and anything
// else to a wall.

static void generate_borders(map & where)
{
for (int x = 0; x < Width; ++x)
for (int y = 0; y < Height; ++y)
{
where(x,y) = WALL;
if (x == 0 || x == Width - 1 || y == 0 || y == Width - 1)
where(x,y) = BORDER;
}
}

// Private implementation of the second step of map generation:
// we place a "start" and "end" tile on our map.

static void place_start_end(map & where)
{
where(0,1) = START;
where(Width-1,Height-2) = END;
}

// Private implementation of the third step of map generation:
// we find a connex set of passable tiles which joins the start
// and end tiles.

// The algorithm consists in exploring the map from the
// top left corner. Each tile has a threshold value
// computed initially, which we use to determine which
// tile is computed next. Once we have reached the bottom
// right tile (and the exit), we cease exploration.

typedef std::pair<int,int> pos;

// The sole purpose of the thresholds is to compare the
// positions in the priority queue. So, we store them as
// part of a comparison structure between positions. So:
class comp
{
// Data
unsigned int tresholds[Width][Height];

public:

// Constructor
comp()
{
for (int x = 0; x < Width; ++x)
for (int y = 0; y < Height; ++y)
{
tresholds[x][y] = std::rand();
}
}

// Comparator
bool operator()(const pos & a, const pos & b) const
{
return (thresholds[a.first][a.second] < tresholds[b.first][b.second]);
}
};

static void compute_path(map & where)
{
// The priority queue is used to determine which wall should
// be turned into a passable element next. It is initialized with
// the top left element.

std::priority_queue<pos,std::vector,comp> candidates;
candidates.push(pos(1,1));

// Explore until we find the exit.
for(;;)
{
pos next = candidates.top();
candidates.pop();

int x = next.first, y = next.second;

// This tile has already been explored
if (where(x,y) == PASS) continue;

where(x,y) = PASS;

// We have reached the exit!
if (next = pos(Width-2,Height-2)) break;

// Otherwise, explore the adjacent tiles.
pos around[] = { pos(x-1,y), pos(x,y-1), pos(x+1,y), pos(x,y+1) };
for (int i = 0; i < 4; ++i)
{
// To determine if they are worth adding to the candidates
// (i.e. they have not been explored yet)
if (where(around[i].first,around[i].second) == WALL)
{
candidates.push(around[i]);
}
}
}
}

}; // map<W,H> class

Share this post


Link to post
Share on other sites
Python to the rescue!


import time, os

# I've replaced the numeric constants with characters that make a prettier animation
TILE_START = "S"
TILE_END = "E"
TILE_BORDER = "X"
TILE_WALL = "."
TILE_PASS = "+"

class Map(object):

def __init__( self, width=10, height=10, startTile=(0,1) ):
""" Creates a new Map object and computes a path through it. """

self.width, self.height, self.startTile = width, height, startTile
self.tiles = [ [TILE_WALL for y in range(height)] for x in range(width) ]

self.__generateMap()

def __generateMap( self ):
for x in xrange(0, self.width):
for y in xrange(0, self.height):
if x == self.startTile[0] and y == self.startTile[1]:
self.tiles[x][y] = TILE_START
elif x == self.width-1 and y == self.height-2:
self.tiles[x][y] = TILE_END
elif x == 0 or x == self.width - 1 or y == 0 or y == self.height - 1:
self.tiles[x][y] = TILE_BORDER

def computePath( self ):
""" Searches the map for the exit in a brute force fashion, starting with the entrance """

candidates = [ self.startTile ]
newCandidates = []
endFound = False

while not endFound:
while len(candidates) > 0:
coords = candidates.pop()
x, y = coords[0], coords[1]

# if tile has not been explored and it is not the end, explore its neighbors
if self.tiles[x][y] != TILE_PASS:

neighbors = ( (x-1, y), (x, y-1), (x+1, y), (x, y+1) )
for nx, ny in neighbors:
tile = self.tiles[nx][ny]
if nx >=0 and nx < self.width and ny >=0 and ny < self.height:
if tile == TILE_WALL:
newCandidates.append( (nx, ny) )
elif tile == TILE_END:
self.tiles[nx][ny] = TILE_PASS
endFound = True

self.tiles[x][y] = TILE_PASS
self.__draw()

candidates += newCandidates

def __draw(self):
os.system("cls")
print self
time.sleep(0.025)

def __str__(self):
description = ""
for row in self.tiles:
for column in row:
description += "%s " % column
description += "\n"
return description

map = Map()
map.computePath()




It took me about 25 minutes to convert the code to Python, then another half hour to debug the algorithm and add a nice animation feature. The program weighs in at 74 lines, including whitespace and comments.

- Mike

Share this post


Link to post
Share on other sites
@doctorsixstring: Obviously I don't see how the Python code is any better or cleaner than the C++ code. Is there an obvious difference in performance or speed or "something" I'm not seeing?

@OP: don't worry if ugly code got you banned there would only be 40 - 50 members here and that includes staff and mods.

Share this post


Link to post
Share on other sites
@ToohrVyk: So elegant :-) i will try this at home. Thanks for the feed back, my teacher never gives feed back or looks at the code, if the game works you get 'A'. (yes it was an assigment, I did finish it first, and this was only a small part of it)

@LessBread: phew

@doctorsixstring: Dont know anything about python, but will check the algorithm
thanks

@Alpha_ProgDes: phew++


Share this post


Link to post
Share on other sites
I doubt the Python code is any faster, but I think it is significantly easier to read and understand (no offense to pascalosti or ToohrVyk ).

The Python code is about half as long as the C++ posted by the OP (137 lines) and ToohrVyk (164 lines), but it does more (animation, custom map size and start tile).

Share this post


Link to post
Share on other sites
Quote:
Original post by doctorsixstring
I doubt the Python code is any faster, but I think it is significantly easier to read and understand (no offense to pascalosti or ToohrVyk ).


I certaintly won't disagree with that! C++ is often a very bad idea for small-to-medium problems such as this one, and sometimes a bad idea for larger problems as well.

While we're at it:

type tile = Wall | Pass | Border | Start | End

(* Aspect of a single tile *)
let aspect = function
| Wall | Border -> "#"
| Pass -> " "
| Start -> "S" | End -> "E"

(* Print the obtained maze *)
let print_maze =
Array.iter
(fun line ->
Array.iter (fun x -> print_string (aspect x)) line;
print_newline())

(* Generate a new fixed-size maze *)
let create_maze() =
let maze = Array.make_matrix 10 10 Border in

(* Step 1 *)
for x = 1 to 8 do
for y = 1 to 8 do
maze.(y).(x) <- Wall
done
done;

(* Step 2 *)
maze.(1).(0) <- Start;
maze.(8).(9) <- End;

(* Step 3 *)
let (put_slow,get_slow) = (* Slow exploration *)
let queue = Queue.create() in
(fun x -> Queue.push x queue),(fun () -> Queue.pop queue)
and (put_fast,get_fast) = (* Tendrils *)
let stack = Stack.create() in
(fun x -> Stack.push x stack),(fun () -> Stack.pop stack)
in

put_fast (1,1);

while maze.(8).(8) <> Pass do
let (x,y) = try get_fast () with Stack.Empty -> get_slow () in
maze.(y).(x) <- Pass;

(* Examine neighbors in random order *)
let neighbors =
List.sort
(fun _ _ -> Random.int 3 - 1)
[ (x+1,y); (x,y+1); (x-1,y); (x,y-1) ]

in List.iter
(fun (x,y) ->
if maze.(y).(x) = Wall then
if Random.int 10 > 0 then put_fast (x,y)
else put_slow (x,y))
neighbors;
done;

(* Return the obtained maze *)
maze

let _ = print_maze (create_maze ())

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
Quote:
Original post by doctorsixstring
I doubt the Python code is any faster, but I think it is significantly easier to read and understand (no offense to pascalosti or ToohrVyk ).


I certaintly won't disagree with that! C++ is often a very bad idea for small-to-medium problems such as this one, and sometimes a bad idea for larger problems as well.

While we're at it:

*** Source Snippet Removed ***


Out of curiosity, what language is that? I don't recognise it at all. It looks like a functional language, at a guess...

Share this post


Link to post
Share on other sites
Quote:
Original post by TheUnbeliever
Out of curiosity, what language is that? I don't recognise it at all. It looks like a functional language, at a guess...


Objective Caml.

Share this post


Link to post
Share on other sites
I'm having trouble running the C++ code

It does not recognize
#include <pair> (or pair.h)
I can comment it out and it works fine until
I try
"works.setup_map()" function
then i get 25 errors

Share this post


Link to post
Share on other sites
Still get the same 25 errors,
here are some of the errors... (which are beyond me)


Error 2 error C3203: 'vector' : unspecialized class template can't be used as a template argument for template parameter '_Container', expected a real type


Error 3 error C2825: '_Container': must be a class or namespace when followed by '::'


Error 6 error C2602: 'std::priority_queue<_Ty,_Container,_Pr>::value_type' is not a member of a base class of 'std::priority_queue<_Ty,_Container,_Pr>'

Share this post


Link to post
Share on other sites
std::priority_queue<pos,std::vector,comp> candidates;

What it's saying is that this std::vector is unspeciallised (as opposed to speciallised eg. std:vector<int>) The priority queue wants a vector of something.

Maybe ToohrVyk can fill you in. He did mention it was untested and full of errors.

Share this post


Link to post
Share on other sites
Ok just checked docos because it compiled fine on VS05 turns out VS allows template template paramaters for the second template param but the standard doesnt :)

change
std::priority_queue<pos,std::vector,comp> candidates;
to
std::priority_queue<pos,std::vector<pos>,comp> candidates;
and it should work

Share this post


Link to post
Share on other sites
took the liberty to read through the code, and found a few mistakes:
// in generate_borders()
if (x == 0 || x == Width - 1 || y == 0 || y == Width - 1)
// should be
if (x == 0 || x == Width - 1 || y == 0 || y == Height - 1)

// in compute_path()
for(;;)
// should imho be (for clarity)
while(true)
// or preferably (perhaps with some checks after the loop)
while( !candidates.empy() ) // to avoid calling candidates.top(); when candidates is empty

// in compute_path()
if (next = pos(Width-2,Height-2)) break;
//should probably be
if (next == pos(Width-2,Height-2)) break;

Share this post


Link to post
Share on other sites
All proposed corrections are necessary and justified. I should probably install a C++ compiler on this computer :) although I disagree with the for(;;) versus while (true) issue. An alternative would have been:

for(;;)
{
assert (!candidates.empty());
// .. code
}

Share this post


Link to post
Share on other sites
For the life of me I could not figure out how to read from the map.
I can assign stuff

creator(2,2) = START; //works fine

when i read

cout << creator(x,y); // I get an offbeat number (pointer address guessing)

And im not sure how to use and iterator on something like this.


here is the code minus the errors,
after this is main, what ive tried.

#include <iostream>
#include <vector>
#include <queue>

#include <utility>
#include <cassert>
#include <cstdlib>

// What a tile is. Silly numeric values, but we don't care.
enum tile_type
{
START = 33,
END = 77,
BORDER = 66,
WALL = 22,
PASS = 55
};

// What a map is. We assume here that maps are always of fixed size.
template<int Width, int Height>
class map
{
// The tiles inside the map. It is a private member, so we
// access its values using operator()
tile_type tiles[Width][Height];

public:

// Access a map tile as read/write
tile_type & operator()(int x,int y)
{
assert (x >= 0);
assert (x < Width);
assert (y >= 0);
assert (y < Height);

return this->tiles[x][y];
}

// Access a map tile as read-only
const tile_type & operator()(int x,int y) const
{
assert (x >= 0);
assert (x < Width);
assert (y >= 0);
assert (y < Height);

return this->tiles[x][y];
}

// A static function for returning a freshly initialized
// map.
static map setup_map()
{
map created;
generate_borders(created);
place_start_end(created);
compute_path(created);
return created;
}



private:

// Private implementation of the first step of map generation:
// we initialize a border around the map, and anything
// else to a wall.

static void generate_borders(map & where)
{
for (int x = 0; x < Width; ++x)
for (int y = 0; y < Height; ++y)
{
where(x,y) = WALL;
if (x == 0 || x == Width - 1 || y == 0 || y == Height - 1)
where(x,y) = BORDER;
}
}

// Private implementation of the second step of map generation:
// we place a "start" and "end" tile on our map.

static void place_start_end(map & where)
{
where(0,1) = START;
where(Width-1,Height-2) = END;
}

// Private implementation of the third step of map generation:
// we find a connex set of passable tiles which joins the start
// and end tiles.

// The algorithm consists in exploring the map from the
// top left corner. Each tile has a threshold value
// computed initially, which we use to determine which
// tile is computed next. Once we have reached the bottom
// right tile (and the exit), we cease exploration.

typedef std::pair<int,int> pos;

// The sole purpose of the thresholds is to compare the
// positions in the priority queue. So, we store them as
// part of a comparison structure between positions. So:
class comp
{
// Data
unsigned int tresholds[Width][Height];

public:

// Constructor
comp()
{
for (int x = 0; x < Width; ++x)
for (int y = 0; y < Height; ++y)
{
tresholds[x][y] = std::rand();
}
}

// Comparator
bool operator()(const pos & a, const pos & b) const
{
return (tresholds[a.first][a.second] < tresholds[b.first][b.second]);
}
};

static void compute_path(map & where)
{
// The priority queue is used to determine which wall should
// be turned into a passable element next. It is initialized with
// the top left element.
std::priority_queue<pos,std::vector<pos>,comp> candidates;

candidates.push(pos(1,1));

// Explore until we find the exit.
//while( !candidates.empty() )
for(;;)
{
assert (!candidates.empty());
pos next = candidates.top();
candidates.pop();

int x = next.first, y = next.second;

// This tile has already been explored
if (where(x,y) == PASS) continue;

where(x,y) = PASS;

// We have reached the exit!
if (next == pos(Width-2,Height-2)) break;

// Otherwise, explore the adjacent tiles.
pos around[] = { pos(x-1,y), pos(x,y-1), pos(x+1,y), pos(x,y+1) };
for (int i = 0; i < 4; ++i)
{
// To determine if they are worth adding to the candidates
// (i.e. they have not been explored yet)
if (where(around[i].first,around[i].second) == WALL)
{
candidates.push(around[i]);
}
}
}
}

}; // map<W,H> class



and

#include "stdafx.h"
#include "TheBrain.h"
#include <iterator>
#include <iostream>

#define ArraySize 10

using std::cout;



int _tmain(int argc, _TCHAR* argv[])
{

map<ArraySize, ArraySize> creator;
//map<ArraySize, ArraySize> *creator;
//creator->setup_map();
creator.setup_map();

//map<int, int>::iterator begin = creator.begin;

creator(2,2) = START;

for(int x = 0; x < ArraySize; x++)
for(int y = 0; y < ArraySize; y++) {
cout << creator(x,y);

if(y == ArraySize)
cout << std::endl; }



cout << std::endl;
return 0;
}

Share this post


Link to post
Share on other sites
setup_map is static, so what you are getting is garbage values, here are a few versions that does what you want, choose whichever you like(though the first one is preferred).

typedef map<ArraySize, ArraySize> MyMap; // for easy typing

// method 1
MyMap map (MyMap::setup_map());
// method 2
MyMap map = MyMap::setup_map();
// method 3
MyMap map;
map = MyMap::setup_map();

Share this post


Link to post
Share on other sites

This topic is 3928 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this