Fill Algorithms
Home * Board Representation * Bitboards * Fill Algorithms
Fill algorithms perform the union of a set with their consecutive direction-wise shifts. The shifted intermediate sets are likely intersected with some mask to avoid board wraps of certain directions, and/or also to consider the occupancy or any reasonable taboo set (i.e. pawn attacks) as flood stopping obstruction.
For the non sliding pieces, pawn, knight and king, one fill cycle covers all potential moves in one certain direction, or even all moves in different directions. However, for the sliding pieces, bishop, rook and queen, one fill cycle covers a direction-wise move step for a union set of attacked squares reachable in one move. Often, the up to seven direction wise fill cycles may be performed in three parallel prefix steps.
Applications of fill algorithms are related to all kinds of pawn properties, progressive mobility and path finding algorithms, f.i. to find so called Trajectories [2] [3] .
Pawn
Pawn fills are performed by north- or south steps, for span determination on the otherwise empty board. If it is about to consider obstructions, the north- or south Dumb7- or Kogge-Stone occluded fill might be applied.
Knight
King
Sliding Pieces
Albeit intended as direction-wise attack generators, a surrounding loop may determine target in at least N moves sets of sliding pieces as well. One may pass not only pieces as argument, but their attacks repetitively, likely with alternating disjoint directions, i.e. file- versus ranks-attacks for rooks and diagonal versus anti-diagonal attacks for bishops.
Forum Posts
- Re: Hyperbola Quiesscene: hardly any improvement by Karlo Bala Jr., CCC, January 14, 2009 » Hyperbola Quintessence
External Links
- Implementing the flood fill algorithm from CodeCodex
- Pathfinding from Wikipedia
- Panta rhei, "everything flows" from Wikipedia
- Panta Rhei - Alles fliesst (1973), YouTube Video
References
- ↑ Picture gallery "Recognition and Success 1955 - 1972" from The Official M.C. Escher Website
- ↑ Boris Stilman (1994). A Linguistic Geometry of the Chess Model. Advances in Computer Chess 7, pdf draft
- ↑ Boris Stilman (2000). Linguistic Geometry - From Search to Construction (Operations Research/Computer Science Interfaces Series). amazon.com