Package eu.iv4xr.framework.extensions.pathfinding

Class Sparse2DTiledSurface_NavGraph

java.lang.Object

eu.iv4xr.framework.extensions.pathfinding.Sparse2DTiledSurface_NavGraph

All Implemented Interfaces:

CanDealWithDynamicObstacle<Sparse2DTiledSurface_NavGraph.Tile>, Navigatable<Sparse2DTiledSurface_NavGraph.Tile>, Pathfinder2<Sparse2DTiledSurface_NavGraph.Tile>, XPathfinder<Sparse2DTiledSurface_NavGraph.Tile>

public class Sparse2DTiledSurface_NavGraph
extends Object
implements Navigatable<Sparse2DTiledSurface_NavGraph.Tile>, XPathfinder<Sparse2DTiledSurface_NavGraph.Tile>, CanDealWithDynamicObstacle<Sparse2DTiledSurface_NavGraph.Tile>

Representing a navigation graph over a 2D tiled-world. The world is assumed to be made of tiles/squares, arranged from tile (0,0) to tile (maxX-1,maxY-1) to form a rectangle world.

The tiles are not explicitly stored. Rather, we only store non-navigable tiles. These are tiles that block movement through them. There are two types: Wall and Door. A wall is always non-navigable. A door can be made blocking/unblocking.

The class also implements XPathfinder, so it offers methods to do pathfinding and exploration over the world.

Author:

Wish

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	Sparse2DTiledSurface_NavGraph.Door
static class	Sparse2DTiledSurface_NavGraph.NonNavigableTile
static class	Sparse2DTiledSurface_NavGraph.Tile
static class	Sparse2DTiledSurface_NavGraph.Wall

Field Summary

Fields

Modifier and Type	Field	Description
boolean	diagonalMovementPossible
(package private) Set<Sparse2DTiledSurface_NavGraph.Tile>	frontierCandidates
Map<Integer,Map<Integer,Sparse2DTiledSurface_NavGraph.NonNavigableTile>>	obstacles
Pathfinder<Sparse2DTiledSurface_NavGraph.Tile>	pathfinder
(package private) boolean	perfect_memory_pathfinding	If true, the pathfinder will assume that the whole navgraph has been "seen", so no vertex would count as unreacahble because it is still unseen.
Map<Integer,Set<Integer>>	seen
int	sizeX	The x coordinates of the this tiled-surface starts from 0 until sizeX-1
int	sizeY	The y coordinates of the this tiled-surface starts from 0 until sizeY-1

Constructor Summary

Constructors

Constructor	Description
Sparse2DTiledSurface_NavGraph()

Method Summary

Modifier and Type	Method	Description
void	addObstacle(Sparse2DTiledSurface_NavGraph.Tile o)	Add a non-navigable tile (obstacle).
float	distance(Sparse2DTiledSurface_NavGraph.Tile from, Sparse2DTiledSurface_NavGraph.Tile to)	The distance between two neighboring tiles.
(package private) float	distSq(int x1, int y1, int x2, int y2)
List<Sparse2DTiledSurface_NavGraph.Tile>	explore(int x, int y, int heuristicX, int heuristicY)
List<Sparse2DTiledSurface_NavGraph.Tile>	explore(Sparse2DTiledSurface_NavGraph.Tile startingLocation, Sparse2DTiledSurface_NavGraph.Tile heuristicLocation)	Return a path from the start node to either a frontier-node or an unexplored node (the implementation decides this).
List<Sparse2DTiledSurface_NavGraph.Tile>	findPath(int fromX, int fromY, int toX, int toY)
List<Sparse2DTiledSurface_NavGraph.Tile>	findPath(Sparse2DTiledSurface_NavGraph.Tile from, Sparse2DTiledSurface_NavGraph.Tile to)	Return a path between "from", to "to".
List<Sparse2DTiledSurface_NavGraph.Tile>	getFrontier()	This returns the set of frontier-tiles.
boolean	hasbeenSeen(int x, int y)
boolean	hasbeenSeen(Sparse2DTiledSurface_NavGraph.Tile tile)	Check is the given node is marked as "has been seen".
float	heuristic(Sparse2DTiledSurface_NavGraph.Tile from, Sparse2DTiledSurface_NavGraph.Tile to)	The estimated distance between two arbitrary vertices.
boolean	isBlocking(Sparse2DTiledSurface_NavGraph.Tile tile)	The tile is blocking (true) if it is a wall or a closed door.
boolean	isDoor(int x, int y)
boolean	isWall(int x, int y)
void	markAsSeen(Sparse2DTiledSurface_NavGraph.Tile p)	Mark the given node as "has been seen".
void	markAsSeen(List<Sparse2DTiledSurface_NavGraph.Tile> newlyseen)	Mark a bunch of nodes as "has been seen".
Iterable<Sparse2DTiledSurface_NavGraph.Tile>	neighbours(Sparse2DTiledSurface_NavGraph.Tile t)	Return the neighbors of a tile.
List<Sparse2DTiledSurface_NavGraph.Tile>	neighbours_(int x, int y)	Return the neighbors of a tile.
List<Sparse2DTiledSurface_NavGraph.Tile>	physicalNeighbours(int x, int y)	Return the neighbors of a tile.
void	removeObstacle(Sparse2DTiledSurface_NavGraph.Tile o)	Remove a non-navigable tile (obstacle).
void	setBlockingState(Sparse2DTiledSurface_NavGraph.Tile tile, boolean isBlocking)	Set the the state of this obstacle to blocking or unblocking.
void	setPerfectMemoryPathfinding(Boolean flag)	When true then the pathfinder will consider all nodes in the graph to have been seen.
String	toString()
boolean	usingPerfectMemoryPathfinding()	When true then the pathfinder will consider all nodes in the graph to have been seen.
void	wipeOutMemory()	Mark all vertices as "unseen".

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface eu.iv4xr.framework.extensions.pathfinding.CanDealWithDynamicObstacle

toggleBlockingOff, toggleBlockingOn

Methods inherited from interface eu.iv4xr.framework.extensions.pathfinding.Pathfinder2

isReachableFrom

Methods inherited from interface eu.iv4xr.framework.extensions.pathfinding.XPathfinder

explore

Field Details

sizeX

public int sizeX

The x coordinates of the this tiled-surface starts from 0 until sizeX-1

sizeY

public int sizeY

The y coordinates of the this tiled-surface starts from 0 until sizeY-1

diagonalMovementPossible

public boolean diagonalMovementPossible

perfect_memory_pathfinding

boolean perfect_memory_pathfinding

If true, the pathfinder will assume that the whole navgraph has been "seen", so no vertex would count as unreacahble because it is still unseen. This essentially turns off memory-based path finding. The default of this flag is false.

obstacles

public Map<Integer,Map<Integer,Sparse2DTiledSurface_NavGraph.NonNavigableTile>> obstacles

seen

public Map<Integer,Set<Integer>> seen

frontierCandidates

Set<Sparse2DTiledSurface_NavGraph.Tile> frontierCandidates

pathfinder

public Pathfinder<Sparse2DTiledSurface_NavGraph.Tile> pathfinder

Constructor Details

Sparse2DTiledSurface_NavGraph

public Sparse2DTiledSurface_NavGraph()

Method Details

addObstacle

public void addObstacle(Sparse2DTiledSurface_NavGraph.Tile o)

Add a non-navigable tile (obstacle).

Specified by:

addObstacle in interface CanDealWithDynamicObstacle<Sparse2DTiledSurface_NavGraph.Tile>

removeObstacle

public void removeObstacle(Sparse2DTiledSurface_NavGraph.Tile o)

Remove a non-navigable tile (obstacle).

Specified by:

removeObstacle in interface CanDealWithDynamicObstacle<Sparse2DTiledSurface_NavGraph.Tile>

markAsSeen

public void markAsSeen(Sparse2DTiledSurface_NavGraph.Tile p)

Description copied from interface: XPathfinder

Mark the given node as "has been seen".

Specified by:

markAsSeen in interface XPathfinder<Sparse2DTiledSurface_NavGraph.Tile>

markAsSeen

public void markAsSeen(List<Sparse2DTiledSurface_NavGraph.Tile> newlyseen)

Description copied from interface: XPathfinder

Mark a bunch of nodes as "has been seen".

Specified by:

markAsSeen in interface XPathfinder<Sparse2DTiledSurface_NavGraph.Tile>

hasbeenSeen

public boolean hasbeenSeen(int x,
 int y)

hasbeenSeen

public boolean hasbeenSeen(Sparse2DTiledSurface_NavGraph.Tile tile)

Description copied from interface: XPathfinder

Check is the given node is marked as "has been seen".

Specified by:

hasbeenSeen in interface XPathfinder<Sparse2DTiledSurface_NavGraph.Tile>

isBlocking

public boolean isBlocking(Sparse2DTiledSurface_NavGraph.Tile tile)

The tile is blocking (true) if it is a wall or a closed door. Else it is non-blocking (false).

Specified by:

isBlocking in interface CanDealWithDynamicObstacle<Sparse2DTiledSurface_NavGraph.Tile>

setBlockingState

public void setBlockingState(Sparse2DTiledSurface_NavGraph.Tile tile,
 boolean isBlocking)

Description copied from interface: CanDealWithDynamicObstacle

Set the the state of this obstacle to blocking or unblocking.

Specified by:

setBlockingState in interface CanDealWithDynamicObstacle<Sparse2DTiledSurface_NavGraph.Tile>

isBlocking - If true then the obstacle will be set to its blocking state, and else non-blocking.

isDoor

public boolean isDoor(int x,
 int y)

isWall

public boolean isWall(int x,
 int y)

usingPerfectMemoryPathfinding

public boolean usingPerfectMemoryPathfinding()

When true then the pathfinder will consider all nodes in the graph to have been seen.

Specified by:

usingPerfectMemoryPathfinding in interface XPathfinder<Sparse2DTiledSurface_NavGraph.Tile>

setPerfectMemoryPathfinding

public void setPerfectMemoryPathfinding(Boolean flag)

When true then the pathfinder will consider all nodes in the graph to have been seen.

Specified by:

setPerfectMemoryPathfinding in interface XPathfinder<Sparse2DTiledSurface_NavGraph.Tile>

wipeOutMemory

public void wipeOutMemory()

Mark all vertices as "unseen".

Specified by:

wipeOutMemory in interface XPathfinder<Sparse2DTiledSurface_NavGraph.Tile>

physicalNeighbours

public List<Sparse2DTiledSurface_NavGraph.Tile> physicalNeighbours(int x,
 int y)

Return the neighbors of a tile. A tile u is a neighbor of a tile t if u is adjacent to t. This method does not consider whether u has been seen or not, nor whether u is navigable.

neighbours_

public List<Sparse2DTiledSurface_NavGraph.Tile> neighbours_(int x,
 int y)

Return the neighbors of a tile. A tile u is a neighbor of a tile t if u is adjacent to t, and moreover u is navigable (e.g. it is not a wall or a closed door). If the flag diagonalMovementPossible is true, then tiles that are diagonally touching t are also considered neighbors.

Only neighbors that have been seen before will be included.

neighbours

public Iterable<Sparse2DTiledSurface_NavGraph.Tile> neighbours(Sparse2DTiledSurface_NavGraph.Tile t)

Return the neighbors of a tile. A tile u is a neighbor of a tile t if u is adjacent to t, and moreover u is navigable (e.g. it is not a wall or a closed door). If the flag diagonalMovementPossible is true, then tiles that are diagonally touching t are also considered neighbors.

Only neighbors that have been seen before will be included.

Specified by:

neighbours in interface Navigatable<Sparse2DTiledSurface_NavGraph.Tile>

Parameters:

t - the index of the vertex to inspect.

Returns:

an iterable of the connected neighbours.

heuristic

public float heuristic(Sparse2DTiledSurface_NavGraph.Tile from,
 Sparse2DTiledSurface_NavGraph.Tile to)

The estimated distance between two arbitrary vertices.

Specified by:

heuristic in interface Navigatable<Sparse2DTiledSurface_NavGraph.Tile>

Parameters:

from - : the index of the vertex to travel from.

to - : the index of the vertex to travel to.

Returns:

the estimated distance.

distance

public float distance(Sparse2DTiledSurface_NavGraph.Tile from,
 Sparse2DTiledSurface_NavGraph.Tile to)

The distance between two neighboring tiles.

Specified by:

distance in interface Navigatable<Sparse2DTiledSurface_NavGraph.Tile>

Parameters:

from - : the index of the vertex to travel from.

to - : the index of the vertex to travel to.

Returns:

the measured distance. NaN if nodes are not connected.

findPath

public List<Sparse2DTiledSurface_NavGraph.Tile> findPath(Sparse2DTiledSurface_NavGraph.Tile from,
 Sparse2DTiledSurface_NavGraph.Tile to)

Description copied from interface: Pathfinder2

Return a path between "from", to "to". The path is represented as a list, whose first element is the node "from", and its last element is "to". The method returns null if no path can be found between them.

Specified by:

findPath in interface Pathfinder2<Sparse2DTiledSurface_NavGraph.Tile>

findPath

public List<Sparse2DTiledSurface_NavGraph.Tile> findPath(int fromX,
 int fromY,
 int toX,
 int toY)

getFrontier

public List<Sparse2DTiledSurface_NavGraph.Tile> getFrontier()

This returns the set of frontier-tiles. A tile is a frontier tile if it is a seen/explored tile and it has at least one unexplored and unblocked neighbor. Note that under this definition a frontier does not have to be reachable. You can use findPath(eu.iv4xr.framework.extensions.pathfinding.Sparse2DTiledSurface_NavGraph.Tile,eu.iv4xr.framework.extensions.pathfinding.Sparse2DTiledSurface_NavGraph.Tile) to check which frontiers are reachable.

Specified by:

getFrontier in interface XPathfinder<Sparse2DTiledSurface_NavGraph.Tile>

distSq

float distSq(int x1,
 int y1,
 int x2,
 int y2)

explore

public List<Sparse2DTiledSurface_NavGraph.Tile> explore(Sparse2DTiledSurface_NavGraph.Tile startingLocation,
 Sparse2DTiledSurface_NavGraph.Tile heuristicLocation)

Description copied from interface: XPathfinder

Return a path from the start node to either a frontier-node or an unexplored node (the implementation decides this). A frontier node is a node with at least one unexplored neighbor. Such a path should only traverse though explored nodes, except the last node which could be an unexplored node. It is up to the implementation to guarantee (or at least make effort for it) that the returned path is navigable. To help chosing which frontier or unexplored node to explore to, a 'heuristic node' is also given. The chosen exploration target is expected to be the closest one, among candidate targets, to the given heuristic node.

Specified by:

explore in interface XPathfinder<Sparse2DTiledSurface_NavGraph.Tile>

explore

public List<Sparse2DTiledSurface_NavGraph.Tile> explore(int x,
 int y,
 int heuristicX,
 int heuristicY)

toString

public String toString()

Overrides:

toString in class Object