tins2021/tiles.go

package tins2021

import (
	"math"
	"math/rand"

	"opslag.de/schobers/geom"
)

var AllDirections = []Direction{DirectionDownRight, DirectionDownLeft, DirectionUpLeft, DirectionUpRight}

func RandomDirection() Direction {
	return AllDirections[rand.Intn(len(AllDirections))]
}

func AdjacentPosition(pos geom.Point, dir Direction) geom.Point {
	if pos.Y%2 == 0 {
		switch dir {
		case DirectionDownRight:
			return geom.Pt(pos.X+1, pos.Y+1)
		case DirectionDownLeft:
			return geom.Pt(pos.X, pos.Y+1)
		case DirectionUpLeft:
			return geom.Pt(pos.X, pos.Y-1)
		case DirectionUpRight:
			return geom.Pt(pos.X+1, pos.Y-1)
		default:
			panic("invalid direction")
		}
	}
	switch dir {
	case DirectionDownRight:
		return geom.Pt(pos.X, pos.Y+1)
	case DirectionDownLeft:
		return geom.Pt(pos.X-1, pos.Y+1)
	case DirectionUpLeft:
		return geom.Pt(pos.X-1, pos.Y-1)
	case DirectionUpRight:
		return geom.Pt(pos.X, pos.Y-1)
	default:
		panic("invalid direction")
	}
}

type Direction int

const (
	DirectionDownRight Direction = iota
	DirectionDownLeft
	DirectionUpLeft
	DirectionUpRight
)

func (d Direction) Reverse() Direction {
	switch d {
	case DirectionDownRight:
		return DirectionUpLeft
	case DirectionDownLeft:
		return DirectionUpRight
	case DirectionUpLeft:
		return DirectionDownRight
	case DirectionUpRight:
		return DirectionDownLeft
	default:
		panic("direction not supported")
	}
}

type Tile struct {
	Inversed bool
	Star     bool
	Heart    bool
}

func (t *Tile) Occupied() bool {
	return t.Star || t.Heart
}

func (t *Tile) Invert() { t.Inversed = !t.Inversed }

type Tiles map[geom.Point]*Tile

func (t Tiles) AllReachable(from geom.Point) bool {
	visited := map[geom.Point]bool{}
	visit := []geom.Point{from}
	for len(visit) > 0 {
		next := visit[0]
		visit = visit[1:]
		for _, dir := range AllDirections {
			neighbour, ok := t.CanMove(next, dir)
			if !ok || visited[neighbour] {
				continue
			}
			visited[neighbour] = true
			visit = append(visit, neighbour)
		}
	}
	return len(visited) == len(t)
}

func (t Tiles) CanMove(p geom.Point, dir Direction) (geom.Point, bool) {
	towards := AdjacentPosition(p, dir)
	from := t[p]
	to := t[towards]
	if to == nil {
		return geom.Point{}, false
	}
	if dir == DirectionDownRight || dir == DirectionDownLeft {
		if !from.Inversed && to.Inversed {
			return geom.Point{}, false
		}
	} else {
		if from.Inversed && !to.Inversed {
			return geom.Point{}, false
		}
	}
	return towards, true
}

func (t Tiles) CanMoveTile(p geom.Point, dir Direction) (geom.Point, *Tile, bool) {
	to, ok := t.CanMove(p, dir)
	if !ok {
		return geom.Point{}, nil, false
	}
	return to, t[to], true
}

func (t Tiles) Distances(from geom.Point) map[geom.Point]int {
	distance := map[geom.Point]int{
		from: 0,
	}
	visit := []geom.Point{from}
	for len(visit) > 0 {
		next := visit[0]
		visit = visit[1:]
		for _, dir := range AllDirections {
			neighbour, ok := t.CanMove(next, dir)
			if !ok {
				continue
			}
			d := distance[next] + 1
			if neighbourD, ok := distance[neighbour]; ok && neighbourD <= d {
				continue
			}
			distance[neighbour] = d
			visit = append(visit, neighbour)
		}
	}
	return distance
}

func (t Tiles) ShortestPath(from, to geom.Point, canMoveTo func(geom.Point, *Tile) bool) []geom.Point {
	distances := map[geom.Point]int{
		from: 0,
	}
	origins := map[geom.Point]geom.Point{
		from: from,
	}
	estimated := map[geom.Point]int{
		from: from.DistInt(to),
	}
	visit := map[geom.Point]bool{from: true}
	for len(visit) > 0 {
		var next geom.Point
		best := math.MaxInt32
		for candidate := range visit {
			e := estimated[candidate]
			if e < best {
				next = candidate
				best = e
			}
		}
		if next == to {
			path := []geom.Point{to}
			for path[0] != from {
				path = append([]geom.Point{origins[path[0]]}, path...)
			}
			return path
		}
		delete(visit, next)
		for _, dir := range AllDirections {
			neighbour, ok := t.CanMove(next, dir)
			if !ok || (canMoveTo != nil && !canMoveTo(neighbour, t[neighbour])) {
				continue
			}
			d := distances[next] + 1
			if neighbourD, ok := distances[neighbour]; ok && neighbourD <= d {
				continue
			}
			distances[neighbour] = d
			origins[neighbour] = next
			estimated[neighbour] = d + neighbour.DistInt(to)
			visit[neighbour] = true
		}
	}
	return []geom.Point{}
}