Генерация лабиринта


Я работаю на генератор лабиринта на С++ в стремлении выучить язык и освежить в памяти некоторые давно потерянных знаний. Я хочу убедиться, что я, используя лучшие практики, и на самом деле делать вещи так, что они должны быть сделаны.

Мой код благополучно скрываются в репозитории GitHub. Я хотел бы иметь двух конкретных классов обзор: Лабиринт.ч (154 строк) (и MazeConstants.ч если это возможно), а также MazePosition.ч (45 строк).

У меня тоже была пара вопросов. Целесообразно ли перегрузить оператор!= в дополнение к оператор==? Я перегрузка оператора== в MazePosition класса, но не оператор!=. Это хорошая практика, чтобы обеспечить конструкторы копирования и перегруженные операторы присваивания, а? Я в основном путают о передовой практике в этих областях, и информацию я нашел в интернете была скудной и в основном только страницы с иллюстрированными примерами. Я планирую отключить какой-либо копировать способности в Лабиринте.класс H на что-то подобное: (boost.org/doc/libs/1_47_0/boost/noncopyable.hpp) потому что нет смысла копировать этот объект по какой-либо причине (слишком медленно, да?).

Файл: MazePosition.ч (45 строк)

/*
* File: MazePosition.h
* Author: mattosaurus
*
* Created on August 6, 2011, 4:26 PM
*/

#ifndef MAZEPOSITION_H
#define MAZEPOSITION_H

class MazePosition{
public:
    MazePosition(int row, int col) : _row(row), _col(col){}

    int getRow() const{
        return _row;
    }
    int getCol() const{
        return _col;
    }

    MazePosition operator+(MazePosition & p2) const{
        int newX = _row + p2.getRow();
        int newY = _col + p2.getCol();
        MazePosition local(newX, newY);
        return local;
    }

    friend bool operator==(MazePosition const&p1, MazePosition const&p2);

private:
    int _row;
    int _col;

};
bool operator==(MazePosition const&p1, MazePosition const&p2) {
        if(p1.getRow() == p2.getRow()){
            return (p1.getCol() == p2.getCol());
        }
        return false;
    }

#endif /* MAZEPOSITION_H */

Файл: Лабиринт.ч (145 строк)

/*
* File: Maze.h
* Author: mattosaurus
*
* Created on August 5, 2011, 3:34 PM
*/

#ifndef MAZE_H
#define MAZE_H
#include <iostream>
#include <exception>
#include <time.h>
#include <vector>
#include <stack>
#include <algorithm>
#include <stdexcept>
#include "MazePosition.h"
#include "MazeConstants.h"
using std::vector;
using std::stack;
typedef vector< vector<int> > IntMaze;
class Maze {
public:
    Maze(int width, int height) : _width(width+2), _height(height+2), _maze(_height, vector<int>(_width))
    {
        MazeInit(_maze, MazeConstants::UNVISITED);
        MazeCarve(_maze, _exitList);
    }

    int getHeight(){
      return _height;
    }
    int getWidth(){
      return _width;
    }

    void MazeInit( IntMaze & maze, int init){
        //initialize all cells to 0 (unvisited)
        //surround with a border of out of bounds cells (-1)

        for(int i = 0; i < maze.capacity(); i++){
            for(int j = 0; j < maze.at(i).capacity(); j++){
                if(i == 0 || i == maze.capacity() -1 ){
                   maze.at(i).at(j) = MazeConstants::INVALID;
                }
                else if(j == 0 || j == maze.at(i).capacity() -1 ){
                    maze.at(i).at(j) = MazeConstants::INVALID;
                }
                else{
                    maze.at(i).at(j) = init;
                }
            }
        }//end initial initialization
    }

    void MazeCarve(IntMaze & maze, vector<MazePosition> & exitList){
        //Pick a starting location (pick something along the height(x) and width(0).
        int row = (rand() % (_height));
        int col = (rand() % (_width));

        MazePosition start(row, col);

        //mark start as visited (non-zero)
        maze.at(start.getRow()).at(start.getCol()) = MazeConstants::START;

        //begin the grunt work
        CarveFrom(maze, start, exitList);
    }

    void CarveFrom(IntMaze & maze, MazePosition & start, vector<MazePosition> & exitList){

        vector<MazePosition> dirCopy = MazeConstants::directions;
        std::random_shuffle(dirCopy.begin(), dirCopy.end());

        for(int i = 0; i < dirCopy.size(); i++){
            MazePosition temp = dirCopy.at(i);
            MazePosition newPos = start + temp;
            //is position valid
            int tile;
            try{
                tile = maze.at(newPos.getRow()).at(newPos.getCol());
            }
            catch(std::out_of_range e){
                continue;
            }
            if(tile == MazeConstants::INVALID){
                exitList.push_back(temp);
                continue;
            }
            if(tile == MazeConstants::UNVISITED){
                maze.at(newPos.getRow()).at(newPos.getCol()) = MazeConstants::FLOOR;
                //since we jump multiple tiles, set the prev one to FLOOR

                //we came from the south
                if(MazeConstants::N == temp){
                    maze.at(newPos.getRow() -1).at(newPos.getCol()) = MazeConstants::FLOOR;
                }
                //came from north
                if( temp == MazeConstants::S ){
                    maze.at(newPos.getRow()+1).at(newPos.getCol()) = MazeConstants::FLOOR;
                }
                //came from west
                if(MazeConstants::E ==temp){
                    maze.at(newPos.getRow()).at(newPos.getCol()-1) = MazeConstants::FLOOR;
                }
                //came from east
                if(MazeConstants::W == temp){
                    maze.at(newPos.getRow()).at(newPos.getCol()+1) = MazeConstants::FLOOR;
                }
                //start looking at the new spot.
                CarveFrom(maze, newPos, exitList);
            }
        }
    }

    friend std::ostream& operator<<(std::ostream& stream, const Maze& m);

private:
    const int _height;
    const int _width;
    IntMaze _maze;
    vector<MazePosition> _exitList;
};

std::ostream& operator<<(std::ostream& stream, const Maze& m) {
    for(int i = 0; i < m._maze.capacity(); i++){
        for(int j = 0; j < m._maze.at(i).capacity(); j++){

/*
* this was added for the pgm output to make things look
* more uniform on the final image, instead of two shades for out of bounds squares.
* Internally, the maze still uses 1 for unvisited - and 0 for invalid. These are only
* altered artificially when the maze is being sent to cout.
*/

int temp = m._maze.at(i).at(j);
if(temp == MazeConstants::UNVISITED){
stream << (temp-1) << " ";

}
else{
stream << temp << " ";

}
        }
        stream << std::endl;
    }
    return stream;
}


#endif /* MAZE_H */


2317
10
задан 2 сентября 2011 в 05:09 Источник Поделиться
Комментарии
4 ответа

Моя самая большая проблема:

Зачем тебе раскрыть внутренние члены через геттеры!!!
Другие люди должны знать, что положение точки в MazeLocation?

int getRow() const{
return _row;
}
int getCol() const{
return _col;
}

И

int getHeight(){
return _height;
}
int getWidth(){
return _width;
}

Выставляя их плотно связывает ваш объект все, что использует их. Насколько я могу сказать единственное, что когда-нибудь понадобится, чтобы знать позицию лабиринт-это лабиринт. Таким образом, вы должны принять 'Лабиринт' друг 'MazePosition и снять геттеры (если вы намерены тесно связать вместе количество Привязок как можно меньше.

Как отмечено в другом месте: вам нужно всего лишь использовать в() если у вас есть непроверенный входного сигнала и используют его для индексации массива. Ваш код использует проверку ввода (как вы цикл от начала до конца), к сожалению, вы делаете ошибку, используя емкость (), а не размер() который является, почему он бросал.

for(int j = 0; j < maze[i].size(); j++)
{ // ^^^^^^
maze[i][j] = MazeConstants::INVALID;
// ^^^^^^ guranteed to be good

Но я бы предпочел итераторы пользователей:

for(IntMaze::iterator loop = maze.begin(); loop != maze.end(); ++loop)
{ // ^^ Prefer pre-increment

for(IntRow::iterator inner = loop->begin(); inner != loop->end(); ++inner)
{

Это делает код легче перевести на стандартные алгоритмы, когда вы узнаете, как использовать их.

10
ответ дан 2 сентября 2011 в 06:09 Источник Поделиться


  1. Если вы перегружаете оператор, убедитесь, что соответствующие операторы ведут себя соответственно - в вашем случае: да, перегрузка !=. Убедитесь, не копировать вставить код, но вызвать оператор == вместо (или ее реализации).

  2. Всегда обеспечивают копирования и операторы присваивания. Если этого не сделать, документ, почему операторы по умолчанию работать. Если вы не хотите копировать / присваивать объекты этого типа (может быть дороже), сделать их частными, а не реализации. Таким образом, вы случайно не скопировать объект, а не копировать.

Читайте хорошие c++ книг, таких как эффективное С++ и более эффективный с++ Скотт Мейерс. Он дает много подсказок о подводных камнях в C++.


Замечание комментировать, когда по умолчанию сделать: да, есть такие (простые) объекты, где по умолчанию сделать. Еще для обслуживания важно определить, является ли автор класса знают, что по умолчанию работает или просто забыли запретить их. Поэтому документирую этот факт необходимо. Вы не можете отличить класс, где кто-то сознательно опирается на механизм по умолчанию или просто забыли выполнить или запретить конструктор копирования / оператор присваивания.

С комментарием на месте легко. В классе есть 3 возможности:


  • настраиваемое копирование и присваивание

  • запрещено копирование и присваивание

  • комментарий о том, что по умолчанию работать

Все остальное-ошибка.

6
ответ дан 2 сентября 2011 в 08:09 Источник Поделиться

Вы растратите СТД::вектор, вы должны взглянуть на ссылку.


  • Вы должны использовать размер() вместо потенциала().

  • Вы могли бы использовать [Х] вместо .в(Х).

Вы ждете out_of_range исключение?

        try{
tile = maze.at(newPos.getRow()).at(newPos.getCol());
}
catch(std::out_of_range e){
continue;
}

Обработка исключений не должна быть частью вашей обычной программной логике, это должно произойти только в "исключительных ситуациях".

Друг декларация не нужна.

"friend bool operator==(MazePosition const&p1, MazePosition const&p2);"

Предложение для MazeInit:

void MazeInit( IntMaze & maze, int init)
{
maze_.clear();
maze_.resize(_height, vector<int>(_width, init));

// Put the borders to MazeConstants::INVALID
std::fill(maze_.front().begin(), maze_.front().end(), MazeConstants::INVALID);
std::fill(maze_.back().begin(), maze_.back().end(), MazeConstants::INVALID);
std::for_each(maze_.begin(), maze_.end(), [](const std::vector<int>& row)
{
row.front() = MazeConstants::INVALID;
row.back() = MazeConstants::INVALID;
});
}

5
ответ дан 2 сентября 2011 в 10:09 Источник Поделиться

Некоторые другие отметить хорошие моменты. Я хотел бы сделать точку или два в общей читабельности.

Это очень трудно для меня, чтобы посмотреть на этот код со стороны и осознать, что он делает. Вот список вещей, которые я думаю, могли бы улучшить общую атмосферу кодекса.


  • Поставил новые строки между заголовком Guard, ваш код#include директивы, "используя"и т. д. и определения классов. Когда я прочитал заголовок, бывший категорий следует читать как котел-плиту и определение класса-это то, что должно торчать. Не разделив их визуально, некоторые люди могут взглянуть на важные детали.

    На самом деле, это опрометчиво положить использования внутри заголовка, потому что это может привести к имени столкновения с файлами, который может включать вы и хотите использовать эти имена.


  • MazeInit и MazeCarve. Зачем начинать эти имена с Лабиринта? Ты уже в Лабиринте класса.

  • MazeInit кажется очень многословный способ обнулить буфер. Обратите внимание, что СТД::вектор::размер можно задать элементы массива в какое-то первоначальное значение. Я думаю что-то вроде этого:

    std::vector&lt;int&gt; initialValues;

    initialValues.resize(width, MazeConstants::INVALID);
    maze.resize(height, initialValues);</pre></p>


  • Это немного трудно для меня, чтобы догадаться, что дележка делает. Имена переменных, как температура не очень помогают. Я хотел бы добавить общий комментарий для описания техники. Существующие комментарии в этой функции допустим, вы уже знаете алгоритм - например. "пришли с востока" - да? Я уверен, что имеет смысл в контексте алгоритма, но если Вы читаете это в первый раз это не очевидно. (Я бы также попытаться сделать эту функцию немного меньше повторов... есть некоторые, как вы можете выразить разные стороны Восток/Запад/Север/Юг как массив констант в цикле и выполнения повторяющихся действий?)

    Также у меня есть некоторые моменты, касающиеся представления данных и памяти макет, который я хотел бы поднять... эти придирчивые и я не обязательно предлагаю вам переписать ваш код, просто прошу подумать об этом, как мысленный эксперимент.


  • Я могу вам запылали от c++ люди, которые ненавидят стиле C, но вы можете также представить различные представления для матрицы. Один из подходов мог бы заключаться в отбрасывании контейнеры STL; простой целочисленный массив может делать, а может вам лучше с памятью, чем косвенность-Ладена векторС. (С вектором>каждый доступ имеет 2 указатель разыменовывает, а строки являются потенциально несмежные.) Она будет также изменить вашу инициализации просто остановлюсь и не выполнять каких-либо дополнительных ассигнований. Это, вероятно, не сделать огромную разницу на производительность и немного религиозный вопрос для некоторых; принять это предложение с недоверием.

  • А на тему альтернативной матрицы представлений, другой подход мог бы перейти от вектора> просто 1-мерный вектор; доступ к местоположения (Х,Y) тогда бы стало выходом из (м * ширина + х). Как и в стиле языка C подход, это также даст вам меньше косвенности при доступе к элементам (1 указателю вместо 2-х смежных элементов), хотя вы, возможно, придется скорректировать некоторые петли так, что они написаны в "построчно" моды. Будьте осторожны об этом умножение в каждой точке, потому что в моем опыте, которые могут добавить вверх.

4
ответ дан 5 сентября 2011 в 06:09 Источник Поделиться