grid.go

package grid

import (
	"image"
	"math"

	"github.com/s0rg/array2d"
	"github.com/s0rg/set"
	"github.com/s0rg/vec2d"
	"github.com/zyedidia/generic/heap"
)

const one = 1.0

// Iter is an iteration callback.
type Iter[T any] func(image.Point, T) bool

// Cast is a ray-casting callback.
type Cast[T any] func(image.Point, float64, T) bool

// Cost is a path-finding callback.
type Cost[T any] func(image.Point, float64, T) (float64, bool)

// Distance is a distance-measurement function.
type Distance func(a, b image.Point) float64

// Map represents generic 2D grid map.
type Map[T any] struct {
	cells array2d.Array[T]
	rc    image.Rectangle
}

// New return empty [Map] with given bounding rectangle.
func New[T any](rc image.Rectangle) (rv *Map[T]) {
	return &Map[T]{
		rc:    rc,
		cells: array2d.New[T](rc.Dx(), rc.Dy()),
	}
}

// Bounds returns grid width and height.
func (m *Map[T]) Bounds() (w, h int) {
	return m.cells.Bounds()
}

// Rectangle returns grid bounding rectangle.
func (m *Map[T]) Rectangle() image.Rectangle {
	return m.rc
}

// Get returns value (if any) at given point.
func (m *Map[T]) Get(p image.Point) (c T, ok bool) {
	return m.cells.Get(p.X, p.Y)
}

// MustGet returns value at given point, it will panic on out-of-bound access.
func (m *Map[T]) MustGet(p image.Point) (c T) {
	var ok bool

	if c, ok = m.Get(p); ok {
		return c
	}

	panic("grid: out-of-bounds access")
}

// Set sets value at given point.
func (m *Map[T]) Set(p image.Point, v T) (ok bool) {
	return m.cells.Set(p.X, p.Y, v)
}

// Iter iterates over map cells.
func (m *Map[T]) Iter(it Iter[T]) {
	m.cells.Iter(func(x, y int, v T) (next bool) {
		return it(image.Pt(x, y), v)
	})
}

// Fill fills map with given constructor.
func (m *Map[T]) Fill(filler func() T) {
	m.cells.Fill(filler)
}

// Neighbours iterates grid cell neighbours in given directions and order.
func (m *Map[T]) Neighbours(
	src image.Point,
	dirs []image.Point,
	iter Iter[T],
) {
	var (
		cur image.Point
		val T
		ok  bool
	)

	for _, d := range dirs {
		cur = src.Add(d)

		if val, ok = m.cells.Get(cur.X, cur.Y); !ok {
			continue
		}

		if !iter(cur, val) {
			break
		}
	}
}

// Path performs A-Star path finding in map.
func (m *Map[T]) Path(
	src, dst image.Point,
	dirs []image.Point,
	dist Distance,
	cost Cost[T],
) (rv []image.Point, ok bool) {
	if !src.In(m.rc) {
		return rv, false
	}

	var val T

	if val, ok = m.cells.Get(dst.X, dst.Y); !ok {
		return rv, false
	}

	tdist := dist(dst, src)

	if _, ok = cost(dst, tdist, val); !ok {
		return rv, false
	}

	var (
		road   *path
		last   image.Point
		closed = make(set.Unordered[image.Point])
	)

	queue := heap.New[*path](func(a, b *path) bool {
		return a.Cost < b.Cost
	})

	queue.Push(road.Fork(src, tdist))

	for queue.Size() > 0 {
		road, _ = queue.Pop()
		last = road.Last()

		if !closed.Add(last) {
			continue
		}

		if last.Eq(dst) {
			return road.Points(), true
		}

		m.Neighbours(last, dirs, func(p image.Point, t T) (ok bool) {
			var ncost float64

			if ncost, ok = cost(p, dist(dst, p), t); ok {
				queue.Push(road.Fork(p, ncost))
			}

			return true
		})
	}

	return nil, false
}

// LineOfSight iterates visible cells within given distance.
func (m *Map[T]) LineOfSight(
	src image.Point,
	distMax float64,
	cast Cast[T],
) {
	if !src.In(m.rc) {
		return
	}

	const maxDegrees = 360.0

	for t := float64(0); t < maxDegrees; t++ {
		m.CastRay(src, t, distMax, cast)
	}
}

// CastRay performs DDA ray cast from point at map with given angle (in degrees), limited by given max distance.
func (m *Map[T]) CastRay(
	src image.Point,
	angle, distMax float64,
	cast Cast[T],
) {
	if !src.In(m.rc) {
		return
	}

	var (
		start      = vec2d.New(float64(src.X), float64(src.Y))
		s, c       = math.Sincos(radians(angle))
		dest       = start.Add(vec2d.New(c, s))
		rdir       = dest.Sub(start).Norm()
		step, rlen vec2d.V[float64]
	)

	if rdir.X < 0 {
		rlen.X = start.X - start.X
		step.X = -one
	} else {
		rlen.X = (start.X + one) - start.X
		step.X = one
	}

	if rdir.Y < 0 {
		rlen.Y = start.Y - start.Y
		step.Y = -one
	} else {
		rlen.Y = (start.Y + one) - start.Y
		step.Y = one
	}

	var (
		unit = vec2d.New(one, one).Div(rdir).Abs()
		mpt  image.Point
		dist float64
		val  T
		ok   bool
	)

	rlen = rlen.Mul(unit)

	for {
		if rlen.X < rlen.Y {
			start.X += step.X
			rlen.X += unit.X
		} else {
			start.Y += step.Y
			rlen.Y += unit.Y
		}

		if dist = math.Max(rlen.X, rlen.Y); dist > distMax {
			break
		}

		mpt = image.Pt(int(start.X), int(start.Y))

		if val, ok = m.cells.Get(mpt.X, mpt.Y); !ok {
			break
		}

		if !cast(mpt, dist, val) {
			break
		}
	}
}

// CastShadow performs recursive shadow-casting.
func (m *Map[T]) CastShadow(
	src image.Point,
	distMax float64,
	cast Cast[T],
) {
	const (
		octetMin = 1
		octetMax = 8
	)

	val, ok := m.cells.Get(src.X, src.Y)
	if !ok {
		return
	}

	cast(src, 0, val)

	for oct := octetMin; oct <= octetMax; oct++ {
		m.emitShadow(src, oct, one, distMax, 0.0, one, cast)
	}
}

// DijkstraMap calculates 'Dijkstra' map for given points.
func (m *Map[T]) DijkstraMap(
	targets []image.Point,
	iter Iter[T],
) (rv *DijkstraMap) {
	rv = &DijkstraMap{
		ranks: array2d.New[uint16](m.cells.Bounds()),
	}

	rv.update(targets, func(p image.Point) (ok bool) {
		val, _ := m.cells.Get(p.X, p.Y)

		return iter(p, val)
	})

	return rv
}

// Line by Bresenham's algorithm.
func (m *Map[T]) LineBresenham(
	src, dst image.Point,
	iter Iter[T],
) {
	if !src.In(m.rc) {
		return
	}

	const two = 2

	var (
		sx, sy = 1, 1
		dx, dy = abs(dst.X - src.X), -abs(dst.Y - src.Y)
		e1     = dx + dy
		e2     int
		val    T
		ok     bool
	)

	if src.X > dst.X {
		sx = -1
	}

	if src.Y > dst.Y {
		sy = -1
	}

	cur := src

	for {
		if val, ok = m.cells.Get(cur.X, cur.Y); !ok {
			break
		}

		if !iter(cur, val) {
			break
		}

		if cur.Eq(dst) {
			break
		}

		e2 = e1 * two

		if e2 >= dy {
			cur.X += sx
			e1 += dy
		}

		if e2 <= dx {
			cur.Y += sy
			e1 += dx
		}
	}
}

func (m *Map[T]) emitShadow(
	src image.Point,
	oct int,
	dist, distMax, slopeLow, slopeHigh float64,
	cast Cast[T],
) {
	if dist > distMax {
		return
	}

	const half = 0.5

	var (
		pt      image.Point
		low     = math.Floor(slopeLow*dist + half)
		high    = math.Ceil(slopeHigh*dist + half)
		val     T
		pdist   float64
		gap, ok bool
	)

	for h := low; h < high; h++ {
		pt = octantPoint(src, oct, int(dist), int(h))

		if val, ok = m.cells.Get(pt.X, pt.Y); !ok {
			continue
		}

		if pdist = dist + DistanceEuclidean(src, pt); pdist > distMax {
			continue
		}

		switch {
		case cast(pt, pdist, val):
			gap = true
		case gap:
			m.emitShadow(src, oct, dist+1, distMax, slopeLow, (h-half)/dist, cast)

			slopeLow = (h + half) / dist
			gap = false
		}
	}

	m.emitShadow(src, oct, dist+1, distMax, slopeLow, slopeHigh, cast)
}

func radians(v float64) (d float64) {
	const rad2deg = 180.0 / math.Pi

	return v / rad2deg
}

func octantPoint(p image.Point, oct, d, h int) (rv image.Point) {
	if oct&0x1 > 0 {
		d = -d
	}

	if oct&0x2 > 0 {
		h = -h
	}

	rv.X, rv.Y = d, h

	if oct&0x4 > 0 {
		rv.X, rv.Y = h, d
	}

	return p.Add(rv)
}

func abs(v int) int {
	if v < 0 {
		return -v
	}

	return v
}