TrianGO
A game of GO on triangles
A. First Edition
This is my project of comp6711 and it is an interesting little game of triangles which simulates some feature
of game GO.
To best understand the game, you may need to download a demo slides from here.
¡¡
¡¡
¡¡
In order to run in OpenGL, you need download "glut32.dll" and "glu32.dll" in your system folder.
i.e. c:\windows\system32
And to compile the code, you need to link with "openGL32.lib, glut32.lib, glu32.lib" in your vc6++.
¡¡
¡¡
E.Further improvement
Compilation:
a) This project only uses common glu and glut as library.
b) In case when system is not installed with these library, copy glu32.lib, glut32.lib to library path of Visual C++ 6.0. For example, the path may look like this:
C:\Program Files\Microsoft Visual Studio\VC98\Lib
c) My code will automatically add libs into project by macros, so you don¡¯t have to add these libs into your Visual6.0 project file setting by hand.
Running:
a) In system where glu or glut library are not installed, as long as you keep glu32.dll and glut32.dll in same directory with executable file ¡°TrianGO.exe¡± it should be able to run correctly.
Operation:
a) create random points: by right click mouse or press ¡®n¡¯;
b) create nested convex hull: by press ¡®n¡¯.
c) create triangulation: press ¡®t¡¯.
d) start playing: left click triangles in chess board.
restart: press ¡®a¡¯ to clear everything.
To show menu: press ¡®m¡¯
To exit: press ¡®esc¡¯
¡¡
F.File listing
1. common.h
2. common.cpp
3. ConvexHull.h
4. ConvexHull.cpp
5. main.cpp
¡¡
file name: common.h
#ifndef COMMON_H
#define COMMON_H
#include <set>
#include <vector>
#include <deque>
using namespace std;
#pragma comment(lib, "opengl32.lib")
#pragma comment(lib, "glu32.lib")
#pragma comment(lib, "glut32.lib")
const int winPos_x=0, winPos_y=0;
const int winSize_width=600, winSize_height=600;
static const char* windowTitle="Convex Hull Demo";
const int MaxIntegerValue=winSize_width/2-30;
typedef float TColor[3];
typedef float TVector2[2];
static TColor red={1,0,0}, green={0,1,0}, blue={0,0,1}, yellow={0,1,1}, beige={1,1,0};
typedef float TPlayerColors[2][3];
static float playerColor[3][3]={{1,0,0}, {0,0,1}, {0,1,1}};
struct TTriangle;
enum FaceStatus
{
Red=0, Blue=1, Empty=2
};
struct TPoint
{
float x;
float y;
const TPoint& operator=(const TPoint& other)
{
x=other.x;
y=other.y;
return *this;
}
TPoint(){;}
TPoint(float theX, float theY)
{
x=theX;
y=theY;
}
void display() const;
void display();
};
struct PrevPoint
{
bool operator()(const TPoint& first, const TPoint& second)
{
if (first.x==second.x)
{
return first.y>second.y;
}
else
{
return first.x<second.x;
}
}
bool operator()(const TPoint& first, const TPoint& second) const
{
if (first.x==second.x)
{
return first.y>second.y;
}
else
{
return first.x<second.x;
}
}
};
static PrevPoint prevPoint;
struct TPointContext
{
TPoint point;
TColor pointColor;
};
int compPoint(const void* elem1, const void* elem2);
float direction(TPoint* p, TPoint* q, TPoint* r);
float generateRandomValue();
void generatePoint(int pointNumber, TPoint*& ptrArray);
typedef TPoint TTriPoint[3];
typedef set<TPoint, PrevPoint> TPointSet;
typedef vector<TPoint> TPointVector;
typedef deque<TPoint> TPointQueue;
typedef deque<TTriangle> TTriangleQueue;
const TPointSet& setCopy(TPointSet& dest, const TPointSet& source);
void generateRandomPoint(int pointNumber, TPointSet& pointSet);
struct TTriangle
{
TTriPoint triangle;
void assign(TPoint p1, TPoint p2, TPoint p3);
bool pointInside(TPoint& point);
void display();
void draw();
TTriangle& operator=(TTriangle& other)
{
for (int i=0; i<3; i++)
{
triangle[i]=other.triangle[i];
}
return *this;
}
};
struct TEdge;
struct TFace;
typedef TEdge* TTripleEdgePtr[3];
typedef TPoint TPairPoint[2];
//undirected edge
struct TEdge
{
TPairPoint pairPoint;
TColor color;
TFace* faces[2];
void display();
void draw();
};
struct PrevEdge
{
//assume the point in edge is sorted when constructed.
//that is, pointPair[0]<pointPair[1]
bool operator()(TEdge* first, TEdge* second)
{
for (int i=0; i<2; i++)
{
if (prevPoint(first->pairPoint[i], second->pairPoint[i]))
{
return true;
}
if (prevPoint(second->pairPoint[i], first->pairPoint[i]))
{
return false;
}
}
//equal edge
return false;
}
bool operator()(TEdge* first, TEdge* second) const
{
for (int i=0; i<2; i++)
{
if (prevPoint(first->pairPoint[i], second->pairPoint[i]))
{
return true;
}
if (prevPoint(second->pairPoint[i], first->pairPoint[i]))
{
return false;
}
}
//equal edge
return false;
}
};
static PrevEdge prevEdge;
typedef set<TEdge*, PrevEdge> TEdgePtrSet;
struct TFace
{
TTripleEdgePtr edges;
TColor color;
FaceStatus status;
bool pointInside(TPoint& point);
void display();
void draw();
};
struct PrevFace
{
//assume three edges are sorted in TFace
bool operator()(TFace* first, TFace* second)
{
for (int i=0; i<3; i++)
{
if (prevEdge(first->edges[i], second->edges[i]))
{
return true;
}
if (prevEdge(second->edges[i], first->edges[i]))
{
return false;
}
}
//if both equal
return false;
}
bool operator()(TFace* first, TFace* second) const
{
for (int i=0; i<3; i++)
{
if (prevEdge(first->edges[i], second->edges[i]))
{
return true;
}
if (prevEdge(second->edges[i], first->edges[i]))
{
return false;
}
}
//if both equal
return false;
}
};
typedef set<TFace*, PrevFace> TFacePtrSet;
typedef set<TFace*> TFacePointerSet;
typedef vector<TFace*> TFacePtrVector;
#endif
¡¡
¡¡
file name: common.cpp
#include "common.h"
#include <GL/glut.h>
#include <iostream>
using namespace std;
float direction(TPoint* p, TPoint* q, TPoint* r)
{
return q->x*r->y +p->x*q->y+p->y*r->x - p->y*q->x - q->y*r->x -p->x*r->y;
}
int compPoint(const void* elem1, const void* elem2)
{
TPoint* ptr1, *ptr2;
ptr1=(TPoint*)elem1;
ptr2=(TPoint*)elem2;
return ptr1->x-ptr2->x;
}
void generateRandomPoint(int pointNumber, TPointSet& pointSet)
{
TPoint point;
pointSet.clear();
for (int i=0; i<pointNumber; i++)
{
point.x=generateRandomValue();
point.y=generateRandomValue();
pointSet.insert(point);
}
}
void TTriangle::draw()
{
glBegin(GL_POLYGON);
for (int i=0; i<3; i++)
{
glColor3fv(red);
glVertex2f(triangle[i].x, triangle[i].y);
}
glEnd();
}
void TTriangle::display()
{
for (int i=0; i<3; i++)
{
triangle[i].display();
}
}
void TPoint::display() const
{
printf("[x=%f,y=%f]\n", x, y);
}
void TPoint::display()
{
printf("[x=%f,y=%f]\n", x, y);
}
/*
void TMyPointSet::display()
{
for (TPointSet::const_iterator it=pointSet.begin(); it!=pointSet.end(); it++)
{
it->display();
}
}
void TMyPointSet::generatePoint(int pointNumber)
{
TPoint point;
pointSet.clear();
for (int i=0; i<pointNumber; i++)
{
point.x=generateRandomValue();
point.y=generateRandomValue();
pointSet.insert(point);
}
}
*/
const TPointSet& setCopy(TPointSet& dest, const TPointSet& source)
{
dest.clear();
TPointSet::const_iterator it;
for (it=source.begin(); it!=source.end(); it++)
{
dest.insert(*it);
}
return dest;
}
void TTriangle::assign(TPoint p1, TPoint p2, TPoint p3)
{
triangle[0]=p1;
triangle[1]=p2;
triangle[2]=p3;
}
bool TTriangle::pointInside(TPoint& point)
{
float result[3];
for (int i=0; i<3; i++)
{
result[i]=direction(triangle+i, triangle+(i+1)%3, &point);
}
return result[0]*result[1]>=0&&result[0]*result[2]>=0&&result[1]*result[2]>=0;
}
bool TFace::pointInside(TPoint& point)
{
float result[3];
TPoint points[3];
points[0]=edges[0]->pairPoint[0];
points[1]=edges[0]->pairPoint[1];
points[2]=edges[2]->pairPoint[1];
for (int i=0; i<3; i++)
{
result[i]=direction(points+i, points+(i+1)%3, &point);
}
return result[0]*result[1]>=0&&result[0]*result[2]>=0&&result[1]*result[2]>=0;
}
void TEdge::draw()
{
glLineWidth(1);
glBegin(GL_LINES);
for (int i=0; i<2; i++)
{
glColor3fv(color);
glVertex2f(pairPoint[i].x, pairPoint[i].y);
}
glEnd();
}
void TEdge::display()
{
printf("display edge\n");
for (int i=0; i<2; i++)
{
pairPoint[i].display();
}
}
void TFace::display()
{
printf("\n***************display face***********************\n");
for (int i=0; i<3; i++)
{
edges[i]->display();
}
}
//why is that sequence? because first edge must have the no.1, no2 vertex
//the last edge or 3rd edge's second vertex must be last one
void TFace::draw()
{
glBegin(GL_POLYGON);
glColor3fv(color);
glVertex2f(edges[0]->pairPoint[0].x, edges[0]->pairPoint[0].y);
glColor3fv(color);
glVertex2f(edges[0]->pairPoint[1].x, edges[0]->pairPoint[1].y);
glColor3fv(color);
glVertex2f(edges[2]->pairPoint[1].x, edges[2]->pairPoint[1].y);
glEnd();
for (int i=0; i<3; i++)
{
edges[i]->draw();
}
}
/*
void TMyPointSet::setArray(TPoint* inputArray, int inputNumber)
{
pointSet.clear();
pointSet.insert(inputArray, inputArray+inputNumber);
}
*/
float generateRandomValue()
{
float intPart, floatPart;
intPart=rand()%MaxIntegerValue * (rand()%2==0?1 : (-1));
floatPart=(float)rand()/(float)RAND_MAX;
return intPart+floatPart;
}
¡¡
file name: convex.h
#ifndef CONVEXHULL_H
#define CONVEXHULL_H
#include <vector>
//#include "DCEL.h"
#include <utility>
#include <GL/glut.h>
#include "common.h"
using namespace std;
struct TConvex;
struct TBoard;
typedef vector<TPointQueue> TPointQueueVector;
typedef pair<TPoint, TPoint> TPointPair;
typedef vector<TPointPair> TPointPairVector;
struct TConvex
{
TPointSet pointSet;
void collectVertexUp(TPointQueue&);
void collectVertexDown(TPointQueue&);
void addPoint(TPointQueue&, TPoint*);
int number;
void generatePoint(int pointNumber);
void display();
void convexHull(const TPointSet& inputSet, TPointQueue& pointqueue);
};
struct TNestConvex
{
static void nestConvex(const TPointSet& pointSet, TPointQueueVector& convexQueue);
static void triangulate(TPointQueueVector& convexQueue, TPointPairVector& pointPairVector);
//static void triangulate(TPointQueueVector& convexQueue, TTriangleQueue& triangleQueue);
static bool triangulate(TPointQueueVector& convexQueue, TBoard& board);
};
struct TBoard
{
TEdgePtrSet edgePtrSet;
TFacePtrSet facePtrSet;
int controlCounter[3];
void makeEdge(TPoint& p1, TPoint& p2, TEdge& result);
void makeFace(TPoint& p1, TPoint& p2, TPoint& p3, TFace& result);
void makeBoard(TTriangleQueue& triangleQueue);
bool insertFace(TPoint& p1, TPoint& p2, TPoint& p3);
void clear();
void draw();
void drawEdge();
void drawFace();
void display();
void displayFace();
TFace* linearSearch(TPoint& point);
//TFace* binarySearch(TPoint& point);
bool validMove(TFace* face, FaceStatus player, bool justTest=false);
//bool hasSpace(TFace* face, bool player);
bool sameColor(TFace* him, FaceStatus player);
bool isSurrounded(TFace* face, bool player);
void getNeighbour(TFace* face, TFace* neighbours[3]);
bool doSearchSpace(TFace* start, FaceStatus player, TFacePointerSet& path);
void removeEnemy(TFace* face, FaceStatus enemy);
int countTriangle();
bool controlBy(TFace* face, FaceStatus& status, TFacePointerSet& path);
};
class TPolygon
{
private:
int number;
TPoint* leftMost;
TPoint* rightMost;
public:
TPoint* ptrArray;
//TPolygon();
void createPolygon(int pointNumber, TPointQueue& pointQueue);
};
#endif
¡¡
file name: convex.cpp
#include <iostream>
#include <cmath>
#include <vector>
#include "common.h"
#include "ConvexHull.h"
using namespace std;
//GLenum drawingMode = GL_POINTS;
vector<TPointContext> separateVector;
vector<TPointContext> connectVector;
vector<TPointContext> polygonVector;
TPolygon polygon;
TConvex convex;
void TPolygon::createPolygon(int pointNumber, TPointQueue& pointQueue)
{
TPointContext pointContext;
number=pointNumber;
::generatePoint(pointNumber, ptrArray);
qsort(ptrArray, number, sizeof(TPoint), compPoint);
leftMost=ptrArray;
rightMost=ptrArray+number-1;
for (int i=0; i<number; i++)
{
if (direction(leftMost, rightMost, ptrArray+i)<=0)
{
pointQueue.push_back(ptrArray[i]);
}
else
{
pointQueue.push_front(ptrArray[i]);
}
}
}
/*
TPolygon::TPolygon()
{
createPolygon();
}
*/
void TConvex::generatePoint(int pointNumber)
{
number=pointNumber;
TPoint point;
for (int i=0; i<number; i++)
{
point.x=generateRandomValue();
point.y=generateRandomValue();
pointSet.insert(point);
}
}
void generatePoint(int pointNumber, TPoint*& ptrArray)
{
TPointContext pointContext;
ptrArray=new TPoint[pointNumber];
for (int i=0; i<pointNumber; i++)
{
ptrArray[i].x=generateRandomValue();
ptrArray[i].y=generateRandomValue();
pointContext.point=ptrArray[i];
memcpy(pointContext.pointColor, red, sizeof(TColor));
separateVector.push_back(pointContext);
//glutPostRedisplay();
glutSwapBuffers();
}
//glutPostRedisplay();
}
void TConvex::addPoint(TPointQueue& pointQueue, TPoint* pointPtr)
{
TPointQueue::reverse_iterator start, last;
while (pointQueue.size()>=2)
{
start=pointQueue.rbegin();
last=start;
start++;
if (direction(&(*start), &(*last), pointPtr)>=0)
{
pointQueue.pop_back();
}
else
{
break;
}
}
pointQueue.push_back(*pointPtr);
}
void TConvex::collectVertexUp(TPointQueue& pointQueue)
{
TPointSet::iterator it, stop;
it=pointSet.begin();
stop=pointSet.end();
pointQueue.push_back(*it);
it++;
pointQueue.push_back(*it);
it++;
while (it!=stop)
{
addPoint(pointQueue, &(*it));
it++;
}
}
void printQueue(TPointQueue& pointQueue)
{
for (TPointQueue::iterator it=pointQueue.begin(); it!=pointQueue.end(); it++)
{
it->display();
}
}
void TConvex::collectVertexDown(TPointQueue& pointQueue)
{
TPointSet::reverse_iterator it, stop;
it=pointSet.rbegin();
stop=pointSet.rend();
pointQueue.push_back(*it);
it++;
pointQueue.push_back(*it);
it++;
while (it!=stop)
{
addPoint(pointQueue, &(*it));
it++;
}
}
void TConvex::display()
{
for (TPointSet::iterator it=pointSet.begin(); it!=pointSet.end(); it++)
{
it->display();
}
}
void TConvex::convexHull(const TPointSet& inputSet, TPointQueue& pointQueue)
{
int upSize, downSize;
TPointQueue upQueue, downQueue;
TPointQueue::iterator it;
TPointSet::const_iterator setIt;
pointSet.clear();
pointQueue.clear();
for (setIt=inputSet.begin(); setIt!=inputSet.end(); setIt++)
{
pointSet.insert(*setIt);
}
if (pointSet.size()<3)
{
for (TPointSet::iterator it=pointSet.begin(); it!=pointSet.end(); it++)
{
pointQueue.push_back(*it);
}
}
else
{
collectVertexUp(upQueue);
collectVertexDown(downQueue);
for (it=upQueue.begin(); it!=upQueue.end(); it++)
{
pointQueue.push_back(*it);
}
pointQueue.pop_back();//remove last
for (it=downQueue.begin(); it!=downQueue.end(); it++)
{
pointQueue.push_back(*it);
}
pointQueue.pop_back();//remove last
}
}
void TNestConvex::nestConvex(const TPointSet& pointSet, TPointQueueVector& convexQueue)
{
TConvex convex;
TPointQueue pointQueue;
TPointSet inputSet;
TPointQueue::iterator qIt;
setCopy(inputSet, pointSet);
while (!inputSet.empty())
{
convex.convexHull(inputSet, pointQueue);
//printf("get a convex\n");
//printQueue(pointQueue);
convexQueue.push_back(pointQueue);
for (qIt=pointQueue.begin(); qIt!=pointQueue.end(); qIt++)
{
inputSet.erase(*qIt);
}
}
}
bool TNestConvex::triangulate(TPointQueueVector& convexQueue, TBoard& board)
{
TPointQueue outside, inside;
TTriangle triangle;
int i, j, k;
int counter;
int inCounter, outCounter;
TPoint outPoint, inPoint, nextIn, p1, p2, p3;
float result;
if (convexQueue.size()==0)
{
return false;
}
for (i=0; i<convexQueue.size()-1; i++)
{
outside=convexQueue[i];
inside=convexQueue[i+1];
j=k=0;
printf("\n");
outCounter=outside.size();
if (inside.size()==1)
{
inCounter=0;
}
else
{
inCounter=inside.size();
}
while (true)
{
outPoint=outside[j];
inPoint=inside[k];
nextIn=inside[(k+1)%inside.size()];
result=direction(&inPoint, &nextIn, &outPoint);
//here for the case the inside has only ONE vertex, the result is always 0
//so, we move outside when result is zero
if (result>0&&inCounter>0)
{
p1=outPoint;
p2=inPoint;
k=(k+1)%inside.size();
p3=inside[k];
inCounter--;
}
else
{
p1=outPoint;
p2=inPoint;
j=(j+1)%outside.size();
p3=outside[j];
outCounter--;
}
//triangle.display();
///////////////////////////
if (!board.insertFace(p1, p2, p3))
{
///////////////////////////////////////////////////
printf("what? and inside convex is*******************\n\n", result);
printQueue(inside);
printf("\n***********outside convex is:*********************\n");
printQueue(outside);
printf("\n********************************\n");
return false;
}
if (inCounter==0&&outCounter==0)
{
break;
}
}
}
outside=convexQueue.back();
outPoint=outside[0];
for (i=2; i<outside.size(); i++)
{
p1=outside[0];
p2=outside[i-1];
p3=outside[i];
if (!board.insertFace(p1, p2, p3))
{
printf("what????*****and the convex is::::\n");
printQueue(outside);
printf("\n**********immediately convex******************\n");
printQueue(convexQueue[convexQueue.size()-2]);
printf("\n**********immediately convex******************\n");
return false;
}
//pointPairVector.push_back(make_pair(outPoint, inPoint));
}
return true;
}
void TNestConvex::triangulate(TPointQueueVector& convexQueue, TPointPairVector& pointPairVector)
{
TPointQueue outside, inside;
int i, j, k;
int counter;
bool inDone, outDone;
TPoint outPoint, inPoint, nextIn, nextOut;
float result;
if (convexQueue.size()<=1)
{
return;
}
for (i=0; i<convexQueue.size()-1; i++)
{
outside=convexQueue[i];
inside=convexQueue[i+1];
//printf("outside queue:\n");
//printQueue(outside);
//printf("inside queue:\n");
//printQueue(inside);
j=k=0;
printf("\n");
if (inside.size()>1)
{
counter=inside.size()+outside.size();
}
else
{
counter=outside.size();
}
//initially both the leftmost point pair will be stored
while (true)
{
outPoint=outside[j];
inPoint=inside[k];
//printf("outside[%f,%f],inside[%f,%f]\n", outPoint.x, outPoint.y, inPoint.x, inPoint.y);
pointPairVector.push_back(make_pair(outPoint, inPoint));
counter--;
if (counter==0)
{
break;
}
nextIn=inside[(k+1)%inside.size()];
result=direction(&inPoint, &nextIn, &outPoint);
//here for the case the inside has only ONE vertex, the result is always 0
//so, we move outside when result is zero
if (result>0)
{
//move outside
k=(k+1)%inside.size();
}
else
{
j=(j+1)%outside.size();
}
}
}
outside=convexQueue.back();
outPoint=outside[0];
for (i=2; i<outside.size(); i++)
{
inPoint=outside[i];
//printf("outside[%f,%f],inside[%f,%f]\n", outPoint.x, outPoint.y, inPoint.x, inPoint.y);
pointPairVector.push_back(make_pair(outPoint, inPoint));
}
}
void TBoard::makeEdge(TPoint& first, TPoint& second, TEdge& result)
{
if (prevPoint(first, second))
{
result.pairPoint[0]=first;
result.pairPoint[1]=second;
}
else
{
result.pairPoint[0]=second;
result.pairPoint[1]=first;
}
}
void TBoard::makeFace(TPoint& p1, TPoint& p2, TPoint& p3, TFace& result)
{
TEdge* swap;
makeEdge(p1, p2, *result.edges[0]);
makeEdge(p1, p3, *result.edges[1]);
makeEdge(p2, p3, *result.edges[2]);
//find the smallest edge
//bubble sorting??
for (int i=0; i<2; i++)
{
for (int j=i+1; j<3; j++)
{
if (!prevEdge(result.edges[i], result.edges[j]))
{
swap=result.edges[i];
result.edges[i]=result.edges[j];
result.edges[j]=swap;
}
}
}
}
void TBoard::clear()
{
TEdgePtrSet::iterator eit;
TFacePtrSet::iterator fit;
for (eit=edgePtrSet.begin(); eit!=edgePtrSet.end(); eit++)
{
delete *eit;
}
edgePtrSet.clear();
for (fit=facePtrSet.begin(); fit!=facePtrSet.end(); fit++)
{
delete *fit;
}
facePtrSet.clear();
}
void TBoard::drawEdge()
{
TEdgePtrSet::iterator eit;
for (eit=edgePtrSet.begin(); eit!=edgePtrSet.end(); eit++)
{
(*eit)->draw();
}
}
void TBoard::drawFace()
{
TFacePtrSet::iterator fit;
for (fit=facePtrSet.begin(); fit!=facePtrSet.end(); fit++)
{
(*fit)->draw();
}
}
void TBoard::draw()
{
TEdgePtrSet::iterator eit;
TFacePtrSet::iterator fit;
for (fit=facePtrSet.begin(); fit!=facePtrSet.end(); fit++)
{
(*fit)->draw();
}
for (eit=edgePtrSet.begin(); eit!=edgePtrSet.end(); eit++)
{
(*eit)->draw();
}
}
TFace* TBoard::linearSearch(TPoint& point)
{
TFacePtrSet::iterator it, stop;
for (it=facePtrSet.begin(); it!=facePtrSet.end(); it++)
{
if ((*it)->pointInside(point))
{
return *it;
}
}
return NULL;
}
void TBoard::displayFace()
{
TFacePtrSet::iterator fit;
printf("display face set\n");
for (fit=facePtrSet.begin(); fit!=facePtrSet.end(); fit++)
{
(*fit)->display();
}
}
void TBoard::display()
{
TEdgePtrSet::iterator eit;
TFacePtrSet::iterator fit;
printf("\n\n*********************************\ndisplay edge set\n");
for (eit=edgePtrSet.begin(); eit!=edgePtrSet.end(); eit++)
{
(*eit)->display();
}
printf("display face set\n");
for (fit=facePtrSet.begin(); fit!=facePtrSet.end(); fit++)
{
(*fit)->display();
}
}
bool TBoard::sameColor(TFace* him, FaceStatus player)
{
return him->status==player;
}
//assume they are same color
bool TBoard::doSearchSpace(TFace* face, FaceStatus player, TFacePointerSet& path)
{
TFace* neighbour[3];
//TFacePointerSet tempPath;
TFacePointerSet::iterator it;
if (path.find(face)!=path.end())
{
return false;
}
if (face->status==Empty)
{
return true;
}
//enemy
if (face->status!=player)
{
return false;
}
//before that, let' place face into path
path.insert(face);
//otherwise it must be friend and we search recursively
//find three neighbours
getNeighbour(face, neighbour);
for (int i=0; i<3; i++)
{
if (neighbour[i]!=NULL)
{
if (path.find(neighbour[i])==path.end())
{
//new path
if (neighbour[i]->status==Empty)
{
return true;
}
if (neighbour[i]->status==player)
{
//avoid infinite loop, we check path at beginning, so don't add it here
//and each sub-path search is independant, so, we give separate path
/*
tempPath.clear();
for (it=path.begin(); it!=path.end(); it++)
{
tempPath.insert(*it);
}
if (doSearchSpace(neighbour[i], player, tempPath))
{
return true;
}
*/
if (doSearchSpace(neighbour[i], player, path))
{
return true;
}
}
}
//else nothing
}
}
//after all,
return false;//no chance to survive
}
void TBoard::getNeighbour(TFace* face, TFace* neighbour[3])
{
for (int i=0; i<3; i++)
{
if (face->edges[i]->faces[0]==face)
{
//doing little testing here
if (face->edges[i]->faces[1]==face)
{
printf("data corrupted! two neighbour are the same!\n");
exit(8);
}
neighbour[i]=face->edges[i]->faces[1];
}
else
{
//doing little testing here
if (face->edges[i]->faces[1]!=face)
{
printf("data corrupted! face itself is not the neighbour!\n");
exit(8);
}
neighbour[i]=face->edges[i]->faces[0];
}
}
}
bool TBoard::controlBy(TFace* face, FaceStatus& status, TFacePointerSet& path)
{
/*
TFace* neighbours[3];
FaceStatus tempStatus;
bool color[2];
if (!path.insert(face).second)
{
return false;
}
color[0]=color[1]=false;
getNeighbour(*it, neighbours);
for (int i=0; i<3; i++)
{
if (neighbours[i]!=NULL)
{
if (neighbours[i]->status==Empty)
{
if (controlBy(neighbours[i], tempStatus, path))
{
color[neighbours[i]->status]=true;
}
}
if (color[Empty]||(color[Red]&&color[Blue]))
{
mutualCount++;
}
else
{
if (color[Red])
{
*/
return true;
}
/*
TFace* TBoard::binarySearch(TPoint& point)
{
TFace face;
TEdge edges[3];
int i;
TFacePtrSet::iterator it;
for (i=0; i<3; i++)
{
face.edges[i]=edges+i;
}
makeFace(point, point, point, face);
it=facePtrSet.upper_bound(&face);
while (it!=facePtrSet.end())
{
if ((*it)->pointInside(point))
{
return *it;
}
it++;
}
return NULL;
}
*/
int TBoard::countTriangle()
{
TFacePointerSet path;
FaceStatus status;
TFacePtrSet::iterator it;
for (int i=0; i<3; i++)
{
controlCounter[i]=0;
}
for (it=facePtrSet.begin(); it!=facePtrSet.end(); it++)
{
if ((*it)->status!=Empty)
{
controlCounter[(*it)->status]++;
}
else
{
path.clear();
if (controlBy(*it, status, path))
{
controlCounter[status]++;
}
else
{
printf("unknown error\n");
exit(8);
}
}
}
return -1;
}
bool TBoard::validMove(TFace* face, FaceStatus player, bool justTest)
{
TFace* neighbour[3];
TFacePointerSet path;
FaceStatus enemy;
int i;
bool canKill=false;
bool isValid=false;
//if non-empty, no good move
if (face->status==Red || face->status==Blue)
{
return false;
}
getNeighbour(face, neighbour);
//so here, but if we do place our
//chess piece, can we kill enemy? So, we need to test enemy's life
//first temparorily change the status of face
face->status=player;
//now test if enemy will survive
enemy=(player==Red)?Blue:Red;
for (i=0; i<3; i++)
{
if (neighbour[i]!=NULL)
{
if (neighbour[i]->status==Empty)
{
isValid=true;
break;
}
if (neighbour[i]->status==player)
{
//avoid infinite loop, we check path at beginning, so don't add it here
//and each sub-path search is independant, so, we give separate path
path.clear();
path.insert(face);
if (doSearchSpace(neighbour[i], player, path))
{
isValid=true;
break;
}
}
//else nothing we ignore
}
}
canKill=false;
for (i=0; i<3; i++)
{
if (neighbour[i]!=NULL)
{
if (neighbour[i]->status==enemy)
{
//avoid infinite loop, we check path at beginning, so don't add it here
//and each sub-path search is independant, so, we give separate path
path.clear();
if (!doSearchSpace(neighbour[i], enemy, path))
{
canKill=true;
if (!justTest)
{
removeEnemy(neighbour[i], enemy);
}
}
}
//else nothing we ignore
}
}
//always reset original status, because we may just do testing
face->status=Empty;
if (canKill)
{
return true;//
}
else
{
//we need to change status back
return isValid;
}
}
void TBoard::removeEnemy(TFace* face, FaceStatus enemy)
{
TFace* neighbour[3];
getNeighbour(face, neighbour);
face->status=Empty;
memcpy(face->color, playerColor[Empty], sizeof(TColor));
for (int i=0; i<3; i++)
{
if (neighbour[i]!=NULL)
{
if (neighbour[i]->status==enemy)
{
neighbour[i]->status=Empty;
removeEnemy(neighbour[i], enemy);//recursive
}
}
}
}
bool TBoard::insertFace(TPoint& p1, TPoint& p2, TPoint& p3)
{
TFace* face;
TEdge edges[3];
TEdge* edge;
int i;
TColor color;
TEdgePtrSet::iterator it;
face=new TFace;
face->status=Empty;
for (i=0; i<3; i++)
{
//temporary assign these edges
face->edges[i]=edges+i;
//color[i]=((edgePtrSet.size()*rand()%10+3)*2)/40.0;
}
makeFace(p1, p2, p3, *face);
for (i=0; i<3; i++)
{
it=edgePtrSet.find(face->edges[i]);
if (it==edgePtrSet.end())
{
//now replace real allocated edge with those temp edges
edge=new TEdge;
edge->faces[0]=face;
edge->faces[1]=NULL;//assume unknown
memcpy(edge->pairPoint, face->edges[i]->pairPoint, sizeof(TPairPoint));
memcpy(edge->color, green, sizeof(TColor));
edgePtrSet.insert(it, edge);
face->edges[i]=edge;
}
else
{
face->edges[i]=*it;
//doing a little testing here
if (face->edges[i]->faces[0]==NULL)
{
printf("data corrupted, dangling edge found\n");
exit(8);
}
if (face->edges[i]->faces[1]!=NULL)
{
printf("\n******************************************\n");
printf("\n\n**********\ndata corrupted, one edge attached with three faces\n");
printf("\nand here is the repeat edge\n");
face->edges[i]->display();
printf("\n************show us the face problem***************\n");
face->display();
printf("\n*****************and all faces are**********************\n");
displayFace();
return false;
//exit(5);
}
face->edges[i]->faces[1]=face;
}
//face->edges[j]=new TEdge;
}
//now add the new face into face set
memcpy(face->color, beige, sizeof(TColor));
facePtrSet.insert(face);
return true;
//printf("now display the board\n");
//displayFace();
}
void TBoard::makeBoard(TTriangleQueue& triangleQueue)
{
TFace* face;
TEdge edges[3];
TEdge* edge;
int i, j;
TColor color;
TEdgePtrSet::iterator it;
for (i=0; i<triangleQueue.size(); i++)
{
face=new TFace;
for (j=0; j<3; j++)
{
//temporary assign these edges
face->edges[j]=edges+j;
//color[j]=i*30+j*40;
}
makeFace(triangleQueue[i].triangle[0], triangleQueue[i].triangle[1],
triangleQueue[i].triangle[2], *face);
for (j=0; j<3; j++)
{
it=edgePtrSet.find(face->edges[j]);
if (it==edgePtrSet.end())
{
//now replace real allocated edge with those temp edges
edge=new TEdge;
edge->faces[0]=face;
edge->faces[1]=NULL;//assume unknown
memcpy(edge->pairPoint, face->edges[j]->pairPoint, sizeof(TPairPoint));
memcpy(edge->color, green, sizeof(TColor));
edgePtrSet.insert(it, edge);
face->edges[j]=edge;
}
else
{
face->edges[j]=*it;
//doing a little testing here
if (face->edges[j]->faces[0]==NULL)
{
printf("data corrupted, dangling edge found\n");
exit(8);
}
if (face->edges[j]->faces[1]!=NULL)
{
printf("\n******************************************\n");
printf("\n\n**********\ndata corrupted, one edge attached with three faces\n");
printf("\nand here is the repeat edge\n");
face->edges[j]->display();
printf("\n************show us the face problem***************\n");
face->display();
printf("\n*****************and all faces are**********************\n");
displayFace();
continue;
//exit(5);
}
face->edges[j]->faces[1]=face;
}
//face->edges[j]=new TEdge;
}
//now add the new face into face set
memcpy(face->color, color, sizeof(TColor));
facePtrSet.insert(face);
//printf("now display the board\n");
//displayFace();
}
}
file name: main.cpp
/*********************************************************
nest convex:
1000: 1.3sec
5000: 5sec
10000: 16sec
triangulation:
1000: 0.3sec
5000: 1.3sec
10000: 1.6sec
*********************************************************/
#include "common.h"
#include "ConvexHull.h"
//#include <windows.h>
#include <GL/glut.h>
#include <vector>
#include <deque>
#include <utility>
#include <ctime>
using namespace std;
extern vector<TPointContext> separateVector;
extern vector<TPointContext> connectVector;
TPointPairVector pairVector;
TTriangleQueue triangleQueue;
extern TConvex convex;
extern TPolygon polygon;
bool gameEnd=false;
FaceStatus player=Red;
TPointQueue pointQueue;
TPointQueueVector convexQueueVector;
TPointSet pointSet;
TPointPairVector pointPairVector;
TFacePtrVector facePtrVector;
TBoard board;
bool showBoard=true;
TFacePtrSet::iterator fit;
void outputMessage();
void output(int x, int y, char *str);
void drawAxis()
{
glLineWidth(1);
glBegin(GL_LINES);
glColor3fv(beige);
glVertex2f(MaxIntegerValue,0);
glColor3fv(red);
glVertex2f(-MaxIntegerValue, 0);
glEnd();
glBegin(GL_LINES);
glColor3fv(beige);
glVertex2f(0, -MaxIntegerValue);
glColor3fv(red);
glVertex2f(0, MaxIntegerValue);
glEnd();
}
void clearAll()
{
separateVector.clear();
connectVector.clear();
pairVector.clear();
convexQueueVector.clear();
pointPairVector.clear();
pairVector.clear();
triangleQueue.clear();
player=Red;
gameEnd=false;
}
int index=0;
void displayMenu()
{
printf("\n***********************************************\n");
printf("<<<<<<<<<<<<<Welcome To TrianGO>>>>>>>>>>>>>>>>>>\n");
printf("<<<<<<<<<<<<<A Game of GO on Triangle>>>>>>>>>>>>\n");
printf("Operation:\n\
a) create random points: by right click mouse or press 'n'; \n\
b) create nested convex hull: by press 'n'. \n\
c) create triangulation: press 't'. \n\
d) start playing: left click triangles in chess board. \n\
restart: press 'a' to clear everything. \n\
show menu: press 'm' \n\
exit: press 'esc'\n");
printf("\n***********************************************\n");
}
void displayCallback()
{
int separateNumber, connectNumber, pairNumber, i, j;
glClearColor(1,1,0,1);
glClear(GL_COLOR_BUFFER_BIT|GL_DEPTH_BUFFER_BIT);
//separateNumber=separateVector.size();
separateNumber=separateVector.size();
connectNumber=connectVector.size();
pairNumber=pairVector.size();
//connectNumber=0;
glPointSize(5.0);
glLineWidth(5);
if (connectNumber>0)
{
glBegin(GL_LINE_LOOP);
for (i=0; i<connectNumber; i++)
{
glColor3fv(connectVector[i].pointColor);
glVertex2f(connectVector[i].point.x, connectVector[i].point.y);
//printf("x=%f, y=%f\n", connectVector[i].pointPtr->x,
// connectVector[i].pointPtr->y);
}
glEnd();
glBegin(GL_POINTS);
for (i=0; i<connectNumber; i++)
{
glColor3fv(connectVector[i].pointColor);
glVertex2f(connectVector[i].point.x, connectVector[i].point.y);
//printf("x=%f, y=%f\n", separateVector[i].pointPtr->x, separateVector[i].pointPtr->y);
}
glEnd();
}
if (separateNumber>0)
{
glBegin(GL_POINTS);
for (i=0; i<separateNumber; i++)
{
glColor3fv(separateVector[i].pointColor);
glVertex2f(separateVector[i].point.x, separateVector[i].point.y);
//printf("x=%f, y=%f\n", separateVector[i].pointPtr->x, separateVector[i].pointPtr->y);
}
glEnd();
}
if (pairNumber>0)
{
for (i=0; i<pairNumber; i++)
{
glBegin(GL_LINES);
glColor3fv(blue);
glVertex2f(pairVector[i].first.x, pairVector[i].first.y);
glColor3fv(blue);
glVertex2f(pairVector[i].second.x, pairVector[i].second.y);
glEnd();
}
}
for (i=0; i<convexQueueVector.size(); i++)
{
glBegin(GL_LINE_LOOP);
for (j=0; j<convexQueueVector[i].size(); j++)
{
glColor3fv(red);
glVertex2f(convexQueueVector[i][j].x, convexQueueVector[i][j].y);
}
glEnd();
}
if (triangleQueue.size()>0)
{
triangleQueue[index].draw();
}
//board.draw();
if (showBoard)
{
/*
for (i=0; i<facePtrVector.size(); i++)
{
facePtrVector[i]->draw();
}
*/
board.drawFace();
}
//board.drawEdge();
//drawAxis();
outputMessage();
glutSwapBuffers();
//glutPostRedisplay();
}
void outputMessage()
{
TFacePtrSet::iterator it;
const int CharHeight=15;
char msg[20];
int winner;
int counter[3]={0};
static char* playerName[4]={"RED", "BLUE", "EMPTY", "NOBODY"};
int currentx, currenty;
for (it=board.facePtrSet.begin(); it!=board.facePtrSet.end(); it++)
{
counter[(*it)->status]++;
}
currentx=-winSize_width/2+2;
currenty=winSize_height/2-CharHeight;
sprintf(msg, "[PLAYER] %s", playerName[player]);
output(currentx, currenty, msg);
currenty-=CharHeight;
for (int i=0; i<3; i++)
{
sprintf(msg, "[%s] %d", playerName[i], counter[i]);
output(currentx, currenty, msg);
currenty-=CharHeight;
}
if (gameEnd)
{
if (counter[Red]>counter[Blue])
{
winner=Red;
}
else
{
if (counter[Red]<counter[Blue])
{
winner=Blue;
}
else
{
winner=3;
}
}
sprintf(msg, "[WINNER] %s!", playerName[winner]);
output(currentx, currenty, msg);
}
}
void output(int x, int y, char *str)
{
int len, i;
glColor3fv(red);
glRasterPos2f(x, y);
len = (int) strlen(str);
for (i = 0; i < len; i++)
{
glutBitmapCharacter(GLUT_BITMAP_8_BY_13 , str[i]);
}
}
void keyboardCallback(unsigned char key, int x, int y)
{
//int i;
//bool noProblem=false;
TPointContext pointContext;
unsigned long int startSec;
TPointPair pointPair;
TPointQueue::iterator it;
TPointSet::iterator setIt;
TFacePtrSet::iterator fit;
//float coord[4];
switch (key)
{
case 27:
exit(0);
break;
case 's':
//convex.generatePoint(10);
generateRandomPoint(10, pointSet);
for (setIt=pointSet.begin(); setIt!=pointSet.end(); setIt++)
{
pointContext.point=*setIt;
memcpy(pointContext.pointColor, red, sizeof(TColor));
separateVector.push_back(pointContext);
}
/*
for (setIt=convex.pointSet.begin(); setIt!=convex.pointSet.end(); setIt++)
{
memcpy(pointContext.pointColor, red, sizeof(TColor));
pointContext.point=*setIt;
separateVector.push_back(pointContext);
}
*/
break;
case 'm':
displayMenu();
break;
case 'c':
convex.convexHull(pointSet, pointQueue);
for (it=pointQueue.begin(); it!=pointQueue.end(); it++)
{
memcpy(pointContext.pointColor, green, sizeof(TColor));
pointContext.point=*it;
connectVector.push_back(pointContext);
}
break;
case 'p':
pointQueue.clear();
polygon.createPolygon(11, pointQueue);
for (it=pointQueue.begin(); it!=pointQueue.end(); it++)
{
memcpy(pointContext.pointColor, blue, sizeof(TColor));
pointContext.point=*it;
connectVector.push_back(pointContext);
//glutPostRedisplay();
}
break;
case 'e':
separateVector.clear();
connectVector.clear();
break;
case 'n':
if (pointSet.size()==0)
{
generateRandomPoint(8, pointSet);
}
convexQueueVector.clear();
startSec=glutGet(GLUT_ELAPSED_TIME);
TNestConvex::nestConvex(pointSet, convexQueueVector);
startSec=glutGet(GLUT_ELAPSED_TIME)-startSec;
//printf("nest convex time takes %d milli seconds\n", startSec);
//TNestConvex::triangulate(convexQueueVector, pointPairVector);
//pairVector.insert(pairVector.end(), pointPairVector.begin(), pointPairVector.end());
break;
case 'r':
startSec=glutGet(GLUT_ELAPSED_TIME);
TNestConvex::triangulate(convexQueueVector, pointPairVector);
startSec=glutGet(GLUT_ELAPSED_TIME)-startSec;
//printf("triangulation time takes %d milli seconds\n", startSec);
pairVector.insert(pairVector.end(), pointPairVector.begin(), pointPairVector.end());
break;
case 'a':
separateVector.clear();
connectVector.clear();
pairVector.clear();
convexQueueVector.clear();
pointPairVector.clear();
pointSet.clear();
triangleQueue.clear();
board.clear();
displayMenu();
break;
case 't':
//triangleQueue.clear();
startSec=glutGet(GLUT_ELAPSED_TIME);
showBoard=TNestConvex::triangulate(convexQueueVector, board);
startSec=glutGet(GLUT_ELAPSED_TIME)-startSec;
//printf("triangulation time takes %d milli seconds\n", startSec);
/*
for (i=0; i<triangleQueue.size(); i++)
{
printf("triangle retrieved\n");
triangleQueue[i].display();
}
*/
if (showBoard)
{
//board.makeBoard(triangleQueue);
clearAll();
}
break;
case 'g':
index=(index+1)%triangleQueue.size();
break;
}
glutPostRedisplay();
}
void reshapeCallback(int width, int height)
{
glutPostRedisplay();
}
void init()
{
displayMenu();
glShadeModel(GL_FLAT);
//glShadeModel(GL_SMOOTH);
gluOrtho2D((float)winSize_width/-2.0, (float)winSize_width/2.0,
(float)winSize_height/-2.0, (float)winSize_height/2.0);
}
void mouseCallback(int button, int state, int x, int y)
{
TPoint point;
TFacePtrSet::iterator it;
TFace* face;
FaceStatus enemy;
//printf("coord[x=%d,y=%d]\n", x, y);
point.x=x-winSize_width/2;
point.y=winSize_height/2-y;
TPointContext pointContext;
if (button==GLUT_LEFT_BUTTON &&state==GLUT_DOWN)
{
face=board.linearSearch(point);
if (face!=NULL)
{
//showBoard=false;
//board.checkColor(face, redPlayer);
if (board.validMove(face, player))
{
memcpy(face->color, playerColor[player], sizeof(TColor));
face->status=player;
enemy=(player==Red)?Blue:Red;
//but before that, let's see if it is end of game.
gameEnd=true;
for (it=board.facePtrSet.begin(); it!=board.facePtrSet.end(); it++)
{
if (board.validMove(*it, enemy, true))
{
gameEnd=false;
break;
}
}
player=(player==Red)?Blue:Red;
glutPostRedisplay();
}
}
}
if (button==GLUT_RIGHT_BUTTON &&state==GLUT_DOWN)
{
pointSet.insert(point);
pointContext.point=point;
memcpy(pointContext.pointColor, red, sizeof(TColor));
separateVector.push_back(pointContext);
glutPostRedisplay();
}
}
int main(int argc, char** argv)
{
srand(time(0));
glutInit(&argc, argv);
glutInitWindowPosition(winPos_x, winPos_y);
glutInitWindowSize(winSize_width, winSize_height);
glutInitDisplayMode(GLUT_RGBA|GLUT_ALPHA|GLUT_DOUBLE);
glutCreateWindow(windowTitle);
glutMouseFunc(mouseCallback);
glutDisplayFunc(displayCallback);
glutKeyboardFunc(keyboardCallback);
glutReshapeFunc(reshapeCallback);
init();
//printf("before convex hull\n");
//convex.display();
//convex.convexHull(pointSet);
//printf("after convex hull\n");
//pointSet.display();
//glutPostRedisplay();
//glutShowWindow();
glutMainLoop();
return 0;
}