Квест для программистов

Модератор: Бессмертные

Ответить
Orlangur
c7i.team
Сообщения: 151
Зарегистрирован: Сб янв 07, 2006 12:59 pm

Квест для программистов

Сообщение Orlangur » Вт окт 06, 2009 11:43 pm

Нужно написать алгоритм, который бы рисовал карту зоны. Есть массив комнат с выходами, каждой комнате нужно назначить целочисленные координаты.
Предполагается, что получающийся граф - планарный; если граф не планарный, то желательно, чтобы было минимальное количество пересечений ребер.
Также для упрощения можно считать, что выходов всего 4 (nesw).

Код: Выделить всё

class Door
{
public:
    Room *getRoom() const;
    bool  isOneside() const;
};

struct Room
{
    struct Exit
    {
        Door *door;

        Exit() : door(0) {}
    };

    Exit exits[6];
 
    int x, y, z;
};
Выходы в exits нумеруются north, east, south, west, up, down.
Исходно дан массив Room* rooms[N], нужно назначить всем комнатам координаты x, y, z.

Нужно, чтобы алгоритм корректно работал в подобных случаях:

Код: Выделить всё

*---*---*---*
|   |       
|   *
|           
*---*---*---*


*---*---*---*
|           |
*---*-------*
Ожидается код на c/c++. Результаты можно слать на admin@c7i.ru.
Написавшему - приятная плюшка.

Danteus
Сообщения: 4
Зарегистрирован: Вт окт 06, 2009 8:23 pm

Сообщение Danteus » Ср окт 07, 2009 1:23 pm

Написал алгоритм.
Корректно обрабатывает ситуации вроде

Код: Выделить всё



  *--*--*--*   
  |
  *---*-*-*   
  |   |   |
  |   *   |
  |   |   |
  |   *   |
  |   |   |
  |   *   |
  *-*-----*
  

  
Работает в плоскости.

Написан на c#, особого смысла переписывать на плюсу я не вижу, т.к. сам алгоритм довольно прост, а адаптировать к реальным данным все равно придется.

Если подходит в таком виде - могу на днях коротко описать и откомментировать.

зы. На больших картах не пробовал, но идея правильная и должна работать. Возможно после небольшой доработки :)

Orlangur
c7i.team
Сообщения: 151
Зарегистрирован: Сб янв 07, 2006 12:59 pm

Сообщение Orlangur » Чт окт 08, 2009 4:29 pm

Да, шли с небольшими комментами на admin@c7i.ru, посмотрим.

Orlangur
c7i.team
Сообщения: 151
Зарегистрирован: Сб янв 07, 2006 12:59 pm

Сообщение Orlangur » Чт окт 15, 2009 10:36 pm

Замечу, что квест пока никто не сделал.

Orlangur
c7i.team
Сообщения: 151
Зарегистрирован: Сб янв 07, 2006 12:59 pm

Сообщение Orlangur » Вт окт 27, 2009 10:45 pm

Текущие алгоритмы (1) не работают также на карте вида

Код: Выделить всё

 5---6-------7
 |   |       |
 |   8---9   |
 |           |
 1---2---3---4

Ответить