Messages

1

General / I'm doing it wrong.

« on: October 21, 2014, 04:02:09 am »

http://pastebin.com/Ur0esPzB

//============================================================================
// Name        : PrimsAlgorithm.cpp
// Author      : Dean Sands
// Version     : 0.0.1a
// Copyright   : I will set your flamingos on fire.
// Description : Prim's Minimum Spanning Tree Maze Creator
//============================================================================
 
 
#include <SFML/Graphics.hpp>
#include <unordered_map>
#include <vector>
#include <deque>
#include <iostream>
#include <cstdlib>
#include <climits>
#include <chrono>
#include <random>
#include <algorithm>
#include <set>
#pragma comment(lib,"glew.lib")
#pragma comment(lib,"sfml-system-d.lib")
#pragma comment(lib,"sfml-window-d.lib")
#pragma comment(lib,"sfml-graphics-d.lib")
 
#define WIDTH 40
#define HEIGHT 30
#define TOTAL (WIDTH*HEIGHT)
 
using namespace std;
 
 
struct node{
        float x;
        float y;
        node(float newX, float newY):x(newX),y(newY){}
};
 
 
struct edge{
        node *a;
        node *b;
        uint64_t weight;
        edge(node *newNodeA, node *newNodeB, uint64_t newWeight=0):a(newNodeA),b(newNodeB), weight(newWeight){}
        bool operator() (edge *i, edge *j) { return (i->weight<j->weight);}
        bool operator() (edge i, edge j) { return (i.weight<j.weight);}
};
 
 
 
set<node*> knownNodes;
set<node*> unknownNodes;
unordered_map<uint64_t, edge*> edgemap;
deque<edge*> edgeQueue;
vector<edge*> usedEdges;
vector<node*> nodelist;
std::mt19937_64 *generator;
 
node *addNode(float x, float y){
        node *newNode=new node(x,y);
        nodelist.push_back(newNode);
        unknownNodes.insert(newNode);
        return newNode;
}
 
void connectNodes(uint64_t a,uint64_t b){
        uint64_t weight;
        edge *newEdge = new edge(nodelist[a],nodelist[b]);
        do{
                weight=(*generator)();
        }while(edgemap.find(weight)!=edgemap.end());
        newEdge->weight=weight;
        edgemap[weight]=newEdge;
        edgeQueue.push_back(newEdge);
}
 
void createNodes(){
        int x=0, y=0;
        for(y=0;y<HEIGHT;y++)for(x=0;x<WIDTH;x++)addNode(x*20,y*20);
}
 
void createEdges(){
        int x=0, y=0;
        //Top row
        for(x=1;x<WIDTH;x++){
                uint64_t myNodeIndex=y*WIDTH+x;
                connectNodes(myNodeIndex-1,myNodeIndex);
        }
        for(y=1;y<HEIGHT;y++){
                for(x=1;x<WIDTH;x++){
                        uint64_t myNodeIndex=y*WIDTH+x;
                        connectNodes(myNodeIndex-1,myNodeIndex);
                        connectNodes(myNodeIndex-WIDTH,myNodeIndex);
                }
        }
}
void primsAlgorithm(){
        bool addA,addB;
        edge *currentEdge;
        node *nodeA, *nodeB;
        int i=0;
        while(!unknownNodes.empty()){
                auto currentEdgeIter = edgeQueue.begin();
                if (currentEdgeIter == edgeQueue.end()){ cout << "End of queue reached." << endl; break; }
                currentEdge = *currentEdgeIter;
                nodeA = currentEdge->a;
                nodeB=currentEdge->b;
                addA = (unknownNodes.find(nodeA) != unknownNodes.end());
                addB=(unknownNodes.find(nodeB)!=unknownNodes.end());
                if (!(addA || addB)) {
                        edgeQueue.pop_front();
                        continue;
                }
                usedEdges.push_back(currentEdge);
                if(addA){unknownNodes.erase(nodeA);}
                if(addB){unknownNodes.erase(nodeB);}
                edgeQueue.pop_front();
                i++;
                std::cout<<i<<endl;
        }
 
        while (!unknownNodes.empty()){
                auto nodeIter = unknownNodes.begin();
                auto nodeC = *nodeIter;
                cout << "Unknown Node:" << nodeC->x << "," << nodeC->y << endl;
                unknownNodes.erase(nodeIter);
        }
}
void display(){
        sf::RenderWindow window(sf::VideoMode(800, 600), "My window");
 
        // run the program as long as the window is open
        while (window.isOpen())
        {
                // check all the window's events that were triggered since the last iteration of the loop
                sf::Event event;
                while (window.pollEvent(event))
                {
                        // "close requested" event: we close the window
                        if (event.type == sf::Event::Closed)
                                window.close();
                        // "close requested" event: we close the window
                        if (event.type == sf::Event::KeyPressed)
                                if (event.key.code == sf::Keyboard::Escape)
                                window.close();
                }
 
                // clear the window with black color
                window.clear(sf::Color::Black);
 
                for(auto thisEdge:usedEdges){
                        sf::Vertex line[] =
                        {
                            sf::Vertex(sf::Vector2f(thisEdge->a->x, thisEdge->a->y)),
                            sf::Vertex(sf::Vector2f(thisEdge->b->x, thisEdge->b->y))
                        };
 
                        window.draw(line, 2, sf::Lines);
                }
 
                for(auto c:nodelist){
                        // define a circle with radius = 5
                        sf::CircleShape *circle=new sf::CircleShape(5);
                        circle->setOrigin(c->x,c->y);
 
                        // change the number of sides (points) to 8
                        circle->setPointCount(8);
                        circle->setFillColor(sf::Color(250, 100, 50));
                        window.draw(*circle);
                        delete circle;
                }
 
                // end the current frame
                window.display();
        }
}
void cleanup(){
        // ******** //
                for(auto nodeX:nodelist){
                        delete nodeX;
                }
                for(auto edgeX:edgemap){
                        delete edgeX.second;
                }
}
 
int main(void) {
        unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
        generator = new std::mt19937_64(seed);
        createNodes();
        cout<<"nodes created."<<endl;
        createEdges();
        cout<<"edges created"<<endl;
        sort(edgeQueue.begin(),edgeQueue.end());
        cout<<"edges sorted"<<endl;
        primsAlgorithm();
        cout<<"edges primmed"<<endl;
        display();
        cout<<"edges displayed"<<endl;
        cleanup();
        cout<<"nodes and edges cleaned"<<endl;
        return EXIT_SUCCESS;
}

I'm trying to use Prim's Minimal Spanning Tree Algorithm to make a maze. I'm clearly doing it wrong.

It should create a maze where the white lines are the actual maze, not the walls. The nodes (rooms) should be marked with circles.
Any thoughts?