net.sf.gridarta.model.floodfill.FloodFill< G extends GameObject< G, A, R, A extends MapArchObject< A, R extends Archetype< G, A, R > Class Template Reference

Implements flood-filling. More...

Collaboration diagram for net.sf.gridarta.model.floodfill.FloodFill< G extends GameObject< G, A, R, A extends MapArchObject< A, R extends Archetype< G, A, R >:

Public Member Functions
void	floodFill (@NotNull final MapModel< G, A, R > mapModel, @NotNull final Point start, @NotNull final List<? extends BaseObject< G, A, R, ?>> archList, @NotNull final InsertionModeSet< G, A, R > insertionModeSet)
	Flood-fill the map. More...

Static Private Attributes
static final byte	BLOCKED = 3
static final byte	BORDER = 1
static final byte	NOT_LOOKED_AT = 0
	Constants for lookArea. More...
static final byte	WAS_EMPTY = 2

Detailed Description

Implements flood-filling.

Algorithmic notes: This algorithm replaces the recursive algorithm used before. This algorithm might not look as efficient as the previous recursive one, but it is. Especially, this algorithm uses very low memory (map size bytes) and the stack amount used is very low and constant. This algorithm behaves extremely fast filling from low x / low y to high x / high y but not so fast when filling in the opposite direction. The algorithm has between linear and quadratic performance, proportional to the map size and depending on the start point for the fill. The effective performance is nearly linear because the creation of arches is the far most cost intensive part, and that's independent of the algorithm. The algorithm needs 5-8 ms to fill an entire 24x24 map. The algorithm needs 250-700 ms to fill an entire 240x240 map. The algorithm needs 1300-2800 ms to fill an entire 480x480 map. More efficient algorithms are known to exist. This algorithm works. But:

• This algorithm is fast enough (usually, maps are 24x24).
• In contrast to the previous algorithm, this algorithm does not cause a StackOverflow on large maps.

Author

Christian Hujer

Definition at line 57 of file FloodFill.java.

Member Function Documentation

floodFill()

void net.sf.gridarta.model.floodfill.FloodFill< G extends GameObject< G, A, R, A extends MapArchObject< A, R extends Archetype< G, A, R >.floodFill	(	@NotNull final MapModel< G, A, R >	mapModel,
		@NotNull final Point	start,
		@NotNull final List<? extends BaseObject< G, A, R, ?>>	archList,
		@NotNull final InsertionModeSet< G, A, R >	insertionModeSet
	)

Flood-fill the map.

Parameters

mapModel	the map model to fill
start	starting point for flood-fill
archList	GameObject list to fill with
insertionModeSet	the insertion mode set to use

Definition at line 77 of file FloodFill.java.

References area, net.sf.gridarta.model.floodfill.FloodFill< G extends GameObject< G, A, R, A extends MapArchObject< A, R extends Archetype< G, A, R >.BLOCKED, net.sf.gridarta.model.floodfill.FloodFill< G extends GameObject< G, A, R, A extends MapArchObject< A, R extends Archetype< G, A, R >.BORDER, net.sf.gridarta.utils.Size2D.getHeight(), net.sf.gridarta.model.maparchobject.MapArchObject< A extends MapArchObject< A >.getMapSize(), net.sf.gridarta.utils.Size2D.getWidth(), net.sf.gridarta.model.maparchobject.MapArchObject< A extends MapArchObject< A >.isPointValid(), net.sf.gridarta.model.floodfill.FloodFill< G extends GameObject< G, A, R, A extends MapArchObject< A, R extends Archetype< G, A, R >.NOT_LOOKED_AT, net.sf.gridarta.utils.RandomUtils.RND, and net.sf.gridarta.model.floodfill.FloodFill< G extends GameObject< G, A, R, A extends MapArchObject< A, R extends Archetype< G, A, R >.WAS_EMPTY.

Referenced by net.sf.gridarta.model.floodfill.FillUtils.floodFill().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

BLOCKED

final byte net.sf.gridarta.model.floodfill.FloodFill< G extends GameObject< G, A, R, A extends MapArchObject< A, R extends Archetype< G, A, R >.BLOCKED = 3

staticprivate

Definition at line 68 of file FloodFill.java.

Referenced by net.sf.gridarta.model.floodfill.FloodFill< G extends GameObject< G, A, R, A extends MapArchObject< A, R extends Archetype< G, A, R >.floodFill().

BORDER

final byte net.sf.gridarta.model.floodfill.FloodFill< G extends GameObject< G, A, R, A extends MapArchObject< A, R extends Archetype< G, A, R >.BORDER = 1

staticprivate

Definition at line 64 of file FloodFill.java.

Referenced by net.sf.gridarta.model.floodfill.FloodFill< G extends GameObject< G, A, R, A extends MapArchObject< A, R extends Archetype< G, A, R >.floodFill().

NOT_LOOKED_AT

final byte net.sf.gridarta.model.floodfill.FloodFill< G extends GameObject< G, A, R, A extends MapArchObject< A, R extends Archetype< G, A, R >.NOT_LOOKED_AT = 0

staticprivate

Constants for lookArea.

Definition at line 62 of file FloodFill.java.

Referenced by net.sf.gridarta.model.floodfill.FloodFill< G extends GameObject< G, A, R, A extends MapArchObject< A, R extends Archetype< G, A, R >.floodFill().

WAS_EMPTY

final byte net.sf.gridarta.model.floodfill.FloodFill< G extends GameObject< G, A, R, A extends MapArchObject< A, R extends Archetype< G, A, R >.WAS_EMPTY = 2

staticprivate

Definition at line 66 of file FloodFill.java.

Referenced by net.sf.gridarta.model.floodfill.FloodFill< G extends GameObject< G, A, R, A extends MapArchObject< A, R extends Archetype< G, A, R >.floodFill().

---

The documentation for this class was generated from the following file:

• src/model/src/main/java/net/sf/gridarta/model/floodfill/FloodFill.java