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?
