Skip to content

Instantly share code, notes, and snippets.

@dugagjin
Created January 21, 2016 17:09
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save dugagjin/895b4509a677aa1c3daf to your computer and use it in GitHub Desktop.
Save dugagjin/895b4509a677aa1c3daf to your computer and use it in GitHub Desktop.
C++/ C/ openGL
#define infinite 999
#define mapDimension 6
typedef struct City City;
struct City {
int distance;
int previousCity;
int visited;
};
typedef struct Path Path;
struct Path {
int startPos;
int endPos;
};
int map[mapDimension][mapDimension];
/* ask some info to user about the map. */
void createMap() {
int z = 0;
for (int x = 0; x < mapDimension; x++) {
for (int y = z; y < mapDimension; y++) {
if (x == y) {
map[x][y] = 0;
y++;
}
printf("If city %c is a neighbor of city %c then give distance otherwise put '-1': ", x + 65, y + 65);
scanf("%d", &map[x][y]);
}
z++;
}
/* Transpose over eye to create a matrix of distances.*/
for (int x = 0; x < mapDimension; x++)
for (int y = 0; y < mapDimension; y++)
map[y][x] = map[x][y];
return;
}
void printMap() {
for (int x = 0; x < mapDimension; x++) {
printf("\n");
for (int y = 0; y < mapDimension; y++)
printf("%d \t", map[x][y]);
}
return;
}
Path askInfoPath() {
Path path;
printf("\n\nWhere do you start & end?\n");
scanf("%d%d", &path.startPos, &path.endPos);
printf("Okay, your path start from %c and ends at %c. You should pass by %c ", path.startPos + 65, path.endPos + 65, path.endPos + 65);
return path;
}
/* core of dijkstra. Look at map and make a path. */
void findPath(int startCity, int nextCity[], int map[][mapDimension], City walker[]) {
nextCity[0] = startCity;
int z = 1;
for (int x = 0; x < mapDimension; x++) {
for (int y = 0; y < mapDimension; y++) {
if (map[nextCity[x]][y] > 0) {
int wayOut = 1;
for (int k = 0; k < mapDimension; k++)
if (y == nextCity[k])
wayOut = 0;
if (wayOut == 1) {
nextCity[z] = y;
z++;
}
if (walker[y].distance > walker[nextCity[x]].distance + map[nextCity[x]][y]){
walker[y].distance = walker[nextCity[x]].distance + map[nextCity[x]][y];
walker[y].previousCity = nextCity[x];
}
}
walker[nextCity[x]].visited = 1;
}
}
return;
}
/* compute path information */
int dijkstra(Path path) {
int index = path.endPos;
int nameCity;
int running = 1;
int x = 0;
City walker [mapDimension];
int nextCity[mapDimension];
for (int x = 0; x < mapDimension; x++) {
walker[x].visited = 0;
walker[x].previousCity = -1;
if (x != path.startPos)
walker[x].distance = infinite;
else
walker[x].distance = 0;
}
findPath(path.startPos, nextCity, map, walker);
/* find path with computed information & return distance to print. */
while (running == 1){
x++;
nameCity = walker[index].previousCity;
if (nameCity > -1 && x < mapDimension) {
index = nameCity;
printf("%c ", nameCity + 65);
}
else
running = 0;
}
return walker[path.endPos].distance;
}
#include <stdio.h>
#include "header.h"
/* Dijkstra program. Default map 6 cities but can be greater.*/
/* User answers few basic questions to have shortest path. */
void main() {
createMap();
printMap();
while (1) {
printf("\nPath distance: %d", dijkstra(askInfoPath()));
}
return;
}
#include <GL/freeglut.h>
#include <GL/gl.h>
#include <math.h>
#include <time.h>
/* length is 85% of previous line. So 1-0.85 = 0.15. */
void tree(GLfloat x1, GLfloat y1, GLfloat x2, GLfloat y2, GLfloat angle, GLint n){
glBegin(GL_LINE_STRIP);
glVertex2f(x1, y1);
glVertex2f(x2, y2);
glEnd();
if (n<1) return;
GLint nn = n - 1;
GLfloat x3 = (x2 - x1)* 0.15 + x1 - x2;
GLfloat y3 = (y2 - y1)* 0.15 + y1 - y2;
tree(x2, y2, x3 * cos(angle) + y3 * sin(angle) + x2, -x3 * sin(angle) + y3 * cos(angle) + y2, angle, nn);
tree(x2, y2, x3 * cos(-angle) + y3 * sin(-angle) + x2, -x3 * sin(-angle) + y3 * cos(-angle) + y2, angle, nn);
}
/* 160 for 20°. Because 180-160 = 20°*/
void draw(){
glClearColor(0.0, 0.0, 0.0, 0.0);
glLineWidth(2);
glColor3f(0.15, 0.6, 0.05);
tree(0.0f, -1.0f, 0.0f, -0.625f, 160, 8);
glEnd();
glFlush();
}
int main(int argc, char** argv){
glutInit(&argc, argv);
glutInitDisplayMode(GLUT_SINGLE);
glutInitWindowSize(1920, 1080);
glutCreateWindow("Fractal tree");
glutDisplayFunc(draw);
glutMainLoop();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment