graphics.cpp

solve the 8-puzzle problem using A* algorithm. Definitely written by my self, also include BGI graph

////////////////////////////////////////////////////////////////////////
//
//   Program Name:  Graphics Engine (Implementation File)
//  	Description:  WinBgi package extracted from:
//                  http://csci.biola.edu/csci105/using_winbgi.html  
//
//                  *slightly modified to run for gcc by N.Reyes              
//
//        History:  18 July 2005
//
////////////////////////////////////////////////////////////////////////


#include <windows.h>
#include <stddef.h>
#include <stdio.h>
#include <math.h>


#include <stdlib.h>
#include <time.h>
#include <string.h>


#include "graphics.h"

///////////////////////////////////////////////////////////////////////

int bgiemu_handle_redraw = TRUE;
int bgiemu_default_mode = VGAHI; //VGAMAX;
///////////////////////////////////////////////////////////////////////

class char_queue { 
  protected:
    char* buf; 
    int   put_pos;
    int   get_pos;
    int   buf_size; 
  public:
    void  put(char ch) { 
	buf[put_pos] = ch; 
	if (++put_pos == buf_size) { 
	    put_pos = 0;
	}
	if (put_pos == get_pos) { // queue is full
	    (void)get(); // loose one character
	}
    }
    char get() { 
	char ch = buf[get_pos]; 
	if (++get_pos == buf_size) { 
	    get_pos = 0;
	}
	return ch;
    }
    bool is_empty() { 
	return get_pos == put_pos; 
    }
    char_queue(int buf_size = 256) { 
	put_pos = get_pos = 0;
	this->buf_size = buf_size;
	buf = new char[buf_size]; 
    }
    ~char_queue() { 
	delete[] buf; 
    }
};

static char_queue kbd_queue;

inline int convert_userbits(DWORD buf[32], unsigned pattern)
{
    int i = 0, j;
    pattern &= 0xFFFF;

    while (true) { 
	for (j = 0; pattern & 1; j++) pattern >>= 1;
	buf[i++] = j;
	if (pattern == 0) { 
	    buf[i++] = 16 - j;
	    return i;
	}
	for (j = 0; !(pattern & 1); j++) pattern >>= 1;
	buf[i++] = j;
    }
} 


class l2elem { 
  public: 
    l2elem* next;
    l2elem* prev;

    void link_after(l2elem* after) { 
	(next = after->next)->prev = this;
	(prev = after)->next = this;
    }
    void unlink() { 
	prev->next = next;
	next->prev = prev;
    }
    void prune() { 
	next = prev = this;
    }
};

class l2list : public l2elem { 
  public:
    l2list() { prune(); }
};

class pen_cache : public l2list { 
    class pen_cache_item : public l2elem {
      public:
    	HPEN pen;
        int  color;
	int  width;
	int  style;
	unsigned pattern;
    };  
    pen_cache_item* free;
    pen_cache_item  cache[PEN_CACHE_SIZE];

  public: 
    pen_cache() { 
	for (int i = 0; i < PEN_CACHE_SIZE-1; i++) { 
	    cache[i].next = &cache[i+1];
	}
	cache[PEN_CACHE_SIZE-1].next = NULL;
	free = cache;
    }
    void select(int color) 
    {
	for (l2elem* elem = next; elem != this; elem = elem->next) { 
	    pen_cache_item* ci = (pen_cache_item*)elem;
	    if (ci->color == color &&
		ci->style == line_settings.linestyle &&
		ci->width == line_settings.thickness &&
		(line_settings.linestyle != USERBIT_LINE 
		 || line_settings.upattern == ci->pattern))
	    {
		ci->unlink(); // LRU discipline
		ci->link_after(this); 

		if (hPen != ci->pen) { 
		    hPen = ci->pen;
		    SelectObject(hdc[0], hPen);
		    SelectObject(hdc[1], hPen);
		}
		return;	    
	    }
	}
	hPen = NULL;
	if (line_settings.linestyle == USERBIT_LINE) { 
	    LOGBRUSH lb;
	    lb.lbColor = PALETTEINDEX(color);
	    lb.lbStyle = BS_SOLID;
	    DWORD style[32]; 
	    hPen = ExtCreatePen(PS_GEOMETRIC|PS_USERSTYLE, 
				line_settings.thickness, &lb, 
				convert_userbits(style,line_settings.upattern),
				style);
	} 
	if (hPen == NULL) { 
	    hPen = CreatePen(line_style_cnv[line_settings.linestyle], 
			     line_settings.thickness, 
			     PALETTEINDEX(color));
	}
	SelectObject(hdc[0], hPen);
	SelectObject(hdc[1], hPen);
	
	pen_cache_item* p;
	if (free == NULL) {
	    p = (pen_cache_item*)prev; 
	    p->unlink();
	    DeleteObject(p->pen);	    
	} else { 
	    p = free;
	    free = (pen_cache_item*)p->next;
	}
	p->pen   = hPen;
	p->color = color;
	p->width = line_settings.thickness;
	p->style = line_settings.linestyle;
	p->pattern = line_settings.upattern;
	p->link_after(this);
    }  
};	


static pen_cache pcache;



class font_cache : public l2list { 
    class font_cache_item : public l2elem {
      public:
    	HFONT font;
        int   type;
	int   direction;
	int   width, height;
    };  
    font_cache_item* free;
    font_cache_item  cache[FONT_CACHE_SIZE];

  public: 
    font_cache() { 
	for (int i = 0; i < FONT_CACHE_SIZE-1; i++) { 
	    cache[i].next = &cache[i+1];
	}
	cache[FONT_CACHE_SIZE-1].next = NULL;
	free = cache;
    }
    void select(int type, int direction, int width, int height) 
    {
	for (l2elem* elem = next; elem != this; elem = elem->next) { 
	    font_cache_item* ci = (font_cache_item*)elem;
	    if (ci->type == type &&
		ci->direction == direction &&
		ci->width == width &&
		ci->height == height)
	    {
		ci->unlink();
		ci->link_after(this);

		if (hFont != ci->font) { 
		    hFont = ci->font;
		    SelectObject(hdc[0], hFont);
		    SelectObject(hdc[1], hFont);
		}
		return;	    
	    }
	}
	hFont = CreateFont(-height,
			   width,
			   direction*900,
			   (direction&1)*900,
			   font_weight[type],
			   FALSE,
			   FALSE,
			   FALSE,
			   DEFAULT_CHARSET, 
			   OUT_DEFAULT_PRECIS,
			   CLIP_DEFAULT_PRECIS,
			   DEFAULT_QUALITY,
			   font_family[type], 
			   font_name[type]);
	SelectObject(hdc[0], hFont);
	SelectObject(hdc[1], hFont);
	
	font_cache_item* p;
	if (free == NULL) {
	    p = (font_cache_item*)prev; 
	    p->unlink();
	    DeleteObject(p->font);	    
	} else { 
	    p = free;
	    free = (font_cache_item*)p->next;
	}
	p->font = hFont;
	p->type = type;
	p->width = width;
	p->height = height;
	p->direction = direction;
	p->link_after(this);
    }  
};	


static font_cache fcache;


#define FLAGS         PC_NOCOLLAPSE
#define PALETTE_SIZE  256

static PALETTEENTRY BGIcolor[64] = {
		{ 0, 0, 0, FLAGS },        // 0
		{ 0, 0, 255, FLAGS },        // 1
		{ 0, 255, 0, FLAGS },        // 2
		{ 0, 255, 255, FLAGS },        // 3
		{ 255, 0, 0, FLAGS },        // 4
		{ 255, 0, 255, FLAGS },         // 5
		{ 165, 42, 42, FLAGS },        // 6
		{ 211, 211, 211, FLAGS },         // 7
		{ 47, 79, 79, FLAGS },        // 8
		{ 173, 216, 230, FLAGS },        // 9
		{ 32, 178, 170, FLAGS },        // 10
		{ 224, 255, 255, FLAGS },        // 11
		{ 240, 128, 128, FLAGS },        // 12
		{ 219, 112, 147, FLAGS },        // 13
		{ 255, 255, 0, FLAGS },        // 14
		{ 255, 255, 255, FLAGS },        // 15
        { 0xF0, 0xF8, 0xFF, FLAGS },        // 16
        { 0xFA, 0xEB, 0xD7, FLAGS },        // 17
        { 0x22, 0x85, 0xFF, FLAGS },        // 18
        { 0x7F, 0xFF, 0xD4, FLAGS },        // 19
        { 0xF0, 0xFF, 0xFF, FLAGS },        // 20
        { 0xF5, 0xF5, 0xDC, FLAGS },        // 21
        { 0xFF, 0xE4, 0xC4, FLAGS },        // 22
        { 0xFF, 0x7B, 0xCD, FLAGS },        // 23
        { 0x00, 0x00, 0xFF, FLAGS },        // 24
        { 0x8A, 0x2B, 0xE2, FLAGS },        // 25
        { 0xA5, 0x2A, 0x2A, FLAGS },        // 26
        { 0xDE, 0xB8, 0x87, FLAGS },        // 27
        { 0x5F, 0x9E, 0xA0, FLAGS },        // 28
        { 0x7F, 0xFF, 0x00, FLAGS },        // 29
        { 0xD2, 0x50, 0x1E, FLAGS },        // 30
        { 0xFF, 0x7F, 0x50, FLAGS },        // 31
        { 0x64, 0x95, 0xED, FLAGS },        // 32
        { 0xFF, 0xF8, 0xDC, FLAGS },        // 33
        { 0xDC, 0x14, 0x3C, FLAGS },        // 34
        { 0x68, 0xCF, 0xDF, FLAGS },        // 35
        { 0x00, 0x00, 0x8B, FLAGS },        // 36
        { 0x00, 0x8B, 0x8B, FLAGS },        // 37
        { 0xB8, 0x86, 0x0B, FLAGS },        // 38
        { 0xA9, 0xA9, 0xA9, FLAGS },        // 39
        { 0x00, 0x64, 0x00, FLAGS },        // 40
        { 0xBD, 0xB7, 0x6B, FLAGS },        // 41
        { 0x8B, 0x00, 0x8B, FLAGS },        // 42
        { 0x55, 0x6B, 0x2F, FLAGS },        // 43
        { 0xFF, 0x8C, 0x00, FLAGS },        // 44
        { 0xB9, 0x82, 0xFC, FLAGS },        // 45
        { 0x8B, 0x00, 0x00, FLAGS },        // 46
        { 0xE9, 0x96, 0x7A, FLAGS },        // 47
        { 0x8F, 0xBC, 0x8F, FLAGS },        // 48
        { 0x48, 0x3D, 0x8B, FLAGS },        // 49
        { 0x2F, 0x4F, 0x4F, FLAGS },        // 50
        { 0x00, 0xCE, 0xD1, FLAGS },        // 51
        { 0x94, 0x00, 0xD3, FLAGS },        // 52
        { 0xFF, 0x14, 0x93, FLAGS },        // 53
        { 0x00, 0xBF, 0xFF, FLAGS },        // 54
        { 0x69, 0x69, 0x69, FLAGS },        // 55
        { 0x1E, 0x90, 0xFF, FLAGS },        // 56
        { 0xB2, 0x22, 0x22, FLAGS },        // 57
        { 0xFF, 0xFA, 0xF0, FLAGS },        // 58
        { 0x22, 0x8B, 0x22, FLAGS },        // 59
        { 0xFF, 0x00, 0xFF, FLAGS },        // 60
        { 0xDC, 0xDC, 0xDC, FLAGS },        // 61
        { 0xF8, 0xF8, 0xBF, FLAGS },        // 62
        { 0xFF, 0xD7, 0x00, FLAGS },        // 63
};
    
static PALETTEENTRY BGIpalette[64];

static short SolidBrushBitmap[8] = 
  {~0xFF, ~0xFF, ~0xFF, ~0xFF, ~0xFF, ~0xFF, ~0xFF, ~0xFF};  
static short LineBrushBitmap[8] = 
  {~0x00, ~0x00, ~0x00, ~0x00, ~0x00, ~0x00, ~0x00, ~0xFF};
static short LtslashBrushBitmap[8] = 
  {~0x01, ~0x02, ~0x04, ~0x08, ~0x10, ~0x20, ~0x40, ~0x80};
static short SlashBrushBitmap[8] = 
  {~0x81, ~0x03, ~0x06, ~0x0C, ~0x18, ~0x30, ~0x60, ~0xC0};
static short BkslashBrushBitmap[8] = 
  {~0xC0, ~0x60, ~0x30, ~0x18, ~0x0C, ~0x06, ~0x03, ~0x81};
static short LtbkslashBrushBitmap[8] = 
  {~0x80, ~0x40, ~0x20, ~0x10, ~0x08, ~0x04, ~0x02, ~0x01};
static short HatchBrushBitmap[8] = 
  {~0x01, ~0x01, ~0x01, ~0x01, ~0x01, ~0x01, ~0x01, ~0xFF};
static short XhatchBrushBitmap[8] = 
  {~0x81, ~0x42, ~0x24, ~0x18, ~0x18, ~0x24, ~0x42, ~0x81};
static short InterleaveBrushBitmap[8] = 
  {~0x55, ~0xAA, ~0x55, ~0xAA, ~0x55, ~0xAA, ~0x55, ~0xAA};
static short WidedotBrushBitmap[8] = 
  {~0x00, ~0x00, ~0x00, ~0x00, ~0x00, ~0x00, ~0x00, ~0x01};
static short ClosedotBrushBitmap[8] = 
  {~0x44, ~0x00, ~0x11, ~0x00, ~0x44, ~0x00, ~0x11, ~0x00};
	
char* grapherrormsg(int code) {	
    static char buf[256];
    FormatMessage(FORMAT_MESSAGE_FROM_SYSTEM, 
    	          NULL, code, 0, 
    	          buf, sizeof buf, NULL);
    return buf;
}

static int gdi_error_code;

int graphresult()
{
    return gdi_error_code; 
}

void setcolor(int c)
{
    c &= MAXCOLORS;
    color = c;
    SetTextColor(hdc[0], PALETTEINDEX(c+BG));
    SetTextColor(hdc[1], PALETTEINDEX(c+BG));
}

int getmaxcolor()
{
    return WHITE;
}

int getmaxmode()
{
    return VGAMAX;
}

char* getmodename(int mode)
{
    static char mode_str[32];
    sprintf(mode_str, "%d x %d %s", window_width, window_height, 
	    mode < 2 ? "EGA" : "VGA");
    return mode_str;
}

int getx()
{
    POINT pos;
    GetCurrentPositionEx(hdc[active_page == visual_page ? 0 : 1], &pos);
    return pos.x;
}

int gety()
{
    POINT pos;
    GetCurrentPositionEx(hdc[active_page == visual_page ? 0 : 1], &pos);
    return pos.y;
}

int getmaxx()
{
    return window_width-1;
}

int getmaxy()
{
    return window_height-1;
}


int getcolor()
{
    return color;
}

char* getdrivername()
{
    return "EGAVGA";
}

void setlinestyle(int style, unsigned int pattern, int thickness)
{
    line_settings.linestyle = style;
    line_settings.thickness = thickness;
    line_settings.upattern  = pattern;
}

void getlinesettings(linesettingstype* ls)
{
    *ls = line_settings;
}