Jump to content
  • Advertisement
Sign in to follow this  
pascalosti

Please dont Ban me....

This topic is 4215 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
Advertisement
Ok..? Are you asking a question? If your trying to show something, a huge page of code doesn't help. What is the point of this post?

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.first,around.second) == WALL)
{
candidates.push(around);
}
}
}
}

}; // 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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!