package main

import "container/heap"

// Optional game helpers. PathTo returns steps after start, including end.
// nil means no known route; an empty non-nil slice means start == end.
func IsClaimed(bases []Base, p Position) []string {
	owners := []string{}
	seen := map[string]bool{}
	for _, base := range bases {
		if abs(base.Position.X-p.X)+abs(base.Position.Y-p.Y) <= 2 && !seen[base.TeamID] {
			owners = append(owners, base.TeamID)
			seen[base.TeamID] = true
		}
	}
	return owners
}
func IsBase(bases []Base, p Position) (string, bool) {
	for _, base := range bases {
		if base.Position == p {
			return base.TeamID, true
		}
	}
	return "", false
}
func tileAt(grid GameMap, p Position) *Tile {
	if p.X < 0 || p.Y < 0 || p.X >= grid.Width || p.Y >= grid.Height {
		return nil
	}
	index := p.Y*grid.Width + p.X
	if index >= len(grid.Cells) {
		return nil
	}
	return &grid.Cells[index]
}
func IsOre(grid GameMap, p Position) string {
	tile := tileAt(grid, p)
	if tile != nil && (tile.Type == "gold" || tile.Type == "iron") && tile.Amount > 0 {
		return tile.Type
	}
	return ""
}
func CanMoveOnto(grid GameMap, bases []Base, p Position, teamID string) bool {
	tile := tileAt(grid, p)
	if tile == nil || tile.Type == "hidden" || tile.Type == "void" {
		return false
	}
	owner, base := IsBase(bases, p)
	return !base || owner == teamID
}
func PathTo(grid GameMap, start, end Position, bases []Base, teamID string, obstacleCost int) []Position {
	if obstacleCost < 1 || !CanMoveOnto(grid, bases, start, teamID) || !CanMoveOnto(grid, bases, end, teamID) {
		return nil
	}
	distances := map[Position]int{start: 0}
	previous := map[Position]Position{}
	queue := &pathHeap{{start, 0}}
	heap.Init(queue)
	for queue.Len() > 0 {
		item := heap.Pop(queue).(pathItem)
		if item.cost != distances[item.p] {
			continue
		}
		if item.p == end {
			route := []Position{}
			for p := end; p != start; p = previous[p] {
				route = append(route, p)
			}
			for i, j := 0, len(route)-1; i < j; i, j = i+1, j-1 {
				route[i], route[j] = route[j], route[i]
			}
			return route
		}
		for dy := -1; dy <= 1; dy++ {
			for dx := -1; dx <= 1; dx++ {
				if dx == 0 && dy == 0 {
					continue
				}
				next := Position{item.p.X + dx, item.p.Y + dy}
				if !CanMoveOnto(grid, bases, next, teamID) {
					continue
				}
				step := 1
				tile := tileAt(grid, next)
				if tile.Type == "mountain" || tile.Type == "crater" {
					step = obstacleCost
				}
				cost := item.cost + step
				if old, exists := distances[next]; exists && old <= cost {
					continue
				}
				distances[next] = cost
				previous[next] = item.p
				heap.Push(queue, pathItem{next, cost})
			}
		}
	}
	return nil
}
func abs(n int) int {
	if n < 0 {
		return -n
	}
	return n
}

type pathItem struct {
	p    Position
	cost int
}
type pathHeap []pathItem

func (h pathHeap) Len() int           { return len(h) }
func (h pathHeap) Less(i, j int) bool { return h[i].cost < h[j].cost }
func (h pathHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *pathHeap) Push(item any)     { *h = append(*h, item.(pathItem)) }
func (h *pathHeap) Pop() any          { old := *h; item := old[len(old)-1]; *h = old[:len(old)-1]; return item }