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

[Orlangur]

Нужно написать алгоритм, который бы рисовал карту зоны. Есть массив комнат с выходами, каждой комнате нужно назначить целочисленные координаты.
Предполагается, что получающийся граф - планарный; если граф не планарный, то желательно, чтобы было минимальное количество пересечений ребер.
Также для упрощения можно считать, что выходов всего 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]

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

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

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

  

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

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

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

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

[Orlangur]

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

[Orlangur]

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

[Orlangur]

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

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

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