path.cpp

VIGASOCO (VIdeo GAmes SOurce COde) Windows port (v0.01)

// Path.cpp
//
//	Note that pacman's mazes are made of tiles >= 0xc0
//
/////////////////////////////////////////////////////////////////////////////

#include <cstdlib>
#include "Game.h"
#include "../Operations.h"
#include "Path.h"
#include "Video.h"

// this table has the (x, y) offsets for a move in any orientation
int movementOffsets[4][2] = {
	{ -1, 0 },		// move right
	{ 0, 1 },		// move down
	{ 1, 0 },		// move left
	{ 0, -1 }		// move up
};

/////////////////////////////////////////////////////////////////////////////
// path related methods
/////////////////////////////////////////////////////////////////////////////

// calculates the square of the distance between 2 points
int Path::distance2(int p1X, int p1Y, int p2X, int p2Y)
{
	return Operations::square<int>(p1X - p2X) + Operations::square<int>(p1Y - p2Y);
}

// calculates the best path between two tiles, given an orientation
void Path::calcPath(int sourceX, int sourceY, Orientation ori, int destX, int destY,
					int &movOffsX, int &movOffsY, Orientation &finalOri)
{
	// calculates the opposite orientation
	Orientation oppositeOri = (Orientation)(ori ^ 0x02);

	finalOri = ori;
	int minDistance = 256*256;

	// tries all orientations
	for (Orientation currentOri = RIGHT; currentOri <= UP; currentOri = (Orientation)(currentOri + 1)){
		// the best path for us is NEVER going back
		if (currentOri == oppositeOri) continue;
		
		// calculates the new position if we move once in the current orientation
		int newPosX = sourceX + movementOffsets[currentOri][0];
		int newPosY = sourceY + movementOffsets[currentOri][1];

		// converts tile position to screen position and gets the asociated tile
		int data = theGame->VRAM[Video::tilePos2ScreenCoord(newPosX, newPosY)];

		// if the tile is >= 0xc0, we can't move in that orientation
		if (data >= 0xc0) continue;

		// calculates distance^2 of the resulting position to the desired position
		int distance2 = Path::distance2(newPosX, newPosY, destX, destY);

		// if the path in the current orientation seems shorter, save it
		if (distance2 < minDistance){
			minDistance = distance2;
			finalOri = currentOri;
		}
	}

	// get best movement offsets
	movOffsX = movementOffsets[finalOri][0];
	movOffsY = movementOffsets[finalOri][1];
}

// calculates a random path, given a point and an orientation
void Path::calcRandomPath(int sourceX, int sourceY, Orientation ori,
						int &movOffsX, int &movOffsY, Orientation &finalOri)
{
	// calculates the opposite orientation
	Orientation oppositeOri = (Orientation)(ori ^ 0x02);

	// picks a new random orientation as the best found
	Orientation currentOri = (Orientation)(rand() & 0x03);

	// keep trying orientations until we find a valid one
	for (int i = 0; i < 4; i++){
		// the best path for us is NEVER going back
		if (currentOri != oppositeOri){
			// calculates the new position if we move once in the current orientation
			int newPosX = sourceX + movementOffsets[currentOri][0];
			int newPosY = sourceY + movementOffsets[currentOri][1];

			// converts tile position to screen position and gets the asociated tile
			int data = theGame->VRAM[Video::tilePos2ScreenCoord(newPosX, newPosY)];

			// if the tile is < 0xc0, we can move in that orientation, exit
			if (data < 0xc0){
				break;
			}
		}

		// tries another orientation
		currentOri = (Orientation)((currentOri + 1) & 0x03);
	}

	// store resulting movement information
	finalOri = currentOri;
	movOffsX = movementOffsets[finalOri][0];
	movOffsY = movementOffsets[finalOri][1];
}