path: root/go/game/ai.go

package game

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

	"golang.org/x/exp/slices"

	"github.com/RyanCarrier/dijkstra"
)

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

func (ai *UnitAI) NextAction() Action {
	return <-ai.actions
}

func (ai *UnitAI) PostAndContinue(a Action) bool {
	if a == nil {
		return true
	}

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

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 NewUnitAI(s *LocalState, u *Unit) *UnitAI {
	aiDesc := u.Card().getAI()
	if aiDesc == "" {
		return nil
	}

	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 fmt.Errorf("No possible selection")
			}

			idx := 0
			if len(options) > 1 {
				idx = rand.Intn(len(options) - 1)
			}
			_ = t.AddSelection(options[idx])
		}
	}
	return nil
}

func (m *Map) generateMapGraphFor(u *Unit) *dijkstra.Graph {
	graph := dijkstra.NewGraph()
	for _, t := range m.AllTiles() {
		graph.AddMappedVertex(t.Position.String())
	}

	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 := dijkstra.NewGraph()
// for _, t := range tilesInRangeFromOrigin(m, origin, u.Movement.Range, true) {
// graph.AddMappedVertex(t.Position.String())
// }

// for _, t := range TilesInRange(m, u, u.Movement.Range) {
// tId := t.Position.String()
// for _, neighbour := range tilesInRangeFromOrigin(m, t.Position, 1, true) {
// if !IsPositionInRange(neighbour.Position, origin, u.Movement.Range) {
// continue
// }

// if u.IsAvailableTile(neighbour) {
// cost := 2
// if t.OnDiagonal(neighbour) {
// cost = 3
// }
// log.Printf("add %v -> %v: %d", tId, neighbour.Position.String(), int64(cost))
// 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, errors.New("no path found")
	}

	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, errors.New("no path found")
	}
}

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 []interface{}) []*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 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(m), 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)
	return actionFromPaths(ai, graph, paths)
}

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

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

	paths := findPathsToInterface(graph, ai.s.Map(), ai.u, options)
	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) {
	fullActions := ai.u.FullActions
	idx := 0
	if len(fullActions) > 1 {
		idx = ai.s.Rand.Intn(len(fullActions) - 1)
	}

	a := fullActions[idx]
	err := selectRandomTargets(ai.s.Rand, a.Targets())
	if err == nil {
		ai.actions <- 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(ai.s.Map()) {
			if p == ai.u {
				inEnemyAttackRange = true
				break out
			}
		}
	}
	if !inEnemyAttackRange && ai.u.HasFullAction() {
		fullAction(ai)
	}

	// 2.
	// TODO: implement path finding
	// if u.AvailMoveActions > 0 {
	// }

	// 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() {
		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)
	}
}