path: root/engines/sword25/math/walkregion.cpp

// -----------------------------------------------------------------------------
// This file is part of Broken Sword 2.5
// Copyright (c) Malte Thiesen, Daniel Queteschiner and Michael Elsd�rfer
//
// Broken Sword 2.5 is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
//
// Broken Sword 2.5 is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with Broken Sword 2.5; if not, write to the Free Software
// Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
// -----------------------------------------------------------------------------

#include <list>
#include <algorithm>
#include "sword25/kernel/inputpersistenceblock.h"
#include "sword25/kernel/outputpersistenceblock.h"
#include "sword25/math/walkregion.h"
#include "sword25/math/line.h"

#define BS_LOG_PREFIX "WALKREGION"

// -----------------------------------------------------------------------------
// Konstanten
// -----------------------------------------------------------------------------

static const int INFINITY = INT_MAX;

// -----------------------------------------------------------------------------
// Konstruktion / Destruktion
// -----------------------------------------------------------------------------

BS_WalkRegion::BS_WalkRegion()
{
	m_Type = RT_WALKREGION;
}

// -----------------------------------------------------------------------------

BS_WalkRegion::BS_WalkRegion(BS_InputPersistenceBlock &Reader, unsigned int Handle) :
	BS_Region(Reader, Handle)
{
	m_Type = RT_WALKREGION;
	Unpersist(Reader);
}

// -----------------------------------------------------------------------------

BS_WalkRegion::~BS_WalkRegion()
{
}

// -----------------------------------------------------------------------------

bool BS_WalkRegion::Init(const BS_Polygon & Contour, const std::vector<BS_Polygon> * pHoles)
{
	// Standard-Initialisierungen der Region vornehmen.
	if (!BS_Region::Init(Contour, pHoles)) return false;

	// Datenstrukturen f�rs Pathfinding vorbereiten
	InitNodeVector();
	ComputeVisibilityMatrix();

	// Erfolg signalisieren.
	return true;
}

// -----------------------------------------------------------------------------

bool BS_WalkRegion::QueryPath(BS_Vertex StartPoint, BS_Vertex EndPoint, BS_Path & Path)
{
	BS_ASSERT(Path.empty());

	// Falls Start und Ziel identisch sind, muss trivialerweise kein Pfad gefunden werden.
	if (StartPoint == EndPoint) return true;

	// Sicherstellen, dass Start und Ziel g�ltig sind und neuen Start- und Zielpunkt finden, falls sie ausserhalb des Polygons liegen.
	if (!CheckAndPrepareStartAndEnd(StartPoint, EndPoint)) return false;

	// Wenn zwischen Start- und Endpunkt eine Sichtlinie besteht, muss kein Pathfindung durchgef�hrt werden und als Ergebnis wird die
	// direkte Verbindungslinie zwischen Start- und Endpunkt zur�ckgegeben.
	if (IsLineOfSight(StartPoint, EndPoint))
	{
		Path.push_back(StartPoint);
		Path.push_back(EndPoint);
		return true;
	}

	return FindPath(StartPoint, EndPoint, Path);
}

// -----------------------------------------------------------------------------

struct DijkstraNode
{
	typedef std::vector<DijkstraNode> Container;
	typedef Container::iterator Iter;
	typedef Container::const_iterator ConstIter;

	DijkstraNode() : Cost(INFINITY), Chosen(false) {};
	ConstIter	ParentIter;
	int			Cost;
	bool		Chosen;
};

static void InitDijkstraNodes(DijkstraNode::Container & DijkstraNodes, const BS_Region & Region, const BS_Vertex & Start, const std::vector<BS_Vertex> & Nodes)
{
	// Ausreichend Platz im Vector reservieren
	DijkstraNodes.resize(Nodes.size());

	// Alle Randknoten initialisieren, die vom Startknoten sichtbar sind
	DijkstraNode::Iter DijkstraIter = DijkstraNodes.begin();
	for (std::vector<BS_Vertex>::const_iterator NodesIter = Nodes.begin(); NodesIter != Nodes.end(); NodesIter++, DijkstraIter++)
	{
		(*DijkstraIter).ParentIter = DijkstraNodes.end();
		if (Region.IsLineOfSight(*NodesIter, Start)) (*DijkstraIter).Cost = (*NodesIter).Distance(Start);
	}
	BS_ASSERT(DijkstraIter == DijkstraNodes.end());
}

static DijkstraNode::Iter ChooseClosestNode(DijkstraNode::Container & Nodes)
{
	DijkstraNode::Iter ClosestNodeInter = Nodes.end();
	int MinCost = INFINITY;

	for (DijkstraNode::Iter iter = Nodes.begin(); iter != Nodes.end(); iter++)
	{
		if (!(*iter).Chosen && (*iter).Cost < MinCost)
		{
			MinCost = (*iter).Cost;
			ClosestNodeInter = iter;
		}
	}

	return ClosestNodeInter;
}

static void RelaxNodes(DijkstraNode::Container & Nodes,
					   const std::vector< std::vector<int> > & VisibilityMatrix, 
					   const DijkstraNode::ConstIter & CurNodeIter)
{
	// Alle Nachfolger vom aktuellen Knoten, die noch nicht gew�hlt wurden, werden in die Randknotenliste eingef�gt und die Kosten werden
	// aktualisiert, wenn ein k�rzerer Pfad zu ihnen gefunden wurde.

	int CurNodeIndex = CurNodeIter - Nodes.begin();
	for (unsigned int i = 0; i < Nodes.size(); i++)
	{
		int Cost = VisibilityMatrix[CurNodeIndex][i];
		if (!Nodes[i].Chosen && Cost != INFINITY)
		{
			int TotalCost = (*CurNodeIter).Cost + Cost;
			if (TotalCost < Nodes[i].Cost)
			{
				Nodes[i].ParentIter = CurNodeIter;
				Nodes[i].Cost = TotalCost;
			}
		}
	}
}

static void RelaxEndPoint(const BS_Vertex & CurNodePos,
						  const DijkstraNode::ConstIter & CurNodeIter,
						  const BS_Vertex & EndPointPos,
						  DijkstraNode & EndPoint,
						  const BS_Region & Region)
{
	if (Region.IsLineOfSight(CurNodePos, EndPointPos))
	{
		int TotalCost = (*CurNodeIter).Cost + CurNodePos.Distance(EndPointPos);
		if (TotalCost < EndPoint.Cost)
		{
			EndPoint.ParentIter = CurNodeIter;
			EndPoint.Cost = TotalCost;
		}
	}
}

bool BS_WalkRegion::FindPath(const BS_Vertex & Start, const BS_Vertex & End, BS_Path & Path) const
{
	// Dies ist eine Implementation des Dijkstra-Algorithmus

	// Randknotenliste initialisieren
	DijkstraNode::Container DijkstraNodes;
	InitDijkstraNodes(DijkstraNodes, *this, Start, m_Nodes);

	// Der Endpunkt wird gesondert behandelt, da er im Sichtbarkeitsgraphen nicht vorhanden ist
	DijkstraNode EndPoint;

	// Da in jedem Durchgang ein Knoten aus der Knotenliste gew�hlt wird, und danach nie wieder gew�hlt werden kann, ist die maximale Anzahl der
	// Schleifendurchl�ufe durch die Anzahl der Knoten begrenzt.
	for (unsigned int i = 0; i < m_Nodes.size(); i++)
	{
		// Bestimme n�chstgelegenen Knoten in der Randknotenliste
		DijkstraNode::Iter NodeInter = ChooseClosestNode(DijkstraNodes);
		(*NodeInter).Chosen = true;

		// Falls kein freier Knoten mehr in der Randknotenliste vorhanden ist, gibt es keinen Weg vom Start- zum Endknoten.
		// Dieser Fall sollte nie auftreten, da die Anzahl der Schleifendurchg�nge begrenzt ist, aber sicher ist sicher.
		if (NodeInter == DijkstraNodes.end()) return false;

		// Wenn der Zielpunkt noch n�her liegt als der n�chte Punkt, ist die Suche beendet
		if (EndPoint.Cost <= (*NodeInter).Cost)
		{
			// Ergebnispfad extrahieren

			// Den Endpunkt in den Ergebnispfad einf�gen
			Path.push_back(End);

			// Die Wegknoten in umgekehrter Reihenfolge ablaufen und in den Ergebnispfad einf�gen
			DijkstraNode::ConstIter CurNode = EndPoint.ParentIter;
			while (CurNode != DijkstraNodes.end())
			{
				BS_ASSERT((*CurNode).Chosen);
				Path.push_back(m_Nodes[CurNode - DijkstraNodes.begin()]);
				CurNode = (*CurNode).ParentIter;
			}

			// Den Startpunkt in den Ergebnispfad einf�gen
			Path.push_back(Start);

			// Die Knoten des Pfades m�ssen ungedreht werden, da sie in umgekehrter Reihenfolge extrahiert wurden.
			// Diesen Schritt k�nnte man sich sparen, wenn man den Pfad vom Ende zum Anfang sucht.
			std::reverse(Path.begin(), Path.end());

			return true;
		}

		// Relaxation-Schritt f�r die Knoten des Graphen und f�r den Endknoten durchf�hren
		RelaxNodes(DijkstraNodes, m_VisibilityMatrix, NodeInter);
		RelaxEndPoint(m_Nodes[NodeInter - DijkstraNodes.begin()], NodeInter, End, EndPoint, *this);
	}

	// Falls die Schleife komplett durchlaufen wurde, wurden alle Knoten gew�hlt und es wurde trotzdem kein Pfad gefunden. Es existiert also keiner.
	return false;
}

// -----------------------------------------------------------------------------

void BS_WalkRegion::InitNodeVector()
{
	// Knoten-Vector leeren.
	m_Nodes.clear();

	// Anzahl der Knoten bestimmen.
	int NodeCount = 0;
	{
		for (unsigned int i = 0; i < m_Polygons.size(); i++)
			NodeCount += m_Polygons[i].VertexCount;
	}

	// Knoten-Vector f�llen
	m_Nodes.reserve(NodeCount);
	{
		for (unsigned int j = 0; j < m_Polygons.size(); j++)
			for (int i = 0; i < m_Polygons[j].VertexCount; i++)
				m_Nodes.push_back(m_Polygons[j].Vertecies[i]);
	}
}

// -----------------------------------------------------------------------------

void BS_WalkRegion::ComputeVisibilityMatrix()
{
	// Sichtbarkeitsmatrix initialisieren
	m_VisibilityMatrix = std::vector< std::vector <int> >(m_Nodes.size(), std::vector<int>(m_Nodes.size(), INFINITY));

	// Sichtbarkeiten zwischen Vertecies berechnen und in die Sichbarkeitsmatrix eintragen.
	for (unsigned int j = 0; j < m_Nodes.size(); ++j)
	{
		for (unsigned int i = j; i < m_Nodes.size(); ++i)
		{
			if (IsLineOfSight(m_Nodes[i], m_Nodes[j]))
			{
				// Wenn eine Sichtlinie besteht wird die Entfernung der Knoten eingetragen
				int Distance = m_Nodes[i].Distance(m_Nodes[j]);
				m_VisibilityMatrix[i][j] = Distance;
				m_VisibilityMatrix[j][i] = Distance;
			}
			else
			{
				// Wenn keine Sichtlinie besteht wird die Entfernung "unendlich" eingetragen
				m_VisibilityMatrix[i][j] = INFINITY;
				m_VisibilityMatrix[j][i] = INFINITY;
			}
		}
	}
}

// -----------------------------------------------------------------------------

bool BS_WalkRegion::CheckAndPrepareStartAndEnd(BS_Vertex & Start, BS_Vertex & End) const
{
	if (!IsPointInRegion(Start))
	{
		BS_Vertex NewStart = FindClosestRegionPoint(Start);

		// Sicherstellen, dass der ermittelte Punkt wirklich innerhalb der Region liegt und Notfalls abbrechen.
		if (!IsPointInRegion(NewStart))
		{
			BS_LOG_ERRORLN("Constructed startpoint ((%d,%d) from (%d,%d)) is not inside the region.",
				NewStart.X, NewStart.Y,
				Start.X, Start.Y);
			return false;
		}

		Start = NewStart;
	}

	// Falls der Zielpunkt au�erhalb der Region liegt, wird der n�chste Punkt innerhalb der Region bestimmt und als Endpunkt benutzt.
	if (!IsPointInRegion(End))
	{
		BS_Vertex NewEnd = FindClosestRegionPoint(End);

		// Sicherstellen, dass der ermittelte Punkt wirklich innerhalb der Region liegt und Notfalls abbrechen.
		if (!IsPointInRegion(NewEnd))
		{
			BS_LOG_ERRORLN("Constructed endpoint ((%d,%d) from (%d,%d)) is not inside the region.",
				NewEnd.X, NewEnd.Y,
				End.X, End.Y);
			return false;
		}

		End = NewEnd;
	}

	// Erfolg signalisieren
	return true;
}

// -----------------------------------------------------------------------------

void BS_WalkRegion::SetPos(int X, int Y)
{
	// Unterschied zwischen alter und neuer Position berechnen.
	BS_Vertex Delta(X - m_Position.X, Y - m_Position.Y);

	// Alle Nodes verschieben.
	for (unsigned int i = 0; i < m_Nodes.size(); i++) m_Nodes[i] += Delta;

	// Region verschieben
	BS_Region::SetPos(X, Y);
}

// -----------------------------------------------------------------------------

bool BS_WalkRegion::Persist(BS_OutputPersistenceBlock & Writer)
{
	bool Result = true;

	// Elternobjekt persistieren.
	Result &= BS_Region::Persist(Writer);

	// Knoten persistieren.
	Writer.Write(m_Nodes.size());
	std::vector<BS_Vertex>::const_iterator It = m_Nodes.begin();
	while (It != m_Nodes.end())
	{
		Writer.Write(It->X);
		Writer.Write(It->Y);
		++It;
	}

	// Sichtbarkeitsmatrix persistieren.
	Writer.Write(m_VisibilityMatrix.size());
	std::vector< std::vector<int> >::const_iterator RowIter = m_VisibilityMatrix.begin();
	while (RowIter != m_VisibilityMatrix.end())
	{
		Writer.Write(RowIter->size());
		std::vector<int>::const_iterator ColIter = RowIter->begin();
		while (ColIter != RowIter->end())
		{
			Writer.Write(*ColIter);
			++ColIter;
		}

		++RowIter;
	}

	return Result;
}

// -----------------------------------------------------------------------------

bool BS_WalkRegion::Unpersist(BS_InputPersistenceBlock & Reader)
{
	bool Result = true;

	// Das Elternobjekt wurde schon �ber den Konstruktor von BS_Region geladen, daher m�ssen an dieser Stelle nur noch die zus�tzlichen Daten von
	// BS_WalkRegion geladen werden.

	// Knoten laden.
	unsigned int NodeCount;
	Reader.Read(NodeCount);
	m_Nodes.clear();
	m_Nodes.resize(NodeCount);
	std::vector<BS_Vertex>::iterator It = m_Nodes.begin();
	while (It != m_Nodes.end())
	{
		Reader.Read(It->X);
		Reader.Read(It->Y);
		++It;
	}

	// Sichtbarkeitsmatrix laden.
	unsigned int RowCount;
	Reader.Read(RowCount);
	m_VisibilityMatrix.clear();
	m_VisibilityMatrix.resize(RowCount);
	std::vector< std::vector<int> >::iterator RowIter = m_VisibilityMatrix.begin();
	while (RowIter != m_VisibilityMatrix.end())
	{
		unsigned int ColCount;
		Reader.Read(ColCount);
		RowIter->resize(ColCount);
		std::vector<int>::iterator ColIter = RowIter->begin();
		while (ColIter != RowIter->end())
		{
			Reader.Read(*ColIter);
			++ColIter;
		}

		++RowIter;
	}

	return Result && Reader.IsGood();
}