源代码：基于A*算法的八数码问题的实现（用OpenGL实现动态演示）

 

转载请注明出处：http://hi.baidu.com/lvchengbin405/blog/item/d95c2a1f722cb36bf624e42e.html

State、EDCNode和EDC的定义与实现请参看上一篇文章：源代码：基于A*算法的八数码问题的实现（类的定义与实现）（http://hi.baidu.com/lvchengbin405/blog/item/e354fd1faaeb09c0a7866921.html）

 

 

 

#include <stdio.h>
#include <stdlib.h>
#include <string>
using namespace std;

#include <glut.h>

#include "EDCPP.h"

#pragma warning (disable:4996)

// define grid size
#define GRID_WIDTH 45
#define GRID_HEIGHT 56   
#define GRID_INTERSPACES_W 10
#define GRID_INTERSPACES_H 20

// define char size
#define FONTSIZEH 12
#define FONTSIZEW 15
#define FONTSIZEHB 18
#define FONTSIZEWB 18
#define VALUEH 16


// draw one line
#define drawOneLine(x1, y1, x2, y2) \
glBegin(GL_LINES);     \
glVertex2f((x1), (y1));\
glVertex2f((x2), (y2));\
glEnd();

// draw one grid
#define drawOneGrid(x1, y1, x2, y2) \
glBegin(GL_LINE_LOOP); \
glVertex2f((x1), (y1));\
glVertex2f((x2), (y1));\
glVertex2f((x2), (y2));\
glVertex2f((x1), (y2));\
glEnd();

// draw char with char size 12 pixes
#define drawChar(c, x, y) \
glRasterPos2f(x, y); \
    glutBitmapCharacter(GLUT_BITMAP_HELVETICA_12, c);

// draw char with char size 18 pixes
#define drawCharB(c, x, y) \
glRasterPos2f(x, y);   \
    glutBitmapCharacter(GLUT_BITMAP_HELVETICA_18, c);

#define STATE_INPUT 1
#define STATE_TRACK 2
#define STATE_END   3
#define STATE_RESTART   4

EDC* edc;
int windows_w;
int windows_h;
int windows_pagew = 0;
int windows_pageh = 0;
int state = 0;
int result = -1;
void drawString12(int x, int y, const char* string)
{
glRasterPos2f(x, y);
for (;*string != '\0';++string)
    {
   glutBitmapCharacter(GLUT_BITMAP_HELVETICA_12, *string);
}
}

void drawString18(int x, int y, const char* string)
{
glRasterPos2f(x, y);
for (;*string != '\0';++string)
    {
   glutBitmapCharacter(GLUT_BITMAP_HELVETICA_18, *string);
}
}


void drawEDCNode(EDCNode* node, int startx, int starty)
{
char g[8];
char h[8];
_itoa(node->GetG(), g, 10);
_itoa(node->GetH(), h, 10);
State* s = node->GetState();

// draw grid
drawOneGrid(startx, starty+FONTSIZEH, startx+GRID_WIDTH, starty-GRID_HEIGHT+FONTSIZEH);

// draw g&h
drawString12(startx+1, starty-1, g);
drawString12(startx+FONTSIZEW*2+1, starty-1, h);

// draw data(from 1 to 8)
starty = starty - VALUEH;
for (int i=0; i<3; i++)
{
   for (int j=0; j<3; j++)
   {
    if (i!=s->blankx || j!=s->blanky)
    {
     drawChar(s->value[i][j], startx+FONTSIZEW*j+1, starty-FONTSIZEH*i-1);
    }
   }
}
}

void drawHeap(int index, int h, int sx, int sy)
{
int dx = h*GRID_WIDTH;
int dy = GRID_HEIGHT + GRID_INTERSPACES_H;
EDCNode* node = edc->GetNodeFromOpenList(index);
if (!node)
   return;
drawEDCNode(node, sx, sy);
if (index*2+1<=edc->GetOpenNum())
{
   drawOneLine(sx+GRID_WIDTH/2, sy-GRID_HEIGHT+FONTSIZEH, sx+GRID_WIDTH/2-dx, sy+FONTSIZEH-dy);
   drawOneLine(sx+GRID_WIDTH/2, sy-GRID_HEIGHT+FONTSIZEH, sx+GRID_WIDTH/2+dx, sy+FONTSIZEH-dy);
   drawHeap(index*2, h/2, sx-dx, sy-dy);
   drawHeap(index*2+1, h/2, sx+dx, sy-dy);
}
else if (index*2<=edc->GetOpenNum())
{
   drawOneLine(sx+GRID_WIDTH/2, sy-GRID_HEIGHT+FONTSIZEH, sx+GRID_WIDTH/2-dx, sy+FONTSIZEH-dy);
   drawHeap(index*2, h/2, sx-dx, sy-dy);
}
}
void drawOpenList(int startx, int starty)
{
char ch[32] = "Open List : ";
int num = edc->GetOpenNum();
sprintf(ch, "Open List : %d", num);
drawString18(startx, starty+FONTSIZEHB, ch);
int x=startx, y=starty-GRID_INTERSPACES_H;
int i = num, j=1;
while (i>0)
{
   i /= 2;
   j *= 2;
}
int sx = startx + j/2*GRID_WIDTH - GRID_INTERSPACES_W;
int sy = starty - GRID_INTERSPACES_H;
drawHeap(1, j/4, sx, sy);
// 绘制第一个节点的儿子
glColor3f(0.0, 1.0, 1.0);
if (edc->GetOpenNum()>0)
{
   EDCNode* parent = new EDCNode(*(edc->GetNodeFromOpenList(1)));
   int line = 20;
   sx += GRID_WIDTH;
   drawOneLine(sx, sy-GRID_HEIGHT/3, sx+GRID_WIDTH+line, sy-GRID_HEIGHT/3);
   drawOneLine(sx+GRID_WIDTH+line, sy-GRID_HEIGHT/3, sx+GRID_WIDTH+line-10, sy-GRID_HEIGHT/3+10);
   drawOneLine(sx+GRID_WIDTH+line, sy-GRID_HEIGHT/3, sx+GRID_WIDTH+line-10, sy-GRID_HEIGHT/3-10);
   drawString12(sx+5, sy-GRID_HEIGHT/3+5, "CHILD");

   EDCNode* child = new EDCNode(*parent);
   if (EDCNode::MoveLeft(child->GetState()))
   {
    child->SetG(edc->CalculateG(parent, child));
    child->SetH(edc->CalculateH(child, edc->GetEnd()));
    sx += GRID_WIDTH + line;
    drawEDCNode(child, sx, sy);
    if (edc->IsInOpenList(child)==-1)
     drawString12(sx, sy+FONTSIZEHB, "N");
    else
     drawString12(sx, sy+FONTSIZEHB, "Y");
    if (edc->IsInCloseList(child)==-1)
     drawString12(sx+GRID_WIDTH-FONTSIZEW, sy+FONTSIZEHB, "N");
    else
     drawString12(sx+GRID_WIDTH-FONTSIZEW, sy+FONTSIZEHB, "Y");
   }
   delete child;

   child = new EDCNode(*parent);
   if (EDCNode::MoveRight(child->GetState()))
   {
    child->SetG(edc->CalculateG(parent, child));
    child->SetH(edc->CalculateH(child, edc->GetEnd()));
    sx += GRID_WIDTH + line;
    drawEDCNode(child, sx, sy);
    if (edc->IsInOpenList(child)==-1)
     drawString12(sx, sy+FONTSIZEHB, "N");
    else
     drawString12(sx, sy+FONTSIZEHB, "Y");
    if (edc->IsInCloseList(child)==-1)
     drawString12(sx+GRID_WIDTH-FONTSIZEW, sy+FONTSIZEHB, "N");
    else
     drawString12(sx+GRID_WIDTH-FONTSIZEW, sy+FONTSIZEHB, "Y");
   }
   delete child;

   child = new EDCNode(*parent);
   if (EDCNode::MoveUp(child->GetState()))
   {
    child->SetG(edc->CalculateG(parent, child));
    child->SetH(edc->CalculateH(child, edc->GetEnd()));
    sx += GRID_WIDTH + line;
    drawEDCNode(child, sx, sy);
    if (edc->IsInOpenList(child)==-1)
     drawString12(sx, sy+FONTSIZEHB, "N");
    else
     drawString12(sx, sy+FONTSIZEHB, "Y");
    if (edc->IsInCloseList(child)==-1)
     drawString12(sx+GRID_WIDTH-FONTSIZEW, sy+FONTSIZEHB, "N");
    else
     drawString12(sx+GRID_WIDTH-FONTSIZEW, sy+FONTSIZEHB, "Y");
   }
   delete child;

   child = new EDCNode(*parent);
   if (EDCNode::MoveDown(child->GetState()))
   {
    child->SetG(edc->CalculateG(parent, child));
    child->SetH(edc->CalculateH(child, edc->GetEnd()));
    sx += GRID_WIDTH + line;
    drawEDCNode(child, sx, sy);
    if (edc->IsInOpenList(child)==-1)
     drawString12(sx, sy+FONTSIZEHB, "N");
    else
     drawString12(sx, sy+FONTSIZEHB, "Y");
    if (edc->IsInCloseList(child)==-1)
     drawString12(sx+GRID_WIDTH-FONTSIZEW, sy+FONTSIZEHB, "N");
    else
     drawString12(sx+GRID_WIDTH-FONTSIZEW, sy+FONTSIZEHB, "Y");
   }
   delete child;

   delete parent;
}
}

void drawCloseList(int startx, int starty)
{
char ch[32] = "Close List : ";
int num = edc->GetCloseNum();
sprintf(ch, "Close List : %d", num);
drawString18(startx-250, starty-FONTSIZEHB, ch);
EDCNode* node = edc->GetNodeFromCloseList(num);
if (!node)
   return;

int sx = startx - GRID_WIDTH - GRID_INTERSPACES_W;
int sy = starty - GRID_INTERSPACES_H;
int x=sx, y=sy;
int i,j;
drawEDCNode(edc->GetNodeFromCloseList(1), sx, sy);
int levelindex1=1,levelindex2=1,parentindex=1;
for (i=2; i<=num; i++)
{
   x -= GRID_WIDTH + GRID_INTERSPACES_W;
   if (edc->GetNodeFromCloseList(i)->GetG() != edc->GetNodeFromCloseList(i-1)->GetG())
   {
    levelindex1 = levelindex2;
    levelindex2 = i;
    x = sx;
    y -= GRID_HEIGHT + GRID_INTERSPACES_H;
   }
   drawEDCNode(edc->GetNodeFromCloseList(i), x, y);
   parentindex = edc->GetNodeParentFromCloseList(i);
   if (parentindex != -1)
    drawOneLine(x+GRID_WIDTH/2, y+FONTSIZEH, sx-(parentindex-levelindex1)*(GRID_WIDTH + GRID_INTERSPACES_W)+GRID_WIDTH/2, y+GRID_INTERSPACES_H+FONTSIZEH);
}
// find path and draw it with red
glColor3f(1.0, 0.0, 0.0);
if (state == STATE_END && result == 1) 
{
   i--;
   while (i!=1)
   {
    drawEDCNode(edc->GetNodeFromCloseList(i), x, y);
    i = edc->GetNodeParentFromCloseList(i);
    j = i;
    while (edc->GetNodeFromCloseList(j-1)!=NULL && edc->GetNodeFromCloseList(j)->GetG() == edc->GetNodeFromCloseList(j-1)->GetG())
     j--;
    drawOneLine(x+GRID_WIDTH/2, y+FONTSIZEH, sx-(i-j)*(GRID_WIDTH + GRID_INTERSPACES_W)+GRID_WIDTH/2, y+GRID_INTERSPACES_H+FONTSIZEH);
    x = sx-(i-j)*(GRID_WIDTH + GRID_INTERSPACES_W);
    y += GRID_HEIGHT + GRID_INTERSPACES_H;
   }
   drawEDCNode(edc->GetNodeFromCloseList(i), x, y);
}
}

void drawFn(int startx, int starty)
{
int g, hdn, hpn, hsn;
edc->GetParas(g, hdn, hpn, hsn);
char ch[128] = "Estimated Function: F(n) = G(n) + H(n)";
drawString18(startx, starty, ch);
if (g==0)
   strcpy(ch, "G(child) = G(parent) + 1");
else if (g==1)
   strcpy(ch, "G(child) = G(parent) + H(child, parent)");
else
   strcpy(ch, "G(child) = 0");
drawString18(startx, starty-FONTSIZEHB, ch);
sprintf(ch, "H(n) = %dDn + %dPn + %dSn", hdn, hpn, hsn);
drawString18(startx, starty-FONTSIZEHB*2, ch);
}

void drawStart(int startx, int starty)
{
char ch[] = "Start State:";
drawString18(startx, starty, ch);
int x=startx, y=starty-FONTSIZEHB;
State* s = edc->GetStart()->GetState();
for (int i=0; i<3; i++)
{
   for (int j=0; j<3; j++)
   {
    if (i!=s->blankx || j!=s->blanky)
    {
     drawCharB(s->value[i][j], x+FONTSIZEWB*j+1, y-FONTSIZEHB*i-1);
    }
   }
}
}

void drawEnd(int startx, int starty)
{
char ch[] = "End   State:";
drawString18(startx, starty, ch);
int x=startx, y=starty-FONTSIZEHB;
State* s = edc->GetEnd()->GetState();
for (int i=0; i<3; i++)
{
   for (int j=0; j<3; j++)
   {
    if (i!=s->blankx || j!=s->blanky)
    {
     drawCharB(s->value[i][j], x+FONTSIZEWB*j+1, y-FONTSIZEHB*i-1);
    }
   }
}
}

void display(void)
{
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluOrtho2D(-windows_w/2+windows_pagew, windows_w/2+windows_pagew, -windows_h/2+windows_pageh, windows_h/2+windows_pageh);

glClear(GL_COLOR_BUFFER_BIT);
//select white
glColor3f(1.0, 1.0, 1.0);
drawOneLine(-1000, 100, -100, 100);
drawOneLine(-100, -800, -100, 800);

glColor3f(1.0, 1.0, 0.0);
drawCloseList(-100, 100);
glColor3f(1.0, 0.0, 1.0);
drawOpenList(-100, 300);

glColor3f(1.0, 0.0, 0.0);
drawFn(-500+50, 100+100+100);
drawStart(-500+50, 100+100);
drawEnd(-500+50+150, 100+100);

glFlush();
}

void reshape(int w, int h)
{
glViewport(0, 0, (GLsizei)w, (GLsizei)h);
windows_w = w; windows_h = h;
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluOrtho2D(-w/2, w/2, -h/2, h/2);
}

void processNormalKeys(unsigned char key, int x, int y)
{
switch (key)
{
case 27: // 'esc'
   exit(1);
case 13: // 'enter'
   if (state == STATE_TRACK)
   {
    result = edc->EDCOnce();
    if (result!=0)
     state = STATE_END;
    glutPostRedisplay();
   }
   break;
case 97: // 'a'
   windows_pagew -= 100;
   glutPostRedisplay();
   break;
case 100: // 'd'
   windows_pagew += 100;
   glutPostRedisplay();
   break;
case 119: // 'w'
   if (windows_pageh !=0)
   {
    windows_pageh += 100;
    glutPostRedisplay();
   }
   break;
case 115: // 's'
   windows_pageh -= 100;
   glutPostRedisplay();
   break;
case 32:   // ' '
   windows_pagew = 0;
   windows_pageh = 0;
   glutPostRedisplay();
   break; 
    default:
        fprintf(stderr, "Unknown key-press: --%d--\n", key);
        break;
    }
}

void processSpecialKeys(int key, int x, int y)
{
switch (key)
{
case GLUT_KEY_LEFT:
   if (state == STATE_INPUT)
   {
    EDCNode::MoveRight(edc->GetStart()->GetState());
    glutPostRedisplay();
   }
   break;
case GLUT_KEY_RIGHT:
   if (state == STATE_INPUT)
   {
    EDCNode::MoveLeft(edc->GetStart()->GetState());
    glutPostRedisplay();
   }
   break;
case GLUT_KEY_UP:
   if (state == STATE_INPUT)
   {
    EDCNode::MoveDown(edc->GetStart()->GetState());
    glutPostRedisplay();
   }
   break;
case GLUT_KEY_DOWN:
   if (state == STATE_INPUT)
   {
    EDCNode::MoveUp(edc->GetStart()->GetState());
    glutPostRedisplay();
   }
   break;
case GLUT_KEY_F1:
   if (state!=STATE_TRACK)
    state = STATE_INPUT;
   break;
case GLUT_KEY_F2:
   state = STATE_TRACK;
   break;
case GLUT_KEY_F3:
   state = STATE_RESTART;
   result = -1;
   edc->StartEDC();
   glutPostRedisplay();
   break;
    default:
        break;
    }
}

void initGL(void)
{
glClearColor(0.0, 0.0, 0.0, 0.0);
glShadeModel(GL_FLAT);
}

void initEDC()
{
State* send = new State();
send->value[0][0] = '1';send->value[0][1] = '2';send->value[0][2] = '3';
send->value[1][0] = '8';send->value[1][1] = '0';send->value[1][2] = '4';
send->value[2][0] = '7';send->value[2][1] = '6';send->value[2][2] = '5';
send->blankx = 1;send->blanky = 1;
EDCNode* nend=new EDCNode();
nend->InitEDCNode(0, send, 0, 0, 0, 0);

EDCNode* nstart = new EDCNode(*nend);

edc = new EDC(nstart, nend, 0, 1, 0, 0);
edc->StartEDC();

delete nstart;
delete nend;
delete send;
//edc->InsertToOpenList(edc->GetStart());

}

void releaseEDC()
{
if (edc)
{
   delete edc;
}
}

int main(int argc, char** argv)
{
initEDC();
int gParas, hParasDn, hParasPn, hParasSn;
printf("估价函数 F(n) = G(n) + H(n) \n");
printf("其中 G(n)有两种计算方式： 输入1时G(child)=G(parent)+H(child,parent)，输入0时G(child)=g(parent)+1\n请输入：");
scanf("%d", &gParas);
printf("其中 H(n)的计算方式为：H(n) = aDn + bPn + cSn \n");
printf("D(n)表示起始节点的格局与目标节点格局的不同牌数，包括空格 \n");
printf("P(n)是指当前格局各将牌离“家”的最短路径之和，包括空格 \n");
printf("S(n)计算方法：依照顺时针方向来检查非中心位置的每个奖牌，若其后紧跟的将牌与目标格局一致，该将牌得0分，否则得2分；中间方格有将牌得1分，否则得0分。所有将牌得分之和即为S(n)。 \n");
printf("请输入a、b、c的值：");
scanf("%d%d%d", &hParasDn, &hParasPn, &hParasSn);
if (!edc)
{
   printf("创建edc对象失败，退出！");
   return 0;
}
edc->SetParas(gParas, hParasDn, hParasPn, hParasSn);
glutInit(&argc, argv);
glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB);
glutInitWindowSize(1000, 700);
glutInitWindowPosition(0, 0);
glutCreateWindow(argv[0]);
//glutFullScreen();
initGL();
glutKeyboardFunc(processNormalKeys);
glutSpecialFunc(processSpecialKeys);
glutDisplayFunc(display);
glutReshapeFunc(reshape);
glutMainLoop();
return 0;
}

 

 

程序运行效果图如下：

 

 

 

按键操作提示
进入图形化界面后，可按下相关键进行操作，一下是按键说明：
 F1：输入状态，用于调整八数码的起始状态，按下该键后，才能编辑八数码的起始状态，方向键有效。
 F2：遍历状态，用于八数码查找路径的单步演示，按下该键后，回车键才有效，F1键无效。
 F3：重来状态，用于八数码重新单步演示及修改起始状态，按下该键后，按F1有效。
 a：调整界面可视视图，视图向左移动一个单位。
 d：调整界面可视视图，视图向右移动一个单位。
 w：调整界面可视视图，视图向上移动一个单位。
 s：调整界面可视视图，视图向下移动一个单位。
 空格：调整界面可视视图，视图回归初始位置。
 回车：在遍历状态下，按该键进行单步演示。
 向上方向键：调整八数码的起始状态，空格下移，下边的数字上移。
 向下方向键：调整八数码的起始状态，空格上移，上边的数字下移。
 向左方向键：调整八数码的起始状态，空格右移，右边的数字左移。
 向右方向键：调整八数码的起始状态，空格左移，左边的数字右移。