Public Group

# 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.

## 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 on other sites
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 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 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 on other sites
Ugly code won't get you banned. Check out the rules for information about what will get you banned.

##### Share on other sites
Python to the rescue!

import time, os# I've replaced the numeric constants with characters that make a prettier animationTILE_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 descriptionmap = 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 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 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)

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

@Alpha_ProgDes: phew++

##### 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 on other sites
Quote:
 Original post by doctorsixstringI 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 ())

1. 1
2. 2
3. 3
Rutin
14
4. 4
5. 5

• 12
• 15
• 9
• 14
• 10
• ### Forum Statistics

• Total Topics
632655
• Total Posts
3007675
• ### Who's Online (See full list)

There are no registered users currently online

×