path: root/go/game/ai.go

package game

import (
	"errors"
	"fmt"
	"math/rand"
	"slices"
	"strconv"
	"strings"
	"sync"

	"github.com/RyanCarrier/dijkstra"
	"muhq.space/muhqs-game/go/log"
)

type UnitAI struct {
	s             *LocalState
	u             *Unit
	actions       chan Action
	target        *Target
	syncGameState *sync.WaitGroup
}

func (ai *UnitAI) String() string {
	return fmt.Sprintf("UnitAI(%s, %v)", getUnitAIDesc(ai.u), ai.u)
}

// NextAction returns the next Action from the AI and if there are more action to receive.
func (ai *UnitAI) NextAction() (a Action, ok bool) {
	a, ok = <-ai.actions
	return
}

// PostAndContinue publishes the action and reports if the AI should continue executing.
func (ai *UnitAI) PostAndContinue(a Action) bool {
	if a == nil {
		return true
	}

	ai.actions <- a
	return ai.awaitGameStateSync()
}

// awaitGameStateSync waits until a new action is needed and reports if the unit is destroyed.
func (ai *UnitAI) awaitGameStateSync() bool {
	ai.syncGameState.Wait()
	ai.syncGameState.Add(1)
	return !ai.u.IsDestroyed()
}

func (ai *UnitAI) promptAction() {
	ai.syncGameState.Done()
}

func (ai *UnitAI) Execute(f func(*UnitAI)) {
	defer close(ai.actions)
	if ai.awaitGameStateSync() {
		// TODO: Investigate hangs when the AI did not issue any actions
		f(ai)
	}
}

func getUnitAIDesc(u *Unit) (desc string) {
	desc = u.Card().getAI()
	if desc == "" {
		desc = SuggestUnitAI(u)
	}
	return desc
}

func NewUnitAI(s *LocalState, u *Unit) *UnitAI {
	aiDesc := getUnitAIDesc(u)
	if aiDesc == "" {
		return nil
	}
	return NewUnitAIFromDesc(s, u, aiDesc)
}

func NewUnitAIFromDesc(s *LocalState, u *Unit, aiDesc string) *UnitAI {
	c := make(chan Action)
	wg := new(sync.WaitGroup)
	wg.Add(1)
	ai := &UnitAI{
		s:             s,
		u:             u,
		actions:       c,
		syncGameState: wg,
	}

	switch aiDesc {
	case "aggressive":
		go ai.Execute(AggressiveAI)
	case "shy":
		go ai.Execute(ShyAI)
	case "wandering":
		aiDesc := u.Card().getCanonicalValues("ai")[0]
		x, err := strconv.Atoi(strings.Split(aiDesc, " ")[1])
		if err != nil {
			log.Panicf("Invalid wandering AI description %s", aiDesc)
		}
		go ai.Execute(func(ai *UnitAI) { WanderingAI(ai, x) })
	case "target-oriented":
		aiDesc := u.Card().getCanonicalValues("ai")[0]
		targetDesc := aiDesc[len("target-oriented")+1:]
		ai.target = newUnitAiTarget(s, newTargetDesc(targetDesc), ai)
		go ai.Execute(TargetOrientedAI)
	}

	return ai
}

func selectRandomTargets(rand *rand.Rand, targets *Targets) error {
	for _, t := range targets.ts {
		for t.RequireSelection() {
			options := t.Options()
			if len(options) == 0 {
				return errors.New("no possible selection")
			}

			idx := rand.Intn(len(options))
			_ = t.AddSelection(options[idx])
		}
	}
	return nil
}

var ErrNoPath = errors.New("no path found")

func generateGraph(tiles []*Tile) *dijkstra.Graph {
	graph := dijkstra.NewGraph()
	for _, t := range tiles {
		graph.AddMappedVertex(t.Position.String())
	}
	return graph
}

func (m *Map) generateMapGraphFor(u *Unit) *dijkstra.Graph {
	graph := generateGraph(m.AllTiles())

	for _, t := range m.AllTiles() {
		tId := t.Position.String()
		for _, neighbour := range TilesInRangeFromOrigin(m, t.Position, 1) {
			if u.IsAvailableTile(neighbour) {
				cost := 2
				if t.OnDiagonal(neighbour) {
					cost = 3
				}
				err := graph.AddMappedArc(tId, neighbour.Position.String(), int64(cost))
				if err != nil {
					log.Panicf("Failed to add mapped arc: %s", err)
				}
			}
		}
	}
	return graph
}

func (m *Map) generateMovementRangeGraphFor(u *Unit) *dijkstra.Graph {
	origin := TileOrContainingPermTile(u).Position
	graph := generateGraph(tilesInRangeFromOrigin(m, origin, u.Movement.Range, true))

	// Add connections for all tiles and their neighbours
	for _, t := range tilesInRangeFromOrigin(m, origin, u.Movement.Range, true) {
		tId := t.Position.String()
		for _, neighbour := range TilesInRangeFromOrigin(m, t.Position, 1) {
			// Skip neighbours not in movement range
			if !IsPositionInRange(neighbour.Position, origin, u.Movement.Range) {
				continue
			}

			if u.IsAvailableTile(neighbour) {
				cost := 2
				if t.OnDiagonal(neighbour) {
					cost = 3
				}
				err := graph.AddMappedArc(tId, neighbour.Position.String(), int64(cost))
				if err != nil {
					log.Panicf("Failed to add mapped arc: %s", err)
				}
			}
		}
	}
	return graph
}

func (m *Map) generateConnectedMovementRangeGraphFor(u *Unit, conn TileType) *dijkstra.Graph {
	origin := TileOrContainingPermTile(u).Position
	graph := generateGraph(tilesInRangeFromOrigin(m, origin, u.Movement.Range, true))

	// Add connections for all tiles and their neighbours
	for _, t := range tilesInRangeFromOrigin(m, origin, u.Movement.Range, true) {
		tId := t.Position.String()
		// Skip tiles with different types
		if t.Type != conn {
			continue
		}
		for _, neighbour := range TilesInRangeFromOrigin(m, t.Position, 1) {
			// Skip neighbours not in movement range or with different type
			if !IsPositionInRange(neighbour.Position, origin, u.Movement.Range) || neighbour.Type != conn {
				continue
			}

			if u.IsAvailableTile(neighbour) {
				cost := 2
				if t.OnDiagonal(neighbour) {
					cost = 3
				}
				err := graph.AddMappedArc(tId, neighbour.Position.String(), int64(cost))
				if err != nil {
					log.Panicf("Failed to add mapped arc: %s", err)
				}
			}
		}
	}
	return graph
}

func findPathTo(graph *dijkstra.Graph, u *Unit, pos Position) (dijkstra.BestPath, error) {
	srcId, err := graph.GetMapping(TileOrContainingPermTile(u).Position.String())
	if err != nil {
		log.Panicf("No mapping %s in Graph: %s", u.Tile().Position.String(), err)
	}

	destId, err := graph.GetMapping(pos.String())
	if err != nil {
		log.Panicf("No mapping %s in Graph: %s", pos.String(), err)
	}

	return graph.Shortest(srcId, destId)
}

func findPathToPermanent(graph *dijkstra.Graph, m *Map, u *Unit, target Permanent) (*dijkstra.BestPath, error) {
	if target.Tile() == nil {
		return nil, ErrNoPath
	}

	var bestPathToUnit *dijkstra.BestPath = nil
	for _, adjacentTile := range TilesInRangeFromOrigin(m, target.Tile().Position, 1) {
		if !u.IsAvailableTile(adjacentTile) {
			continue
		}
		path, err := findPathTo(graph, u, adjacentTile.Position)
		if err != nil {
			continue
		} else if bestPathToUnit == nil || path.Distance < bestPathToUnit.Distance {
			bestPathToUnit = &path
		}
	}

	if bestPathToUnit != nil {
		return bestPathToUnit, nil
	} else {
		return nil, ErrNoPath
	}
}

func findPathsToPermanents(graph *dijkstra.Graph, m *Map, u *Unit, permanents []Permanent) []*dijkstra.BestPath {
	paths := []*dijkstra.BestPath{}

	for _, perm := range permanents {
		if bestPath, err := findPathToPermanent(graph, m, u, perm); err == nil {
			paths = append(paths, bestPath)
		}
	}
	return paths
}

func findPathsToUnits(graph *dijkstra.Graph, m *Map, u *Unit, units []*Unit) []*dijkstra.BestPath {
	perms := []Permanent{}
	for _, unit := range units {
		perms = append(perms, unit)
	}

	return findPathsToPermanents(graph, m, u, perms)
}

func findPathsToInterface(graph *dijkstra.Graph, m *Map, u *Unit, options []any) []*dijkstra.BestPath {
	paths := []*dijkstra.BestPath{}
	for _, option := range options {
		var bestPath *dijkstra.BestPath
		switch o := option.(type) {
		case Permanent:
			bestPath, _ = findPathToPermanent(graph, m, u, o)
		case *Tile:
			if bestPathToTile, err := findPathTo(graph, u, o.Position); err != nil {
				bestPath = &bestPathToTile
			}
		default:
			log.Fatalf("path finding towards %t not implemented: %s", o, o)
		}

		if bestPath != nil {
			paths = append(paths, bestPath)
		}
	}
	return paths
}

func moveToRandomTile(ai *UnitAI) Action {
	if ai.u.AvailMoveActions == 0 {
		return nil
	}

	a := NewMoveAction(ai.u)
	err := selectRandomTargets(ai.s.Rand, a.Targets())
	if err != nil {
		return nil
	}

	return a
}

func moveAwayFromEnemies(ai *UnitAI) Action {
	if ai.u.AvailMoveActions == 0 {
		return nil
	}

	// A Movement graph is not sufficient because we have to check the distance to units potentially not in range.
	graph := ai.s.Map().generateMapGraphFor(ai.u)
	var farest *Tile
	var farestEnemyDistance int64

	// Check all reachable tiles
	for _, availableTile := range ai.u.MoveRangeTiles() {
		var nearestEnemy int64 = -1

		for _, enemyUnit := range ai.s.EnemyUnits(ai.u.Controller()) {
			// Get distance to the enemy unit
			p, err := findPathTo(graph, enemyUnit, availableTile.Position)
			if err != nil {
				continue
			}
			if nearestEnemy == -1 || p.Distance < nearestEnemy {
				nearestEnemy = p.Distance
			}
		}

		if farest == nil || farestEnemyDistance < nearestEnemy {
			farest = availableTile
			farestEnemyDistance = nearestEnemy
		}
	}

	// No move possible
	if farest == nil {
		return nil
	}

	a := NewMoveAction(ai.u)
	_ = a.Target().AddSelection(farest)
	return a
}

func actionFromPaths(ai *UnitAI, graph *dijkstra.Graph, paths []*dijkstra.BestPath) Action {
	nearest := 0
	for i, p := range paths {
		if p == nil {
			continue
		}

		if paths[nearest] == nil || p.Distance < paths[nearest].Distance {
			nearest = i
		}
	}

	if paths[nearest] == nil {
		return nil
	}

	m := ai.s.Map()
	var target *Tile
	for _, id := range paths[nearest].Path[1:] {
		mapping, _ := graph.GetMapped(id)
		var x, y int
		_, _ = fmt.Sscanf(mapping, "(%d, %d)", &x, &y)
		nextStep := m.TileAt(Position{X: x, Y: y})
		if slices.Contains(ai.u.MoveRangeTiles(), nextStep) {
			target = nextStep
		} else {
			break
		}
	}

	a := NewMoveAction(ai.u)
	_ = a.Target().AddSelection(target)
	return a
}

func moveTowardsNearestEnemyUnit(ai *UnitAI) Action {
	if ai.u.AvailMoveActions == 0 {
		return nil
	}

	graph := ai.s.Map().generateMapGraphFor(ai.u)
	enemyUnits := ai.s.EnemyUnits(ai.u.Controller())
	if len(enemyUnits) == 0 {
		return nil
	}

	paths := findPathsToUnits(graph, ai.s.Map(), ai.u, enemyUnits)
	if len(paths) == 0 {
		return nil
	}
	return actionFromPaths(ai, graph, paths)
}

func moveTowardsNearestTargetOption(ai *UnitAI, options []any) Action {
	if ai.u.AvailMoveActions == 0 {
		return nil
	}

	graph := ai.s.Map().generateMapGraphFor(ai.u)

	paths := findPathsToInterface(graph, ai.s.Map(), ai.u, options)
	if len(paths) == 0 {
		return nil
	}
	return actionFromPaths(ai, graph, paths)
}

func attackAttackableEnemyPerm(ai *UnitAI) Action {
	if ai.u.AvailAttackActions == 0 {
		return nil
	}

	a := NewAttackAction(ai.u)
	err := selectRandomTargets(ai.s.Rand, a.Targets())
	if err != nil {
		return nil
	}
	return a
}

func fullAction(ai *UnitAI) Action {
	fullActions := ai.u.FullActions

	a := fullActions[ai.s.Rand.Intn(len(fullActions))]
	if a.Targets() != nil && a.Targets().RequireSelection() {
		err := selectRandomTargets(ai.s.Rand, a.Targets())
		if err != nil {
			log.Warn("ai full action error", "error", err)
			return nil
		}
	}

	return a
}

//  1. If enemy Unit in attack Range then
//     attack enemy Unit in Range
//  2. While move action available do
//     3a. If enemy unit exists
//     move towards nearest enemy unit until it is in attack range
//     if attack action avail then proceed at 1.
//     3b. Otherwise
//     move to random tile in movement range
func AggressiveAI(ai *UnitAI) {
	// 1.
	a := attackAttackableEnemyPerm(ai)
	if !ai.PostAndContinue(a) {
		return
	}

	// 2.
	if ai.u.AvailMoveActions > 0 {
		a = moveTowardsNearestEnemyUnit(ai)
		if !ai.PostAndContinue(a) {
			return
		}

		if a != nil && ai.u.AvailAttackActions > 0 {
			AggressiveAI(ai)
		} else { // 3b.
			a = moveToRandomTile(ai)
			if a != nil {
				ai.actions <- a
			}
		}
	}
}

// 2.2 Shy
//  1. If not in the attack Range of an enemy Unit then
//     activate full action if available
//  2. If move action available then
//     move to most distant point from all enemy units
//  3. If enemy Unit in attack Range then
//     attack enemy Unit in Range
func ShyAI(ai *UnitAI) {
	// 1.
	inEnemyAttackRange := false
out:
	for _, enemyUnit := range ai.s.EnemyUnits(ai.u.Controller()) {
		for _, p := range enemyUnit.AttackablePermanents() {
			if p == ai.u {
				inEnemyAttackRange = true
				break out
			}
		}
	}
	if !inEnemyAttackRange && ai.u.HasFullAction() {
		if a := fullAction(ai); a != nil {
			ai.actions <- a
			return
		}
	}

	// 2.
	if ai.u.AvailMoveActions > 0 {
		a := moveAwayFromEnemies(ai)
		if !ai.PostAndContinue(a) {
			return
		}
	}

	// 3.
	if a := attackAttackableEnemyPerm(ai); a != nil {
		ai.actions <- a
	}
}

// 2.3 Wandering X
//  1. If enemy unit in Range X then
//     execute aggressive AI
//  2. If move action available then
//     move to random tile in movement Range
//     proceed at 1.
func WanderingAI(ai *UnitAI, x int) {
	// 1.
	for _, enemyUnit := range ai.s.EnemyUnits(ai.u.Controller()) {
		if IsPositionInRange(ai.u.Tile().Position, TileOrContainingPermTile(enemyUnit).Position, x) {
			AggressiveAI(ai)
			break
		}
	}

	// 2.
	if ai.u.AvailMoveActions > 0 {
		a := moveToRandomTile(ai)
		if !ai.PostAndContinue(a) {
			return
		}
		WanderingAI(ai, x)
	}
}

// 2.4 Target-oriented TARGET
// 1. Use full action if possible
// 2a. If a TARGET exists and is reachable
//
//	Move onto or towards nearest TARGET
//	3a. If enemy Unit in attack Range
//	    attack enemy Unit in Range
//
// 2b. Otherwise
//
//	execute wandering 3 AI
func TargetOrientedAI(ai *UnitAI) {
	// 1.
	if ai.u.HasFullAction() {
		ai.actions <- fullAction(ai)
		return
	}

	// 2a.
	options := ai.target.Options()
	if len(options) > 0 {
		if ai.u.AvailMoveActions > 0 {
			a := moveTowardsNearestTargetOption(ai, options)
			if !ai.PostAndContinue(a) {
				return
			}
		}

		// 3a.
		a := attackAttackableEnemyPerm(ai)
		if !ai.PostAndContinue(a) {
			return
		}
	} else { // 2b.
		WanderingAI(ai, 3)
	}
}

// SuggestUnitAI returns a suggested UnitAI variant for the specified card.
// If there is no special case for a unit, a rough heuristic is used to determinw the AI.
// Units with full actions are shy and everything else is aggresive.
func SuggestUnitAI(unit *Unit) string {
	switch unit.card.Name {
	case "King":
		return "shy"
	case "Farmer":
		return "target-oriented farm tile"
	default:
		if unit.HasFullAction() {
			return "shy"
		} else {
			return "aggressive"
		}
	}
}

// SimpleAiControl implements a simple state-based AI.
type SimpleAiControl struct {
	p    *Player
	last PlayerNotification
	uAis map[*Unit]*UnitAI
}

func NewSimpleAiControl(p *Player) *SimpleAiControl {
	aiCtrl := &SimpleAiControl{
		p:    p,
		uAis: make(map[*Unit]*UnitAI),
	}
	return aiCtrl
}

func (ai *SimpleAiControl) Player() *Player {
	return ai.p
}

// RecvAction implements the actual AI's logic.
func (ai *SimpleAiControl) RecvAction() (Action, error) {
	switch ai.last.Notification {
	case PriorityNotification:
		return ai.handlePriority(), nil
	case TargetSelectionPrompt:
		return ai.handleTargetSelection(), nil
	}
	return NewPassPriority(ai.p), nil
}

func (ai *SimpleAiControl) handlePriority() Action {
	s := ai.p.gameState
	active := s.ActivePlayer() == ai.p

	if !active {
		spells := ai.p.Hand.FilterCards(func(c *Card) bool { return c.Type == CardTypes.Spell })
		// s.FilterPermanents(func(p Permanent) { return p.HasFreeAction()
		if len(spells) != 0 {
		}

		freeActions := []Action{}
		if len(freeActions) != 0 {
		}
	} else {
		switch s.ActivePhase() {
		case Phases.UpkeepPhase:
			// Select units to disband
		case Phases.ActionPhase:
			// Slow Actions
			if s.stack.IsEmpty() {
				for _, u := range s.OwnUnits(ai.p) {
					as := u.AvailSlowActions()
					if len(as) == 0 {
						delete(ai.uAis, u)
						continue
					} else if _, ok := as[0].(*StreetAction); ok && len(as) == 1 {
						// FIXME: Support Street Actions
						delete(ai.uAis, u)
						continue
					}

					var uAi *UnitAI
					var ok bool
					if uAi, ok = ai.uAis[u]; !ok {
						uAi = NewUnitAI(s, u)
						ai.uAis[u] = uAi
					}
					uAi.promptAction()
					a, more := uAi.NextAction()
					if !more {
						// Consume all available actions to not consider the unit this term again.
						u.tap()
						// Delete unitAI if it finished its turn
						delete(ai.uAis, u)
						continue
					}
					if a == nil && more {
						log.Fatal(uAi, " returned a nil action")
					}
					return a
				}
			}
		case Phases.BuyPhase:
			// TODO: support buying stuff
		case Phases.DiscardStep:
			// TODO: support "smarter" discarding
			t := ai.last.Context.(*Targets)
			for _, c := range ai.p.Hand.Cards() {
				_ = t.AddSelection(c)
			}
			return newTargetSelection(ai.p, t)
		}
	}
	return NewPassPriority(ai.p)
}

func (ai *SimpleAiControl) handleTargetSelection() Action {
	s := ai.p.gameState
	ctx := ai.last.Context.(TargetSelectionCtx)
	t := ctx.Action.Targets()
	switch s.ActivePhase() {
	case Phases.UpkeepPhase:
		// Select units to disband
	case Phases.ActionPhase:
	case Phases.BuyPhase:
		// TODO: support buying stuff
	case Phases.DiscardStep:
		// TODO: support "smarter" discarding
		for _, c := range ai.p.Hand.Cards() {
			_ = t.AddSelection(c)
		}
		return ctx.Action
	}

	_ = selectRandomTargets(s.Rand, t)
	return ctx.Action
}

func (*SimpleAiControl) SendAction(Action) error {
	return nil
}

// SendNotification simply stores the last  notification sent by the game.
func (ai *SimpleAiControl) SendNotification(n PlayerNotification) error {
	ai.last = n
	return nil
}

func (ai *SimpleAiControl) RecvNotification() (n PlayerNotification, err error) {
	return
}

func (ai *SimpleAiControl) Close() {
}