state.cpp

八数码小游戏

#include "StdAfx.h"
#include ".\state.h"
#include "func.h"
#include <cmath>

// default constructor
CState::CState(void)
{
	childNum = 0;
	parent = NULL;
	g = 0;
}

// copy constructor
CState::CState(const CState& state)
{
	childNum = 0;
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			num[i][j] = state.num[i][j];
}

CState::~CState(void)
{
}

// Free the space of childs and all offsprings
// Need careful use!
void CState::Free()
{
	for (int i = 0; i < childNum; i++)
	{
		child[i]->Free();
		delete child[i];
	}
}

// Get the position of number d in (r, c)
void CState::GetPos(int d, int& r, int& c)
{
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
		{
			if (num[i][j] == d)
			{
				r = i;
				c = j;
				return;
			}
		}
}

// generate a new child given a direction for the move of blank grid
// if the direction cannot be expanded, return false
// else return the new created child address in ch.
bool CState::NewChild(int dir, CState* destState, CState*& ch)
{
	CState* c = new CState(*this);
	int r0, c0, r1, c1;
	GetPos(0, r0, c0);
	r1 = r0 + offset[dir].row;
	c1 = c0 + offset[dir].col;
	if (r1 < 0 || r1 > 2 || c1 < 0 || c1 > 2)
	{
		delete c;
		return false;
	}
	Swap(c->num[r0][c0], c->num[r1][c1]);
	c->g = this->g + 1;
	c->h = Distance(c, destState);
	this->child[childNum++] = c;
	c->parent = this;
	
	ch = c;
	return true;
}

// remove a child given its address
void CState::RemoveChild(CState* c)
{
	int i = 0;
	while (i < childNum && child[i] != c)
		i++;
	for (; i < childNum - 1; i++)
		child[i] = child[i + 1];
	childNum--;
}

// update the heuristic information of all offsprings
void CState::UpdateChildren(int var)
{
	g += var;
	for (int i = 0; i < childNum; i++)
		child[i]->UpdateChildren(var);
}

// judge if the state is even
// not used for now, but perhaps will use in the future
bool CState::IsEvenState()
{
	int a[8];
	int m = 0;
	int count = 0;
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			if (num[i][j] != 0)
				a[m++] = num[i][j];

	for (int i = 0; i < 8; i++)
		for (int j = i + 1; j < 8; j++)
			if (a[i] > a[j])
				count++;

	if (count % 2 == 0)
		return true;
	else
		return false;
}

// compute the distance of two states. It's a friend of CState class.
int Distance(CState* a, CState* b)
{
	int sum = 0;
	int r, c;
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
		{
			b->GetPos(a->num[i][j], r, c);
			sum += abs(i - r) + abs(j - c);
		}

	return sum;
}