func (a *Interact) findTargets(ent *game.Entity, g *game.Game) []*game.Entity {
	var targets []*game.Entity
	for _, e := range g.Ents {
		x, y := e.Pos()
		dx, dy := e.Dims()
		if e == ent {
			continue
		}
		if e.ObjectEnt == nil {
			continue
		}
		if e.Sprite().State() != "ready" {
			continue
		}
		if distBetweenEnts(e, ent) > a.Range {
			continue
		}
		if !ent.HasLos(x, y, dx, dy) {
			continue
		}

		// Make sure it's still active:
		active := false
		active = true
		if !active {
			continue
		}

		targets = append(targets, e)
	}
	return targets
}

func WaypointsFunc(me *game.Entity) lua.GoFunction {
	return func(L *lua.State) int {
		if !game.LuaCheckParamsOk(L, "Waypoints") {
			return 0
		}
		g := me.Game()
		L.NewTable()
		count := 0
		for _, wp := range g.Waypoints {
			if wp.Side != me.Side() {
				continue
			}
			count++
			L.PushInteger(count)
			L.NewTable()
			L.PushString("Name")
			L.PushString(wp.Name)
			L.SetTable(-3)
			L.PushString("Radius")
			L.PushNumber(wp.Radius)
			L.SetTable(-3)
			L.PushString("Pos")
			game.LuaPushPoint(L, int(wp.X), int(wp.Y))
			L.SetTable(-3)
			L.SetTable(-3)
		}
		return 1
	}
}

func (a *AoeAttack) AiAttackPosition(ent *game.Entity, x, y int) game.ActionExec {
	if !ent.HasLos(x, y, 1, 1) {
		base.Log().Printf("Don't have los")
		return nil
	}
	if a.Ap > ent.Stats.ApCur() {
		base.Log().Printf("Don't have the ap")
		return nil
	}
	var exec aoeExec
	exec.SetBasicData(ent, a)
	exec.X, exec.Y = x, y
	return &exec
}

func (exec *moveExec) measureCost(ent *game.Entity, g *game.Game) int {
	if len(exec.Path) == 0 {
		base.Error().Printf("Zero length path")
		return -1
	}
	if g.ToVertex(ent.Pos()) != exec.Path[0] {
		base.Error().Printf("Path doesn't begin at ent's position, %d != %d", g.ToVertex(ent.Pos()), exec.Path[0])
		return -1
	}
	graph := g.Graph(ent.Side(), true, nil)
	v := g.ToVertex(ent.Pos())
	cost := 0
	for _, step := range exec.Path[1:] {
		dsts, costs := graph.Adjacent(v)
		ok := false
		prev := v
		base.Log().Printf("Adj(%d):", v)
		for j := range dsts {
			base.Log().Printf("Node %d", dsts[j])
			if dsts[j] == step {
				cost += int(costs[j])
				v = dsts[j]
				ok = true
				break
			}
		}
		base.Log().Printf("%d -> %d: %t", prev, v, ok)
		if !ok {
			return -1
		}
	}
	return cost
}

func distBetweenEnts(e1, e2 *game.Entity) int {
	x1, y1 := e1.Pos()
	dx1, dy1 := e1.Dims()
	x2, y2 := e2.Pos()
	dx2, dy2 := e2.Dims()

	var xdist int
	switch {
	case x1 >= x2+dx2:
		xdist = x1 - (x2 + dx2)
	case x2 >= x1+dx1:
		xdist = x2 - (x1 + dx1)
	default:
		xdist = 0
	}

	var ydist int
	switch {
	case y1 >= y2+dy2:
		ydist = y1 - (y2 + dy2)
	case y2 >= y1+dy1:
		ydist = y2 - (y1 + dy1)
	default:
		ydist = 0
	}

	if xdist > ydist {
		return xdist
	}
	return ydist
}

func (a *Interact) Prep(ent *game.Entity, g *game.Game) bool {
	if a.Preppable(ent, g) {
		a.ent = ent
		room := g.House.Floors[0].Rooms[ent.CurrentRoom()]
		for _, door := range a.doors {
			_, other_door := g.House.Floors[0].FindMatchingDoor(room, door)
			if other_door != nil {
				door.HighlightThreshold(true)
				other_door.HighlightThreshold(true)
			}
		}
		return true
	}
	return false
}

func (a *Interact) AiToggleDoor(ent *game.Entity, door *house.Door) game.ActionExec {
	if door.AlwaysOpen() {
		return nil
	}
	for fi, f := range ent.Game().House.Floors {
		for ri, r := range f.Rooms {
			for di, d := range r.Doors {
				if d == door {
					return a.makeDoorExec(ent, fi, ri, di)
				}
			}
		}
	}
	return nil
}

func rangedDistBetween(e1, e2 *game.Entity) int {
	e1x, e1y := e1.Pos()
	e2x, e2y := e2.Pos()
	dx := e1x - e2x
	dy := e1y - e2y
	if dx < 0 {
		dx = -dx
	}
	if dy < 0 {
		dy = -dy
	}
	if dx > dy {
		return dx
	}
	return dy
}

func (a *Move) findPath(ent *game.Entity, x, y int) {
	g := ent.Game()
	dst := g.ToVertex(x, y)
	if dst != a.dst || !a.calculated {
		a.dst = dst
		a.calculated = true
		src := g.ToVertex(a.ent.Pos())
		graph := g.Graph(ent.Side(), true, nil)
		cost, path := algorithm.Dijkstra(graph, []int{src}, []int{dst})
		if len(path) <= 1 {
			return
		}
		a.path = algorithm.Map(path, [][2]int{}, func(a interface{}) interface{} {
			_, x, y := g.FromVertex(a.(int))
			return [2]int{int(x), int(y)}
		}).([][2]int)
		a.cost = int(cost)

		if path_tex != nil {
			pix := path_tex.Pix()
			for i := range pix {
				for j := range pix[i] {
					pix[i][j] = 0
				}
			}
			current := 0.0
			for i := 1; i < len(a.path); i++ {
				src := g.ToVertex(a.path[i-1][0], a.path[i-1][1])
				dst := g.ToVertex(a.path[i][0], a.path[i][1])
				v, cost := graph.Adjacent(src)
				for j := range v {
					if v[j] == dst {
						current += cost[j]
						break
					}
				}
				pix[a.path[i][1]][a.path[i][0]] += byte(current)
			}
			path_tex.Remap()
		}
	}
}

func (a *Move) findPath(ent *game.Entity, x, y int) {
	g := ent.Game()
	dst := g.ToVertex(x, y)
	if dst != a.dst || !a.calculated {
		a.dst = dst
		a.calculated = true
		src := g.ToVertex(a.ent.Pos())
		graph := g.Graph(ent.Side(), true, nil)
		cost, path := algorithm.Dijkstra(graph, []int{src}, []int{dst})
		if len(path) <= 1 {
			return
		}
		a.path = algorithm.Map(path, [][2]int{}, func(a interface{}) interface{} {
			_, x, y := g.FromVertex(a.(int))
			return [2]int{int(x), int(y)}
		}).([][2]int)
		a.cost = int(cost)
		a.drawPath(ent, g, graph, src)
	}
}

func limitPath(ent *game.Entity, start int, path []int, max int) []int {
	total := 0
	graph := ent.Game().Graph(ent.Side(), true, nil)
	for last := 1; last < len(path); last++ {
		adj, cost := graph.Adjacent(start)
		found := false
		for index := range adj {
			if adj[index] == path[last] {
				total += int(cost[index])
				if total > max {
					return path[0:last]
				}
				start = adj[index]
				found = true
				break
			}
		}
		if !found {
			base.Log().Printf("PATH: DIdn't find, %d / %d", last+1, len(path))
			return path[0:last]
		}
	}
	return path
}

func (a *Interact) findDoors(ent *game.Entity, g *game.Game) []*house.Door {
	room_num := ent.CurrentRoom()
	room := g.House.Floors[0].Rooms[room_num]
	x, y := ent.Pos()
	dx, dy := ent.Dims()
	ent_rect := makeIntFrect(x, y, x+dx, y+dy)
	var valid []*house.Door
	for _, door := range room.Doors {
		if door.AlwaysOpen() {
			continue
		}
		if ent_rect.Overlaps(makeRectForDoor(room, door)) {
			valid = append(valid, door)
		}
	}
	return valid
}

func (a *Interact) AiInteractWithObject(ent, object *game.Entity) game.ActionExec {
	if ent.Stats.ApCur() < a.Ap {
		return nil
	}
	if distBetweenEnts(ent, object) > a.Range {
		return nil
	}
	x, y := object.Pos()
	dx, dy := object.Dims()
	if !ent.HasLos(x, y, dx, dy) {
		return nil
	}
	var exec interactExec
	exec.SetBasicData(ent, a)
	exec.Target = object.Id
	return &exec
}

func (a *AoeAttack) AiBestTarget(ent *game.Entity, extra_dist int, spec AiAoeTarget) (x, y int, targets []*game.Entity) {
	ex, ey := ent.Pos()
	max := 0
	best_dist := 10000
	var bx, by int
	var radius int
	if a.Range > 0 {
		radius += a.Range
	}
	if extra_dist > 0 {
		radius += extra_dist
	}
	for x := ex - radius; x <= ex+radius; x++ {
		for y := ey - radius; y <= ey+radius; y++ {
			if !ent.HasLos(x, y, 1, 1) {
				continue
			}
			targets = a.getTargetsAt(ent.Game(), x, y)
			ok := true
			count := 0
			for i := range targets {
				if targets[i].Side() != ent.Side() {
					count++
				} else if ent.Side() == game.SideHaunt && spec == AiAoeHitMinionsOk {
					if targets[i].HauntEnt == nil || targets[i].HauntEnt.Level != game.LevelMinion {
						ok = false
					}
				} else if spec != AiAoeHitAlliesOk {
					ok = false
				}
			}
			dx := x - ex
			if dx < 0 {
				dx = -dx
			}
			dy := y - ey
			if dy < 0 {
				dy = -dy
			}
			dist := dx
			if dy > dx {
				dist = dy
			}
			if ok && (count > max || count == max && dist < best_dist) {
				max = count
				best_dist = dist
				bx, by = x, y
			}
		}
	}
	return bx, by, a.getTargetsAt(ent.Game(), bx, by)
}

func (a *Move) AiMoveToPos(ent *game.Entity, dst []int, max_ap int) game.ActionExec {
	base.Log().Printf("PATH: Request move to %v", dst)
	graph := ent.Game().Graph(ent.Side(), false, nil)
	src := []int{ent.Game().ToVertex(ent.Pos())}
	_, path := algorithm.Dijkstra(graph, src, dst)
	base.Log().Printf("PATH: Found path of length %d", len(path))
	ppx, ppy := ent.Pos()
	if path == nil {
		return nil
	}
	_, xx, yy := ent.Game().FromVertex(path[len(path)-1])
	base.Log().Printf("PATH: %d,%d -> %d,%d", ppx, ppy, xx, yy)
	if ent.Stats.ApCur() < max_ap {
		max_ap = ent.Stats.ApCur()
	}
	path = limitPath(ent, src[0], path, max_ap)
	_, xx, yy = ent.Game().FromVertex(path[len(path)-1])
	base.Log().Printf("PATH: (limited) %d,%d -> %d,%d", ppx, ppy, xx, yy)
	if len(path) <= 1 {
		return nil
	}
	var exec moveExec
	exec.SetBasicData(ent, a)
	exec.Path = path
	return &exec
}

// Returns an array of all entities of a specified type that are in this
// entity's los.  The entities in the array will be sorted in ascending order
// of distance from this entity.
//    Format
//    ents = nearestNEntites(max, kind)
//
//    Input:
//    max  - integer - Maximum number of entities to return
//    kind - string  - One of "intruder" "denizen" "minion" "servitor"
//                     "master" "non-minion" "non-servitor" "non-master" and
//                     "all".  The "non-*" parameters indicate denizens only
//                     (i.e. will *not* include intruders) that are not of the
//                     type specified.
//
//    Output:
//    ents - array[integer] - Array of entity ids.
func NearestNEntitiesFunc(me *game.Entity) lua.GoFunction {
	valid_kinds := map[string]bool{
		"intruder": true,
		"denizen":  true,
		"minion":   true,
		"servitor": true,
		"master":   true,
		"object":   true,
	}
	return func(L *lua.State) int {
		if !game.LuaCheckParamsOk(L, "NearestNEntities", game.LuaInteger, game.LuaString) {
			return 0
		}
		g := me.Game()
		max := L.ToInteger(-2)
		kind := L.ToString(-1)
		if !valid_kinds[kind] {
			err_str := fmt.Sprintf("NearestNEntities expects kind in the set ['intruder' 'denizen' 'servitor' 'master' 'minion'], got %s.", kind)
			base.Warn().Printf(err_str)
			L.PushString(err_str)
			L.Error()
			return 0
		}
		var eds entityDistSlice
		for _, ent := range g.Ents {
			if ent.Stats != nil && ent.Stats.HpCur() <= 0 {
				continue
			}
			switch kind {
			case "intruder":
				if ent.Side() != game.SideExplorers {
					continue
				}
			case "denizen":
				if ent.Side() != game.SideHaunt {
					continue
				}
			case "minion":
				if ent.HauntEnt == nil || ent.HauntEnt.Level != game.LevelMinion {
					continue
				}
			case "servitor":
				if ent.HauntEnt == nil || ent.HauntEnt.Level != game.LevelServitor {
					continue
				}
			case "master":
				if ent.HauntEnt == nil || ent.HauntEnt.Level != game.LevelMaster {
					continue
				}
			case "object":
				if ent.ObjectEnt == nil {
					continue
				}
			}
			x, y := ent.Pos()
			dx, dy := ent.Dims()
			if !me.HasTeamLos(x, y, dx, dy) {
				continue
			}
			eds = append(eds, entityDist{rangedDistBetween(me, ent), ent})
		}
		// TODO: ONLY GUYS THAT EXIST
		sort.Sort(eds)
		if max > len(eds) {
			max = len(eds)
		}
		if max < 0 {
			max = 0
		}
		eds = eds[0:max]

		// eds contains the results, in order.  Now we make a lua table and
		// populate it with the entity ids of the results.
		L.NewTable()
		for i := range eds {
			L.PushInteger(i + 1)
			game.LuaPushEntity(L, eds[i].ent)
			L.SetTable(-3)
		}
		return 1
	}
}