#include <MinimalSectorAbstraction.h>

Collaboration diagram for MinimalSectorAbstraction:

[legend]

Public Member Functions
	MinimalSectorAbstraction (Map *map, int sectorSize)
	MinimalSectorAbstraction::MinimalSectorAbstraction() More...

void	OpenGLDraw ()
	MinimalSectorAbstraction::OpenGLDraw() More...

void	Draw (Graphics::Display &display) const

int	GetSector (int x, int y)
	MinimalSectorAbstraction::GetSector() More...

int	GetRegion (int x, int y)
	MinimalSectorAbstraction::GetRegion() More...

void	GetXYLocation (unsigned int sector, unsigned int region, unsigned int &x, unsigned int &y) const
	MinimalSectorAbstraction::GetXYLocation() More...

void	GetNeighbors (unsigned int sector, unsigned int region, std::vector< tempEdgeData > &edges) const
	MinimalSectorAbstraction::GetNeighbors() More...

int	GetAdjacentSector (unsigned int sector, int direction)
	MinimalSectorAbstraction::GetAdjacentSector() More...

void	OptimizeRegionLocations ()
	MinimalSectorAbstraction::OptimizeRegionLocations() More...

void	InitializeOptimization ()
	MinimalSectorAbstraction::InitializeOptimization() More...

bool	PerformOneOptimizationStep ()
	MinimalSectorAbstraction::PerformOneOptimizationStep() More...

int	GetAbstractionBytesUsed ()

Private Member Functions
void	BuildAbstraction ()
	MinimalSectorAbstraction::BuildAbstraction() More...

void	GetEdges (std::vector< std::vector< int > > &areas, int xSector, int ySector, std::vector< tempEdgeData > &edges)
	MinimalSectorAbstraction::GetEdges() More...

void	GetEdgeHelper (std::vector< int > &startRegion, int startIndex, int startOffset, std::vector< int > &targetRegion, int tarGetIndex, int targetOffset, std::vector< tempEdgeData > &edges, int direction)
	MinimalSectorAbstraction::GetEdgeHelper() More...

int	GetSectorRegions (std::vector< int > &area, int absXSector, int absYSector)
	MinimalSectorAbstraction::GetSectorRegions() More...

void	LabelRegion (std::vector< int > &area, int x, int y, int label)
	MinimalSectorAbstraction::LabelRegion() More...

void	StoreSectorInMemory (sectorInfo &si, std::vector< int > &area, std::vector< tempEdgeData > &edges)
	MinimalSectorAbstraction::StoreSectorInMemory() More...

uint8_t	GetAbstractEdge (tempEdgeData &data)
	MinimalSectorAbstraction::GetAbstractEdge() More...

uint8_t	GetAbstractLocation (std::vector< int > area, int value)
	MinimalSectorAbstraction::GetAbstractLocation() More...

int	FindParentRegion (int startLoc, std::vector< int > &parents, int mapXOffset, int mapYOffset)
	MinimalSectorAbstraction::FindParentRegion() More...

double	GetRegionError (int fromSector, int fromRegion, int sx, int sy, double limit)
	MinimalSectorAbstraction::GetRegionError() More...

void	MoveRegionCenter (int sector, int region)
	MinimalSectorAbstraction::MoveRegionCenter() More...

void	ComputePotentialMemorySavings ()
	MinimalSectorAbstraction::ComputePotentialMemorySavings() More...

void	ResetAbstractCenter (int sector, int region)
	MinimalSectorAbstraction::ResetAbstractCenter() More...

Private Attributes
int	numXSectors

int	numYSectors

std::vector< sectorInfo >	sectors

std::vector< uint8_t >	memory

std::vector< std::vector< double > >	regionError

Map *	map

std::vector< std::vector< int > >	areas

int	sectorSize

int	optimizationIndex

Detailed Description

MinimalSectorAbstraction.

Builds a map abstraction

Builds a map abstraction as described in AI Game Programming Wisdom 4.

The abstraction is optimized to use relatively little memory. This is the first version of the abstraction that I wrote. The code could be a bit cleaner...but it works

Definition at line 92 of file MinimalSectorAbstraction.h.

Constructor & Destructor Documentation

◆ MinimalSectorAbstraction()

MinimalSectorAbstraction::MinimalSectorAbstraction	(	Map *	m,
		int	theSectorSize
	)

MinimalSectorAbstraction::MinimalSectorAbstraction()

Constructor for minimal sector abstraction

Parameters

m	The map for which the abstraction is created

Returns: none

Definition at line 52 of file MinimalSectorAbstraction.cpp.

References BuildAbstraction(), Map::GetMapHeight(), Map::GetMapWidth(), map, numXSectors, numYSectors, optimizationIndex, sectors, and sectorSize.

Member Function Documentation

◆ BuildAbstraction()

void MinimalSectorAbstraction::BuildAbstraction ( )

private

MinimalSectorAbstraction::BuildAbstraction()

Start the abstraction buildling process.

The abstraction is built in 3 steps. First, we identify the regions in each sector. Then, we find the edges between each region. Finally we store a compact representation of the abstraction. An optimization phase can optionally be run.

As this isn't production code, we don't actually free any of the memory allocated during the construction of the abstraction.

Parameters

none

Returns: none

Definition at line 81 of file MinimalSectorAbstraction.cpp.

References areas, ComputePotentialMemorySavings(), GetEdges(), GetSectorRegions(), memory, numXSectors, numYSectors, sectors, and StoreSectorInMemory().

Referenced by MinimalSectorAbstraction().

◆ ComputePotentialMemorySavings()

void MinimalSectorAbstraction::ComputePotentialMemorySavings ( )

private

MinimalSectorAbstraction::ComputePotentialMemorySavings()

print how much memory would be saved using 'default' sectors

Parameters

none

Returns: none

Definition at line 1146 of file MinimalSectorAbstraction.cpp.

References GetNeighbors(), and sectors.

Referenced by BuildAbstraction().

◆ Draw()

void MinimalSectorAbstraction::Draw ( Graphics::Display & display ) const

Definition at line 556 of file MinimalSectorAbstraction.cpp.

References Colors::bluegreen, Graphics::Display::DrawLine(), GetNeighbors(), Map::GetOpenGLCoord(), GetXYLocation(), map, numXSectors, numYSectors, sectors, sectorSize, and Colors::yellow.

Referenced by Map2DSectorAbstraction::Draw().

◆ FindParentRegion()

int MinimalSectorAbstraction::FindParentRegion	(	int	startLoc,
		std::vector< int > &	parents,
		int	mapXOffset,
		int	mapYOffset
	)

private

MinimalSectorAbstraction::FindParentRegion()

Helper function for GetRegion()

Does a breadth-first search looking for the region associated with a particular point.

Parameters

startLoc	The initial offset in the region
parents	The possible region centers
mapXOffset	The x offset of the top of the sector
mapYOffset	The y offset of the top of the sector

Returns: The region the point is in

Definition at line 821 of file MinimalSectorAbstraction.cpp.

References Map::GetTerrainType(), kGround, map, and sectorSize.

Referenced by GetRegion().

◆ GetAbstractEdge()

uint8_t MinimalSectorAbstraction::GetAbstractEdge ( tempEdgeData & data )

private

MinimalSectorAbstraction::GetAbstractEdge()

Turn the edge data structure into a compressed edge.

A quick helper function for turning tempEdgeData into a compressed (1byte) edge representation.

Parameters

data edge data

Returns: A 1 byte representation of an edge

Definition at line 365 of file MinimalSectorAbstraction.cpp.

References tempEdgeData::direction, and tempEdgeData::to.

Referenced by StoreSectorInMemory().

◆ GetAbstractionBytesUsed()

int MinimalSectorAbstraction::GetAbstractionBytesUsed ( )

inline

Definition at line 108 of file MinimalSectorAbstraction.h.

References memory, and sectors.

◆ GetAbstractLocation()

uint8_t MinimalSectorAbstraction::GetAbstractLocation	(	std::vector< int >	area,
		int	value
	)

private

MinimalSectorAbstraction::GetAbstractLocation()

Choose a region center.

Find a region center, placing it at the point closest to the average weight of all points in the region.

Parameters

area	The sector data for the computation
value	The region number we are trying to analyze

Returns: The offset of the region center from the sector start

Definition at line 386 of file MinimalSectorAbstraction.cpp.

References sectorSize.

Referenced by ResetAbstractCenter(), and StoreSectorInMemory().

◆ GetAdjacentSector()

int MinimalSectorAbstraction::GetAdjacentSector	(	unsigned int	sector,
		int	direction
	)

MinimalSectorAbstraction::GetAdjacentSector()

Returns the sector in a given direction

Given a direction and a sector, compute which sector is immediately adjacent in that direction.

Parameters

sector	The sector to use
direction	The direction to use

Returns: The sector in the particular direction

Definition at line 735 of file MinimalSectorAbstraction.cpp.

References numXSectors.

Referenced by Map2DSectorAbstraction::ApplyAction(), and Map2DSectorAbstraction::GetSuccessors().

◆ GetEdgeHelper()

void MinimalSectorAbstraction::GetEdgeHelper	(	std::vector< int > &	startRegion,
		int	startIndex,
		int	startOffset,
		std::vector< int > &	targetRegion,
		int	targetIndex,
		int	targetOffset,
		std::vector< tempEdgeData > &	edges,
		int	direction
	)

private

MinimalSectorAbstraction::GetEdgeHelper()

Generic procedure for iterating along the edge of a sector checking for edges.

GetEdgeHelper takes two (assumed) adjacent sectors and checks those sectors for all edges between them. For each sector a startIndex and offset is used so that the same code can be used for any two edges. Checks begin between the startIndex and targetIndex and at each step the indices are updated by the offset.

Parameters

startRegion	This vector holds the region data for the starting sector
startIndex	The first index to check in the startRegion
startOffset	The offset (step) between indices we want to compare
targetRegion	The region data for the goal sector
targetIndex	The first index to check in the target region
targetOffset	The offset (step) between indices we want to compare
edges	The storage for any edges we find
direction	The direction that all edges will go

Returns: none

Definition at line 258 of file MinimalSectorAbstraction.cpp.

References tempEdgeData::direction, tempEdgeData::from, sectorSize, and tempEdgeData::to.

Referenced by GetEdges().

◆ GetEdges()

void MinimalSectorAbstraction::GetEdges	(	std::vector< std::vector< int > > &	areas,
		int	xSector,
		int	ySector,
		std::vector< tempEdgeData > &	edges
	)

private

MinimalSectorAbstraction::GetEdges()

Check for edges in and out of a sector.

This is the high-level code which checks for edges between sectors

Parameters

areas	An array which marks the region for each piece of the map
xSector	The x-sector which we are checking
ySector	The y-sector which we are checking
edges	A vector of edge data holding the edges from this particular region

Returns: none

Definition at line 132 of file MinimalSectorAbstraction.cpp.

References areas, tempEdgeData::direction, tempEdgeData::from, GetEdgeHelper(), numXSectors, numYSectors, sectorSize, and tempEdgeData::to.

Referenced by BuildAbstraction().

◆ GetNeighbors()

void MinimalSectorAbstraction::GetNeighbors	(	unsigned int	sector,
		unsigned int	region,
		std::vector< tempEdgeData > &	edges
	)		const

MinimalSectorAbstraction::GetNeighbors()

Find the edges in/out of the given sector

Extract the edges from the abstraction and return them.

Parameters

sector	The sector to use
region	The region to use
edges	On return contains the edges from this sector/region

Returns: none

Definition at line 691 of file MinimalSectorAbstraction.cpp.

References tempEdgeData::direction, tempEdgeData::from, memory, sectors, and tempEdgeData::to.

Referenced by ComputePotentialMemorySavings(), Draw(), Map2DSectorAbstraction::GetActions(), Map2DSectorAbstraction::GetSuccessors(), and OpenGLDraw().

◆ GetRegion()

int MinimalSectorAbstraction::GetRegion	(	int	x,
		int	y
	)

MinimalSectorAbstraction::GetRegion()

Find the region associated with an x/y coordinate

Returns the region of the sector that the x/y coordinate is in. If coordinates are invalid, returns -1.

Parameters

x	The x-coordinate for the computation
y	The y-coordinate for the computation

Returns: The region for this coordinate

Definition at line 789 of file MinimalSectorAbstraction.cpp.

References FindParentRegion(), GetSector(), Map::GetTerrainType(), kGround, map, memory, sectors, and sectorSize.

Referenced by Map2DSectorAbstraction::GetAbstractState().

◆ GetRegionError()

double MinimalSectorAbstraction::GetRegionError	(	int	fromSector,
		int	fromRegion,
		int	sx,
		int	sy,
		double	limit
	)

private

MinimalSectorAbstraction::GetRegionError()

Compute the "error" for the current region center

Given a point within a region, compute the cost between that point and every neighboring region. Use that cost to formulate an "error" term which is returned.

In this case we compuate the number of nodes expanded above what is optimal (the optimal path length)

An error bound is used to reduce computation. If this point is too expensive (above the error limit) we can stop early.

Parameters

fromSector	The sector we start in
fromRegion	The region we start in
sx	The start x-location in the region
sy	The start y-location in the region
limit	If the error exceeds this limit we can stop

Returns: none

Definition at line 1094 of file MinimalSectorAbstraction.cpp.

Referenced by MoveRegionCenter().

◆ GetSector()

int MinimalSectorAbstraction::GetSector	(	int	x,
		int	y
	)

MinimalSectorAbstraction::GetSector()

Given an x/y coordinate, return the sector

Parameters

x	The x-coordinate for the computation
y	The y-coordinate for the computation

Returns: The sector of the x/y coordinate

Definition at line 765 of file MinimalSectorAbstraction.cpp.

References numXSectors, numYSectors, and sectorSize.

Referenced by Map2DSectorAbstraction::GetAbstractState(), and GetRegion().

◆ GetSectorRegions()

int MinimalSectorAbstraction::GetSectorRegions	(	std::vector< int > &	area,
		int	absXSector,
		int	absYSector
	)

private

MinimalSectorAbstraction::GetSectorRegions()

Do a BFS to find and label the regions in a sector

Does a BFS to find and label all the regions in a sector. Used when building the abstraction

Parameters

area	Data structure containing the labelled points
absXSector	The x offset of the sector
absYSector	The y offset of the sector

Returns: The number of regions in the sector

Definition at line 888 of file MinimalSectorAbstraction.cpp.

References Map::GetTerrainType(), kGround, LabelRegion(), map, and sectorSize.

Referenced by BuildAbstraction().

◆ GetXYLocation()

void MinimalSectorAbstraction::GetXYLocation	(	unsigned int	sector,
		unsigned int	region,
		unsigned int &	x,
		unsigned int &	y
	)		const

MinimalSectorAbstraction::GetXYLocation()

Given a sector and region, compute the x/y location.

Parameters

sector	the sector to use
region	the region to use
x	the x-coordinate of the region center
y	the y-coordinate of the region center

Returns: none

Definition at line 667 of file MinimalSectorAbstraction.cpp.

References memory, numXSectors, sectors, and sectorSize.

Referenced by Draw(), Map2DSectorAbstraction::GetState(), and OpenGLDraw().

◆ InitializeOptimization()

void MinimalSectorAbstraction::InitializeOptimization ( )

MinimalSectorAbstraction::InitializeOptimization()

Initialize variables for optimization

Optimization can be run in one step or incrementally. This initializes the variables to run the optimization incrementally.

Parameters

none

Returns: none

Definition at line 962 of file MinimalSectorAbstraction.cpp.

References optimizationIndex, regionError, and sectors.

Referenced by OptimizeRegionLocations().

◆ LabelRegion()

void MinimalSectorAbstraction::LabelRegion	(	std::vector< int > &	area,
		int	x,
		int	y,
		int	label
	)

private

MinimalSectorAbstraction::LabelRegion()

Do a BFS within a region to label it

Performs the BFS within one region to label that region.

Parameters

area	The stored labels
x	The starting location for the BFS
y	The starting location for the BFS
label	The label to use

Returns: none

Definition at line 936 of file MinimalSectorAbstraction.cpp.

References sectorSize.

Referenced by GetSectorRegions().

◆ MoveRegionCenter()

void MinimalSectorAbstraction::MoveRegionCenter	(	int	sector,
		int	region
	)

private

MinimalSectorAbstraction::MoveRegionCenter()

Optimize a region center

Try every possible location for a region center. Choose the one which minimizes the error returned by GetRegionError.

Parameters

sector	The sector to test
region	The region in the sector to test

Returns: none

Definition at line 1048 of file MinimalSectorAbstraction.cpp.

References areas, fless(), GetRegionError(), memory, numXSectors, regionError, sectors, and sectorSize.

◆ OpenGLDraw()

void MinimalSectorAbstraction::OpenGLDraw ( )

MinimalSectorAbstraction::OpenGLDraw()

Draw the abstraction using OpenGL

Draws the abstraction & edges using OpenGL. If the abstraction is being optimized, draws the edges being optimized in red.

Parameters

none

Returns: none

Definition at line 444 of file MinimalSectorAbstraction.cpp.

References GetNeighbors(), Map::GetOpenGLCoord(), GetXYLocation(), map, numXSectors, numYSectors, optimizationIndex, sectors, and sectorSize.

◆ OptimizeRegionLocations()

void MinimalSectorAbstraction::OptimizeRegionLocations ( )

MinimalSectorAbstraction::OptimizeRegionLocations()

Perform complete optimization on map.

Parameters

none

Returns: none

Definition at line 1030 of file MinimalSectorAbstraction.cpp.

References InitializeOptimization(), and PerformOneOptimizationStep().

◆ PerformOneOptimizationStep()

bool MinimalSectorAbstraction::PerformOneOptimizationStep ( )

MinimalSectorAbstraction::PerformOneOptimizationStep()

Perform one optimization step. Must be called after InitializeOptimization().

Perform a single optimization on the next sector to be optimized.

Parameters

none

Returns: true if the optimization is finished, false otherwise

Definition at line 978 of file MinimalSectorAbstraction.cpp.

References optimizationIndex, and sectors.

Referenced by OptimizeRegionLocations().

◆ ResetAbstractCenter()

void MinimalSectorAbstraction::ResetAbstractCenter	(	int	sector,
		int	region
	)

private

MinimalSectorAbstraction::ResetAbstractCenter()

Reset a region to the weighted average location.

Resets a region center to the weighted average of the region. This is used when optimizing an abstraction a second time to reset the location of the abstract center.

Sometimes more than one region center will get moved to correct for some topology feature, when only one region center really needs to be moved. By moving the region center back to the default location we help improve this case when running optimization a second time

Parameters