net.sf.gridarta.model.floodfill

Class FloodFill<G extends GameObject<G,A,R>,A extends MapArchObject<A>,R extends Archetype<G,A,R>>

java.lang.Object

net.sf.gridarta.model.floodfill.FloodFill<G,A,R>

public class FloodFill<G extends GameObject<G,A,R>,A extends MapArchObject<A>,R extends Archetype<G,A,R>>
extends java.lang.Object

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.

Constructor Summary

Constructors

Constructor and Description
FloodFill()

Method Summary

Modifier and Type	Method and Description
void	floodFill(@NotNull MapModel<G,A,R> mapModel, @NotNull java.awt.Point start, @NotNull java.util.List<? extends BaseObject<G,A,R,?>> archList, @NotNull InsertionModeSet<G,A,R> insertionModeSet) Flood-fill the map.

Methods inherited from class java.lang.Object

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

Constructor Detail

FloodFill

public FloodFill()

Method Detail

floodFill

public void floodFill(@NotNull
                      @NotNull MapModel<G,A,R> mapModel,
                      @NotNull
                      @NotNull java.awt.Point start,
                      @NotNull
                      @NotNull java.util.List<? extends BaseObject<G,A,R,?>> archList,
                      @NotNull
                      @NotNull 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