Package net.sf.gridarta.model.floodfill

Class FloodFill<G extends GameObject<G,​A,​R>,​A extends MapArchObject<A>,​R extends Archetype<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 Description
      FloodFill()  

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method 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